マルチエージェントシステムに関する先駆的研究：マルチエージェントシステムとは、複数の自律的な主体（エージェント）間の相互作用に関する研究分野である。従来、エージェントによる協調問題解決に関しては、様々な応用事例を扱える一般的な技術が欠落していた。また、利害が対立するエージェント間の合意形成に関しては、ミクロ経済学の一分野としてマーケットデザイン研究が進展しているが、ネットワークでの匿名性や現実の応用で生じる制約条件は考慮の対象外であった。本研究では、分散制約充足問題と呼ばれる一般的な枠組を提案し、種々の理論的性質を満たすアルゴリズムを提案している。また、匿名性を用いた不正行為である架空名義入札に頑健な入札メカニズム、および種々の制約を満たすマッチングメカニズムを提案している。本研究により、分散制約充足問題という新しい研究分野が開拓され、マーケットデザインに関する情報科学の観点からの新しい課題と解決策が示され、研究コミュニティが発展している。本成果は、マルチエージェントシステムとマーケットデザイン研究の今後の理論的発展及び実用化に寄与することが期待される。

「ヘドニックゲームの新たな選好モデルにおけるコア安定性の一考察」

「2次元格子空間上の施設配置問題におけるパレート効率性の考察」
「下限制約と初期保有財を考慮した学校選択メカニズムの特徴付け」

「分割関数ゲームの提携構造形成アルゴリズム」

「学校選択制におけるパレート効率的かつ耐戦略的なメカニズム」

「異なる性質を有する二施設配置のための架空名義操作不可能なメカニズム」

「日本の学校選択制に適用可能なマッチングメカニズムの提案」
「私的観測付無限回繰り返しチーム生産ゲームのサボタージュ行動」

「クラウドソーシングのための一般化スコアリングルールの提案」

「戦略的操作不可能なケーキ分割メカニズムの提案」
「不完全観測繰り返しゲームのチーム生産モデルにおける均衡解析」

「架空名義操作不可能な再配分メカニズムの特徴付け」

「効率的な資源利用のための利用予測申告と実行動に関する一考察」
「効率性と誘因制約を両立可能な物々交換モデルの特徴付け」

「地域制約の下での戦略的操作不可能なマッチングメカニズム」

「地域制約の下での戦略的操作不可能なマッチングメカニズム」

「下限制約付きマッチングメカニズムの理論的設計と評価」

「架空名義操作不可能な施設配置メカニズムの特徴付け」

"A Compact Representation Scheme of Coalitional Games Based on Multi‐Terminal Zero‐Suppressed Binary Decision Diagrams"

‟A Compact Representation Scheme of Coalitional Games Based on Multi-Terminal Zero-Suppressed Binary Decision Diagrams”

「線形計画法を用いた提携構造形成と利得配分の同時解決」

‟Laboratories/students problem with minimun/maximum quotas”

「匿名の開環境下における協力ゲームについて」

"Reducing the Search Space of Resource Constrained DCOPs"

「自動メカニズムデザインを利用した組合せオークションのルール抽出アルゴリズムの提案」

"Effect of DisCSP Variable-Ordrering Heuristics in Scale-free Networks"

「協力ゲームにおける特性関数のエージェントのタイプに基づく簡略表記法」
「MC-nets を用いた提携構造形成アルゴリズムの拡張：負の利得と外部性の導入」

"False-name-proofness in Online Mechanisms"

「架空名義操作不可能な組合せオークションメカニズム：VCG メカニズムの改良」
「架空名義操作不可能な施設配置メカニズムの特徴付け」

「入札者の選好を考慮した検索連動型広告オークションの提案」

"The Distributed Constraint Satisfaction Problem: Formalization and Algorithms"
"Distributed Breakout Algorithm for Solving Distributed Constraint Satisfaction Problems"

「第一価格入札における架空名義入札の影響の解析」
「分散制約最適化問題に基づく提携構造形成問題」

「架空名義入札に頑健な再配分メカニズムの提案」
「架空名義操作不可能な組合せオークションの割当規則の特性」
「第一価格入札における架空名義操作の影響の解析」

"Characterizing False-name-proof Allocation Rules in Combinatorial Auctions"

「適切な掲載数を決定するキーワード広告オークションの提案」

「ネットワーク分散部分観測可能マルコフ決定過程におけるプラン構築への通信の導入」

横尾真, Vincent Conitzer, Tuomas Sandholm, 大田直樹, 岩崎敦,「開環境での協力ゲームにおける解概念の提案」

Takayuki Suyama, and Makoto Yokoo. AAMAS'04 Proceedings of the Third International Joint Conference on Autonomous Agents and Multiagent Systems, vol.1, pp.160-167.

櫻井 祐子，横尾 真，松原 繁夫

出版者・発行元：Performance Evaluation Review  

Selling resources via auctions often seems profit-optimal in theory. Yet in practice, providers most often choose to sell homogeneous resources such as cloud computing instances at fixed prices. While it has been argued that this is explained by relatively non-volatile demand distributions and highly competitive market environments, these arguments only paint a partial picture. Through a formal game theoretic analysis, we show that the relative profit increase of offering resources through a spot pricing mechanism instead of at a fixed price is unbounded as long as a sufficiently competitive outside option exists, even if demand is very non-volatile. To explain the lack of spot pricing in practice, we consider that users might be biased against more complex auction-based mechanisms. We find that in large, non-volatile markets even a very small user bias will turn fixed-pricing profit-optimal if demand is sufficiently large and non-volatile. We derive a sufficient condition under which fixed prices are profit-optimal and illustrate the observed effects through a numerical example.

DOI： 10.1145/3673660.3655089

Scopus

出版者・発行元：Proceedings of the AAAI Conference on Artificial Intelligence  

We study a practical two-sided matching problem of allocating children to daycare centers, which has significant social implications. We are cooperating with several municipalities in Japan and our goal is to devise a reliable and trustworthy clearing algorithm to deal with the problem. In this paper, we describe the design of our new algorithm that minimizes the number of unmatched children while ensuring stability. We evaluate our algorithm using real-life data sets, and experimental results demonstrate that our algorithm surpasses the commercial software that currently dominates the market in terms of both the number of matched children and the number of blocking coalitions (measuring stability). Our findings have been reported to local governments, and some are considering adopting our proposed algorithm in the near future, instead of the existing solution. Moreover, our model and algorithm have broader applicability to other important matching markets, such as hospital-doctor matching with couples and school choice with siblings.

DOI： 10.1609/aaai.v38i20.30244

Scopus

記述言語：英語   掲載種別：研究論文（学術雑誌）  

DOI： https://doi.org/10.1016/j.geb.2023.12.006.

掲載種別：研究論文（学術雑誌）   出版者・発行元：Games and Economic Behavior  

The notion of envy-freeness is a natural and intuitive fairness requirement in resource allocation. With indivisible goods, such fair allocations are not guaranteed to exist. Classical works have avoided this issue by introducing an additional divisible resource, i.e., money. In this paper, we aim to design a truthful allocation mechanism of indivisible goods to achieve fairness and efficiency criteria with a limited amount of subsidy. Following the work of Halpern and Shah, our central question is as follows: to what extent do we need to rely on the power of money to accomplish these objectives? We show that, when agents have matroidal valuations, there is a truthful allocation mechanism that achieves envy-freeness and utilitarian optimality by subsidizing each agent with at most 1, the maximum marginal contribution of each item for each agent. The design of the mechanism rests crucially on the underlying matroidal M-convexity of the Lorenz dominating allocations.

DOI： 10.1016/j.geb.2023.12.006

Web of Science

Scopus

researchmap

記述言語：英語   出版者・発行元：PLoS ONE  

We identify a new class of distributional constraints defined as a union of symmetric M-convex sets, which can represent a wide range of real-life constraints in two-sided matching settings. Since M-convexity is not closed under union, a union of symmetric M-convex sets does not belong to this well-behaved class of constraints. Consequently, devising a fair and strategyproof mechanism to handle this new class is challenging. We present a novel mechanism for it called Quota Reduction Deferred Acceptance (QRDA), which repeatedly applies the standard Deferred Acceptance mechanism by sequentially reducing artificially introduced maximum quotas. We show that QRDA is fair and strategyproof when handling a union of symmetric M-convex sets, which extends previous results obtained for a subclass of the union of symmetric M-convex sets: ratio constraints. QRDA always yields a weakly better matching for students than a baseline mechanism called Artificial Cap Deferred Acceptance (ACDA). We also experimentally show that QRDA outperforms ACDA in terms of nonwastefulness.

DOI： 10.1371/journal.pone.0289965

Web of Science

Scopus

PubMed

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

DOI： https://doi.org/10.1609/aaai.v38i20.30244

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

DOI： https://doi.org/10.1609/aaai.v38i9.28842

出版者・発行元：Proceedings - 2024 IEEE Conference on Artificial Intelligence, CAI 2024  

Continuous Distributed Constraint Optimization Problems (C-DCOPs) are a significant constraint handling framework to model continuous variable problems of multi-agent systems. Many excellent algorithms have been designed to solve C-DCOPs in recent decades. However, these algorithms are prone to falling into local optimum, which is a major challenge in solving C-DCOPs. This paper proposes a Group Correction-based Local Disturbance Particle Swarm Optimization algorithm named GC-LDP to improve its solution quality. In GC-LDP, we introduce two items, the average of the personal best positions and the average of the personal current positions, into the velocity update formula of traditional Particle Swarm Optimization to utilize the group knowledge to correct the exploitation direction. In addition, a local disturbance strategy is designed in GC-LDP to increase the swarm diversity by searching the nearest particle group in the solution space to enhance the algorithm's exploration ability. GC-LDP has been theoretically proven to be an anytime algorithm. Furthermore, based on the extensive experiments on four types of benchmark problems, we demonstrate that GC-LDP outperforms state-of-the-art C-DCOP algorithms in terms of convergence speed and solution quality.

DOI： 10.1109/CAI59869.2024.00128

Scopus

掲載種別：研究論文（学術雑誌）  

DOI： 10.48550/arXiv.2402.01084

researchmap

出版者・発行元：Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS  

The theory of two-sided matching has been extensively developed and applied to many real-life application domains. As the theory has been applied to increasingly diverse types of environments, researchers and practitioners have encountered various forms of distributional constraints. As a mechanism can handle a more general class of constraints, we can assign students more flexibly to colleges to increase students' welfare. However, it turns out that there exists a trade-off between students' welfare (efficiency) and fairness (which means no student has justified envy). Furthermore, this trade-off becomes sharper as the class of constraints becomes more general. The first contribution of this paper is to clarify the boundary on whether a strategyproof and fair mechanism can satisfy certain efficiency properties for each class of constraints. Our second contribution is to establish a weaker fairness requirement called envy-freeness up to k peers (EF-k), which is inspired by a similar concept used in the fair division of indivisible items. EF-k guarantees that each student has justified envy towards at most k students. By varying k, EF-k can represent different levels of fairness. We investigate theoretical properties associated with EF-k. Furthermore, we develop two contrasting strategyproof mechanisms that work for general hereditary constraints, i.e., one mechanism can guarantee a strong efficiency requirement, while the other can guarantee EF-k for any fixed k. We evaluate the performance of these mechanisms through computer simulation.

Scopus

出版者・発行元：Lecture Notes in Networks and Systems  

In a conventional contextual multi-armed bandit problem, the feedback (or reward) is immediately observable after an action. Nevertheless, delayed feedback arises in numerous real-life situations and is particularly crucial in time-sensitive applications. The exploration-exploitation dilemma becomes particularly challenging under such conditions, as it couples with the interplay between delays and limited resources. Besides, a limited budget often aggravates the problem by restricting the exploration potential. A motivating example is the distribution of medical supplies at the early stage of COVID-19. The delayed feedback of testing results, thus insufficient information for learning, degraded the efficiency of resource allocation. Motivated by such applications, we study the effect of delayed feedback on constrained contextual bandits. We develop a decision-making policy, delay-oriented resource allocation with learning (DORAL), to optimize the resource expenditure in a contextual multi-armed bandit problem with arm-dependent delayed feedback.

DOI： 10.1007/978-3-031-60221-4_20

Web of Science

Scopus

記述言語：日本語   出版者・発行元：一般社団法人 人工知能学会  

<p>本論文では，時間の経過に伴い選好が変化する状況を捉えることのできる，2 期間を通じた両方向マッチングを考察する．このようなモデルでは，各期間で異なるエージェントとマッチングすることが可能である．従来の研究では，いずれの期間においても，エージェント一人，あるいはエージェントのペアが結託することで得をするようなことがないマッチングを動的安定なマッチングとして定義している． 本論文では，2 期間マッチングにおける新たな公平性および非浪費性，個人合理性を定義し，動的安定性との関係性について考察する．また，定義した公平性と非浪費性を同時に満たすマッチングの存在性について議論する．</p>

DOI： 10.11517/pjsai.jsai2024.0_1i3gs501

CiNii Research

掲載種別：研究論文（国際会議プロシーディングス）   出版者・発行元：Proceedings of the AAAI Conference on Artificial Intelligence  

We study the fair division of indivisible items with subsidies among n agents, where the absolute marginal valuation of each item is at most one. Under monotone valuations (where each item is a good), it is known that a maximum subsidy of 2(n − 1) and a total subsidy of 2(n − 1)2 are sufficient to guarantee the existence of an envy-freeable allocation. In this paper, we improve upon these bounds, even in a wider model. Namely, we show that, given an EF1 allocation, we can compute in polynomial time an envy-free allocation with a subsidy of at most n − 1 per agent and a total subsidy of at most n(n − 1)/2. Moreover, we present further improved bounds for monotone valuations.

DOI： 10.1609/aaai.v38i9.28842

Scopus

researchmap

その他リンク： https://dblp.uni-trier.de/db/conf/aaai/aaai2024.html#KawaseMSTY24

記述言語：日本語   出版者・発行元：一般社団法人 人工知能学会  

<p>本発表では，一次元線分上の施設配置ゲーム，すなわち，参加するエージェントが一次元線分上の自分の位置を申告した際に，それらの申告から施設の配置を定める問題を考える．本発表では特に，Ordered Weighted Average メカニズムに着目し，その操作の非自明性について議論する．Ordered Weighted Average メカニズムとは，エージェントの申告の値を昇順に整列し，その順番に従って重みをかけ，その総和を返すようなメカニズムである．本発表では，それぞれの順序にかける重みを変えることにより，操作の非自明性がどのように変化するかを解析する．</p>

DOI： 10.11517/pjsai.jsai2024.0_2f6gs502

CiNii Research

記述言語：日本語   出版者・発行元：一般社団法人 人工知能学会  

<p>整凸関数は，M凸関数やL凸関数などを含む離散凸解析における基本的な関数クラスである．近年，離散最適化問題に対するアルゴリズム開発のために，L拡張可能関数という概念が提案された．整数格子点上の関数hがL拡張可能とは，半整数格子点上のL凸関数gが存在して，gの定義域を整数格子点上に制限したものがhに一致するときにいう．このとき，gはhのL凸緩和という．L拡張可能性は，NP困難である様々な離散最適化問題に対して，近似アルゴリズムや高速な厳密解法などを開発する際に有用であることが知られている．本論文では，整凸関数のL拡張可能性について調べることを目的とする．特に，線形補間によるL拡張可能性に着目し，そのような拡張が可能である整凸関数の特徴付けについて議論する．</p>

DOI： 10.11517/pjsai.jsai2024.0_3xin235

CiNii Research

記述言語：日本語   出版者・発行元：一般社団法人 人工知能学会  

<p>情報伝播付きの両方向マッチングに関しては，いくつかの自然な仮定のもとで，安定なアルゴリズムが耐戦略性を満足できないことが知られている．本研究では，耐戦略性の緩和による，安定なアルゴリズムの設計可能性を吟味する．具体的には，耐戦略性を操作の非自明性に緩和しても，依然安定なアルゴリズムが存在しないことを示す．</p>

DOI： 10.11517/pjsai.jsai2024.0_1i3gs504

CiNii Research

記述言語：日本語   出版者・発行元：一般社団法人 人工知能学会  

<p>情報伝播を伴うメカニズムはエージェントにインセンティブを与えできるだけ多くの同僚をメカニズムに参加させることと目的としている．情報伝播を伴う施設配置ゲームは耐戦略性，パレート効率性，匿名性を満たすメカニズムが存在しない不可能性定理が知られており，匿名性を満足しない耐戦略性，パレート効率性を満たすメカニズムが2つ知られている． 我々の目的は耐戦略性，パレート効率性を満たすメカニズムが他に存在するか検証することである． 本論文では匿名性に焦点を当てる．まず分割を導入して部分匿名性を定義し，耐戦略性，パレート効率性を満たすメカニズムが存在する分割の条件を明らかにした．</p>

DOI： 10.11517/pjsai.jsai2024.0_3xin250

CiNii Research

記述言語：日本語   出版者・発行元：一般社団法人 人工知能学会  

<p>両方向のマッチング理論は広範囲に発展しており，学生の嫉妬を減少させ，総合的な福祉を向上させるようなマッチングを求めることが望まれている．しかし，効率性と公平性の間にはトレードオフが存在することが明らかになっている．そのため，本研究では，現実の世界で適用可能の一定の公平性を維持することで，効率性を向上させることを考える．我々の貢献はreverse Envy-Freeness up to k peers (r-EF-k; 最大k人の人物からのみ嫉妬を受け得る)と呼ばれるより弱い公平性の要件を提案することである．kを変化させることで，r-EF-kは異なる公平性のレベルを要求することができる．本研究では，一般的な制約下において，r-EF-kおよび効率性を満たすメカニズムについて議論する．</p>

DOI： 10.11517/pjsai.jsai2024.0_2f6gs501

CiNii Research

記述言語：日本語   出版者・発行元：一般社団法人 人工知能学会  

<p>提携構造形成問題は、提携値の和が最大化されるようにエージェントの提携を決定する問題であり、様々なアルゴリズムが提案されている。我々は、提携間に外部性が存在する提携構造形成問題に対して、従来提案されているMaxSAT符号化よりも効率的に求解可能にするための改良を提案する。計算機実験により、従来手法と比較してCPU計算時間の削減が可能になることを示す。</p>

DOI： 10.11517/pjsai.jsai2024.0_2m4os11b04

CiNii Research

記述言語：日本語   出版者・発行元：一般社団法人 人工知能学会  

<p>行動経済学において，人は自分に近い人との比較で幸福度が決定するという仮説が提唱されている．この仮説に従い，本研究では，ソーシャルネットワーク上で直接つながっている相手に対してのみ嫉妬が発生する状況での両方向マッチングを考え，公平性と効率性の関係について検証する．特に，前述のような嫉妬を隣人への嫉妬として，また，隣人への嫉妬が存在しないという性質を局所公平性として定義し，これを従来の公平性の緩和として採用する．そして，マッチング市場における片側の選好を制限することで，隣人への嫉妬がなく（つまり，局所的に公平であり），かつパレート効率的であるマッチングの存在性およびそのようなマッチングを出力するメカニズムについて議論する．</p>

DOI： 10.11517/pjsai.jsai2024.0_3xin2112

CiNii Research

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

DOI： https://doi.org/10.3233/FAIA230507

出版者・発行元：Frontiers in Artificial Intelligence and Applications  

Ride-hailing services' main feature is mediating the assignment and transactions between drivers and passengers. Essentially, they decide on the quality of passengers' experience and the drivers' workload balancing. To boost the company's profit, these services try to maximize the utility for the passengers by optimizing the matching, resulting in shorter waiting times and better service availability. Often, in the process of maximizing revenue, drivers' interests get sidelined. We focus on two objectives: efficiency (minimizing total distance traveled by drivers) and fairness (minimizing the maximum traveled distance by any driver) for shared-mode rides, where the vehicles' capacity is two passengers. We theoretically show the relation between the optimal solutions of both objectives and as the problem is computationally intractable, we propose a heuristic algorithm to achieve an approximately optimal solution. We also propose a re-assignment-based algorithm when the aim is to achieve maximum matching with fairness up to a given threshold, if that is feasible. The experimental analysis for the proposed algorithms on real-world data from Chicago city shows that our approach can significantly improve fairness for drivers without losing much efficiency.

DOI： 10.3233/FAIA230507

Scopus

出版者・発行元：Proceedings of the 37th AAAI Conference on Artificial Intelligence, AAAI 2023  

In this paper, we study a daycare matching problem in Japan and report the design and implementation of a new centralized algorithm. There are two features that make this market different from the classical hospital-doctor matching problem: i) some children are initially enrolled and prefer to be transferred to other daycare centers; ii) one family may be associated with two or more children and is allowed to submit preferences over combinations of daycare centers. We revisit some well-studied properties including individual rationality, non-wastefulness, as well as stability, and generalize them to this new setting. We design an algorithm based on integer programming (IP) that captures these properties and conduct experiments on five real-life data sets provided by three municipalities. Experimental results show that i) our algorithm performs at least as well as currently used methods in terms of numbers of matched children and blocking coalition; ii) we can find a stable outcome for all instances, although the existence of such an outcome is not guaranteed in theory.

Scopus

掲載種別：研究論文（国際会議プロシーディングス）   出版者・発行元：Springer  

DOI： 10.1007/978-3-031-25549-6

researchmap

掲載種別：研究論文（学術雑誌）   出版者・発行元：Artificial Intelligence  

In this work, we consider a student-project-resource matching-allocation problem, where students have preferences over projects and the projects have preferences over students. In this problem, students and indivisible resources are many-to-one matched to projects whose capacities are endogenously determined by the resources allocated to them. Traditionally, this problem is decomposed into two separate problems: (1) resources are allocated to projects based on expectations (a resource allocation problem), and (2) students are matched to projects based on the capacities determined in the previous problem (a matching problem). Although both problems are well-understood, if the expectations used in the first are incorrect, we obtain a sub-optimal outcome. Thus, this problem should be solved as a whole without dividing it into two parts. We show that no strategyproof mechanism satisfies fairness and weak efficiency requirements. Given this impossibility result, we develop a new class of strategyproof mechanisms called Sample and Deferred Acceptance (SDA), which satisfies several properties on fairness and efficiency. We experimentally compare several SDA instances as well as existing mechanisms, and show that an SDA instance strikes a good balance of fairness and efficiency when students are divided into different types according to their preferences.

DOI： 10.1016/j.artint.2023.103855

Web of Science

Scopus

researchmap

掲載種別：研究論文（国際会議プロシーディングス）  

DOI： 10.1609/aaai.v37i12.26694

researchmap

その他リンク： https://dblp.uni-trier.de/db/conf/aaai/aaai2023.html#0001TMTY23

掲載種別：研究論文（学術雑誌）   出版者・発行元：Artificial Intelligence  

We consider an allocation problem of multiple types of objects to agents, where each type of object has multiple copies (e.g., multiple seats in a school), each agent is endowed with an object, and some distributional constraints are imposed on the allocation (e.g., minimum/maximum quotas). We develop two mechanisms that are strategyproof, feasible (they always satisfy distributional constraints), and individually rational, assuming the distributional constraints are represented by an M-convex set. One mechanism, based on Top Trading Cycles, is Pareto efficient; the other, which belongs to the mechanism class specified by Kojima et al. [1], satisfies a relaxed fairness requirement. The class of distributional constraints we consider contains many situations raised from realistic matching problems, including individual minimum/maximum quotas, regional maximum quotas, type-specific quotas, and distance constraints. Finally, we experimentally evaluate the performance of these mechanisms by a computer simulation.

DOI： 10.1016/j.artint.2022.103825

Web of Science

Scopus

researchmap

掲載種別：研究論文（学術雑誌）  

DOI： 10.48550/arXiv.2309.10968

researchmap

掲載種別：研究論文（学術雑誌）  

DOI： 10.48550/arXiv.2308.11230

researchmap

記述言語：日本語   出版者・発行元：一般社団法人 人工知能学会  

<p>ダブルオークションは売手と買手の双方が価格を提示した上で，誰がどのような価格で取引を行うか決定するオークション形態である．同一の財を多数取引する場合に適するため，現在では証券取引や為替取引，ビットコイン等の暗号資産取引などで用いられている．一般にオークションが満たすべき性質として，全体の効用を最大化するパレート効率性，参加者が損をしないという個人合理性，嘘の評価額を提示する動機が存在しない誘因両立性，主催者が赤字にならないことを保証する予算均衡性といったものが挙げられる．しかし，ダブルオークションにおいては全てを満足するメカニズムは存在しない．本研究ではこれらの性質を目的関数や等式制約に組み込む形で最適化問題へと帰着させ，深層学習を用いて解くためのネットワークを提案する．特に売手と買手の個人合理性を必ず達成するとともに，入力の並び替えに対して同変な結果を出力するような対称性をもったアーキテクチャを構築した．そして学習によって得られたメカニズムの有効性を数値実験によって検証し，誘因両立性と予算均衡性をほとんど満足しながら既存のMDプロトコルを上回る効用が得られることを確かめた．</p>

DOI： 10.11517/pjsai.jsai2023.0_1f4gs505

CiNii Research

記述言語：日本語   出版者・発行元：一般社団法人 人工知能学会  

<p>整凸関数は，M凸関数やL凸関数などを含む離散凸解析における基本的な関数クラスである．近年，離散最適化問題に対するアルゴリズム開発のために，L拡張可能関数という概念が提案された．整数格子点上の関数hがL拡張可能とは，半整数格子点上のL凸関数gが存在して，gの定義域を整数格子点上に制限したものがhに一致するときにいう．このとき，gはhのL凸緩和という．L拡張可能性は，NP困難である様々な離散最適化問題に対して，近似アルゴリズムや高速な厳密解法などを開発する際に有用であることが知られている．本論文では，整凸関数のL拡張可能性について調べることを目的とし，その準備となる証明を行った．具体的には，まず，半整数格子点上で整凸関数と同様の性質を持つ関数，半整凸関数を新たに定義する．そして，整凸関数が半整凸関数に緩和できる条件や，半整凸関数がL凸性を満たす条件を調べる．さらに，これらを利用することで，整凸関数がL拡張可能である条件を明らかにするための方向性を示す．</p>

DOI： 10.11517/pjsai.jsai2023.0_2j4gs102

CiNii Research

記述言語：日本語   出版者・発行元：一般社団法人 人工知能学会  

<p>施設配置ゲームは近年のアルゴリズム的ゲーム理論に関する理論の発展の中で，最もよく議論されたモデルの一つである．中でも中位投票者メカニズムは社会全体の厚生を最大化させる意思決定メカニズムとして知られている．一方，情報伝播を伴うメカニズム設計は，マーケットデザイン理論の新たなパラダイムとして知られている．本研究では施設配置ゲームのためのメカニズム設計において，情報伝播の影響を分析する．まず，特定のクラスの耐戦略的なメカニズムに関する不可能性定理を示したあと，耐戦略性を満足するメカニズムを二つ提案し，その特性を詳細に分析する．</p>

DOI： 10.11517/pjsai.jsai2023.0_1f3gs503

CiNii Research

記述言語：日本語   出版者・発行元：一般社団法人 人工知能学会  

<p>一次元区間上の施設配置メカニズムの近似アルゴリズムによる解析において，エージェントの効用の最小値が大きいほどよいとされる平等性にもとづく目的関数や，エージェントの効用の総和が大きいほどよいとされる効率性にもとづいた目的関数が用いられた．目的関数に対する近似比は1に近いほどよいとされる．中点メカニズムは平等性に基づく目的関数で1の指標をもち，効率性に基づく目的関数でも比較的よい値をもつ．また，ナッシュメカニズムは平等性に基づく目的関数，効率性に基づく目的関数の双方で比較的1に近い値をもつ．しかし，中点メカニズムとナッシュメカニズムは戦略的操作が可能な場合が存在する． そこで，本研究では中点メカニズムとナッシュメカニズムに対してエージェントの申告値を考えることで，2種のメカニズムの戦略的操作の考察を行う． 結果として，中央値メカニズムはエージェントの申告値の区間が小さい場合にあるエージェントが効用を1にする戦略的操作が可能な場合が存在する．一方でナッシュメカニズムでは非常に多くのエージェントが特定の値を申告する場合に1人のエージェントの戦略的操作の影響が非常に小さくなることを示した．</p>

DOI： 10.11517/pjsai.jsai2023.0_2f5gs502

CiNii Research

記述言語：日本語   出版者・発行元：一般社団法人 人工知能学会  

<p>ヘドニックゲームは，エージェントのグループを適切なサブグループに分割する数理モデルで，従来協力ゲームの一分野として研究がなされてきた．一方，許可構造つきの協力ゲームは，エージェントのゲームへの参加が，別のエージェントによる許可制であるようなモデルである．本研究では，ヘドニックゲームに許可構造を導入し，情報拡散，すなわち，できる限り多くの許可を出すことのインセンティブが成立するヘドニックゲームの解について議論する．具体的には，まずナッシュ安定解と情報拡散が非両立であることを示す．この不可能性を受け，情報拡散のインセンティブを有するアルゴリズムを提案し，達成可能な社会的余剰の近似率を示す．</p>

DOI： 10.11517/pjsai.jsai2023.0_2f4gs503

CiNii Research

記述言語：その他   掲載種別：研究論文（その他学術会議資料等）   出版者・発行元：Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)  

In this paper, we consider the study of two classes of mechanism design problems for locating a facility on a wheel graph with k≥ 4 vertices, where a vertex is located at the center, which is surrounded by a cycle graph with k- 1 vertices and connected to each vertex in the cycle. Two domains of agents’ preferences are considered; the single-peaked domain and the single-dipped domain. We are interested in the existence of anonymous social choice functions that are false-name-proof and Pareto efficient. For both domains of preferences, we provide the necessary and sufficient condition on the graph parameter k to guarantee the existence of such social choice functions. Namely, for the single-peaked preference domain, such social choice functions exist if and only if k≤ 5. On the other hand, for the single-dipped preference domain, such social choice functions exist if and only if k≤ 7.

DOI： 10.1007/978-3-031-21203-1_9

Web of Science

Scopus

researchmap

その他リンク： https://dblp.uni-trier.de/db/conf/prima/prima2022.html#OsoegawaTY22

記述言語：英語   掲載種別：研究論文（学術雑誌）  

記述言語：その他   掲載種別：研究論文（その他学術会議資料等）   出版者・発行元：Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)  

This paper introduces a new problem called the Robust Maximum Satisfiability problem (R-MaxSAT), as well as its extension called the Robust weighted Partial MaxSAT (R-PMaxSAT). In R-MaxSAT (or R-PMaxSAT), a problem solver called defender hopes to maximize the number of satisfied clauses (or the sum of their weights) as the standard MaxSAT/partial MaxSAT problem, although she must ensure that the obtained solution is robust (In this paper, we use the pronoun “she” for the defender and “he” for the attacker). We assume an adversary called the attacker will flip some variables after the defender selects a solution. R-PMaxSAT can formalize the robust Clique Partitioning Problem (robust CPP), where CPP has many real-life applications. We first demonstrate that the decision version of R-MaxSAT is Σ2P -complete. Then, we develop two algorithms to solve R-PMaxSAT, by utilizing a state-of-the-art SAT solver or a Quantified Boolean Formula (QBF) solver as a subroutine. Our experimental results show that we can obtain optimal solutions within a reasonable amount of time for randomly generated R-MaxSAT instances with 30 variables and 150 clauses (within 40 s) and R-PMaxSAT instances based on CPP benchmark problems with 60 vertices (within 500 s).

DOI： 10.1007/978-3-031-20862-1_2

Web of Science

Scopus

researchmap

その他リンク： https://dblp.uni-trier.de/db/conf/pricai/pricai2022-1.html#SugaharaYBKY22

記述言語：その他   掲載種別：研究論文（学術雑誌）  

DOI： 10.1613/jair.1.13499

掲載種別：研究論文（国際会議プロシーディングス）   出版者・発行元：ijcai.org  

DOI： 10.24963/ijcai.2022/27

researchmap

その他リンク： https://dblp.uni-trier.de/db/conf/ijcai/ijcai2022.html#ChoTY22

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

出版者・発行元：Proceedings of the 36th AAAI Conference on Artificial Intelligence, AAAI 2022  

Two-sided matching is an important research area that has had a major impact on the design of real-world matching markets. One consistent feature in many of the real-world applications is that they impose new feasibility constraints that lead to research challenges. We survey developments in the field of two-sided matching with various constraints, including those based on regions, diversity, multi-dimensional capacities, and matroids.

Scopus

記述言語：その他   掲載種別：研究論文（学術雑誌）   出版者・発行元：Economics Letters  

Many real matching markets are subject to distributional constraints. When the set of feasible matchings is restricted by some distributional constraints, a stable matching may not exist. In contrast, a weakly stable matching is guaranteed to exist under a very general class of constraints that satisfies a condition called heredity. However, it has been an open question whether a weakly stable matching can be obtained by a strategy-proof mechanism. We negatively answer this open question; no weakly stable and strategy-proof mechanism exists under any heredity feasibility constraint in general.

DOI： 10.1016/j.econlet.2022.110675

Web of Science

Scopus

researchmap

記述言語：その他   掲載種別：研究論文（その他学術会議資料等）  

記述言語：英語  

記述言語：英語  

DOI： 10.1613/jair.1.13499

掲載種別：研究論文（国際会議プロシーディングス）   出版者・発行元：International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS)  

researchmap

その他リンク： https://dl.acm.org/doi/10.5555/3535850.3535911

掲載種別：研究論文（国際会議プロシーディングス）   出版者・発行元：International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS)  

researchmap

その他リンク： https://dl.acm.org/doi/10.5555/3535850.3536011

記述言語：英語   掲載種別：研究論文（学術雑誌）   出版者・発行元：Constraints  

A Clique Partitioning Problem (CPP) finds an optimal partition of a given edge-weighted undirected graph, such that the sum of the weights is maximized. This general graph problem has a wide range of real-world applications, including correlation clustering, group technology, community detection, and coalition structure generation. Although a CPP is NP-hard, due to the recent advance of Integer Linear Programming (ILP) solvers, we can solve reasonably large problem instances by formulating a CPP as an ILP instance. The first ILP formulation was introduced by Grötschel and Wakabayashi (Mathematical Programming, 45(1-3), 59–96, 1989). Recently, Miyauchi et al. (2018) proposed a more concise ILP formulation that can significantly reduce transitivity constraints as compared to previously introduced models. In this paper, we introduce a series of concise ILP formulations that can reduce even more transitivity constraints. We theoretically evaluate the amount of reduction based on a simple model in which edge signs (positive/negative) are chosen independently. We show that the reduction can be up to 50% (dependent of the ratio of negative edges) and experimentally evaluate the amount of reduction and the performance of our proposed formulation using a variety of graph data sets. Experimental evaluations show that the reduction can exceed 50% (where edge signs can be correlated), and our formulation outperforms the existing state-of-the-art formulations both in terms of memory usage and computational time for most problem instances.

DOI： 10.1007/s10601-022-09326-z

Web of Science

Scopus

researchmap

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

DOI： https://doi.org/10.1609/aaai.v36i11.21495

記述言語：その他   掲載種別：研究論文（学術雑誌）   出版者・発行元：Artificial Intelligence  

We extend the well-known model of graph-restricted games due to Myerson to signed graphs. In our model, it is possible to explicitly define not only that some players are friends (as in Myerson's model) but also that some other players are enemies. As such our games can express a wider range of situations, e.g., animosities between political parties. We define the value for signed graph games using the axiomatic approach that closely follows the celebrated characterization of the Myerson value. Furthermore, we propose an algorithm for computing an arbitrary semivalue, including the extension of the Myerson value proposed by us. We also develop a pseudo-polynomial algorithm for power indices in weighted voting games for signed graphs with bounded treewidth. Moreover, we consider signed graph games with a priori defined alliances (unions) between players and propose algorithms to compute the extension of the Owen value to this setting.

DOI： 10.1016/j.artint.2022.103792

Scopus

researchmap

記述言語：英語   掲載種別：研究論文（学術雑誌）   出版者・発行元：Autonomous Agents and Multi-Agent Systems  

In many real-life scenarios, a group of agents needs to agree on a common action, e.g., on a location for a public facility, while there is some consistency between their preferences, e.g., all preferences are derived from a common metric space. The facility location problem models such scenarios and it is a well-studied problem in social choice. We study mechanisms for facility location on unweighted undirected graphs that are resistant to manipulations (strategy-proof, abstention-proof, and false-name-proof) by both individuals and coalitions on one hand and anonymous and efficient (Pareto-optimal) on the other. We define a new family of graphs, ZV-line graphs, and show a general facility location mechanism for these graphs that satisfies all these desired properties. This mechanism can also be computed in polynomial time and it can equivalently be defined as the first Pareto-optimal location according to some predefined order. Our main result, the ZV-line graphs family and the mechanism we present for it, unifies all works in the literature of false-name-proof facility location on discrete graphs including the preliminary (unpublished) works we are aware of. In particular, we show mechanisms for all graphs of at most five vertices, discrete trees, bicliques, and clique tree graphs. Finally, we discuss some generalizations and limitations of our result for facility location problems on other structures: Weighted graphs, large discrete cycles, infinite graphs; and for facility location problems concerning infinite societies.

DOI： 10.1007/s10458-021-09535-5

Web of Science

Scopus

researchmap

出版者・発行元：Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS  

Mechanism design over social networks, whose goal is to incentivize agents to diffuse the information of a mechanism to their followers, as well as to report their true preferences, is one of the new trends in market design. In this paper, we reconsider the traditional house allocation problem with existing tenants from the perspective of mechanism design over social networks. Since our model is a generalization of the networked housing market investigated by Kawasaki et al. [9], no mechanism simultaneously satisfies strategy-proofness, individual rationality and Pareto efficiency for general social network structures. We therefore examine the cases where the social network has a tree structure. We first show that even for the restricted structure, a weaker welfare requirement called non-wastefulness is not achievable by any strategy-proof and individually rational mechanism. We then show that a non-trivial modification of You Request My House - I Get Your Turn mechanism (YRMH-IGYT) is individually rational, strategy-proof, and weakly non-wasteful. Furthermore, it chooses an allocation in the strict core for neighbors and satisfies weak group strategy-proofness.

Scopus

記述言語：日本語   出版者・発行元：一般社団法人 人工知能学会  

<p>本論文では，Robust MaxSAT (R-MaxSAT) の一般化である，Robust weighted Partial MaxSAT (R-PMaxSAT) を提案する． R-PMaxSAT における意思決定者は，充足する節の重みの和を最大化する割当を探索することを目的とする． 一方で，R-PMaxSAT における敵対者は，意思決定者が決定した割当に対して，定数個以下のブール変数の割当を変更可能である． そのため，意思決定者が決定した割当は，敵対者による攻撃に対して頑健な必要がある． この問題の決定問題版は Sigma2P 完全であると証明されている． また，R-PMaxSAT は，敵対者が存在する場合の Clique Partitioning Problem (CPP) である robust CPP を表現できるため，多くの現実的なモデルに応用可能である． 本論文では，SAT ソルバー，QBF ソルバーをサブルーチンとして利用し，R-PMaxSAT の最適解を与える 2 種類のアルゴリズムを提案する． 計算機実験において，提案したアルゴリズムを利用することで，現実的な時間の下で最適解を導出可能であることを示した．</p>

DOI： 10.11517/pjsai.jsai2022.0_4f1os8a04

CiNii Research

Web of Science

掲載種別：研究論文（国際会議プロシーディングス）   出版者・発行元：AAAI Press  

DOI： 10.1609/aaai.v36i11.21495

researchmap

その他リンク： https://dblp.uni-trier.de/db/conf/aaai/aaai2022.html#0001BY22

Web of Science

出版者・発行元：Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS  

The notion of envy-freeness is a natural and intuitive fairness requirement in resource allocation. With indivisible goods, such fair allocations are unfortunately not guaranteed to exist. Classical works have avoided this issue by introducing an additional divisible resource, i.e., money, to subsidize envious agents. In this paper, we aim to design a truthful allocation mechanism of indivisible goods to achieve both fairness and efficiency criteria with a limited amount of subsidy. Following the work of Halpern and Shah, our central question is as follows: to what extent do we need to rely on the power of money to accomplish these objectives? We show that, when agents have matroidal valuations, there is a truthful allocation mechanism that achieves envy-freeness and utilitarian optimality by subsidizing each agent with at most 1, the maximum marginal contribution of each item for each agent. The design of the mechanism rests crucially on the underlying matroidal M-convexity of the Lorenz dominating allocations. For superadditive valuations, we show that there is a truthful mechanism that achieves envy-freeness and utilitarian optimality, with each agent receiving a subsidy of at most m; furthermore, we show that the amount m is necessary even when agents have additive valuations.

Scopus

掲載種別：研究論文（学術雑誌）  

DOI： 10.48550/arXiv.2212.02751

researchmap

出版者・発行元：IJCAI International Joint Conference on Artificial Intelligence  

A new paradigm of mechanism design, called mechanism design over social networks, investigates agents' incentives to diffuse the information of mechanisms to their followers over social networks. In this paper we consider it for two-sided matching, where the agents on one side, say students, are distributed over social networks and thus are not fully observable to the mechanism designer, while the agents on the other side, say colleges, are known a priori. The main purpose of this paper is to clarify the existence of mechanisms that satisfy several properties that are classified into four criteria: incentive constraints, efficiency constraints, stability constraints, and fairness constraints. We proposed three mechanisms and showed that no mechanism is better than these mechanisms, i.e., they are in the Pareto frontier according to the set of properties defined in this paper.

Scopus

記述言語：日本語   出版者・発行元：一般社団法人 人工知能学会  

<p>マルチエージェント経路探索 (Multi-agent Pathfinding, MAPF) 問題は，それぞれ相異なるスタートとゴールが定められたエージェントの集合を入力とし，エージェント同士の衝突が発生しない経路の割当を解とする問題である．NP困難であることが知られている，各エージェントがゴールに到達するまでに要する時間の総和の最小化について，Meta-Agent Conflict Based Search (MA-CBS) と呼ばれる有力な厳密アルゴリズムが存在する．MA-CBS の動作は，マージポリシーと呼ばれる条件に応じて変化するが，従来用いられてきた静的なマージポリシーのもとでは，一部のMAPFインスタンスにおいて膨大な実行時間を要することが知られている．そこで本論文では，アルゴリズムの性質を動的に変化させる新たなマージポリシーを提案する．また，提案したマージポリシーを実装したアルゴリズムが，従来と比較して多様なインスタンスで効率的に動作することを計算機実験で示す．</p>

DOI： 10.11517/pjsai.jsai2022.0_1n1gs503

CiNii Research

記述言語：日本語   出版者・発行元：一般社団法人 人工知能学会  

<p>マルチエージェントシステムの分野において，エージェントにソーシャルネットワーク上での情報拡散の動機を与える意思決定メカニズムの設計が注目を集めている．本論文では，学生と学校との間のマッチング問題に関して，学生間のソーシャルネットワーク上での情報拡散を動機づけるマッチングメカニズムの設計を行う．具体的には，誘因，効率性，安定性，ならびに公平性の４つの評価指標に着目し，他のメカニズムに支配されない，すなわちパレートフロンティアな，３つのマッチングメカニズムを提案する．</p>

DOI： 10.11517/pjsai.jsai2022.0_2n4gs505

CiNii Research

記述言語：英語  

記述言語：英語  

記述言語：その他   掲載種別：研究論文（その他学術会議資料等）  

DOI： 10.1007/978-3-030-87756-9_25

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

DOI： 10.3233/FAIA200097

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

DOI： 10.3233/FAIA200096

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

記述言語：その他   掲載種別：研究論文（その他学術会議資料等）  

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

記述言語：英語   掲載種別：研究論文（学術雑誌）  

Repeated Multimarket Contact with Private Monitoring: A Belief-Free Approach

DOI： 10.1609/aaai.v34i02.5576

記述言語：英語   掲載種別：研究論文（学術雑誌）  

DOI： 10.1007/s10458-020-09448-9

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

DOI： 10.1609/aaai.v34i02.5576

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

Auctions via a social network, pioneered by Li et al. (2017), have been attracting considerable attention in the literature of mechanism design for auctions. However, no known mechanism has satisfied strategy-proofness, non-deficit, non-wastefulness, and individual rationality for a multi-unit unit-demand auction. In this paper, we first propose a mechanism that satisfies all of the above properties. We then make a comprehensive comparison with two naive mechanisms, showing that the proposed mechanism dominates them in social surplus, seller's revenue, and incentive for truth-telling by buyers. We also analyze the characteristics of the social surplus and the revenue achieved by the proposed mechanism, including the constant approximability of the worst-case efficiency loss and the complexity of optimizing revenue from the seller's perspective.

DOI： 10.1609/aaai.v34i02.5579

記述言語：その他   掲載種別：研究論文（学術雑誌）  

DOI： 10.1007/s10458-019-09429-7

記述言語：その他   掲載種別：研究論文（学術雑誌）  

DOI： 10.1007/s10458-020-09448-9

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

In the literature of mechanism design, market mechanisms have been developed by professionals based on their experience. The concept of automated mechanism design (AMD), initiated by Sandholm (2002), is a ground-breaking computer-aided framework to develop market mechanisms. In this paper, we apply a very recent AMD approach based on Boolean Satisfiability (SAT) to the mechanism design of false-name-proof facility location. We first provide a general theoretical characteristic of false-name-proof mechanisms, which enables a quite compact representation of target mechanisms. Our approach successfully reproduces several known results in the literature on false-name-proof facility locations over discrete structures. Furthermore, some unknown mechanisms are discovered for locating a public good on a 2-by-2 grid, and an impossibility result is revealed for locating a public bad, with an additional mild assumption, on a 2-by-3 grid. Finally, we demonstrate the extendability of our approach, by providing a new false-name-proof mechanism for a slightly modified problem of locating a public good.

DOI： 10.1007/978-3-030-33792-6_20

記述言語：日本語   掲載種別：研究論文（学術雑誌）  

Applying Criterion of Leveling of Costs to Dynamic Programming for Shortest Path Finding Problems

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

Coalition Structure Generation (CSG), which is a leading research issue in the domain of coalitional games, divides agents into exhaustive and disjoint coalitions to optimize social welfare. This paper studies CSG problems over weighted undirected graphs in which the weight on an edge between any two connecting agents represents how well they work together in a coalition. The weight can have either a positive or a negative value. We examine two types of problems. One is a CSG without any restrictions on the number of coalitions, and another is a CSG with k coalitions where k is determined in advance. We present two methods to solve these problems: ILP formulation and MaxSAT encoding.

DOI： 10.1007/978-3-030-33792-6_21

記述言語：英語   掲載種別：研究論文（学術雑誌）  

DOI： 10.1016/j.artint.2019.03.002

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

Auction is the common paradigm for resource allocation which is a fundamental problem in human society. Existing research indicates that the two primary objectives, the seller's revenue and the allocation efficiency, are generally conflicting in auction design. For the first time, we expand the domain of the classic auction to a social graph and formally identify a new class of auction mechanisms on graphs. All mechanisms in this class are incentive-compatible and also promote all buyers to diffuse the auction information to others, whereby both the seller's revenue and the allocation efficiency are significantly improved comparing with the Vickrey auction. It is found that the recently proposed information diffusion mechanism is an extreme case with the lowest revenue in this new class. Our work could potentially inspire a new perspective for the efficient and optimal auction design and could be applied into the prevalent online social and economic networks.

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

In this paper, we study coalition formation in hedonic games through the fairness criterion of envy-freeness. Since the grand coalition is always envy-free, we focus on the conjunction of envy-freeness with stability notions. We first show that, in symmetric and additively separable hedonic games, an individually stable and justified envy-free partition may not exist and deciding its existence is NP-complete. Then, we prove that the top responsiveness property guarantees the existence of a Pareto optimal, individually stable, and envy-free partition, but it is not sufficient for the conjunction of core stability and envy-freeness. Finally, under bottom responsiveness, we show that deciding the existence of an individually stable and envy-free partition is NP-complete, but a Pareto optimal and justified envy-free partition always exists.

DOI： 10.24963/ijcai.2019/10

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

We study how stability can be maintained even after any set of at most k players leave their groups, in the context of hedonic games. While stability properties ensure an outcome to be robust against players' deviations, it has not been considered how an unexpected change caused by a sudden deletion of players affects stable outcomes. In this paper, we propose a novel criterion that reshapes stability form robustness aspect. We observe that some stability properties can be no longer preserved even when a single agent is removed. However, we obtain positive results by focusing on symmetric friend-oriented hedonic games. We prove that we can efficiently decide the existence of robust outcomes with respect to Nash stability under deletion of any number of players or contractual individual stability under deletion of a single player. We also prove that symmetric additively separable games always admit an individual stable outcome that is robust with respect to individual rationality.

DOI： 10.24963/ijcai.2019/52

記述言語：英語   掲載種別：研究論文（その他学術会議資料等）  

In mechanism design, fairness is one of the central criteria for analyzing mechanisms. Recently, a new fairness concept called envy-freeness of a group toward a group (GtG-EFness) has received attention, which requires that no group of agents envies any other group. In this paper, we consider GtG-EFness in more general combinatorial auctions, including several subclasses of the multi-unit auction domain (unit-demand, diminishing marginal values, and all-or-nothing), and reveal the tight bound of the competitive ratios. In particular, we prove that the tight bound of the competitive ratio is 1/k (where k is the number of items) for the general combinatorial auction domain. We also clarify the relationship with Walrasian equilibria and conclude that no group envies any other group in any Walrasian equilibrium.

DOI： 10.1007/978-3-030-26176-4_45

記述言語：英語   掲載種別：研究論文（学術雑誌）  

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

In many real-life scenarios, a group of agents needs to agree on a common action, e.g., on a location for a public facility, while there is some consistency between their preferences, e.g., all preferences are derived from a common metric space. The facility location problem models such scenarios and it is a well-studied problem in social choice. We study mechanisms for facility location on unweighted undirected graphs, which are resistant to manipulations (strategy-proof, abstention-proof, and false-name-proof) by both individuals and coalitions and are efficient (Pareto optimal). We define a family of graphs, ZV-line graphs, and show a general facility location mechanism for these graphs which satisfies all these desired properties. Our result unifies the few works in the literature of false-name-proof facility location on discrete graphs including the preliminary (unpublished) works we are aware of.

記述言語：その他   掲載種別：研究論文（その他学術会議資料等）  

DOI： 10.1007/978-3-030-26176-4_45

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

Weighted Constraint Satisfaction Problems (WCSPs) are an elegant paradigm for modeling combinatorial optimization problems. A key assumption in this model is that all constraints are specified or known a priori, which does not hold in some applications where constraints may encode preferences of human users. Incomplete WCSPs (IWCSPs) extend WCSPs by allowing some constraints to be partially specified, and they can be elicited from human users during the execution of IWCSP algorithms. Unfortunately, existing approaches assume that the elicitation of preferences does not incur any additional cost. This assumption is unrealistic as human users are likely bothered by repeated elicitations and will refuse to provide an unbounded number of preferences. Therefore, we propose the IWCSP with Elicitation Cost (IWCSP+EC) model, which extends IWCSPs to include elicitation costs, as well as three parameterized heuristics that allow users to trade off solution quality for fewer elicited preferences and faster computation times. They provide theoretical quality guarantees for problems where elicitations are free. Our model and heuristics thus extend the state of the art in constraint reasoning to better model and solve agent-based applications with user preferences.

記述言語：英語   掲載種別：研究論文（学術雑誌）  

Privacy stochastic games in distributed constraint reasoning

DOI： 10.1007/s10472-019-09628-8

記述言語：日本語   掲載種別：研究論文（学術雑誌）  

提携構造形成問題は協力ゲーム理論の問題の一つで，エージェント集合を社会的利得が最大となるよう分割する問題である．本論文で扱う分割関数ゲームでは，分割で得られる個々のチーム（提携）の利得はそのチームのメンバーだけでは決まらず，他チームのメンバー構成の影響も受ける．また提携の利得は必ずしも正であるとは限らず，負の利得もあり得る．分割決定木は分割関数ゲームの簡潔記述法の一つである．本論文では，分割決定木で記述された問題の二つの解法を提案する．一つは深さ優先分枝限定法に基づくアルゴリズムで，もう一つはMaxSAT問題に帰着させる手法である．ランダムに生成した数千のインスタンスによる計算機実験を行い，利得が正のみの問題に対しては前者が優れ，負の利得もある問題に対しては後者が優れていることが分かった．<br />

DOI： 10.14923/transinfj.2018JDP7037

記述言語：その他   掲載種別：研究論文（学術雑誌）  

DOI： 10.1016/j.artint.2019.03.002

記述言語：英語   掲載種別：研究論文（学術雑誌）  

The Coalition Structure Generation (CSG) problem plays an important role in the domain of coalition games. Its goal is to create coalitions of agents so that the global welfare is maximized. To date, Weighted Partial MaxSAT (WPM) encoding has shown high efficiency in solving the CSG problem, which encodes a set of constraints into Boolean propositional logic and employs an off-the-shelf WPM solver to find out the optimal solution. However, in existing WPM encodings, a number of redundant encodings are asserted. This results in additional calculations and correspondingly incurs performance penalty. Against this background, this paper presents an Improved Rule Relation-based WPM (I-RWPM) encoding for the CSG problem, which is expressed by a set of weighted rules in a concise representation scheme called Marginal Contribution net (MC-net). In order to effectively reduce the constraints imposed on encodings, we first identify a subset of rules in an MC-net, referred as a set of freelance rules. We prove that solving the problem made up of all freelance rules can be achieved with a straightforward means without any extra encodings. Thus the set of rules requiring to be encoded is downsized. Next, we improve the encoding of transitive relations among rules. To be specific, compared with the existing rule relation-based encoding that generates transitive relations universally among all rules, I-RWPM only considers the transitivity among rules with particular relationship. In this way, the number of constraints to be encoded can be further decreased. Experiments suggest that I-RWPM significantly outperforms other WPM encodings for solving the same set of problem instances.

DOI： 10.1007/s10601-018-9295-4

記述言語：英語   掲載種別：研究論文（学術雑誌）  

Improved WPM encoding for coalition structure generation under MC-nets

DOI： 10.1007/s10601-018-9295-4

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

記述言語：英語   掲載種別：研究論文（学術雑誌）  

In this work, we approach the issue of privacy in distributed constraint reasoning by studying how agents compromise solution quality for preserving privacy, using utility and game theory. We propose a utilitarian definition of privacy in the context of distributed constraint reasoning, detail its different implications, and present a model and solvers, as well as their properties. We then show how important steps in a distributed constraint optimization with privacy requirements can be modeled as a planning problem, and more specifically as a stochastic game. We present experiments validating the interest of our approach, according to several criteria.

DOI： 10.1007/s10472-019-09628-8

記述言語：英語   掲載種別：研究論文（学術雑誌）  

DOI： 10.1613/jair.1.11254

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

We introduce a new fundamental problem called triangular trade, which is a natural extension of the well-studied prisoner’s dilemma for three (or more) players where a player cannot directly punish a seemingly defecting player. More specifically, this problem deals with a situation where the power/influence of players is one-way, players would be better off if they maintain circular cooperation, but each player has an incentive to defect. We analyze whether players can sustain such circular cooperation when they repeatedly play this game and each player observes the actions of another player with some observation errors (imperfect private monitoring). We confirm that no simple strategy can constitute an equilibrium within any reasonable parameter settings when there are only two actions: “Cooperate” and “Defect.” Thus, we introduce two additional actions: “Whistle” and “Punish,” which can be considered as a slight modification of “Cooperate.” Then, players can achieve sustainable cooperation using a simple strategy called Remote Punishment strategy (RP), which constitutes an equilibrium for a wide range of parameters. Furthermore, we show the payoff obtained by a variant of RP is optimal within a very general class of strategies that covers virtually all meaningful strategies.

DOI： 10.1007/978-3-030-03098-8_15

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

In this paper, we consider a student-project-resource allocation problem, in which students and indivisible resources are allocated to every project. The allocated resources determine endogenously the student capacity of a project. Traditionally, this problem is divided in two: (I) resources are allocated to projects based on expected demands (resource allocation problem), and (II) students are matched with projects based on the capacity determined in the previous problem (many-to-one matching problem). Although both problems are well-understood, unless the expectations used in the first problem are correct, we obtain a suboptimal outcome. Thus, it is desirable to solve this problem as a whole, without dividing it. We start by introducing a compact representation that takes advantage of the symmetry of preferences. Then, we show that computing a nonwasteful matching is FP^NP -complete. Besides, a fair matching can be found in polynomial-time. Finally, deciding whether a stable (i.e. nonwasteful and fair) matching exists is NP^NP -complete.

DOI： 10.1007/978-3-030-03098-8_14

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

We consider an allocation problem of multiple types objects to agents, where each type of an object has multiple copies (e.g., mult iple seats of a school), each agent is endowed with an object, and some distributional constraints are imposed on the allocation (e.g., minimum/maximum quotas). We develop a mechanism that is based on the Top Trading Cycles mechanism, which Is strategy-proof, feasible (always satisfies distributional constraints). Pareto efficient, and individually rational, assuming the distributional constraints are represented as an M-convex set. The class of distributional cons traints we consider contains many situations raised from realistic matching problems, including individual minimum/maximum quot as, regional maximum quotas, type-specific quotas, and distance constraints. To the best of our knowledge, we are the first to develop a mechanism with these desirable properties.

記述言語：英語   掲載種別：研究論文（学術雑誌）  

We consider two-sided matching problems where agents on one side of the market (hospitals) are required to satisfy certain distributional constraints. We show that when the preferences and constraints of the hospitals can be represented by an M♮-concave function, (i) the generalized Deferred Acceptance (DA) mechanism is strategyproof for doctors, (ii) it produces the doctor-optimal stable matching, and (iii) its time complexity is proportional to the square of the number of possible contracts. Furthermore, we provide sufficient conditions under which the generalized DA mechanism satisfies these desirable properties. These conditions are applicable to various existing works and enable new applications as well, thereby providing a recipe for developing desirable mechanisms in practice.

DOI： 10.1016/j.jet.2018.05.004

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

In this paper, we identify a new class of distributional constraints defined as a union of symmetric M-convex sets, which can represent a variety of real-life constraints in two-sided matching settings. Since M-convexity is not closed under union, a union of symmetric M-convex sets does not belong to this well-behaved class of constraints in general. Thus, developing a fair and strategyproof mechanism that can handle this class is challenging. We present a novel mechanism called Quota Reduction Deferred Acceptance (QRDA), which repeatedly applies the standard DA mechanism by sequentially reducing artificially introduced maximum quotas. We show that QRDA is fair and strategyproof when handling a union of symmetric M-convex sets. Furthermore, in comparison to a baseline mechanism called Artificial Cap Deferred Acceptance (ACDA), QRDA always obtains a weakly better matching for students and, experimentally, performs better in terms of nonwastefulness.

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

Facility location is a well-studied problem in social choice literature. where agents' preferences are restricted to be single-peaked. When the number of agents is treated as a variable (e.g., not observable a priori), a social choice function must be defined so that it can accept any possible number of preferences as input. Furthermore, there exist cases where multiple choices must be made continuously while agents dynamically arrive/leave. Under such variable and dynamic populations, a social choice function needs to give each agent an incentive to sincerely report her existence. In this paper we investigate facility location models with variable and dynamic populations. For a static, i.e., one-shot, variable population model, we provide a necessary and sufficient condition for a social choice function to satisfy participation, as well as truthfulness, anonymity, and Pareto efficiency. The condition is given as a further restriction on the well-known median voter schemes. For a dynamic model, we first propose an online social choice function, which is optimal for the total sum of the distances between the choices in the previous and current periods, among any Pareto efficient functions. We then define a generalized class of online social choice functions and compare their performances both theoretically and experimentally.

記述言語：英語   掲載種別：研究論文（学術雑誌）  

We consider two-sided matching problems where agents on one side of the market (hospitals) are required to satisfy certain distributional constraints. We show that when the preferences and constraints of the hospitals can be represented by an M♮-concave function, (i) the generalized Deferred Acceptance (DA) mechanism is strategyproof for doctors, (ii) it produces the doctor-optimal stable matching, and (iii) its time complexity is proportional to the square of the number of possible contracts. Furthermore, we provide sufficient conditions under which the generalized DA mechanism satisfies these desirable properties. These conditions are applicable to various existing works and enable new applications as well, thereby providing a recipe for developing desirable mechanisms in practice.

DOI： 10.1016/j.jet.2018.05.004

記述言語：英語   掲載種別：研究論文（学術雑誌）  

DOI： 10.1007/s10458-018-9386-z

記述言語：英語   掲載種別：研究論文（学術雑誌）  

The Distributed Constraint Optimization Problem (DCOP) lies at the foundations of multiagent cooperation. With DCOPs, the optimization in distributed resource allocation problems is formalized using constraint optimization problems. The solvers for the problem are designed based on decentralized cooperative algorithms that are performed by multiple agents. In a conventional DCOP, a single objective is considered. The Multiple Objective Distributed Constraint Optimization Problem (MODCOP) is an extension of the DCOP framework, where agents cooperatively have to optimize simultaneously multiple objective functions. In the conventional MODCOPs, a few objectives are globally defined and agents cooperate to find the Pareto optimal solution. However, such models do not capture the interests of each agent. On the other hand, in several practical problems, the share of each agent is important. Such shares are modeled as preference values of agents. This class of problems can be defined using the MODCOP on the preferences of agents. In particular, we define optimization problems based on leximin ordering and Asymmetric DCOPs (Leximin AMODCOPs). The leximin defines an ordering among vectors of objective values. In addition, Asymmetric DCOPs capture the preferences of agents. Because the optimization based on the leximin ordering improves the equality among the satisfied preferences of the agents, this class of problems is important. We propose several solution methods for Leximin AMODCOPs generalizing traditional operators into the operators on sorted objective vectors and leximin. The solution methods applied to the Leximin AMODCOPs are based on pseudo trees. Also, the investigated search methods employ the concept of boundaries of the sorted vectors.

DOI： 10.1111/coin.12106

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

In this paper, we propose a fractional preference model for the facility location game with two facilities that serve the similar purpose on a line where each agent has his location information as well as fractional preference to indicate how well they prefer the facilities. The preference for each facility is in the range of [0, L] such that the sum of the preference for all facilities is equal to 1. The utility is measured by subtracting the sum of the cost of both facilities from the total length L where the cost of facilities is defined as the multiplication of the fractional preference and the distance between the agent and the facilities. We first show that the lower bound for the objective of mini-1 mizing total cost is at least Ω(n3). Hence, we use the utility function to analyze the agents' satification. Our objective is to place two facilities on [0, L] to maximize the social utility or the minimum utility. For each objective function, we propose deterministic strategy-proof mechanisms. For the objective of maximizing the social utility, we present an optimal deterministic strategy-proof mechanism in the case where agents can only misreport their locations. In the case where agents can only misreport their preferences, we present a 2-approximation deterministic strategy-proof mechanism. Finally, we present a 4-approximation deterministic strategyproof mechanism and a randomized strategy-proof mechanism with an approximation ratio of 2 where agents can misreport both the preference and location information. Moreover, we also give a lower-bound of 1.06. For the objective of maximizing the minimum utility, we give a lower-bound of 1.5 and present a 2-approximation deterministic strategyproof mechanism where agents can misreport both the preference and location.

記述言語：英語   掲載種別：研究論文（学術雑誌）  

DOI： 10.1111/coin.12106

記述言語：英語   掲載種別：研究論文（学術雑誌）  

DOI： 10.3233/FI-2018-1642

記述言語：英語   掲載種別：研究論文（学術雑誌）  

DOI： 10.3233/FI-2018-1641

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

Route optimization is an important problem for single agents and multi-agent systems. In route optimization tasks, the considered challenges generally belong to the family of shortest path problems. Such problems are solved using optimization algorithms, such as the A∗algorithm, which is based on tree search and dynamic programming. In several practical cases, cost values should be as evenly minimized for individual parts of paths as possible. These situations are also considered as multi-objective problems for partial paths. Since dynamic programming approaches are employed for the shortest path problems, different types of criteria which can be decomposed with dynamic programming might be applied to the conventional solution methods. For this class of problems, we employ a leximax-based criterion, which considers the bottlenecks and unfairness among the cost values of partial paths. This criterion is based on a similar criterion called leximin for multiobjective maximization problems. It is also generalized for objective vectors which have variable lengths. We address an extension of the conventional A∗search algorithm and investigate an issue concerning on-line search algorithms. The influence of the proposed approach is experimentally evaluated.

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

記述言語：英語   掲載種別：研究論文（その他学術会議資料等）  

Coalition Structure Generation for Partition Function Games Utilizing a Concise Graphical Representation

DOI： 10.1007/978-3-319-69131-2_9

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

Much of the Distributed Constraint Satisfaction Problem (DisCSP) solving research has addressed cooperating agents, and privacy was frequently mentioned as a significant motivation of the decentralization. While privacy may have a role for cooperating agents, it is easier understood in the context of self-interested utility-based agents, and this is the situation considered here. With utility-based agents, the DisCSP framework can be extended to model privacy and satisfaction under the concept of utility. We introduce Utilitarian Distributed Constraint Satisfaction Problems (UDisCSP), an extension of the DisCSP that exploits the rewards for finding a solution and the costs for losing privacy as guidance for the utility-based agents. A parallel can be drawn between Partially Observable Markov Decision Processes (POMDPs) and the problems solved by individual agents for UDisCSPs. Common DisCSP solvers are extended to take into account the utility function. In these extensions we assume that the planning problem is further restricting the set of communication actions to only the ones available in the corresponding solver protocols. The solvers obtained propose the action to be performed in each situation, defining thereby the policy of the agents.

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

We consider the problem of locating facilities on a discrete acyclic graph, where agents’ locations are publicly known and the agents are requested to report their demands, i.e., which facilities they want to access. In this paper, we study the effect of manipulations by agents that utilize vacant vertices. Such manipulations are called rename or false-name manipulations in game theory and mechanism design literature. For locating one facility on a path, we carefully compare our model with traditional ones and clarify their differences by pointing out that some existing results in the traditional model do not carry over to our model. For locating two facilities, we analyze the existing and new mechanisms from a perspective of approximation ratio and provide non-trivial lower bounds. Finally, we introduce a new mechanism design model where richer information is available to the mechanism designer and show that under the new model false-name-proofness does not always imply population monotonicity.

記述言語：日本語   掲載種別：研究論文（学術雑誌）  

記述言語：英語   掲載種別：研究論文（学術雑誌）  

We consider a school choice program where minimum quotas are imposed for each school, i.e., a school must be assigned at least a certain number of students to operate. We require that the obtained matching must respect the initial endowments, i.e., each student must be assigned to a school that is at least as good as her initial endowment school. Although minimum quotas are relevant in school choice programs and strategy-proofness is important to many policymakers, few existing mechanisms simultaneously achieve both. One difficulty is that no strategy-proof mechanism exists that is both efficient and fair under the presence of minimum quotas. Furthermore, existing mechanisms require that all students consider all schools acceptable to obtain a feasible matching that respects minimum quotas. This assumption is unrealistic in a school choice program.

We consider the environment where a student considers her initial endowment school acceptable and the initial endowments satisfy all the minimum quotas. We develop two strategy-proof mechanisms. One mechanism, which we call the Top Trading Cycles among Representatives with Supplementary Seats (TTCR-SS), is based on the Top Trading Cycles (TTC) mechanism and is significantly extended to handle the supplementary seats of schools while respecting minimum quotas. TTCR-SS is Pareto efficient. The other mechanism, which we call Priority List-based Deferred Acceptance with Minimum Quotas (PLDA-MQ), is based on the Deferred Acceptance (DA) mechanism. PLDA-MQ is fair, satisfies a concept called Priority List-based (PL-) stability, and obtains the student-optimal matching within all PL-stable matchings. Our simulation results show that our new mechanisms are significantly better than simple extensions of the existing mechanisms.

DOI： 10.1016/j.artint.2017.04.006

記述言語：英語   掲載種別：研究論文（学術雑誌）  

We consider a school choice program where minimum quotas are imposed for each school, i.e., a school must be assigned at least a certain number of students to operate. We require that the obtained matching must respect the initial endowments, i.e., each student must be assigned to a school that is at least as good as her initial endowment school. Although minimum quotas are relevant in school choice programs and strategy-proofness is important to many policymakers, few existing mechanisms simultaneously achieve both. One difficulty is that no strategy-proof mechanism exists that is both efficient and fair under the presence of minimum quotas. Furthermore, existing mechanisms require that all students consider all schools acceptable to obtain a feasible matching that respects minimum quotas. This assumption is unrealistic in a school choice program.
We consider the environment where a student considers her initial endowment school acceptable and the initial endowments satisfy all the minimum quotas. We develop two strategy-proof mechanisms. One mechanism, which we call the Top Trading Cycles among Representatives with Supplementary Seats (TTCR-SS), is based on the Top Trading Cycles (TTC) mechanism and is significantly extended to handle the supplementary seats of schools while respecting minimum quotas. TTCR-SS is Pareto efficient. The other mechanism, which we call Priority List-based Deferred Acceptance with Minimum Quotas (PLDA-MQ), is based on the Deferred Acceptance (DA) mechanism. PLDA-MQ is fair, satisfies a concept called Priority List-based (PL-) stability, and obtains the student optimal matching within all PL-stable matchings. Our simulation results show that our new mechanisms are significantly better than simple extensions of the existing mechanisms. (C) 2017 The Authors. Published by Elsevier B.V.

DOI： 10.1016/j.artint.2017.04.006

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

We investigate hedonic games under enemies aversion and friends appreciation, where every agent considers other agents as either a friend or an enemy. We extend these simple preferences by allowing each agent to also consider other agents to be neutral. Neutrals have no impact on her preference, as in a graphical hedonic game. Surprisingly, we discover that neutral agents do not simplify matters, but cause complexity. We prove that the core can be empty under enemies aversion and the strict core can be empty under friends appreciation. Furthermore, we show that under both preferences, deciding whether the strict core is nonempty, is NP^NP-complete. This complexity extends to the core under enemies aversion. We also show that under friends appreciation, we can always find a core stable coalition structure in polynomial time.

記述言語：英語   掲載種別：研究論文（学術雑誌）  

To handle diverse types of practical applications, this paper develops a theory of two-sided matching under distributional constraints. The only requirement we impose on the constraints is heredity, a condition that if a matching is feasible, then any matching that assigns weakly fewer students at each school is also feasible. This condition is more general than those studied in existing research such as regional maximum quotas and diversity constraints in school choice. When distributional constraints are imposed, there does not necessarily exist a stable matching, i.e., a matching that satisfies fairness and nonwastefulness. We propose a new mechanism called the Adaptive Deferred Acceptance mechanism (ADA), which satisfies strategyproofness for students, nonwastefulness, and a weaker fairness property. We also offer a technique to apply the ADA even if the constraints do not satisfy the heredity condition (e.g., minimum quotas). We demonstrate the applicability of our analysis in actual application domains.

DOI： 10.1257/mic.20160124

記述言語：英語   掲載種別：研究論文（学術雑誌）  

To handle various applications, we study matching under constraints. The only requirement on the constraints is heredity; given a feasible matching, any matching with fewer students at each school is also feasible. Heredity subsumes existing constraints such as regional maximum quotas and diversity constraints. With constraints, there may not exist a matching that satisfies fairness and nonwastefulness (i. e., stability). We demonstrate our new mechanism, the Adaptive Deferred Acceptance mechanism (ADA), satisfies strategy-proofness for students, nonwastefulness, and a weaker fairness property. We also offer a technique to apply ADA even if heredity is violated (e.g., minimum quotas).

DOI： 10.1257/mic.20160124

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

Privacy has been a major motivation for distributed problem optimization. However, even though several methods have been proposed to evaluate it, none of them is widely used. The Distributed Constraint Optimization Problem (DCOP) is a fundamental model used to approach various families of distributed problems. Here we approach the problem by letting both the optimized costs found in DCOPs and the privacy requirements guide the agents' exploration of the search space. We introduce Utilitarian Distributed Constraint Optimization Problem (UDCOP) where the costs and the privacy requirements are used as parameters to a heuristic modifying the search process. Common stochastic algorithms for decentralized constraint optimization problems are evaluated here according to how well they preserve privacy.

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

We investigate markets with a set of students on one side and a set of colleges on the other. A student and college can be linked by a weighted contract that defines the student's wage, while a college's budget for hiring students is limited. Stability is a crucial requirement for matching mechanisms to be applied in the real world. A standard stability requirement is coalitional stability, i.e., no pair of a college and group of students has incentive to deviate. We find that a coalitionally stable matching is not guaranteed to exist, verifying the coalitional stability for a given matching is coXP- complete, and the problem to find whether a coalitionally stable matching exists in a given market, is NPNP-complete (that is Ef-complete). Given these computational hardness results, we pursue a weaker stability requirement called pairwise stability, i.e., no pair of a college and single student has incentive to deviate. We then design a strategy-proof mechanism that works in polynomial-Time for computing a pairwise stable matching in typed markets in which students are partitioned into types that induce their possible wages.

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

Several methods exist for electing committees of representatives and conducting multiple referenda based on approval voting. Recently, a family of rules for approval-based voting using ordered weighted averaging was proposed in [1], ranging from a simple candidate-wise majority (minisum) to egalitarian rule (minimax). Even though the first rule is strategyproof and the second is not, due to its egalitarian nature, only a partial study on manipulation has been conducted for inbetween rules. This paper investigates the maiiipulability of fair rules within this family. We first prove that all rules parameterized by fair (non-increasing) weight vectors are manipulable, except minisum, if we consider them either resolute with a tie-breaking mechanism or irresolute with classic extension principles. Then, we conduct an empirical study of the proportion of elections that are manipulable, showing that it increases based on the rule's fairness.

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

The Distributed Constraint Optimization Problem (DCOP) formulation is a powerful tool for modeling multi-Agent coordination problems. Researchers have recently extended this model to Proactive Dynamic DCOPs (PD-DCOPs) to capture the inherent dynamism present in many coordination problems. The PD-DCOP formulation is a finite-horizon model that assumes a finite horizon is known a priori. It ignores changes to the problem after the horizon and is thus not guaranteed to find optimal solutions for infinite-horizon problems, which often occur in the real world. Therefore, we (i) propose the Infinite-Horizon PD-DCOP (IPD- DCOP) model, which extends PD-DCOPs to handle infinite horizons', (ii) exploit the convergence properties of Markov chains to determine the optimal solution to the problem after it has converged; (Hi) propose three distributed greedy algorithms to solve IPD-DCOPs; (iv) provide theoretical quality guarantees on the new model; and (v) empirically evaluate both proactive and reactive algorithms to determine the tradeoffs between the two classes. The final contribution is important as, thus far. researchers have exclusively evaluated the two classes of algorithms in isolation. As a result, it is difficult to identify the characteristics of problems that they excel in. Our results arc the first in this important direction.

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

The coalition structure generation (CSG) problem consists in partitioning a group of agents into coalitions to maximize the sum of their values. We consider here the rase of coalitional games whose characteristic function is compactly represented by a set of weighted conjunctive formulae (an MC-net). In this context the CSG problem is known to be computationally hard in general. In this paper, we first study some key parameters of MC- nets that complicate solving make the CSG problem. Then we consider a specific class of MC-nets, called bipolar MC- nets, and prove that the CSG problem is polynomial for this class. Finally, we show that the CS-core of a game represented by a bipolar MC-net is never empty, and that an imputation belonging to the CS-core can be computed in polynomial time.

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

記述言語：英語   掲載種別：研究論文（学術雑誌）  

DOI： 10.1613/jair.5297

記述言語：英語   掲載種別：研究論文（学術雑誌）  

DOI： 10.1109/MIS.2017.3

記述言語：英語   掲載種別：研究論文（学術雑誌）  

DOI： 10.1109/MIS.2017.3

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

We consider a social choice problem where individual rationality is required. The status quo belongs to the outcome space, and the selected alternative must be weakly better than the status quo for everybody. If the mechanism designer has no knowledge of the alternatives, we obtain a negative result: any individually rational (IR) and strategy-proof (SP) mechanism can choose at most one alternative (besides the status quo), regardless of the preferences. To overcome this negative result, we consider a domain where the alternatives have a known structure, i.e., an agent is indifferent between the status quo and a subset of the outcomes. This set is exogenously given and public information. This assumption is natural if the social choice involves the participation of agents. For example, consider a group of people organizing a trip where participation is voluntary. We can assume each agent is indifferent between the trip plans in which she does not participate and the status quo (i.e., no trip). In this setting, we obtain more positive results: we develop a class of mechanisms called Approve and Choose mechanisms, which are IR and SP, and can choose multiple alternatives as well as the status quo.

DOI： 10.1007/978-3-319-44832-9_11

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

Much of the Distributed Constraint Satisfaction Problem (DisCSP) solving research has addressed cooperating agents, and privacy was frequently mentioned as a significant motivation of the decentralization. While privacy may have a role for cooperating agents, it is easier understood in the context of self-interested utility-based agents, and this is the situation considered here. With utility-based agents, the DisCSP framework can be extended to model privacy and satisfaction under the concept of utility. We introduce Utilitarian Distributed Constraint Satisfaction Problems (UDisCSP), an extension of the DisCSP that exploits the rewards for finding a solution and the costs for losing privacy as guidance for the utility-based agents. A parallel can be drawn between Partially Observable Markov Decision Processes (POMDPs) and the problems solved by individual agents for UDisCSPs. Common DisCSP solvers are extended to take into account the utility function. In these extensions we assume that the planning problem is further restricting the set of communication actions to only the ones available in the corresponding solver protocols. The solvers obtained propose the action to be performed in each situation, defining thereby the policy of the agents.

記述言語：英語   掲載種別：研究論文（学術雑誌）  

This paper considers matching problems with individual/regional minimum/maximum quotas. Although such quotas are relevant in many real-world settings, there is a lack of strategyproof mechanisms that take such quotas into account. We first show that without any restrictions on the regional structure, checking the existence of a feasible matching that satisfies all quotas is NP-complete. Then, assuming that regions have a hierarchical structure (i.e., a tree), we show that checking the existence of a feasible matching can be done in time linear in the number of regions. We develop two strategyproof matching mechanisms based on the Deferred Acceptance mechanism (DA), which we call Priority List based Deferred Acceptance with Regional minimum and maximum Quotas (PLDA-RQ) and Round-robin Selection Deferred Acceptance with Regional minimum and maximum Quotas (RSDA-RQ). When regional quotas are imposed, a stable matching may no longer exist since fairness and nonwastefulness, which compose stability, are incompatible. We show that both mechanisms are fair. As a result, they are inevitably wasteful. We show that the two mechanisms satisfy different versions of nonwastefulness respectively; each is weaker than the original nonwastefulness. Moreover, we compare our mechanisms with an artificial cap mechanism via simulation experiments, which illustrate that they have a clear advantage in terms of nonwastefulness and student welfare.

DOI： 10.1016/j.artint.2016.02.002

記述言語：英語   掲載種別：研究論文（学術雑誌）  

This paper considers matching problems with individual/regional minimum/maximum quotas. Although such quotas are relevant in many real-world settings, there is a lack of strategyproof mechanisms that take such quotas into account. We first show that without any restrictions on the regional structure, checking the existence of a feasible matching that satisfies all quotas is NP-complete. Then, assuming that regions have a hierarchical structure (i.e., a tree), we show that checking the existence of a feasible matching can be done in time linear in the number of regions. We develop two strategyproof matching mechanisms based on the Deferred Acceptance mechanism (DA), which we call Priority List based Deferred Acceptance with Regional minimum and maximum Quotas (PLDA-RQ) and Round-robin Selection Deferred Acceptance with Regional minimum and maximum Quotas (RSDA-RQ). When regional quotas are imposed, a stable matching may no longer exist since fairness and nonwastefulness, which compose stability, are incompatible. We show that both mechanisms are fair. As a result, they are inevitably wasteful. We show that the two mechanisms satisfy different versions of nonwastefulness respectively; each is weaker than the original nonwastefulness. Moreover, we compare our mechanisms with an artificial cap mechanism via simulation experiments, which illustrate that they have a clear advantage in terms of nonwastefulness and student welfare. (C) 2016 The Authors. Published by Elsevier B.V.

DOI： 10.1016/j.artint.2016.02.002

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

Centrality indices aim to quantify the importance of nodes or edges in a network. A number of new centrality indices have recently been proposed to try and capture the role of nodes in connecting the network. While these indices seem to deliver new insights, to date not enough is known about their theoretical properties. To address this issue, we propose an axiomatic approach. Specifically, we prove that there exists a unique centrality index satisfying some intuitive properties related to network connectivity. This new index, which we call Attachment Centrality, is equivalent to the Myerson value of a particular graph-restricted coalitional game. Building upon our theoretical analysis, we show that our Attachment Centrality has certain computational properties that are more attractive than the Myerson value for an arbitrary game.

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

Current approaches that model dynamism in DCOPs solve a sequence of static problems, reacting to changes in the environment as the agents observe them. Such approaches thus ignore possible predictions on future changes. To overcome this limitation, we introduce Proactive Dynamic DCOPs (PD-DCOPs), a novel formalism to model dynamic DCOPs in the presence of exogenous uncertainty. In contrast to reactive approaches, PD-DCOPs are able to explicitly model the possible changes to the problem, and take such information into account proactively, when solving the dynamically changing problem. The additional expressivity of this formalism allows it to model a wider variety of distributed optimization problems. Our work presents both theoretical and practical contributions that advance current dynamic DCOP models: (i) we introduce the PD-DCOP model, which explicitly captures dynamic changes of the DCOP over time; (ii) we discuss the complexity of this new class of DCOPs; and (iii) we develop both exact and approximation algorithms with quality guarantees to solve PD-DCOPs proactively.

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

This paper develops a strategy-proof and Pareto efficient mechanism for a school choice program called Top Trading Cycles among Representatives with Supplementary Seats (TTCR-SS). We consider a setting where minimum quotas are imposed for each school, i.e., a school is required to be assigned at least a certain number of students to operate, and the obtained matching must respect initial endowments, i.e., each student must be assigned to a school that is at least as good as her initial endowment school. Although minimum quotas are relevant in school choice programs and strategy-proofness is important to many policymakers, few existing mechanisms achieve both of them simultaneously. Furthermore, existing mechanisms require that all students consider all schools acceptable to obtain a feasible matching that respects minimum quotas and cannot guarantee Pareto efficiency. TTCR-SS is based on Top Trading Cycles (TTC) mechanism, while it is significantly extended to handle the supplementary seats of schools while respecting minimum quotas. Our simulation results show TTCR-SS is significantly better than an existing TTC-based mechanism in terms of students' welfare.

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

Sequential allocation is one of the most fundamental models for allocating indivisible items to agents in a decentralized manner, in which agents sequentially pick their favorite items among the remainder based on a pre-defined priority ordering of agents (a sequence). In recent years, algorithmic issues about agents' manipulations have also been investigated, such as the computational complexity of verifying whether a given bundle of items is achievable and maximizing one's utility under a given additive utility function. In this paper we consider a slightly modified model, where the selection process is divided into rounds, each agent obtains exactly one item in each round, and the sequence per round is determined uniformly at random. It is natural to expect that finding a profitable manipulation is difficult even for the case of two agents, since a manipulator must consider exponentially many possible sequences with respect to the number of rounds due to randomization. To our surprise, however, an optimal manipulation can be computed without any exploration for exponentially decaying utilities. Furthermore, for general additive utilities, although some exploration is required, it can still be done in polynomial time with respect to the number of rounds.

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

In most previous models of coalition structure generation, it is assumed that agents may partition themselves into any coalition structure. In practice, however, there may be physical and organizational constraints that limit the number of co-existing coalitions. In this paper, we introduce k-coalitional games: a type of partition function game especially designed to model such situations. We propose an extension of the Shapley value for these games, and study its axiomatic and computational properties. In particular, we show that, under some conditions, it can be computed in polynomial time given two existing representations of coalitional games with externalities. Finally, we use k-coalitional games to analyse the relative importance of geographical locations in the game of Diplomacy.

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

This paper considers a mechanism design problem for locating two identical facilities on an interval, in which an agent can pretend to be multiple agents. A mechanism selects a pair of locations on the interval according to the declared singlepeaked preferences of agents. An agent's utility is determined by the location of the better one (typically the closer to her ideal point). This model can represent various application domains. For example, assume a company is going to release two models of its product line and performs a questionnaire survey in an online forum to determine their detailed specs. Typically, a customer will buy only one model, but she can answer multiple times by logging onto the forum under several email accounts. We first characterize possible outcomes of mechanisms that satisfy false-name-proofness, as well as some mild conditions. By extending the result, we completely characterize the class of false-name-proof mechanisms when locating two facilities on a circle.We then clarify the approximation ratios of the false-name-proof mechanisms on a line metric for the social and maximum costs. 1 Introduction.

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

Consider the problem of estimating the expected number of distinct eligible voters among the authors of a set of electronic signatures gathered for a petition (or citizen initiative) that has to pass legally required thresholds. We formalize this problem and propose an extension to the Pretty Good Privacy Web Of Trust, a mechanism for reciprocally certifying identities between peers. The extension (a) enables agents to certify additional relevant statements about others, and (b) gives agents opportunities for negative authentication statements (e.g., on ineligibility of an identity). A Bayesian Network model enables inferences on the data provided by the proposed PGP extension. Simulations and an agent-based platform are used to validate the concepts.

記述言語：英語   掲載種別：研究論文（学術雑誌）  

We study matching markets in which institutions may have minimum and maximum quotas. Minimum quotas are important in many settings, such as hospital residency matching, military cadet matching, and school choice, but current mechanisms are unable to accommodate them, leading to the use of ad hoc solutions. We introduce two new classes of strategyproof mechanisms that allow for minimum quotas as an explicit input and show that our mechanisms improve welfare relative to existing approaches. Because minimum quotas cause a theoretical incompatibility between standard fairness and nonwastefulness properties, we introduce new second-best axioms and show that they are satisfied by our mechanisms. Last, we use simulations to quantify (1) the magnitude of the potential efficiency gains from our mechanisms and (2) how far the resulting assignments are from the first-best definitions of fairness and nonwastefulness. Combining both the theoretical and simulation results, we argue that our mechanisms will improve the performance of matching markets with minimum quota constraints in practice.

DOI： 10.1145/2841226

記述言語：英語   掲載種別：研究論文（その他学術会議資料等）  

How is cooperation/collusion sustained in repeated multimarket contact with observation errors?

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

We develop flexible reward plans to elicit truthful predictive probability distribution over a set of uncertain events from workers. In general, strictly proper scoring rules for categorical events only reward a worker for an event that actually occurred. However, different incorrect predictions vary in quality, and the principal would like to assign different rewards to them, according to her subjective similarity among events; e.g. a prediction of overcast is closer to sunny than rainy. We propose concrete methods so that the principal can assign rewards for incorrect predictions according to her similarity between events. We focus on two representative examples of strictly proper scoring rules: spherical and quadratic, where a worker’s expected utility is represented as the inner product of her truthful predictive probability and her declared probability. In this paper, we generalize the inner product by introducing a reward matrix that defines a reward for each prediction outcome pair. We first show that if the reward matrix is symmetric and positive definite, both the spherical and quadratic proper scoring rules guarantee the maximization of a worker’s expected utility when she truthfully declares her prediction. We next compare our rules with the original spherical/quadratic proper scoring rules in terms of the variance of rewards obtained by workers. Finally, we show our experimental results using Amazon Mechanical Turk.

DOI： 10.1007/978-3-319-25524-8_25

記述言語：英語   掲載種別：研究論文（その他学術会議資料等）  

Leximin Asymmetric Multiple Objective DCOP on Factor Graph

DOI： 10.1007/978-3-319-25524-8_9

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

The cake cutting problem must fairly allocate a divisible good among agents who have varying preferences over it. Recently, designing strategy-proof cake cutting mechanisms has caught considerable attention from AI and MAS researchers. Previous works assumed that an agent’s utility function is additive so that theoretical analysis becomes tractable. However, in practice, agents have non-additive utility functions over a resource. In this paper, we consider the allor-nothing utility function as a representative example of non-additive utility because it can widely cover agents’ preferences for real-world resources, such as the usage of meeting rooms, time slots for computational resources, bandwidth usage, and so on. We first show the incompatibility between envy-freeness and Pareto efficiency when each agent has all-or-nothing utility. We next propose two strategy-proof mechanisms that satisfy Pareto efficiency, which are based on a serial dictatorship mechanism, at the sacrifice of envy-freeness. To address computational feasibility, we propose an approximation algorithm to find a near-optimal allocation in time polynomial in the number of agents, since the problem of finding a Pareto efficient allocation is NP-hard. As another approach that abandon Pareto efficiency, we develop an envy-free mechanism and show that one of our serial dictatorship based mechanisms satisfies proportionality in expectation, which is a weaker definition of proportionality. Finally, we evaluate the efficiency obtained by our proposed mechanisms by computational experiments.

DOI： 10.1007/978-3-319-25524-8_8

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

Leximin AMODCOP has been proposed as a class of Multiple Objective Distributed Constraint Optimization Problems, where multiple objectives for individual agents are optimized based on the leximin operator. This problem also relates to Asymmetric DCOPs with the criteria of fairness among agents, which is an important requirement in practical resource allocation tasks. Previous studies explore only Leximin AMODCOPs on constraint graphs limited to functions with unary or binary scopes.We address the Leximin AMODCOPs on factor graphs that directly represent n-ary functions. A dynamic programming method on factor graphs is investigated as an exact solution method. In addition, for relatively dense problems, we also investigate several inexact algorithms.

DOI： 10.1007/978-3-319-25524-8_9

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

In this paper we study the exchange of indivisible objects where agents' possible preferences over the objects are strict and share a common structure among all of them, which represents a certain level of asymmetry among objects. A typical example of such an exchange model is a re-scheduling of tasks over several processors, since all task owners are naturally assumed to prefer that their tasks are assigned to fast processors rather than slow ones. We focus on designing exchange rules (a.k.a. mechanisms) that simultaneously satisfy strategyproofness, individual rationality, and Pareto efficiency. We first provide a general impossibility result for agents' preferences that are determined in an additive manner, and then show an existence of such an exchange rule for further restricted lexicographic preferences. We finally find that for the restricted case, a previously known equivalence between the single-valuedness of the strict core and the existence of such an exchange rule does not carry over.

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

Weighted voting games allow for studying the distribution of power between agents in situations of collective decision making. While the conventional version of these games assumes that any agent is always ready to cooperate with all others, recently, more involved models have been proposed, where cooperation is subject to restrictions. Following Myerson [1977], such restrictions are typically represented by a graph that expresses available communication links among agents. In this paper, we study the time complexity of computing two well-known power indices - the Shapley-Shubik index and the Banzhaf index - in the graph-restricted weighted voting games. We show that both are #P-complete and propose a dedicated dynamic-programming algorithm that runs in pseudo-polynomial time for graphs with the bounded treewidth.

記述言語：英語   掲載種別：研究論文（その他学術会議資料等）  

DOI： 10.1145/2764468.2764501

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

School choice programs are implemented to give students/parents an opportunity to choose the public school the students attend. Controlled school choice programs need to provide choices for students/parents while maintaining distributional constraints on the balance on the composition of students, typically in terms of socioeconomic status. Previous works show that setting soft-bounds, which flexibly change the priorities of students based on their types, is more appropriate than setting hard-bounds, which strictly limit the number of accepted students for each type. We consider a case where soft-bounds are imposed and one student can belong to multiple types, e.g., "financially-distressed" and "minority" types. We first show that when we apply a model that is a straightforward extension of an existing model for disjoint types, there is a chance that no stable matching exists. Thus, we propose an alternative model and an alternative stability definition, where a school has reserved seats for each type. We show that a stable matching is guaranteed to exist in this model, and develop a mechanism called Deferred Acceptance for Overlapping Types (DA-OT). The DA-OT mechanism is strategy-proof and obtains the student-optimal matching within all stable matchings. Computer simulation results illustrate that the DA-OT outperforms an artificial cap mechanism, where the number of seats for each type is fixed.

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

We propose a novel representation for coalitional games with externalities, called Partition Decision Trees. This representation is based on rooted directed trees, where non-leaf nodes are labelled with agents' names, leaf nodes are labelled with payoff vectors, and edges indicate membership of agents in coalitions. We show that this representation is fully expressive, and for certain classes of games significantly more concise than an extensive representation. Most importantly, Partition Decision Trees are the first formalism in the literature under which most of the direct extensions of the Shapley value to games with externalities can be computed in polynomial time.

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

Core-selection is a crucial property of social choice functions, or rules, in social choice literature. It is also desirable to address the incentive of agents to cheat by misreporting their preferences. This paper investigates an exchange problem where each agent may have multiple indivisible goods, agents' preferences over sets of goods are assumed to be lexicographic, and side payments are not allowed. We propose an exchange rule called augmented top-trading-cycles (ATTC) procedure based on the original TTC procedure. We first show that the ATTC procedure is core-selecting. We then show that finding a beneficial misreport under the ATTC procedure is NP-hard. Under the ATTC procedure, we finally clarify the relationship between preference misreport and splitting, which is a different type of manipulation.

記述言語：英語   掲載種別：研究論文（学術雑誌）  

When forming the grand coalition is not possible or optimal, agents need to create a coalition structure. The idea of the core can be extended to such a case. In this paper, we propose an innovative exact algorithm called CoreD to check core-non-emptiness for coalition structures. A more straightforward exact algorithm based on existing techniques, which we call CoreP, first obtains the value of optimal coalition structure by solving an integer programming problem. Then, it checks whether that value can be divided without making a blocking (dissatisfied) coalition. In contrast, CoreD first finds a minimal value of the optimal coalition structure so that there exists no blocking coalition. Next, it checks whether the optimal value equals the minimal value We empirically show that when the core is empty, CoreD is by far superior to CoreP. Also, to find a second-best payoff vector when the core is empty, we propose a new solution concept called the weak ε-core⁺, which can utilize the approximate value of the optimal coalition structure. Based on the idea of CoreD, we further develop an algorithm for checking the non-emptiness of the weak ε-core⁺.

DOI： 10.1016/j.artint.2015.01.001

記述言語：英語   掲載種別：研究論文（その他学術会議資料等）  

Parametric mechanism design via quantifier elimination

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

We study the problem where a group of agents need to choose from a finite set of social outcomes. We assume every agent's valuation for every outcome is bounded and the bounds are public information. For our model, no mechanism simultaneously satisfies strategy-proofness, individual rationality, non-deficit, and efficiency. In light of this, we aim to design mechanisms that are strategy-proof, individually rational, non-deficit, and minimize the worst-case efficiency loss. We propose a family of mechanisms called the shifted Groves mechanisms, which are generalizations of the Groves mechanisms. We first show that if there exist mechanisms that are strategy-proof, individually rational, and non-deficit, then there exist shifted Groves mechanisms with these properties. Our main result is an Automated Mechanism Design (AMD) approach for identifying the (unique) optimal shifted Groves mechanism, which minimizes the worst-case efficiency loss among all shifted Groves mechanisms. Finally, we prove that the optimal shifted Groves mechanism is globally optimal among all deterministic mechanisms that are strategy-proof, individually rational, and non-deficit.

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

Cake cutting has been recognized as a fundamental model in fair division, and several envy-free cake cutting algorithms have been proposed. Recent works from the computer science field proposed novel mechanisms for cake cutting, whose approaches are based on the theory of mechanism design; these mechanisms are strategy-proof, i.e., no agent has any incentive to misrepresent her utility function, as well as envy-free. We consider a different type of manipulations; each agent might create fake identities to cheat the mechanism. Such manipulations have been called Sybils or falsename manipulations, and designing robust mechanisms against them, i.e., false-name-proof, is a challenging problem in mechanism design literature. We first show that no randomized false-name-proof cake cutting mechanism simultaneously satisfies ex-post envy-freeness and Pareto efficiency. We then propose a new randomized mechanism that is optimal in terms of worst-case loss among those that satisfy false-name-proofness, ex-post envy-freeness, and a new weaker efficiency property. However, it reduces the amount of allocations for an agent exponentially with respect to the number of agents. To overcome this negative result, we provide another new cake cutting mechanism that satisfies a weaker notion of false-name-proofness, as well as ex-post envy-freeness and Pareto efficiency.

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

This paper considers matching problems with hierarchical regional minimum quotas. Although such quotas are relevant in many real-world settings, it is known that nonwastefulness and fairness (which compose stability) are incompatible when minimum quotas are imposed. We develop a new strategy-proof nonwasteful mechanism called Adaptive Deferred Acceptance with Regional minimum Quotas (ADARQ), which is fairer than an existing nonwasteful mechanism called Multi-Stage DA with Regional minimum Quotas (MSDA-RQ).

記述言語：英語  

Can local caution restore global tacit collusion?: Repeated multimarket contact with observation

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

This paper analyzes repeated multimarket contact with observation errors where two players operate in multiple markets simultaneously. Multimarket contact has received much attention from the literature of economics, management, and information systems. Despite vast empirical studies that examine whether multimarket contact fosters cooperation/collusion, little is theo-retically known as to how players behave in an equilibrium when each player receives a noisy observation of other firms' actions. This paper tackles an essentially realistic situation where the players do not share common information; each player may observe a different signal (private monitoring). Thus, players have difficulty in having a common understanding about which market their opponent should be punished in and when punishment should be started and ended. We first theoretically show that an extension of 1-period mutual punishment (IMP) for an arbitrary number of markets can be an equilibrium. Second, by applying a verification method, we identify a simple equilibrium strategy called "locally cautioning (LC)" that restores collusion after observation error or deviation. We then numerically reveal that LC significantly outperforms IMP and achieves the highest degree of collusion.

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

MC-nets is a concise representation of the characteristic functions that exploits a set of rules to compute payoffs. Given aMC-nets instance, the problem of computing a payoff division in the least core, which is a generalization of the core-non-emptiness problem that is known to be coNP-complete, is definitely a hard computational problem. In fact, to the best of our knowledge, no algorithm can actually compute such a payoff division for MC-nets instances with dozens of agents. We propose a new algorithm for this problem, that exploits the constraint generation technique to solve the linear programming problem that potentially has a huge number of constraints. Our experimental results are striking since, using 8 GB memory, our proposed algorithm can successfully compute a payoff division in the least core for the instances with up to 100 agents, but the naive algorithm fails due to a lack of memory for instances with 30 or more agents.

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

We address a variation of Multiple Objective Distributed Constraint Optimization Problems (MODCOPs). In the conventional MODCOPs, a few objectives are globally defined and agents cooperate to find the Pareto optimal solution. On the other hand, in several practical problems, the share of each agent is important. Such shares are represented as preference values of agents. This class of problems is defined as theMODCOP on the preferences of agents. Particularly, we focus on the optimization problems based on the leximin ordering (Leximin AMODCOPs), which improves the equality among agents. The solution methods based on pseudo trees are applied to the Leximin AMODCOPs.

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

記述言語：日本語   掲載種別：研究論文（学術雑誌）  

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

This paper proposes a new approach to building false-name-proof (FNP) combinatorial auctions from those that are FNP only with single-minded bidders, each of whom requires only one particular bundle. Under this approach, a general bidder is decomposed into a set of single-minded bidders, and after the decomposition the price and the allocation are determined by the FNP auctions for single-minded bidders. We first show that the auctions we get with the single-minded decomposition are FNP if those for single-minded bidders satisfy a condition called PIA. We then show that another condition, weaker than PIA, is necessary for the decomposition to build FNP auctions. To close the gap between the two conditions, we have found another sufficient condition weaker than PIA for the decomposition to produce strategy-proof mechanisms. Furthermore, we demonstrate that once we have PIA, the mechanisms created by the decomposition actually satisfy a stronger version of false-name-proofness, called false-name-proofness with withdrawal.

DOI： 10.3233/978-1-61499-419-0-945

記述言語：日本語   掲載種別：研究論文（学術雑誌）  

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

We study a mechanism design problem for exchange economies where each agent is initially endowed with a set of indivisible goods and side payments arc not allowed. We assume each agent can withhold some endowments. as well as misreport her preference. Under this assumption, strategyproofness requires that for each agent, reporting her true preference with revealing all her endowments is a dominant strategy, and thus implies individual rationality. Our objective in this paper is to analyze the effect of such private ownership in exchange economies with multiple endowments. As fundamental results, we first show that the revelation principle holds under a natural assumption and that strategyproofness and Pareto efficiency are incompatible even under the lexicographic preference domain. We then propose a class of exchange rules, each of which has a corresponding directed graph to prescribe possible trades, and provide necessary and sufficient conditions on the graph structure so that they satisfy strategyproofness.

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

Individual rationality, Pareto efficiency, and strategy-proofness are crucial properties of decision making functions, or mechanisms, in social choice literatures. In this paper we investigate mechanisms for exchange models where each agent is initially endowed with a set of goods and may have indifferences on distinct bundles of goods, and monetary transfers are not allowed. Sönmez (1999) showed that in such models, those three properties are not compatible in general. The impossibility, however, only holds under an assumption on preference domains. The main purpose of this paper is to discuss the compatibility of those three properties when the assumption does not hold. We first establish a preference domain called top-only preferences, which violates the assumption, and develop a class of exchange mechanisms that satisfy all those properties. Each mechanism in the class utilizes one instance of the mechanisms introduced by Saban and Sethuraman (2013). We also find a class of preference domains called m-chotomous preferences, where the assumption fails and these properties are incompatible.

記述言語：英語   掲載種別：研究論文（その他学術会議資料等）  

This paper considers the matching problem with regional quotas, in particular, regional minimum quotas. Although such quotas are relevant in many real-world settings, there is a lack of strategy-proof mechanisms that consider regional minimum quotas. We first show that without any restrictions on the region structure, finding a feasible matching that satisfies all quotas is NP-complete. Then, assuming that regions have a hierarchical structure (in this case, a tree), and maximum quotas are imposed only on individual schools, we show that checking the existence of a feasible matching can be done in a linear time in the number of regions. Furthermore, we develop strategy-proof matching mechanisms based on the Deferred Acceptance mechanism (DA), which we call Multi-Stage DA with Regional minimum Quotas (MSDA-RQ) and Round-robin Selection DA with Regional minimum Quotas (RSDA-RQ). When minimum quotas are imposed, fairness and nonwastefulness are incompatible. We prove that RSDA-RQ is fair but wasteful, while MSDA-RQ is nonwasteful but not fair. Moreover, we compare our mechanisms with artificial cap mechanisms whose individual maximum quotas are adjusted beforehand so that all regional quotas can be automatically satisfied. Our simulation reveals that our mechanisms substantially outperform artificial cap mechanisms in terms of student welfare. Furthermore, it illustrates the trade-off between our mechanisms.

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

Although the celebrated Vickrey auction is strategy-proof and guaranteed to achieve an efficient allocation in a single-object auction, if there exists no outside party (i.e., a seller or an auctioneer) with the right to collect the payment, the collected payment will be wasted. Redistribution mechanisms try to redistribute the payment to participating agents as much as possible without violating strategy-proofness. However, when a losing agent can obtain part of the payment, she may have an incentive to participate under multiple identities and receive a greater share of the redistribution. Our goal is to develop false-name-proof redistribution mechanisms that are robust against such manipulations. First, we prove that no mechanism simultaneously satisfies false-name-proofness and allocative efficiency, except for the Vickrey auction. Next, we propose a class of false-name-proof redistribution mechanisms, which are characterized by several parameters. We show that each mechanism in the class is not dominated by any other false-name-proof mechanism in terms of social welfare. Precisely, by choosing these parameters appropriately, all instances of this class are guaranteed to achieve at least the same amount of social welfare obtained by any false-name-proof mechanism. Furthermore, we formalize an optimization problem that determines appropriate parameter values based on prior information about participating agents.

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

This paper proposes a novel market-based system for ridesharing, where commuters are matched based on their declared travel constraints, the number of available seats (which could be zero), and their costs. Based on this information, the system then designates commuters to be either drivers or riders, finds appropriate matches, and calculates rewards for drivers and payments for riders. We show that, for this system, the well-known Vickrey-Clarke-Groves (VCG) mechanism is incentive compatible (IC), individually rational (IR) and efficient (i.e., minimizing cost), but results in a very high deficit, thus requiring large subsidies. We therefore investigate alternative mechanisms. We first consider mechanisms with fixed prices and show that no such mechanism can be both efficient and IC. Thus, we propose an inefficient IC mechanism but which has deficit control. We then consider a VCG mechanism with two-sided reserve prices. We show that this mechanism is IC and IR for a certain range of reserve prices, and we analyse the deficit bounds and how these can be controlled. We furthermore show that the deficit can be controlled even further by limiting the (costly) detours taken by the drivers when computing the allocations, thereby trading off efficiency and deficit.

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

The class of Groves mechanisms has been attracting much attention in mechanism design literature due to two attractive characteristics: utilitarian efficiency (also called social welfare maximization) and dominant strategy incentive compatibility. However, when strategic agents can create multiple fake identities and reveal more than one preference under them, a refined characteristic called false-name-proofness is required. Utilitarian efficiency and false-name-proofness are incompatible in combinatorial auctions, if we also have individual rationality as a desired condition. However, although individual rationality is strongly desirable, if participation is mandatory due to social norms or reputations, a mechanism without individual rationality can be sustained. In this paper we investigate the relationship between utilitarian efficiency and false-name-proofness in a social choice environment with monetary transfers. We show that in our modelization no mechanism simultaneously satisfies utilitarian efficiency, false-name-proofness, and individual rationality. Considering this fact, we ignore individual rationality and design various mechanisms that simultaneously satisfy the other two properties. We also compare our different mechanisms in terms of the distance to individual rationality. Finally we illustrate our mechanisms on a facility location problem.

記述言語：日本語   掲載種別：研究論文（学術雑誌）  

記述言語：日本語   掲載種別：研究論文（学術雑誌）  

Complete/Incomplete Algorithms for MO-DCOPs (in Japanese)

記述言語：日本語   掲載種別：研究論文（学術雑誌）  

A Hybrid Algorithm for Distributed Constraint Optimization (in Japanese)

記述言語：日本語   掲載種別：研究論文（学術雑誌）  

エージェント間に外部性が存在する場合の戦略的操作不可能な割当 てメカニズムの提案

記述言語：英語   掲載種別：研究論文（その他学術会議資料等）  

Strategy-proof mechanisms for the k-winner selection problem

DOI： 10.1007/978-3-642-44927-7_20

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

The goal of this paper is to develop a strategy-proof (SP) mechanism for the k-winner selection problem, which finds a set of (at most) k winners among participants. Here, we assume the winners can have positive/negative externalities with each other; the gross utility of a winner not only depends on whether she wins, but also on the other winners. If the types of agents, i.e., the gross utilities of agents, are known, we can obtain a Pareto efficient (PE) allocation that maximizes the sum of the gross utilities of winners in polynomial time, assuming k is a constant. On the other hand, when the types of agents are private information, we need a mechanism that can elicit the true types of agents; it must satisfy SP. We first show that there exists no SP mechanism that is PE, individual rational (IR), and non-deficit (ND) in a general setting where we put no restrictions on possible agent types. Thus, we need to give up at least one of these desirable properties. Next, we examine how a family of Vickrey-Clarke-Groves (VCG) based mechanisms works for this problem. We consider two alternative VCG-based mechanisms in this setting, both of which are SP and PE. We show that one alternative, called VCG-ND, is ND but not IR, and the other alternative, called VCG-IR, is IR but not ND. Also, we show special cases where VCG-ND satisfies IR, or VCG-IR satisfies ND. Moreover, we propose mechanisms called VCG-ND+ and VCG-IR+, which can be applied to a general setting, where a mechanism designer has partial knowledge about the possible interactions among agents. Both VCG-ND+ and VCG-IR+ are SP, IR, and ND, but they are not PE. Finally, we present a concise graphical representation scheme of agant types.

DOI： 10.1007/978-3-642-44927-7_20

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

The Max-Sum algorithm is a solution method for the Distributed Constraint Optimization Problem (DCOP) which is a fundamental problem in multiagent cooperation. Particularly, we focus on the case of Max-Sum on a spanning tree, where the algorithm is an exact solution method. In this case, all agents simultaneously compute globally optimal objective values as erootf nodes of the tree that represents the problem. On the other hand, a tiebreak is generally necessary in order to determine a unique optimal solution among the agents. While top-down post-processing is a well-known solution, one can prefer to design the solver as a bottom-up computation that is simply integrated to pre-processing. To address this issue, we investigate a technique that employs a preference ordering based on spanning trees for the optimization algorithms. With this technique, top-down processing to choose a unique optimal solution can be embedded into bottom-up optimization via small weight values for the preference ordering. We also evaluate an integrated algorithm that maintains both tree structures and quasi-optimal solutions using the bottom-up approaches.

DOI： 10.1007/978-3-642-44927-7_14

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

P2P social networks defined by user actions (e.g., P2P discussion forums) are expected to be ideal environments for Sybil and false identity attacks (just as in the case of the similar web based systems: YouTube, etc.). In particular, these attacks are a significant impediment for meaningful electronic petition drives since they render impossible the verification of the eligibility of participants. While many electronic social networks strive for guaranteeing the privacy (e.g., by anonymization) of their users, existing systems for petition drives, like DirectDemocracyP2P.net, encourage users to disclose their real identities and are meaningless when users do not follow this request. We describe a framework and investigate techniques for running decentralized peer-to-peer census processes that enable observers to independently verify the identity of participants in a social network.

DOI： 10.1109/WI-IAT.2013.149

記述言語：日本語   掲載種別：研究論文（学術雑誌）  

記述言語：日本語   掲載種別：研究論文（学術雑誌）  

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

When forming the grand coalition is not possible/optimal, agents need to create a coalition structure. The idea of the core can be extended to such a case. In this paper, we propose an innovative algorithm called CoreD to check core-non-emptiness for coalition structures. A more straightforward algorithm based on existing techniques, which we call CoreP, first obtains the value of optimal coalition structure by solving an integer programming problem. Then, it checks whether that value can be divided without making a blocking (dissatisfied) coalition. In contrast, CoreD first finds a minimal amount value of optimal coalition structure so that there exists no blocking coalition. Then, it checks whether the optimal value can be equal to the minimal value. We empirically show that when the core is empty, CoreD is by far superior to CoreP. Also, to find a second-best payoff vector when the core is empty, we propose a new solution concept called the weak ε-core⁺, which can utilize the approximate value of the optimal coalition structure. Based on the idea of CoreD, we further develop an algorithm for checking the non-emptiness of the weak ε-core⁺.

DOI： 10.1109/WI-IAT.2013.99

記述言語：英語   掲載種別：研究論文（その他学術会議資料等）  

Embedding Preference Ordering for Single-phase Self-stabilizing DCOP Solvers

記述言語：英語   掲載種別：研究論文（その他学術会議資料等）  

Ability grouping of crowd workers via reward discrimination

DOI： 10.1609/hcomp.v1i1.13083

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

記述言語：日本語  

記述言語：日本語  

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

記述言語：その他  

Pseudo-Tree Based Hybrid Algorithm for Distributed Constraint Optimization

記述言語：日本語   掲載種別：研究論文（学術雑誌）  

Distributed Search Methods for Quantified Distributed Constraint Optimization Problem

DOI： 10.1527/tjsai.28.43

記述言語：日本語   掲載種別：研究論文（学術雑誌）  

Interactive Algorithm for Multi-objective Constraint Optimization

DOI： 10.1527/tjsai.28.57

記述言語：英語   掲載種別：研究論文（学術雑誌）  

Many real world problems involve multiple criteria that should be considered separately and optimized simultaneously. A Multi-Objective Constraint Optimization Problem (MO-COP) is the extension of a mono-objective Constraint Optimization Problem (COP). In aMO-COP, it is required to provide the most preferred solution for a user among many optimal solutions. In this paper, we develop a novel Interactive Algorithm for MO-COP (MO-IA). The characteristics of this algorithm are as follows: (i) it can guarantee to find a Pareto solution, (ii) it narrows a region, in which Pareto front may exist, gradually, (iii) it is based on a pseudo-tree, which is a widely used graph structure in COP algorithms, and (iv) the complexity of this algorithm is determined by the induced width of problem instances. In the evaluations, we use an existing model for representing a utility function, and show empirically the effectiveness of our algorithm. Furthermore, we propose an extension of MO-IA, which finds several Pareto solutions so that we can provide a narrower region, in which Pareto front may exist, i.e., our extended algorithm can provide the more detailed information for Pareto front.

DOI： 10.1527/tjsai.28.57

記述言語：英語   掲載種別：研究論文（学術雑誌）  

This tutorial focuses on designing a mechanism that achieves a socially desirable outcome or a goal of the designer that arises from some practical demands, as several advanced topics on mechanism design theory. We first briefly explains the theory of combinatorial auctions via the most well-known Vickrey-Clarke-Groves mechanism. Second, as an example that designs a new mechanism for a practical demand, we introduce false-name bids and illustrate how we improve a trivial robust mechanism against false-name bids. Furthermore, we explore models and several theoretical results on mechanisms of a keyword auction and a two-sided matching as other well-known topics of mechanism design theory.

DOI： 10.11309/jssst.30.1_34

記述言語：英語   掲載種別：研究論文（学術雑誌）  

This tutorial introduces a cooperative game theory which is one of main parts in game theory. A cooperative game theory consists of two major research topics. The first topic involves how to divide the value of the coalition among agents. We explain the desirable ways of dividing the rewards among cooperative agents, called solution concepts. The traditional cooperative game theory provides a number of solution concepts, such as the core, the Shapley value, and the nucleolus. We introduce some algorithms for dividing the obtained rewards among agents and show their computational complexities. The second topic involves partitioning a set of agents into coalitions so that the sum of the rewards of all coalitions is maximized. This is called Coalition Structure Generation problem (CSG). We explain efficient constraint optimization algorithms for solving the CSG problem. Furthermore, we introduce concise representation schemes for a characteristic function, since it is likely that we can solve solution concepts/CSG problem more efficiently by utilizing concise representation methods for a game.

DOI： 10.11309/jssst.30.2_33

記述言語：英語   掲載種別：研究論文（学術雑誌）  

Distributed Constraint Optimization problems (DCOPs) have been studied as a fundamental model of multiagent cooperation. In traditional DCOPs, all agents cooperate to optimize the sum of their cost functions. However, in practical systems some agents may desire to select the value of their variables without cooperation. In special cases, such agents may take the values with the worst impact on the quality of the result reachable by the optimization process. Similar classes of problems have been studied as Quantified (Distributed) Constraint Problems, where the variables of the CSP have existential/universal quantifiers. All constraints should be satisfied independently of the value taken by universal variables. In this paper, a Quantified Distributed Constraint Optimization problem (QDCOP) that extends the framework of DCOPs is presented. We apply existential/universal quantifiers to distinct uncooperative variables. A universally quantified variable is left unassigned by the optimization as the result has to hold when it takes any value from its domain, while an existentially quantified variable takes exactly one of its values for each context. We consider that the QDCOP applies the concept of game tree search to DCOP. If the original problem is a minimization problem, agents that own universally quantified variables may intend to maximize the cost value in the worst case. Other agents normally intend to optimize the minimizing problems. Therefore, only the bounds, especially the upper bounds, of the optimal value are guaranteed. The purpose of the new class of problems is to compute such bounds, as well as to compute sub-optimal solutions. For the QDCOP, we propose solution methods that are based on min-max/alpha-beta and ADOPT algorithms.

DOI： 10.1527/tjsai.28.43

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

DirectDemocracyP2P5 is an open source platform developed in JAVA and offering peer-to-peer and mobile ad hoc wireless communication capabilities. The platform offers an API supporting plugins, beside its main application: deliberative petition drives (aka citizens' initiatives with integrated argumentation) [1]. An authentication-by-reputation technique based on digital signatures and peer review [2], [3] is integrated into the platform via this main application. Each peer manages independently its database of items of interest. The items of interest are encapsulated as self-contained pieces of information and uniquely identifiable using a system of global identifiers (GIDs). Each GID consists of a combination of public keys with creation dates, or digest values. Communication is based on a combination of push and pull mechanisms. [1]

DOI： 10.1109/P2P.2013.6688733

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

This paper presents a framework for combining multiple strategy-proof resource allocation mechanisms, in which participants are divided into several groups (partitions) and each mechanism is applied to one partition. The idea of dividing participants into several groups is introduced to achieve budget balance in a redistribution mechanism, i.e., the payment (money) collected in one partition is distributed in another partition. Furthermore, this idea has been used to adjust parameters of a mechanism (e.g., the reservation price in an auction) based on the information of participants in one partition in order to improve the mechanism's efficiency or revenue. This paper presents a unified framework called a generalized partition mechanism, in which information, money, and unsold goods can be transferred among partitions. This framework is very general and thus can be applied to various settings, including cases where a redistribution mechanism must adjust parameters to obtain a better social surplus. We provide a sufficient condition on the flow of information, money, and goods among partitions so that the generalized partition mechanism is strategy-proof, assuming that each mechanism applied to the partition is strategy-proof. We can use this sufficient condition as a guideline for combining multiple mechanisms. To show the applicability of this guideline, we develop new redistribution mechanisms based on this guideline, in which the utility of a participant can be non-quasi-linear.

DOI： 10.1109/WI-IAT.2012.256

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

A Distributed Constraint Satisfaction Problem (DisCSP) is a constraint satisfaction problem in which variables and constraints are distributed among multiple agents. Various algorithms for solving DisC-SPs have been developed, which are intended for general purposes, i.e., they can be applied to any network structure. However, if a network has some particular structure, e.g., the network structure is scale-free, we can expect that some specialized algorithms or heuristics, which are tuned for the network structure, can outperform general purpose algorithms/heuristics. In this paper, as an initial step toward developing specialized algorithms for particular network structures, we examine variable-ordering heuristics in scale-free networks. We use the classic asynchronous backtracking algorithm as a baseline algorithm and examine the effect of variable-ordering heuristics. First, we show that the choice of variable-ordering heuristics is more influential in scale-free networks than in random networks. Furthermore, we develop a novel variable-ordering heuristic that is specialized to scale-free networks. Experimental results illustrate that our new variable-ordering heuristic is more effective than a standard degree-based variable-ordering heuristic. Our proposed heuristic reduces the required cycles by 30% at the critical point.

DOI： 10.1007/978-3-642-25920-3_12

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

Many real world problems involve multiple criteria that should be considered separately and optimized simultaneously. A Multi-Objective Constraint Optimization Problem (MO-COP) is the extension of a mono-objective Constraint Optimization Problem (COP). In a MO-COP, it is required to provide the most preferred solution for a user among many optimal solutions. In this paper, we develop a novel Interactive Algorithm for MO-COP (MO-IA). The characteristics of this algorithm are as follows: (i) it can guarantee to find a Pareto solution, (ii) it narrows a region, in which Pareto front may exist, gradually, (iii) it is based on a pseudo-tree, which is a widely used graph structure in COP algorithms, and (iv) the complexity of this algorithm is determined by the induced width of problem instances. In the evaluations, we use an existing model for representing a utility function, and show empirically the effectiveness of our algorithm. Furthermore, we propose an extension of MO-IA, which can provide the more detailed information for Pareto front.

DOI： 10.1007/978-3-642-33558-7_41

記述言語：日本語   掲載種別：研究論文（学術雑誌）  

記述言語：日本語   掲載種別：研究論文（学術雑誌）  

記述言語：英語   掲載種別：研究論文（学術雑誌）  

In multihop wireless networks (MWNs), the selective forwarding attack is a special case of denial of service attack. In this attack, the malicious wireless nodes only forward a subset of the received packets, but drop the others. This attack becomes more severe if multiple attackers exist and collude together to disrupt the normal functioning of the secure protocols. By colluding, each attacker can even only drop a little packets, but the overall loss of the path will be high. However, most prior researches on selective forwarding attacks assume the attackers do not collude with each other. Furthermore, the previous works also lack of comprehensive security analysis. In this paper, by utilizing the game theoretic approach, we analyze the collusion in selective forwarding attacks. We first put forward a sub-route oriented punish and reward scheme, and propose an multi-attacker repeated colluding game. Then by static and dynamic analysis of this colluding attack game, we find the sub-game equilibriums which indicate the attackers' optimal attack strategies. Based on the analysis result, we establish a security policies for multihop wireless networks, to threaten and detect the malicious insider nodes which collude with each other to launch the selective forwarding attacks.

DOI： 10.1016/j.comcom.2012.07.006

記述言語：日本語  

クラウドソーシングにおける品質コントロールの一考察

記述言語：英語   掲載種別：研究論文（その他学術会議資料等）  

Interactive Algorithm for Multi-objective Constraint Optimization

DOI： 10.1007/978-3-642-33558-7_41

記述言語：日本語  

BnB-ADOPT-p：分散制約最適化問題におけるハイブリッド型の解法の提案

記述言語：英語   掲載種別：研究論文（学術雑誌）  

In multihop wireless networks (MWNs), the selective forwarding attack is a special case of denial of service attack. In this attack, the malicious wireless nodes only forward a subset of the received packets, but drop the others. This attack becomes more severe if multiple attackers exist and collude together to disrupt the normal functioning of the secure protocols. By colluding, each attacker can even only drop a little packets, but the overall loss of the path will be high. However, most prior researches on selective forwarding attacks assume the attackers do not collude with each other. Furthermore, the previous works also lack of comprehensive security analysis. In this paper, by utilizing the game theoretic approach, we analyze the collusion in selective forwarding attacks. We first put forward a sub-route oriented punish and reward scheme, and propose an multi-attacker repeated colluding game. Then by static and dynamic analysis of this colluding attack game, we find the sub-game equilibriums which indicate the attackers' optimal attack strategies. Based on the analysis result, we establish a security policies for multihop wireless networks, to threaten and detect the malicious insider nodes which collude with each other to launch the selective forwarding attacks.

DOI： 10.1016/j.comcom.2012.07.006

記述言語：英語   掲載種別：研究論文（学術雑誌）  

Broadly, distributed problem solving is a subfield within multiagent systems, where the focus is to enable multiple agents to work together to solve a problem. These agents are often assumed to be cooperative, that is, they are part of a team or they are self-interested but incentives or disincentives have been applied such that the individual agent rewards are aligned with the team reward. We illustrate the motivations for distributed problem solving with an example. Imagine a decentralized channel-allocation problem in a wireless local area network (WLAN), where each access point (agent) in the WLAN needs to allocate itself a channel to broadcast such that no two access points with overlapping broadcast regions (neighboring agents) are allocated the same channel to avoid interference. Figure 1 shows example mobile WLAN access points, where each access point is a Create robot fitted with a wireless CenGen radio card. Figure 2a shows an illustration of such a problem with three access points in a WLAN, where each oval ring represents the broadcast region of an access point.

記述言語：日本語  

多目的制約最適化問題：ユーザとの対話型解法の提案

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

We generalize a pseudo-tree based solver to employ boundaries of multi-objective DCOPs. Multi-objective problems have been addressed in the research area of DCOPs recently. For the case of multiple objectives, the objective values are defined as the result of separate evaluation schemes. Applying multi-objectives to pseudo-tree based search is also important to generalize several traditional solvers. Here, we introduce boundaries for the vector of objective values in a solver based on pseudo-trees. Both the bottom-up computation of the partial dynamic-programming and the top-down computation of the tree-search employ the bounded vectors of the objective values. Several operations including aggregation, decomposition and comparison of objective values are extended for the bounded vectors.

DOI： 10.1007/978-3-642-32729-2_10

記述言語：日本語   掲載種別：研究論文（学術雑誌）  

記述言語：英語   掲載種別：研究論文（学術雑誌）  

A Distributed Constraint Satisfaction Problem (DisCSP) is a constraint satisfaction problem in which variables and constraints are distributed among multiple agents. Various algorithms for solving DisCSPs have been developed, which are intended for general purposes, i.e., they can be applied to any network structure. However, if a network has some particular structure, e.g., the network structure is scale-free, we can expect that some specialized algorithms/heuristics, which are tuned for the network structure, can outperform general purpose algorithms/heuristics. In this paper, as an initial step toward developing specialized algorithms for particular network structures, we examine variable-ordering heuristics in scale-free networks. We use the classic asynchronous backtracking algorithm (ABT) as a baseline algorithm and examine the effect of variable-ordering heuristics. First, we show that the choice of variable-ordering heuristics is more influential in scale-free networks than in random networks. Furthermore, we develop a novel variable-ordering heuristic that is specialized to scale-free networks. In the evaluations, we show that our new variable-ordering heuristic is more effective than a standard degree-based variable-ordering heuristic. Our proposed heuristic reduces the required cycles by 30% at the critical point where the required cycles are maximum.

DOI： 10.3233/MGS-2012-0189

記述言語：英語   掲載種別：研究論文（学術雑誌）  

Effect of DisCSP Variable-Ordering Heuristics in Scale-free Networks

DOI： 10.3233/MGS-2012-0189

記述言語：日本語   掲載種別：研究論文（学術雑誌）  

記述言語：日本語  

Introduction of Game Theory for Computer Scientists

DOI： 10.11309/jssst.29.2_65

記述言語：日本語   掲載種別：研究論文（学術雑誌）  

記述言語：日本語   掲載種別：研究論文（学術雑誌）  

記述言語：日本語   掲載種別：研究論文（学術雑誌）  

擬似木に基づく分散制約最適化問題の精度保証付き非厳密解法の提案

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

We develop a real-time algorithm based on a Monte-Carlo game tree search for solving a quantified constraint satisfaction problem (QCSP), which is a CSP where some variables are universally quantified. A universally quantified variable represents a choice of nature or an adversary. The goal of a QCSP is to make a robust plan against an adversary. However, obtaining a complete plan off-line is intractable when the size of the problem becomes large. Thus, we need to develop a real-time algorithm that sequentially selects a promising value at each deadline. Such a problem has been considered in the field of game tree search. In a standard game tree search algorithm, developing a good static evaluation function is crucial. However, developing a good static evaluation function for a QCSP is very difficult since it must estimate the possibility that a partially assigned QCSP is solvable. Thus, we apply a Monte-Carlo game tree search technique called UCT. However, the simple application of the UCT algorithm does not work since the player and the adversary are asymmetric, i.e., finding a game sequence where the player wins is very rare. We overcome this difficulty by introducing constraint propagation techniques. We experimentally compare the winning probability of our UCT-based algorithm and the state-of-the-art alpha-beta search algorithm. Our results show that our algorithm outperforms the state-of-the-art algorithm in large-scale problems.

DOI： 10.5591/978-1-57735-516-8/IJCAI11-116

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

Envy-freeness is a well-known fairness concept for analyzing mechanisms. Its traditional definition requires that no individual envies another individual. However, an individual (or a group of agents) may envy another group, even if she (or they) does not envy another individual. In mechanisms with monetary transfer, such as combinatorial auctions, considering such fairness requirements, which are refinements of traditional envy-freeness, is meaningful and brings up a new interesting research direction in mechanism design. In this paper, we introduce two new concepts of fairness called envy-freeness of an individual toward a group, and envy-freeness of a group toward a group . They are natural extensions of traditional envy-freeness. We discuss combinatorial auction mechanisms that satisfy these concepts. First, we characterize such mechanisms by focusing on their allocation rules. Then we clarify the connections between these concepts and three other properties: the core, strategy-proofness, and false-name-proofness.

DOI： 10.5591/978-1-57735-516-8/IJCAI11-073

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

Forming effective coalitions is a major research challenge in AI and multi-agent systems (MAS). Thus, coalitional games, including Coalition Structure Generation (CSG), have been attracting considerable attention from the AI research community. Traditionally, the input of a coalitional game is a black-box function called a characteristic function. A range of previous studies have found that many problems in coalitional games tend to be computationally intractable when the input is a black-box function. Recently, several concise representation schemes for a characteristic function have been proposed. Although these schemes are effective for reducing the representation size, most problems remain computationally intractable. In this paper, we develop a new concise representation scheme based on the idea of agent types. Intuitively, a type represents a set of agents, which are recognized as having the same contribution. This representation can be exponentially more concise than existing concise representation schemes. Furthermore, this idea can be used in conjunction with existing schemes to further reduce the representation size. Moreover, we show that most of the problems in coalitional games, including CSG, can be solved in polynomial time in the number of agents, assuming the number of possible types is fixed.

DOI： 10.5591/978-1-57735-516-8/IJCAI11-074

記述言語：日本語   掲載種別：研究論文（学術雑誌）  

記述言語：日本語   掲載種別：研究論文（学術雑誌）  

分散制約充足問題：特定の制約網に特化した変数順序付けヒューリスティックの提案

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

Coalitional games, including Coalition Structure Generation (CSG), have been attracting considerable attention from the AI research community. Traditionally, the input of a coalitional game is a black-box function called a characteristic function. Previous studies have found that many problems in coalitional games tend to be computationally intractable in this black-box function representation. Recently, several concise representation schemes for a characteristic function have been proposed. Among them, a synergy coalition group (SCG) has several good characteristics, but its representation size tends to be large compared to other representation schemes. We propose a new concise representation scheme for a characteristic function based on a Zero-suppressed Binary Decision Diagram (ZDD) and a SCG. We show our scheme (i) is fully expressive, (ii) can be exponentially more concise than the SCG representation, (iii) can solve core-related problems in polynomial time in the number of nodes, and (iv) can solve a CSG problem reasonably well by utilizing a MIP formulation. A Binary Decision Diagram (BDD) has been used as unified infrastructure for representing/manipulating discrete structures in such various domains in AI as data mining and knowledge discovery. Adapting this common infrastructure brings up the opportunity of utilizing abundant BDD resources and cross-fertilization with these fields.

DOI： 10.1007/978-3-642-25044-6_4

記述言語：日本語   掲載種別：研究論文（学術雑誌）  

記述言語：日本語   掲載種別：研究論文（学術雑誌）  

記述言語：日本語   掲載種別：研究論文（学術雑誌）  

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

A Distributed Constraint Optimization Problem (DCOP) is a fundamental problem that can formalize various applications related to multi-agent cooperation. Since it is NP-hard, considering faster incomplete algorithms is necessary for large-scale applications. Most incomplete algorithms generally do not provide any guarantees on the quality of solutions. Some notable exceptions are DALO, the bounded max-sum algorithm, and ADPOP. In this paper, we develop a new solution criterion called p-optimality and an incomplete algorithm for obtaining a p-optimal solution. The characteristics of this algorithm are as follows: (i) it can provide the upper bounds of the absolute/relative errors of the solution, which can be obtained a priori/a posteriori, respectively, (ii) it is based on a pseudo-tree, which is a widely used graph structure in complete DCOP algorithms, (iii) it is a one-shot type algorithm, which runs in polynomial-time in the number of agents n assuming p is fixed, and (iv) it has adjustable parameter p, so that agents can trade-off better solution quality against computational overhead. The evaluation results illustrate that this algorithm can obtain better quality solutions and bounds compared to existing bounded incomplete algorithms, while the run time of this algorithm is shorter.

DOI： 10.1007/978-3-642-23786-7_50

記述言語：英語   掲載種別：研究論文（その他学術会議資料等）  

Reducing the Search Space of Resource Constrained DCOPs

DOI： 10.1007/978-3-642-23786-7_44

記述言語：英語   掲載種別：研究論文（その他学術会議資料等）  

Pseudo-tree-based Incomplete Algorithm for Distributed Constraint Optimization with Quality Bounds

DOI： 10.1007/978-3-642-23786-7_50

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

We use the Constraint Satisfaction Problem (CSP) framework to model and solve the problem of designing substitution functions for substitution- permutation (SP) networks as proposed by Shannon for the architecture of ciphers. Many ciphers are designed using the SP pattern, and differ mainly by two parametrized functions: substitution and permutation. The most difficult of the two is the substitution function, which has to be nonlinear (a requirement that was difficult to define and quantify). Over time, researchers such as Nyberg, Pieprzyk and Matsui have proposed various metrics of nonlinearity that make the function robust to modern attacks. Before us, people have attempted various ways to design functions that respect these metrics. In the past people hand-picked substitution tables (S-boxes) by trying various values. Recently they use difficult to analyze constructs (such as Bent functions, spectral inversion, inverses in Galois fields) whose outputs are tested for nonlinearity. While efficient, such techniques are neither exhaustive (optimal), nor did they manage to generate better substitutions than the ones hand-picked in the past. We show that Matsui's nonlinearity requirement can be naturally modelled using CSPs. Based on a combination of existing CSP techniques and some new filtering operators that we designed specially for the new types of constraints, we manage to obtain better S-boxes than any previously published ones. The simplicity of the CSP framework and availability of general CSP solvers like ours, makes it easy for more people to design their own ciphers with easy to understand security parameters. Here we report on this new application of CSPs.

DOI： 10.1007/978-3-642-23786-7_7

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

Distributed constraint optimization problems (DCOPs) have been studied as a basic framework of multi-agent cooperation. The Resource Constrained DCOP (RCDCOP) is a special DCOP framework that contains n-ary hard constraints for shared resources. In RCDCOPs, for a value of a variable, a certain amount of the resource is consumed. Upper limits on the total use of resources are defined by n-ary resource constraints. To solve RCDCOPs, exact algorithms based on pseudo-trees employ virtual variables whose values represent use of the resources. Although, virtual variables allow for solving the problems without increasing the depth of the pseudo-tree, they exponentially increase the size of search spaces. Here, we reduce the search space of RCDCOPs solved by a dynamic programming method. Several boundaries of resource use are exploitable to reduce the size of the tables. To employ the boundaries, additional pre-processing and further filtering are applied. As a result, infeasible solutions are removed from the tables. Moreover, multiple elements of the tables are aggregated into fewer elements. By these modifications, redundancy of the search space is removed. One of our techniques reduces the size of the messages by an order of magnitude.

DOI： 10.1007/978-3-642-23786-7_44

記述言語：英語   掲載種別：研究論文（学術雑誌）  

A significant body of work exists on effectively allowing multiple agents to coordinate to achieve a shared goal. In particular, a growing body of work in the Distributed Constraint Optimization (DCOP) framework enables such coordination with different amounts of teamwork. Such algorithms can implicitly or explicitly trade-off improved solution quality with increased communication and computation requirements. However, the DCOP framework is limited to planning problems; DCOP agents must have complete and accurate knowledge about the reward function at plan time. We extend the DCOP framework, defining the Distributed Coordination of Exploration and Exploitation (DCEE) problem class to address real-world problems, such as ad-hoc wireless network optimization, via multiple novel algorithms. DCEE algorithms differ from DCOP algorithms in that they (1) are limited to a finite number of actions in a single trial, (2) attempt to maximize the on-line, rather than final, reward, (3) are unable to exhaustively explore all possible actions, and (4) may have knowledge about the distribution of rewards in the environment, but not the rewards themselves. Thus, a DCEE problem is not a type of planning problem, as DCEE algorithms must carefully balance and coordinate multiple agents' exploration and exploitation. Two classes of algorithms are introduced: static estimation algorithms perform simple calculations that allow agents to either stay or explore, and balanced exploration algorithms use knowledge about the distribution of the rewards and the time remaining in an experiment to decide whether to stay, explore, or (in some algorithms) backtrack to a previous location. These two classes of DCEE algorithms are compared in simulation and on physical robots in a complex mobile ad-hoc wireless network setting. Contrary to our expectations, we found that increasing teamwork in DCEE algorithms may lower team performance. In contrast, agents running DCOP algorithms improve their reward as teamwork increases. We term this previously unknown phenomenon the team uncertainty penalty, analyze it in both simulation and on robots, and present techniques to ameliorate the penalty.

DOI： 10.1142/S0219525911003104

記述言語：英語   掲載種別：研究論文（学術雑誌）  

A significant body of work exists on effectively allowing multiple agents to coordinate to achieve a shared goal. In particular, a growing body of work in the Distributed Constraint Optimization (DCOP) framework enables such coordination with different amounts of teamwork. Such algorithms can implicitly or explicitly trade-off improved solution quality with increased communication and computation requirements. However, the DCOP framework is limited to planning problems
DCOP agents must have complete and accurate knowledge about the reward function at plan time. We extend the DCOP framework, defining the Distributed Coordination of Exploration and Exploitation (DCEE) problem class to address real-world problems, such as ad-hoc wireless network optimization, via multiple novel algorithms. DCEE algorithms differ from DCOP algorithms in that they (1) are limited to a finite number of actions in a single trial, (2) attempt to maximize the on-line, rather than final, reward, (3) are unable to exhaustively explore all possible actions, and (4) may have knowledge about the distribution of rewards in the environment, but not the rewards themselves. Thus, a DCEE problem is not a type of planning problem, as DCEE algorithms must carefully balance and coordinate multiple agents' exploration and exploitation. Two classes of algorithms are introduced: static estimation algorithms perform simple calculations that allow agents to either stay or explore, and balanced exploration algorithms use knowledge about the distribution of the rewards and the time remaining in an experiment to decide whether to stay, explore, or (in some algorithms) backtrack to a previous location. These two classes of DCEE algorithms are compared in simulation and on physical robots in a complex mobile ad-hoc wireless network setting. Contrary to our expectations, we found that increasing teamwork in DCEE algorithms may lower team performance. In contrast, agents running DCOP algorithms improve their reward as teamwork increases. We term this previously unknown phenomenon the team uncertainty penalty, analyze it in both simulation and on robots, and present techniques to ameliorate the penalty. © 2011 World Scientific Publishing Company.

DOI： 10.1142/S0219525911003104

記述言語：英語   掲載種別：研究論文（学術雑誌）  

This paper presents a new way of formalizing the Coalition Structure Generation problem (CSG), so that we can apply constraint optimization techniques to it. Forming effective coalitions is a major research challenge in AI and multi-agent systems. CSG involves partitioning a set of agents into coalitions so that social surplus is maximized. Traditionally, the input of the CSG problem is a black-box function called a characteristic function, which takes a coalition as an input and returns the value of the coalition. As a result, applying constraint optimization techniques to this problem has been infeasible. However, characteristic functions that appear in practice often can be represented concisely by a set of rules, rather than a single black-box function. Then, we can solve the CSG problem more efficiently by applying constraint optimization techniques to the compact representation directly. We present new formalizations of the CSG problem by utilizing recently developed compact representation schemes for characteristic functions. We first characterize the complexity of the CSG under these representation schemes. In this context, the complexity is driven more by the number of rules rather than by the number of agents. Furthermore, as an initial step towards developing efficient constraint optimization algorithms for solving the CSG problem, we develop mixed integer programming formulations and show that an off-the-shelf optimization package can perform reasonably well, i.e., it can solve instances with a few hundred agents, while the state-of-the-art algorithm (which does not make use of compact representations) can solve instances with up to 27 agents.

DOI： 10.1527/tjsai.26.451

記述言語：英語  

記述言語：日本語   掲載種別：研究論文（学術雑誌）  

施設配置問題は，施設の配置場所を適切に決定する問題であり，経済学を始めとして様々な分野で広く研究が行われてきた．特に戦略的操作不可能（各参加者にとって正直が最良の策）な配置メカニズムの設計が重要な課題として認知されている．一方，インターネットを介してこのような施設配置を実現する場合には，一人の参加者が複数の参加者であるかのように振る舞う架空名義操作と呼ばれる不正行為が可能となる．本研究では，施設配置メカニズムの架空名義操作不可能性（参加者が架空名義を行っても得をしない性質）を定式化し，この性質を満たす配置メカニズムの特徴付けを与える．

記述言語：英語  

記述言語：日本語   掲載種別：研究論文（学術雑誌）  

記述言語：日本語   掲載種別：研究論文（学術雑誌）  

記述言語：日本語   掲載種別：研究論文（学術雑誌）  

記述言語：日本語   掲載種別：研究論文（学術雑誌）  

記述言語：日本語   掲載種別：研究論文（学術雑誌）  

記述言語：日本語   掲載種別：研究論文（学術雑誌）  

記述言語：英語   掲載種別：研究論文（その他学術会議資料等）  

Effect of DisCSP Variable-Ordering Heuristics in Scale-free Networks

DOI： 10.1007/978-3-642-25920-3_12

記述言語：日本語  

記述言語：日本語  

記述言語：日本語   掲載種別：研究論文（学術雑誌）  

記述言語：英語   掲載種別：研究論文（その他学術会議資料等）  

A Quantified Distributed Constraint Optimization Problems

記述言語：英語   掲載種別：研究論文（学術雑誌）  

記述言語：英語   掲載種別：研究論文（学術雑誌）  

記述言語：英語   掲載種別：研究論文（学術雑誌）  

記述言語：日本語   掲載種別：研究論文（学術雑誌）  

Applying Soft Arc Consistency to Distributed Constraint Optimization Problems

記述言語：英語   掲載種別：研究論文（学術雑誌）  

This article presents an asynchronous algorithm for solving distributed constraint optimization problems (DCOPs). The proposed technique unifies asynchronous backtracking (ABT) and asynchronous distributed optimization (ADOPT) where valued nogoods enable more flexible reasoning and more opportunities for communication, leading to an important speed-up. While feedback can be sent in ADOPT by COST messages only to one predefined predecessor, our extension allows for sending such information to any relevant agent. The concept of valued nogood is an extension by Dago and Verfaille of the concept of classic nogood that associates the list of conflicting assignments with a cost and, optionally, with a set of references to culprit constraints. DCOPs have been shown to have very elegant distributed solutions, such as ADOPT, distributed asynchronous overlay (DisAO), or DPOP. These algorithms are typically tuned to minimize the longest causal chain of messages as a measure of how the algorithms will scale for systems with remote agents (with large latency in communication). ADOPT has the property of maintaining the initial distribution of the problem. To be efficient, ADOPT needs a preprocessing step consisting of computing a Depth-First Search (DFS) tree on the constraint graph. Valued nogoods allow for automatically detecting and exploiting the best DFS tree compatible with the current ordering. To exploit such DFS trees it is now sufficient to ensure that they exist. Also, the inference rules available for valued nogoods help to exploit schemes of communication where more feedback is sent to higher priority agents. Together they result in an order of magnitude improvement. © 2008 Springer Science+Business Media, LLC.

DOI： 10.1007/s10458-008-9069-2

記述言語：日本語   掲載種別：研究論文（学術雑誌）  

A Resource Constrained Distributed Constraint Optimization Method using Resource Constraint Free Psudo-tree

記述言語：英語   掲載種別：研究論文（学術雑誌）  

記述言語：英語   掲載種別：研究論文（その他学術会議資料等）  

Directed Soft Arc Consistency in Pseudo-trees

記述言語：日本語   掲載種別：研究論文（学術雑誌）  

記述言語：日本語   掲載種別：研究論文（学術雑誌）  

記述言語：日本語   掲載種別：研究論文（学術雑誌）  

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

記述言語：英語   掲載種別：研究論文（その他学術会議資料等）  

Resource constrained distributed constraint optimization with virtual variables

記述言語：英語   掲載種別：研究論文（その他学術会議資料等）  

Resource constrained distributed constraint optimization using resource constraint free pseudo-tree

記述言語：日本語   掲載種別：研究論文（学術雑誌）  

記述言語：英語   掲載種別：研究論文（学術雑誌）  

記述言語：英語   掲載種別：研究論文（学術雑誌）  

記述言語：英語   掲載種別：研究論文（学術雑誌）  

A great deal of research is actively being conducted concerning Internet auctions. A method has previously been proposed for obtaining the optimal bidding strategy by using dynamic programming in a sequential auction, which is one form of auction. However, the conventional method assumes that the utility of an agent who is bidding takes a general additive form, and the remaining endowment of money during bidding has to be represented in each of the various states that are taken into consideration in the dynamic programming procedure. As a result, when the initial endowment of money m is large, the number of states that have to be taken into consideration becomes extremely large. In this paper, by assuming that the utility of an agent takes a quasi-linear form, which is a type of additive form, the authors show that the optimal strategy using dynamic programming is obtained since the number of states is reduced to 1/m times the number obtained when the utility takes a general additive form. However, when the agent utility is assumed to take a quasi-linear form, it is impossible to represent budget constraints. Therefore, in this paper, the authors propose a method of quickly obtaining a quasi-optimal strategy when budget constraints exist by modifying the strategy that is obtained when quasi-linear utility is assumed and show the effectiveness of the proposed method through experimental evaluations. © 2007 Wiley Periodicals, Inc.

DOI： 10.1002/scj.10465

記述言語：英語   掲載種別：研究論文（学術雑誌）  

記述言語：英語   掲載種別：研究論文（学術雑誌）  

This paper presents a new false-name-proof multiunit auction protocol called the Greedy ALlocation (GAL) protocol. Internet auctions have become an integral part of Electronic Commerce and a promising field for applying agent and Artificial Intelligence technologies. Although the Internet provides an excellent infrastructure for executing auctions, the possibility of a new type of cheating called false-name bids has been pointed out. A false-name bid is a bid submitted under a fictitious name. A protocol called the Iterative Reducing (IR) protocol has been developed for multi-unit auctions and has proven to be false-name-proof, that is, using false-name bids is useless. For Internet auction protocols, being false-name-proof is important since identifying each participant on the Internet is virtually impossible. One shortcoming of the IR protocol is that it requires the auctioneer to carefully predetermine the reservation price for one unit. Our newly developed GAL protocol is easier to use than the IR, since the auctioneer does not need to set the reservation price nor any other parameters. The evaluation results show that the GAL protocol can obtain a social surplus that is very close to Pareto efficient. Furthermore, the obtained social surplus and seller's revenue are much better than those of the IR protocol even if the reservation price is set optimally. © 2006 Wiley Periodicals, Inc.

DOI： 10.1002/scj.10664

記述言語：日本語   掲載種別：研究論文（学術雑誌）  

掲載種別：研究論文（学術雑誌）  

記述言語：日本語   掲載種別：研究論文（学術雑誌）  

記述言語：英語   掲載種別：研究論文（学術雑誌）  

Implementing A Strategyproof Greedy-Allocation Combinatorial Auction and Extending to Ascending Auction

DOI： 10.1002/scj.20748

記述言語：英語   掲載種別：研究論文（学術雑誌）  

Auctions have recently commanded a great deal of attention in the field of multiagent systems. Correctly judging the quality of auctioned goods is often difficult for amateurs, in particular, on the Internet auctions. We have formalized such a situation so that Nature selects the quality of the auctioned good. Experts can observe Nature's selection (i.e., the quality of the good) correctly, while amateurs, including the auctioneer, cannot. In other words, the information on Nature's selection is asymmetric between experts and amateurs. In this situation, it is difficult to attain an efficient allocation, since experts have a clear advantage over amateurs, and they would not reveal their valuable information without some reward. We have succeeded in developing a single-unit auction protocol in which truth-telling is a dominant strategy for each expert. In this paper, we focus on a combinatorial auction protocol under asymmetric information on Nature's selection. Experts may have an interest in, and expert knowledge on, Nature's selection for several goods, that is, experts are versatile. However, the case of versatile experts is very complicated. Thus, as a first step, we assume experts to have an interest in, and expert knowledge on, a single good. That is, experts are single-skilled. Under these assumptions, we develop an auction protocol in which the dominant strategy for experts is truth-telling. Also, for amateurs, truth-telling is the best response when experts tell the truth. By making experts to elicit their information on the quality of the goods, the protocol can achieve a socially desirable, (i.e., Pareto efficient) allocation, if certain assumptions are satisfied. © 2005 Wiley Periodicals, Inc.

DOI： 10.1002/scj.20390

記述言語：英語  

DOI： 10.1007/s10458-005-0983-2

記述言語：英語   掲載種別：研究論文（学術雑誌）  

The auction is a fast-developing, important area of electronic commerce in which software agent techniques are expected to find promising applications. By the use of the Internet, large-scale auctions can be realized at low cost. On the other hand, there arises the problem of illegal conduct of a new type, utilizing the name-concealment properties of the network. This paper proposes a new double auction protocol guaranteeing robustness to false-name bids, which constitute one type of such illegal conduct. The double auction is an auction in which multiple buyers/sellers exist and engage in bidding. It is widely used in dealing with foreign currency, credit, stocks, and other goods. For cases in which there is no false-name bid, the double auction protocol (PMD protocol) has been proposed, which is motivation-compatible in the dominant strategy. Considering the possible case in which the seller pretends to be a buyer and bids under another name, it is possible in the PMD protocol for the bidder to increase his benefit by a false-name bid. Thus, motivation compatibility is not guaranteed. This paper proposes the threshold price double auction protocol (TPD), which is motivation-compatible in the dominant strategy even if false-name bids are possible. The TPD protocol has the feature that the number of deals and the prices of deals are controlled by using the threshold price of the good. It is shown by simulation experiments that the TPD protocol realizes a social surplus which is very close to the Pareto-efficient assignment by appropriately setting the threshold price. © 2005 Wiley Periodicals, Inc.

DOI： 10.1002/ecjb.20180

記述言語：英語   掲載種別：研究論文（学術雑誌）  

In this paper, we develop a new double auction protocol called the Threshold Price Double auction (TPD) protocol, which is dominant-strategy incentive compatible even if participants can submit several bids under fictitious names (false-name bids). In Internet auctions, false-name bids are very difficult to detect since identifying each participant on the Internet is virtually impossible. The characteristics of the TPD protocol are that the number of trades and prices of exchange are controlled by the threshold price. Simulation results show that this protocol can achieve a social surplus that is very close to being Pareto efficient. © 2003 Elsevier B.V. All rights reserved.

DOI： 10.1016/j.dss.2003.10.009

記述言語：英語   掲載種別：研究論文（学術雑誌）  

記述言語：英語   掲載種別：研究論文（その他学術会議資料等）  

This paper develops a new ascending-price multi-unit auction protocol that has the following characteristics: (i) it has an open format, and (ii) sincere bidding is an equilibrium strategy even if the marginal values of each agent can increase and agents can submit false-name bids. False-name bids are bids submitted under fictitious names such as multiple e-mail addresses, which can be done easily on the Internet. This is the first protocol that has both of these characteristics. Our simulation results indicate that the developed protocol obtains a social surplus close to Pareto efficient. © 2004 Elsevier B.V. All rights reserved.

DOI： 10.1016/j.dss.2004.08.005

記述言語：英語  

DOI： 10.1093/ietfec/E88-A.1.255

記述言語：英語   掲載種別：研究論文（学術雑誌）  

We present a new series of distributed constraint satisfaction algorithms, the distributed breakout algorithms, which is inspired by local search algorithms for solving the constraint satisfaction problem (CSP). The basic idea of these algorithms is for agents to repeatedly improve their tentative and flawed sets of assignments for variables simultaneously while communicating such tentative sets with each other until finding a solution to an instance of the distributed constraint satisfaction problem (DisCSP). We introduce four implementations of the distributed breakout algorithms: SINGLE-DB, MULTI-DB, MULTI-DB+, and MULTI-DB++. SiNGLE-DB is a distributed breakout algorithm for solving the DisCSP, where each agent has a single local variable and its related constraints. MULTI-DB, on the other hand, is another distributed breakout algorithm for solving the distributed SAT (DisSAT) problem, where each agent has multiple local variables and their related clauses. MULTI-DB+ and MULTI-DB++ are stochastic variations of MULTI-DB. In MULTI-DB+, we introduce a technique called random break into MULTI-DB
in MULTI-DB++, we introduce a technique called random walk into MULTI-DB+. We conducted experiments to compare these algorithms with the asynchronous type of distributed constraint satisfaction algorithm. Through these experiments, we found that SINGLE-DB, MULTI-DB, and MULTI-DB+ scale up better than the asynchronous type of distributed constraint satisfaction algorithms, but they sometimes show very poor performance. On the other hand, we also found that MULTI-DB++, which uses random walk, provides a clear performance improvement. © 2004 Elsevier B.V. All rights reserved.

DOI： 10.1016/j.artint.2004.08.004

記述言語：英語   掲載種別：研究論文（学術雑誌）  

The Distributed Constraint Optimization Problem (DCOP) is a promising approach for modeling distributed reasoning tasks that arise in multiagent systems. Unfortunately, existing methods for DCOP are not able to provide theoretical guarantees on global solution quality while allowing agents to operate asynchronously. We show how this failure can be remedied by allowing agents to make local decisions based on conservative cost estimates rather than relying on global certainty as previous approaches have done. This novel approach results in a polynomial-space algorithm for DCOP named Adopt that is guaranteed to find the globally optimal solution while allowing agents to execute asynchronously and in parallel. Detailed experimental results show that on benchmark problems Adopt obtains speedups of several orders of magnitude over other approaches. Adopt can also perform bounded-error approximation - it has the ability to quickly find approximate solutions and, unlike heuristic search methods, still maintain a theoretical guarantee on solution quality. © 2004 Elsevier B.V. All rights reserved.

DOI： 10.1016/j.artint.2004.09.003

記述言語：英語  

DOI： 10.1016/j.artint.2004.08.004

記述言語：英語  

DOI： 10.1016/j.artint.2004.10.007

記述言語：英語  

記述言語：英語  

記述言語：英語  

記述言語：英語   掲載種別：研究論文（学術雑誌）  

We describe three market-inspired approaches to propositional satisfiability. The first is based on a formulation of satisfiability as production on a supply chain, where producers of particular variable assignments must acquire licenses to fail to satisfy particular clauses. Experiments show that although this general supply-chain protocol can converge to market allocations corresponding to satisfiable truth assignments, it is impractically slow. We find that a simplified market structure and a variation on the pricing method can improve performance significantly. We compare the performance of the three market-based protocols with distributed breakout algorithm and GSAT on benchmark 3-SAT problems. We identify a tradeoff between performance and economic realism in the market protocols, and a tradeoff between performance and the degree of decentralization between the market protocols and distributed breakout. We also conduct informal and experimental analyses to gain insight into the operation of price-guided search. © 2002 Elsevier Science B.V. All rights reserved.

DOI： 10.1016/S0004-3702(02)00386-7

記述言語：英語   掲載種別：研究論文（学術雑誌）  

In this paper, we will propose a new solution method for SAT (Satisfiability Problems) using FPGA (Field-Programmable Gate Arrays) and logic synthesis system. This method is distinctive in that a logic circuit specialized to solve each problem instance is configured on FPGA. This approach has become possible due to the progress in reconfigurable computing technology in recent years and opens a new possibility in design principle of algorithms: SAT is a kind of constraint satisfaction problem and is a general framework which can represent many application problems. In this paper, we will propose various algorithms which are suitable for implementation on hardware. Among these algorithms, the one which has the highest performance has a performance equal to the Davis-Putman algorithm which introduced the heuristic with dynamic ordering of variables. From the evaluation results using simulation, we show that by the method proposed herein, the solution of a 3-SAT problem instance with 400 variables generated in a very hard random can be obtained in 1.6 minutes when the circuit is operated at a machine cycle of 10 MHz. Moreover, a very hard problem instance with 128 variables and 256 clauses was packaged on FPGAs and its operation was confirmed.

DOI： 10.1002/ecjb.10134

記述言語：日本語  

"Bundle Design in Robust Combinatorial Auction Protocol against False-name Bids'', Makoto Yokoo, Yuko Sakurai, and Shigeo Matsubara, Computer Software (Journal of Japanese Society for Software Science and Technology)

記述言語：日本語  

"Designing an Auction Protocol under Asymmetric Information on Nature's Selection'', Takayuki Ito, Makoto Yokoo, , and Shigeo Matsubara, Computer Software (Journal of Japanese Society for Software Science and Technology)

記述言語：日本語  

"An Average-case Budget-Non-Negative Double Auction Protocol'', Yuko Sakurai and Makoto Yokoo, Journal of Japanese Society for Artificial Intelligence

記述言語：英語  

記述言語：英語   掲載種別：研究論文（その他学術会議資料等）  

In open environments there is no central control over agent behaviors. On the contrary, agents in such systems can be assumed to be primarily driven by self interests. Under the assumption that agents remain in the system for significant time periods, or that the agent composition changes only slowly, we have previously presented a prescriptive strategy for promoting and sustaining cooperation among self-interested agents. The adaptive, probabilistic policy we have prescribed promotes reciprocative cooperation that improves both individual and group performance in the long run. In the short run, however, selfish agents could still exploit reciprocative agents. In this paper, we evaluate the hypothesis that the exploitative tendencies of selfish agents can be effectively curbed if reciprocative agents share their "opinions" of other agents. Since the true nature of agents is not known a priori and is learned from experience, believing others can also pose its own hazards. We provide a learned trust-based evaluation function that is shown to resist both individual and concerted deception on the part of selfish agents in a package delivery domain. © 2002 Elsevier Science B.V. All rights reserved.

DOI： 10.1016/S0004-3702(02)00289-8

記述言語：英語   掲載種別：研究論文（その他学術会議資料等）  

We propose a safe exchange mechanism involving indivisible goods and divisible goods. A typical situation is an exchange involving goods and money in a person-to-person trade in an Internet auction. Although the Internet and agent technologies have facilitated world-wide trade, we sometimes encounter risky situations, such as fraud, in the process of exchanges involving goods and money. This problem is becoming more serious with the growing popularity of person-to-person trade. One of the reasons why fraud is becoming widespread is that obtaining a new identifier in a network is cheap. This makes it almost impossible to exclude malicious agents from trade. One solution is to impose an entry fee. However, if the entry fee is too high, it will discourage newcomers from starting deals. To resolve the conflict between safety and convenience, we developed three exchange mechanisms that can guarantee against defection from a contract. Two of them reduce the entry fee by integrating multiple deals and controlling the flow of goods and money. The other reduces the entry fee by incorporating a third-party agent into the exchange process. We examine the lower bound of the entry fee for both of these mechanisms and describe a calculation method by which this value can be obtained in linear time. Our results show that the described mechanism can effectively reduce the lower bound of the entry fee. © 2002 Elsevier Science B.V. All rights reserved.

DOI： 10.1016/S0004-3702(02)00276-X

記述言語：英語  

記述言語：日本語  

"Robust Multi-unit Auction Protocol against False-name Bids'', Makoto Yokoo, Yuko Sakurai, and Shigeo Matsubara, Journal of Japanese Society for Artificial Intelligence

記述言語：日本語  

"Robust Combinatorial Auction Protocol against False-name Bids'', Makoto Yokoo, Yuko Sakurai, and Shigeo Matsubara, Transactions of Information Society of Japan

記述言語：日本語  

"A Dynamic Programming Model for Determining Bidding Strategies in Sequential Auctions: Quasi-linear Utility and Budget Constraints'', Hiromitsu Hattori, Makoto Yokoo, Yuko Sakurai, and Toramatsu Shintani, Transactions of the Institute of Electronics, Information and Communication Engineers

記述言語：英語   掲載種別：研究論文（学術雑誌）  

This paper presents a new combinatorial auction protocol that is robust against false-name bids. Internet auctions have become an integral part of Electronic Commerce (EC) and a promising field for applying agent and Artificial Intelligence technologies. Although the Internet provides an excellent infrastructure for combinatorial auctions, we must consider the possibility of a new type of cheating, i.e., an agent tries to profit from submitting several bids under fictitious names (false-name bids). If there exists no false-name bid, the Generalized Vickrey Auction protocol (GVA) satisfies individual rationality, Pareto efficiency, and incentive compatibility. On the other hand, when false-name bids are possible, it is theoretically impossible for a combinatorial auction protocol to simultaneously satisfy these three properties. Our newly developed Leveled Division Set (LDS) protocol, which is a modification of the GVA, utilizes reservation prices of auctioned goods for making decisions on whether to sell goods in a bundle or separately. The LDS protocol satisfies individual rationality and incentive compatibility even if agents can submit false-name bids, although it is not guaranteed to achieve a Pareto efficient social surplus. Simulation results show that the LDS protocol can achieve a better social surplus than that for a protocol that always sells goods in one bundle. © 2001 Elsevier Science B.V. All rights reserved.

DOI： 10.1016/S0004-3702(01)00077-7

記述言語：英語   掲載種別：研究論文（学術雑誌）  

This paper reports on an innovative approach for solving satisfiability problems for propositional formulas in conjunctive normal form (SAT) by creating a logic circuit that is specialized to solve each problem instance on field programmable gate arrays (FPGAs). This approach has become feasible due to recent advances in reconfigurable computing and has opened up an exciting new research field in algorithm design. SAT is an important subclass of constraint satisfaction problems, which can formalize a wide range of application problems. We have developed a series of algorithms that are suitable for logic circuit implementation, including an algorithm whose performance is equivalent to the Davis-Putnam procedure with powerful dynamic variable ordering. Simulation results show that this method can solve a hard random 3-SAT problem with 400 variables within 1.6 min at a clock rate of 10 MHz. Faster speeds can be obtained by increasing the clock rate. Furthermore, we have actually implemented a 128-variable 256-clause problem instance on FPGAs.

DOI： 10.1109/92.920826

記述言語：英語  

記述言語：英語  

記述言語：日本語  

"Solving Satisfiability Problems using Reconfigurable Computing'', Takayuki Suyama, Makoto Yokoo, Hiroshi Sawada, and Akira Nagoya, Transactions of the Institute of Electronics, Information and Communication Engineers

記述言語：日本語  

"An Efficient Approximate Algorithm for Winner Determination in Combinatorial Auctions'', Yuko Sakurai, Makoto Yokoo, and Kouji Kamei, Journal of Japanese Society for Artificial Intelligence

記述言語：日本語  

"Robust Double Auction Protocol against False-name Bids'', Makoto Yokoo, Yuko Sakurai, and Shigeo Matsubara, Transactions of the Institute of Electronics, Information and Communication Engineers

記述言語：日本語   掲載種別：研究論文（その他学術会議資料等）  

The Effect of False-name Declarations in Mechanism Design : Towards Collective Decision Making on the Internet.

DOI： 10.11309/jssst.17.445

記述言語：日本語  

A Limitation of the Generalized Vickrey Auction in Electonic Commerce : Robustness against Falsename Bids

DOI： 10.11309/jssst.17.109

記述言語：日本語  

"The Effect of False-name Declarations in Mechanism Design: Towards Collective Decision Making on the Internet'', Makoto Yokoo, Yuko Sakurai, and Shigeo Matsubara, Computer Software (Journal of Japanese Society for Software Science and Technology)

記述言語：日本語  

"A Limitation of the Generalized Vickrey Auction in Electronic Commerce: Robustness against False-name Bids'', Yuko Sakurai, Makoto Yokoo, and Shigeo Matsubara, Computer Software (Journal of Japanese Society for Software Science and Technology)

記述言語：日本語  

"The Effect of Nogood Learning in Distributed Constraint Satisfaction'', Katsutoshi Hirayama and Makoto Yokoo, Journal of Japanese Society for Artificial Intelligence

記述言語：日本語  

"Distributed Constraint Satisfaction Algorithms for Complex Local Problems'', Mkoto Yokoo and Katsutoshi Hirayama, Journal of Japanese Society for Artificial Intelligence

記述言語：英語  

記述言語：日本語  

"Frequency Assignment for Cellular Mobile Systems Using Constraint Satisfaction Techniques'', Makoto Yokoo and Katsutoshi Hirayama, Transactions of Information Society of Japan

記述言語：日本語  

"Defection-Free Exchange Mecahnisms for Information Good'', Shigeo Matsubara and Makoto Yokoo, Journal of Japanese Society for Artificial Intelligence

記述言語：英語  

記述言語：日本語  

"Multi-State Commitment Search'', Yasuhiko Kitamura, Makoto Yokoo, Tomohisa Miyaji, and Shoji Tatsumi, Journal of Japanese Society for Artificial Intelligence

記述言語：日本語  

"Analyzing Landscapes of CPSs'', Makoto Yokoo, Computer Software (Journal of Japanese Society for Software Science and Technology)

記述言語：日本語  

"Distributed Partial Constraint Satisfaction Problem'', Katsutoshi Hirayama and Makoto Yokoo, Journal of Japanese Society for Artificial Intelligence

記述言語：英語  

記述言語：日本語  

"Distributed Breakout Algorithm for Solving Distributed Constraint Satisfaction Problems'', Makoto Yokoo and Katsutoshi Hirayama, Transactions of Information Society of Japan

担当ページ：総ページ数：676   記述言語：英語  

Principles of Practice in Multi-Agent Systems: 12th International Conference, PRIMA 2009, Nagoya, Japan, December 14-16, 2009, Proceedings (Lecture Notes in Computer Science)

担当ページ：総ページ数：486, 担当ページ数：53-64   記述言語：英語  

New Frontiers in Artificial Intelligence, Joint JSAI 2005 Workshop Post-Proceedings (Lecture Notes in Computer Science)

担当ページ：総ページ数：147   記述言語：その他  

記述言語：日本語   著書種別：学術書

担当ページ：総ページ数：138   記述言語：その他  

担当ページ：Chapter "Robust Combinatorial Auction Protocol against False-name Bids"   記述言語：英語   著書種別：学術書

担当ページ：総ページ数：236   記述言語：英語  

Intelligent Agents: Specification, Modeling, and Applications, 4th Pacific Rim International Workshop on Multi-Agents, PRIMA 2001, Taipei, Taiwan, July 28-29, 2001, Proceedings (Lecture Notes in Computer Science)

記述言語：英語   著書種別：学術書

担当ページ：Chapter Title "Search Algorithms for Agents"   記述言語：英語   著書種別：学術書

開催年月日： 2022年2月

記述言語：日本語  

開催地：金沢勤労者プラザ(石川県金沢市), ハイブリッド開催  

開催年月日： 2022年2月

記述言語：日本語  

開催地：金沢勤労者プラザ(石川県金沢市), ハイブリッド開催  

開催年月日： 2021年9月

記述言語：日本語  

開催地：オンライン  

開催年月日： 2021年9月

記述言語：日本語  

開催地：オンライン  

開催年月日： 2021年9月

記述言語：日本語  

開催地：オンライン  

開催年月日： 2021年8月

記述言語：日本語  

開催地：オンライン  

開催年月日： 2021年8月

記述言語：英語  

開催地：Dagstuhl, Wadern (Online)   国名：ドイツ連邦共和国  

開催年月日： 2021年8月

記述言語：英語  

開催地：Dagstuhl, Wadern (Online)   国名：ドイツ連邦共和国  

開催年月日： 2021年7月

記述言語：英語  

開催地：Dagstuhl, Wadern (Online)   国名：ドイツ連邦共和国  

開催年月日： 2021年6月

開催地：City University of Hong Kong (Online)  

開催年月日： 2021年6月

記述言語：日本語  

開催地：オンライン  

開催年月日： 2021年6月

記述言語：日本語  

開催地：オンライン  

開催年月日： 2021年3月

記述言語：日本語  

開催地：オンライン   国名：日本国  

開催年月日： 2021年3月

記述言語：日本語  

開催地：オンライン   国名：日本国  

開催年月日： 2020年9月

記述言語：日本語  

開催地：オンライン   国名：日本国  

開催年月日： 2020年9月

記述言語：日本語  

開催地：オンライン   国名：日本国  

開催年月日： 2020年9月

記述言語：日本語  

開催地：オンライン   国名：日本国  

開催年月日： 2020年6月

記述言語：日本語  

開催地：オンライン   国名：日本国  

開催年月日： 2020年6月

記述言語：日本語   会議種別：口頭発表（一般）  

開催地：オンライン   国名：日本国  

開催年月日： 2020年6月

記述言語：日本語  

開催地：オンライン   国名：日本国