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

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

「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.

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

Publisher：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

Publisher：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

Language：English   Publishing type：Research paper (scientific journal)  

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

Publishing type：Research paper (scientific journal)   Publisher：Elsevier BV  

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

Language：English   Publisher：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

Language：English   Publishing type：Research paper (international conference proceedings)  

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

Language：English   Publishing type：Research paper (international conference proceedings)  

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

Language：Japanese   Publisher：The Japanese Society for Artificial Intelligence  

<p>In this presentation, we consider a facility location game on a one-dimensional line segment, i.e., a problem in which participating agents declare their positions on a one-dimensional line segment and a mechanism determines the placement of facilities based on these declarations. In particular, we focus on the ordered weighted average (OWA) mechanisms and discuss its non-obvious manipulability. An OWA mechanism is a mechanism that orders the agent's reported values in ascending order, applies weights according to that order, and returns the sum of the weights. In this presentation, we analyze how the non-obvious manipulability changes by changing the weights in an OWA.</p>

DOI： 10.11517/pjsai.jsai2024.0_2f6gs502

CiNii Research

Language：Japanese   Publisher：The Japanese Society for Artificial Intelligence  

<p>Integrally convex functions are a basic class of functions in discrete convex analysis, including M-convex functions and L-convex functions. Recently, the concept of L-extendable functions has been proposed for algorithm development for discrete optimization problems. A function h on an integer lattice is L-extendable if there exists an L-convex function g on a half-integer lattice such that the restriction of g on the integer lattice coincides with that of h. L-extendability is known to be useful in developing approximation algorithms and fast exact algorithms for various discrete optimization problems that are NP-hard. The purpose of this paper is to investigate L-extendability of integrally convex functions. In particular, we focus on L-extensibility by linear interpolation and discuss a characterization of integrally convex functions for which such extensions are possible.</p>

DOI： 10.11517/pjsai.jsai2024.0_3xin235

CiNii Research

Language：Japanese   Publisher：The Japanese Society for Artificial Intelligence  

<p>It is known that there is no stable algorithm that satisfy strategy-proofness in the two-sided matching with information diffusion. In this research, we examine the existence of stable algorithms by weakening the incentive requirement. More precisely, we show that even the non-obvious manipulability property is not achievable by stable algorithms.</p>

DOI： 10.11517/pjsai.jsai2024.0_1i3gs504

CiNii Research

Language：Japanese   Publisher：The Japanese Society for Artificial Intelligence  

<p>Diffusion mechanism design is a new research paradigm in the literature of mechanism design, which aims to incentivise agents to invite as many colleagues as possible to participate in a mechanism. An existing work on diffusion mechanism design for facility location games showed that there is no mechanism that satisfies strategy-proofness, Pareto efficiency and full anonymity, as well as proposed two naive mechanisms that satisfy strategy-proofness and Pareto efficiency by ignoring the full anonymity property. In this paper we aim to reveal to what extent strategy-proof and Pareto efficient mechanisms could be anonymous. We first define a class of anonymity properties by introducing a concept of partitions of the set of participating agents, and clarify a sufficient condition on partitions that guarantees the existence of mechanisms satisfying an anonymity property, as well as strategy-proofness and Pareto efficiency.</p>

DOI： 10.11517/pjsai.jsai2024.0_3xin250

CiNii Research

Language：Japanese   Publisher：The Japanese Society for Artificial Intelligence  

<p>The theory of two-sided matching has been extensively developed, and it is hoped that matching will reduce students' envies and improve overall welfare. However, it turns out that there exists a trade-off between efficiency and fairness. Therefore, keeping fairness at a certain level that can be applied in the real world also leads to increased efficiency. Our contribution is to establish a weaker fairness requirement called reverse Envy-Freeness from up to k peers (r-EF-k). r-EF-k requires that each student is envied by at most k students. By varying k, r-EF-k can represent different levels of fairness. We discuss mechanism that satisfy r-EF-k and certain efficiency properties.</p>

DOI： 10.11517/pjsai.jsai2024.0_2f6gs501

CiNii Research

Language：Japanese   Publisher：The Japanese Society for Artificial Intelligence  

<p>The Coalition Structure Generation (CSG) problem involves dividing the set of agents to maximize the sum of coalition values, and various algorithms have been proposed to address it. We propose an improvement that enables more efficient solving of the CSG problem, where externalities exist between coalitions, compared to the conventional MaxSAT encoding. Computational experiments demonstrate that our approach can reduce CPU computation time compared to traditional methods.</p>

DOI： 10.11517/pjsai.jsai2024.0_2m4os11b04

CiNii Research

Language：Japanese   Publisher：The Japanese Society for Artificial Intelligence  

<p>According to the insights of behavioral economics, it is believed that people feel happiness by comparing themselves with others who are close to them. In accordance with this insight, this study considers two-sided matching where envy occurs only with those directly connected in the social network, and examines the relationship between efficiency and fairness. In particular, we define the aforementioned envy as local envy, and adopt the absence of local envy as a relaxation of conventional fairness. Then, by restricting preferences on one side, we discuss the existence of matchings that are both locally envy free and Pareto efficient, as well as mechanisms to find such matchings.</p>

DOI： 10.11517/pjsai.jsai2024.0_3xin2112

CiNii Research

Publishing type：Research paper (international conference proceedings)   Publisher：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

Other Link： https://dblp.uni-trier.de/db/conf/aaai/aaai2024.html#KawaseMSTY24

Publisher：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

Publishing type：Research paper (scientific journal)  

DOI： 10.48550/arXiv.2402.01084

researchmap

Publisher：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

Publisher：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

Language：Japanese   Publisher：The Japanese Society for Artificial Intelligence  

<p>In this paper, we explore a two-period matching problem in which agents' preferences may evolve over time. This model enables agents to be matched with different partners over the two periods. Previous research defines dynamic stability as the absence of any single agent or pair of agents gaining an advantage through coalition across any period. We introduce new fairness, nonwastefulness and individually rationality notions tailored for the two-period matching setting and examine its relationship with dynamic stability. We also discuss the existence of matching that simultaneously satisfies the newly introduced fairness and nonwastefulness properties.</p>

DOI： 10.11517/pjsai.jsai2024.0_1i3gs501

CiNii Research

Language：English   Publishing type：Research paper (international conference proceedings)  

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

Publisher：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

Publisher：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

Publishing type：Research paper (international conference proceedings)   Publisher：Springer  

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

researchmap

Publishing type：Research paper (scientific journal)   Publisher：Elsevier BV  

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

Publishing type：Research paper (international conference proceedings)  

DOI： 10.1609/aaai.v37i12.26694

researchmap

Other Link： https://dblp.uni-trier.de/db/conf/aaai/aaai2023.html#0001TMTY23

Publishing type：Research paper (scientific journal)   Publisher：Elsevier BV  

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

Language：Japanese   Publisher：The Japanese Society for Artificial Intelligence  

<p>Mechanism design, a branch of economics, aims at designing rules that can autonomously achieve desired outcomes in resource allocation and public decision making. The research on mechanism design using machine learning is called automated mechanism design or mechanism learning. In our research, we construct a new network based on the existing method for single auctions and aim to automatically design an mechanism by applying it to double auctions. Especially, we focus on the following four desirable properties for the mechanism: individual rationality, balanced budget, Pareto efficiency, and incentive compatibility. We conducted experiments assuming a small-scale double auction and clarified the convergence of the obtained mechanism. We also confirmed how much the learnt mechanism satisfies the four properties compared to two representative protocols. As a result, we verified that the mechanism is more budget-balanced than VCG protocol and more Pareto-efficient than MD protocol, with the incentive compatibility mostly guaranteed.</p>

DOI： 10.11517/pjsai.jsai2023.0_1f4gs505

CiNii Research

Language：Japanese   Publisher：The Japanese Society for Artificial Intelligence  

<p>Integrally convex functions are a basic class of functions in discrete convex analysis, including M-convex functions and L-convex functions. Recently, the concept of L-extendable functions has been proposed for algorithm development for discrete optimization problems. A function h on an integer lattice is L-extendable if there exists an L-convex function g on a half-integer lattice such that the restriction of g on the integer lattice coincides with that of h. L-extendability is known to be useful in developing approximation algorithms and fast exact algorithms for various discrete optimization problems that are NP-hard. The purpose of this paper is to investigate L-extendability of integrally convex functions. Specifically, we first define a half-integrally convex function on a half-integer lattice that has properties similar to those of an integrally convex function. Then, we investigate the conditions under which an integrally convex function can be relaxed to a half-integrally convex function. Finally, we point out a research direction to investigate the condition under which an integrally convex function is L-extendable.</p>

DOI： 10.11517/pjsai.jsai2023.0_2j4gs102

CiNii Research

Language：Japanese   Publisher：The Japanese Society for Artificial Intelligence  

<p>Diffusion mechanism design is a new research paradigm in the literature of mechanism design, which aims to incentivise agents to invite as many colleagues as possible to participate in a mechanism. In this paper we apply diffusion mechanism design to the facility location game, one of the most well-studied model in MAS domain. We first provide a general impossibility result on the existence of possibly randomized facility location mechanisms that are strategy-proof, Pareto efficient and fully anonymous. We then present two strategy-proof mechanisms that satisfy some weaker notions of anonymity.</p>

DOI： 10.11517/pjsai.jsai2023.0_1f3gs503

CiNii Research

Language：Japanese   Publisher：The Japanese Society for Artificial Intelligence  

<p>We consider manipulation on facility location mechanisms which do not satisfy strategyproofness.Specifically, we deal with two mechanisms called the midpoint mechanism and the Nash mechanism. In the midpoint mechanism, the location is determined as half of the sum of the minimum and maximum values among the reported values.In the Nash mechanism, the location of facility is determined as that maximizing the product of utilities of the agents.Agents can improve their utility by manipulation in those mechanisms. In this paper, we investigate how one agent can manipulate the location of a facility in those mechanisms.</p>

DOI： 10.11517/pjsai.jsai2023.0_2f5gs502

CiNii Research

Language：Japanese   Publisher：The Japanese Society for Artificial Intelligence  

<p>Hedonic games are mathematical models in which a group of agents is divided into appropriate subgroups, and have been studied as a field of cooperative games. Cooperative games with permission structures, on the other hand, are models in which an agent’s participation in a game is by permission of another agent. In this paper, we introduce a permission structure into SASHG, a type of hedonic game, and consider solutions to hedonic games in which information diffusion, i.e., the incentive to issue as many permissions as possible, holds. Specifically, we first show that Nash stable solutions and information diffusion are incompatible. Given this impossibility, we propose an algorithm with incentives for information diffusion and show the approximate rate of social surplus that can be achieved. As a result, we show the incompatibility theorem of social surplus maximization and Nash stability with incentives for information diffusion, and furthermore, we show that the achievable approximation rate is 0.</p>

DOI： 10.11517/pjsai.jsai2023.0_2f4gs503

CiNii Research

Publishing type：Research paper (scientific journal)  

DOI： 10.48550/arXiv.2308.11230

researchmap

Publishing type：Research paper (scientific journal)  

DOI： 10.48550/arXiv.2309.10968

researchmap

Language：Others   Publishing type：Research paper (other academic)   Publisher：Springer  

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

Other Link： https://dblp.uni-trier.de/db/conf/prima/prima2022.html#OsoegawaTY22

Language：English   Publishing type：Research paper (scientific journal)  

Language：Others   Publishing type：Research paper (other academic)   Publisher：Springer  

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

Other Link： https://dblp.uni-trier.de/db/conf/pricai/pricai2022-1.html#SugaharaYBKY22

Language：Others   Publishing type：Research paper (scientific journal)  

DOI： 10.1613/jair.1.13499

Publishing type：Research paper (international conference proceedings)   Publisher：ijcai.org  

DOI： 10.24963/ijcai.2022/27

researchmap

Other Link： https://dblp.uni-trier.de/db/conf/ijcai/ijcai2022.html#ChoTY22

Language：English   Publishing type：Research paper (international conference proceedings)  

Publisher：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

Language：Others   Publishing type：Research paper (scientific journal)   Publisher：Elsevier BV  

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

Language：English  

DOI： 10.1613/jair.1.13499

Language：English  

Language：Others   Publishing type：Research paper (other academic)  

Publishing type：Research paper (international conference proceedings)   Publisher：International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS)  

researchmap

Other Link： https://dl.acm.org/doi/10.5555/3535850.3535911

Publishing type：Research paper (international conference proceedings)   Publisher：International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS)  

researchmap

Other Link： https://dl.acm.org/doi/10.5555/3535850.3536011

Language：English   Publishing type：Research paper (scientific journal)   Publisher：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

Language：English   Publishing type：Research paper (international conference proceedings)  

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

Language：Others   Publishing type：Research paper (scientific journal)   Publisher：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

Language：English   Publishing type：Research paper (scientific journal)   Publisher：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

Language：Japanese   Publisher：The Japanese Society for Artificial Intelligence  

<p>The multi-agent pathfinding (MAPF) problem takes as input a set of agents with different starts and goals, and assigns a path that does not cause conflicts among the agents. There is a powerful exact algorithm called Meta-Agent Conflict Based Search (MA-CBS) for minimizing the sum of the costs for each agent to reach the goal, which is known to be NP-hard. The behavior of MA-CBS varies depending on a condition called the merge policy, but it is known that it requires a huge amount of execution time for some MAPF instances under the conventional static merge policy. In this paper, we propose a new merge policy that dynamically changes the properties of the algorithm, and show by computer experiments that the algorithm that implements the proposed merge policy runs efficiently on more various instances than the conventional one.</p>

DOI： 10.11517/pjsai.jsai2022.0_1n1gs503

CiNii Research

Language：Japanese   Publisher：The Japanese Society for Artificial Intelligence  

<p>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 from 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.</p>

DOI： 10.11517/pjsai.jsai2022.0_2n4gs505

CiNii Research

Publisher：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

Publisher：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

Language：Japanese   Publisher：The Japanese Society for Artificial Intelligence  

<p>This paper presents a new problem called Robust weighted Partial Maximum Satisfiability (R-PMaxSAT), which is an extension of Robust MaxSAT (R-MaxSAT) whose decision version is Sigma2P-complete. In R-MaxSAT (or R-PMaxSAT), a problem solver called the defender expects to maximize the number of satisfied clauses (or the sum of their weights) as a standard MaxSAT, although the obtained solution must be robust. We presume an adversary called the attacker will modify some variables after the defender decides a solution. R-PMaxSAT can formalize a robust Clique Partitioning Problem (robust CPP), where CPP has many real-life applications. Then, we introduce two algorithms to solve R-PMaxSAT, by utilizing a modern SAT solver or a QBF solver as a subroutine. Our experimental results show that we can obtain optimal solutions within reasonable time for randomly generated R-MaxSAT instances and robust CPP instances based on CPP benchmark problems.</p>

DOI： 10.11517/pjsai.jsai2022.0_4f1os8a04

CiNii Research

Web of Science

Publishing type：Research paper (international conference proceedings)   Publisher：AAAI Press  

DOI： 10.1609/aaai.v36i11.21495

researchmap

Other Link： https://dblp.uni-trier.de/db/conf/aaai/aaai2022.html#0001BY22

Web of Science

Publisher：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

Publishing type：Research paper (scientific journal)  

DOI： 10.48550/arXiv.2212.02751

researchmap

Language：English  

Language：English  

Language：Others   Publishing type：Research paper (other academic)  

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

Language：English   Publishing type：Research paper (international conference proceedings)  

Language：English   Publishing type：Research paper (international conference proceedings)  

DOI： 10.3233/FAIA200097

Language：English   Publishing type：Research paper (international conference proceedings)  

DOI： 10.3233/FAIA200096

Language：English   Publishing type：Research paper (international conference proceedings)  

Language：Others   Publishing type：Research paper (other academic)  

Language：English   Publishing type：Research paper (international conference proceedings)  

Language：English   Publishing type：Research paper (international conference proceedings)  

Language：English   Publishing type：Research paper (scientific journal)  

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

DOI： 10.1609/aaai.v34i02.5576

Language：English   Publishing type：Research paper (scientific journal)  

DOI： 10.1007/s10458-020-09448-9

Language：English   Publishing type：Research paper (international conference proceedings)  

DOI： 10.1609/aaai.v34i02.5576

Language：English   Publishing type：Research paper (international conference proceedings)  

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

Language：Others   Publishing type：Research paper (scientific journal)  

DOI： 10.1007/s10458-019-09429-7

Language：Others   Publishing type：Research paper (scientific journal)  

DOI： 10.1007/s10458-020-09448-9

Language：English   Publishing type：Research paper (international conference proceedings)  

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

Language：Japanese   Publishing type：Research paper (scientific journal)  

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

Language：English   Publishing type：Research paper (international conference proceedings)  

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

Language：English   Publishing type：Research paper (scientific journal)  

DOI： 10.1016/j.artint.2019.03.002

Language：English   Publishing type：Research paper (international conference proceedings)  

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.

Language：English   Publishing type：Research paper (international conference proceedings)  

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

Language：English   Publishing type：Research paper (international conference proceedings)  

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

Language：English   Publishing type：Research paper (scientific journal)  

Language：English   Publishing type：Research paper (other academic)  

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

Language：English   Publishing type：Research paper (international conference proceedings)  

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.

Language：Others   Publishing type：Research paper (other academic)  

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

Language：English   Publishing type：Research paper (international conference proceedings)  

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.

Language：English   Publishing type：Research paper (scientific journal)  

Privacy stochastic games in distributed constraint reasoning

DOI： 10.1007/s10472-019-09628-8

Language：Japanese   Publishing type：Research paper (scientific journal)  

Coalition Structure Generation for Partition Function Games Utilizing Partition Decision Trees
This paper studies coalition structure generation (CSG) problems for partition function games (PFGs) which are coalitional games with externalities. In PFGs, each value of a coalition depends on how the other agents are partitioned. In this paper, we consider CSG problems when there exist both positive and negative values for coalitions. We apply a compact representation method called Partition Decision Trees<br />
(PDTs) to represent PFGs and propose two different methods to solve CSG problems: a depth-first branch-and-bound algorithm and MaxSAT encoding.

DOI： 10.14923/transinfj.2018JDP7037

Language：Others   Publishing type：Research paper (scientific journal)  

DOI： 10.1016/j.artint.2019.03.002

Language：English   Publishing type：Research paper (scientific journal)  

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

Language：English   Publishing type：Research paper (scientific journal)  

Improved WPM encoding for coalition structure generation under MC-nets

DOI： 10.1007/s10601-018-9295-4

Language：English   Publishing type：Research paper (international conference proceedings)  

Language：English   Publishing type：Research paper (scientific journal)  

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

Language：English   Publishing type：Research paper (scientific journal)  

DOI： 10.1613/jair.1.11254

Language：English   Publishing type：Research paper (international conference proceedings)  

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

Language：English   Publishing type：Research paper (international conference proceedings)  

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

Language：English   Publishing type：Research paper (international conference proceedings)  

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.

Language：English   Publishing type：Research paper (scientific journal)  

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

Language：English   Publishing type：Research paper (international conference proceedings)  

Language：English   Publishing type：Research paper (international conference proceedings)  

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.

Language：English   Publishing type：Research paper (international conference proceedings)  

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.

Language：English   Publishing type：Research paper (scientific journal)  

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

Language：English   Publishing type：Research paper (scientific journal)  

DOI： 10.1007/s10458-018-9386-z

Language：English   Publishing type：Research paper (scientific journal)  

DOI： 10.3233/FI-2018-1641

Language：English   Publishing type：Research paper (scientific journal)  

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

Language：English   Publishing type：Research paper (international conference proceedings)  

Language：English   Publishing type：Research paper (international conference proceedings)  

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.

Language：English   Publishing type：Research paper (scientific journal)  

DOI： 10.1111/coin.12106

Language：English   Publishing type：Research paper (scientific journal)  

DOI： 10.3233/FI-2018-1642

Language：English   Publishing type：Research paper (international conference proceedings)  

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.

Language：English   Publishing type：Research paper (international conference proceedings)  

Language：English   Publishing type：Research paper (international conference proceedings)  

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.

Language：English   Publishing type：Research paper (other academic)  

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

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

Language：English   Publishing type：Research paper (international conference proceedings)  

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.

Language：Japanese   Publishing type：Research paper (scientific journal)  

Language：English   Publishing type：Research paper (scientific journal)  

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

Language：English   Publishing type：Research paper (scientific journal)  

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

Language：English   Publishing type：Research paper (international conference proceedings)  

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.

Language：English   Publishing type：Research paper (scientific journal)  

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

Language：English   Publishing type：Research paper (scientific journal)  

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

Language：English   Publishing type：Research paper (international conference proceedings)  

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.

Language：English   Publishing type：Research paper (international conference proceedings)  

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.

Language：English   Publishing type：Research paper (international conference proceedings)  

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.

Language：English   Publishing type：Research paper (international conference proceedings)  

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.

Language：English   Publishing type：Research paper (international conference proceedings)  

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.

Language：English   Publishing type：Research paper (international conference proceedings)  

Language：English   Publishing type：Research paper (scientific journal)  

DOI： 10.1613/jair.5297

Language：English   Publishing type：Research paper (scientific journal)  

DOI： 10.1109/MIS.2017.3

Language：English   Publishing type：Research paper (scientific journal)  

DOI： 10.1109/MIS.2017.3

Language：English   Publishing type：Research paper (international conference proceedings)  

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

Language：English   Publishing type：Research paper (international conference proceedings)  

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.

Language：English   Publishing type：Research paper (scientific journal)  

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

Language：English   Publishing type：Research paper (scientific journal)  

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

Language：English   Publishing type：Research paper (international conference proceedings)  

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.

Language：English   Publishing type：Research paper (international conference proceedings)  

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.

Language：English   Publishing type：Research paper (international conference proceedings)  

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.

Language：English   Publishing type：Research paper (international conference proceedings)  

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.

Language：English   Publishing type：Research paper (international conference proceedings)  

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.

Language：English   Publishing type：Research paper (international conference proceedings)  

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.

Language：English   Publishing type：Research paper (international conference proceedings)  

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.

Language：English   Publishing type：Research paper (scientific journal)  

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

Language：English   Publishing type：Research paper (other academic)  

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

Language：English   Publishing type：Research paper (international conference proceedings)  

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

Language：English   Publishing type：Research paper (other academic)  

Leximin Asymmetric Multiple Objective DCOP on Factor Graph

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

Language：English   Publishing type：Research paper (international conference proceedings)  

Language：English   Publishing type：Research paper (international conference proceedings)  

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

Language：English   Publishing type：Research paper (international conference proceedings)  

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

Language：English   Publishing type：Research paper (international conference proceedings)  

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.

Language：English   Publishing type：Research paper (international conference proceedings)  

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.

Language：English   Publishing type：Research paper (international conference proceedings)  

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.

Language：English   Publishing type：Research paper (other academic)  

DOI： 10.1145/2764468.2764501

Language：English   Publishing type：Research paper (international conference proceedings)  

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.

Language：English   Publishing type：Research paper (international conference proceedings)  

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.

Language：English   Publishing type：Research paper (scientific journal)  

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

Language：English   Publishing type：Research paper (other academic)  

Parametric mechanism design via quantifier elimination

Language：English   Publishing type：Research paper (international conference proceedings)  

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.

Language：English   Publishing type：Research paper (international conference proceedings)  

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.

Language：English   Publishing type：Research paper (international conference proceedings)  

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).

Language：English  

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

Language：English   Publishing type：Research paper (international conference proceedings)  

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.

Language：English   Publishing type：Research paper (international conference proceedings)  

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.

Language：English   Publishing type：Research paper (international conference proceedings)  

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.

Language：English   Publishing type：Research paper (international conference proceedings)  

Language：Japanese   Publishing type：Research paper (scientific journal)  

Language：English   Publishing type：Research paper (international conference proceedings)  

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

Language：Japanese   Publishing type：Research paper (scientific journal)  

Language：English   Publishing type：Research paper (international conference proceedings)  

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.

Language：English   Publishing type：Research paper (international conference proceedings)  

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.

Language：English   Publishing type：Research paper (international conference proceedings)  

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.

Language：English   Publishing type：Research paper (other academic)  

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.

Language：English   Publishing type：Research paper (international conference proceedings)  

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.

Language：English   Publishing type：Research paper (international conference proceedings)  

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.

Language：Japanese   Publishing type：Research paper (scientific journal)  

Language：Japanese   Publishing type：Research paper (scientific journal)  

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

Language：Japanese   Publishing type：Research paper (scientific journal)  

A Hybrid Algorithm for Distributed Constraint Optimization (in Japanese)

Language：Japanese   Publishing type：Research paper (scientific journal)  

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

Language：English   Publishing type：Research paper (other academic)  

Strategy-proof mechanisms for the k-winner selection problem

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

Language：English   Publishing type：Research paper (international conference proceedings)  

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

Language：English   Publishing type：Research paper (international conference proceedings)  

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

Language：English   Publishing type：Research paper (international conference proceedings)  

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

Language：Japanese   Publishing type：Research paper (scientific journal)  

Language：Japanese   Publishing type：Research paper (scientific journal)  

Language：English   Publishing type：Research paper (international conference proceedings)  

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

Language：English   Publishing type：Research paper (other academic)  

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

Language：English   Publishing type：Research paper (other academic)  

Ability grouping of crowd workers via reward discrimination

DOI： 10.1609/hcomp.v1i1.13083

Language：English   Publishing type：Research paper (international conference proceedings)  

Language：Japanese  

Language：Japanese  

Language：English   Publishing type：Research paper (international conference proceedings)  

Language：Others  

Pseudo-Tree Based Hybrid Algorithm for Distributed Constraint Optimization

Language：English   Publishing type：Research paper (international conference proceedings)  

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

Language：Japanese   Publishing type：Research paper (scientific journal)  

Distributed Search Methods for Quantified Distributed Constraint Optimization Problem

DOI： 10.1527/tjsai.28.43

Language：Japanese   Publishing type：Research paper (scientific journal)  

Interactive Algorithm for Multi-objective Constraint Optimization

DOI： 10.1527/tjsai.28.57

Language：English   Publishing type：Research paper (scientific journal)  

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

Language：English   Publishing type：Research paper (scientific journal)  

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

Language：English   Publishing type：Research paper (scientific journal)  

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

Language：English   Publishing type：Research paper (scientific journal)  

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

Language：English   Publishing type：Research paper (international conference proceedings)  

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

Language：English   Publishing type：Research paper (international conference proceedings)  

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

Language：Japanese   Publishing type：Research paper (scientific journal)  

Language：English   Publishing type：Research paper (international conference proceedings)  

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

Language：Japanese   Publishing type：Research paper (scientific journal)  

Language：English   Publishing type：Research paper (scientific journal)  

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

Language：Japanese  

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

Language：English   Publishing type：Research paper (other academic)  

Interactive Algorithm for Multi-objective Constraint Optimization

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

Language：Japanese  

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

Language：English   Publishing type：Research paper (scientific journal)  

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

Language：English   Publishing type：Research paper (scientific journal)  

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.

Language：Japanese  

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

Language：English   Publishing type：Research paper (international conference proceedings)  

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

Language：Japanese   Publishing type：Research paper (scientific journal)  

Language：English   Publishing type：Research paper (scientific journal)  

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

Language：English   Publishing type：Research paper (scientific journal)  

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

DOI： 10.3233/MGS-2012-0189

Language：Japanese   Publishing type：Research paper (scientific journal)  

Language：Japanese  

Introduction of Game Theory for Computer Scientists

DOI： 10.11309/jssst.29.2_65

Language：Japanese   Publishing type：Research paper (scientific journal)  

Language：Japanese   Publishing type：Research paper (scientific journal)  

Language：Japanese   Publishing type：Research paper (scientific journal)  

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

Language：English   Publishing type：Research paper (international conference proceedings)  

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

Language：English   Publishing type：Research paper (international conference proceedings)  

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

Language：English   Publishing type：Research paper (international conference proceedings)  

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

Language：Japanese   Publishing type：Research paper (scientific journal)  

Language：Japanese   Publishing type：Research paper (scientific journal)  

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

Language：English   Publishing type：Research paper (international conference proceedings)  

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

Language：Japanese   Publishing type：Research paper (scientific journal)  

Language：Japanese   Publishing type：Research paper (scientific journal)  

Language：Japanese   Publishing type：Research paper (scientific journal)  

Language：English   Publishing type：Research paper (international conference proceedings)  

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

Language：English   Publishing type：Research paper (other academic)  

Reducing the Search Space of Resource Constrained DCOPs

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

Language：English   Publishing type：Research paper (other academic)  

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

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

Language：English   Publishing type：Research paper (international conference proceedings)  

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

Language：English   Publishing type：Research paper (international conference proceedings)  

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

Language：English   Publishing type：Research paper (scientific journal)  

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

Language：English   Publishing type：Research paper (scientific journal)  

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

Language：English   Publishing type：Research paper (scientific journal)  

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

Language：English  

Language：Japanese   Publishing type：Research paper (scientific journal)  

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

Language：English  

Language：Japanese   Publishing type：Research paper (scientific journal)  

Language：Japanese   Publishing type：Research paper (scientific journal)  

Language：Japanese   Publishing type：Research paper (scientific journal)  

Language：Japanese   Publishing type：Research paper (scientific journal)  

Language：Japanese   Publishing type：Research paper (scientific journal)  

Language：Japanese   Publishing type：Research paper (scientific journal)  

Language：English   Publishing type：Research paper (other academic)  

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

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

Language：Japanese  

Language：Japanese  

Language：Japanese   Publishing type：Research paper (scientific journal)  

Language：English   Publishing type：Research paper (other academic)  

A Quantified Distributed Constraint Optimization Problems

Language：English   Publishing type：Research paper (scientific journal)  

Language：English   Publishing type：Research paper (scientific journal)  

Language：English   Publishing type：Research paper (scientific journal)  

Language：Japanese   Publishing type：Research paper (scientific journal)  

Applying Soft Arc Consistency to Distributed Constraint Optimization Problems

Language：English   Publishing type：Research paper (scientific journal)  

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

Language：Japanese   Publishing type：Research paper (scientific journal)  

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

Language：English   Publishing type：Research paper (scientific journal)  

Language：English   Publishing type：Research paper (other academic)  

Directed Soft Arc Consistency in Pseudo-trees

Language：Japanese   Publishing type：Research paper (scientific journal)  

Language：Japanese   Publishing type：Research paper (scientific journal)  

Language：Japanese   Publishing type：Research paper (scientific journal)  

Language：English   Publishing type：Research paper (international conference proceedings)  

Language：English   Publishing type：Research paper (other academic)  

Resource constrained distributed constraint optimization with virtual variables

Language：English   Publishing type：Research paper (other academic)  

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

Language：Japanese   Publishing type：Research paper (scientific journal)  

Language：English   Publishing type：Research paper (scientific journal)  

Language：English   Publishing type：Research paper (scientific journal)  

Language：English   Publishing type：Research paper (scientific journal)  

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

Language：English   Publishing type：Research paper (scientific journal)  

Language：English   Publishing type：Research paper (scientific journal)  

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

Language：Japanese   Publishing type：Research paper (scientific journal)  

Publishing type：Research paper (scientific journal)  

Language：Japanese   Publishing type：Research paper (scientific journal)  

Language：English   Publishing type：Research paper (scientific journal)  

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

DOI： 10.1002/scj.20748

Language：English   Publishing type：Research paper (scientific journal)  

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

Language：English  

DOI： 10.1007/s10458-005-0983-2

Language：English   Publishing type：Research paper (scientific journal)  

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

Language：English   Publishing type：Research paper (scientific journal)  

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

Language：English   Publishing type：Research paper (scientific journal)  

Language：English   Publishing type：Research paper (other academic)  

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

Language：English  

DOI： 10.1093/ietfec/E88-A.1.255

Language：English   Publishing type：Research paper (scientific journal)  

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

Language：English   Publishing type：Research paper (scientific journal)  

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

Language：English  

DOI： 10.1016/j.artint.2004.08.004

Language：English  

DOI： 10.1016/j.artint.2004.10.007

Language：English  

Language：English  

Language：English  

Language：English   Publishing type：Research paper (scientific journal)  

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

Language：English   Publishing type：Research paper (scientific journal)  

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

Language：Japanese  

"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)

Language：Japanese  

"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)

Language：Japanese  

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

Language：English  

Language：English   Publishing type：Research paper (other academic)  

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

Language：English   Publishing type：Research paper (other academic)  

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

Language：English  

Language：Japanese  

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

Language：Japanese  

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

Language：Japanese  

"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

Language：English   Publishing type：Research paper (scientific journal)  

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

Language：English   Publishing type：Research paper (scientific journal)  

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

Language：English  

Language：English  

Language：Japanese  

"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

Language：Japanese  

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

Language：Japanese  

"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

Language：Japanese   Publishing type：Research paper (other academic)  

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

DOI： 10.11309/jssst.17.445

Language：Japanese  

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

DOI： 10.11309/jssst.17.109

Language：Japanese  

"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)

Language：Japanese  

"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)

Language：Japanese  

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

Language：Japanese  

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

Language：English  

Language：Japanese  

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

Language：Japanese  

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

Language：English  

Language：Japanese  

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

Language：Japanese  

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

Language：Japanese  

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

Language：English  

Language：Japanese  

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

Responsible for pages：総ページ数：676   Language：English  

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

Responsible for pages：総ページ数：486, 担当ページ数：53-64   Language：English  

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

Responsible for pages：総ページ数：147   Language：Others  

Language：Japanese   Book type：Scholarly book

Responsible for pages：総ページ数：138   Language：Others  

Responsible for pages：Chapter "Robust Combinatorial Auction Protocol against False-name Bids"   Language：English   Book type：Scholarly book

Responsible for pages：総ページ数：236   Language：English  

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)

Language：English   Book type：Scholarly book

Responsible for pages：Chapter Title "Search Algorithms for Agents"   Language：English   Book type：Scholarly book

Event date： 2022.2

Language：Japanese  

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

Event date： 2022.2

Language：Japanese  

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

Event date： 2021.9

Language：Japanese  

Venue：オンライン  

Event date： 2021.9

Language：Japanese  

Venue：オンライン  

Event date： 2021.9

Language：Japanese  

Venue：オンライン  

Event date： 2021.8

Language：Japanese  

Venue：オンライン  

Event date： 2021.8

Language：English  

Venue：Dagstuhl, Wadern (Online)   Country：Germany  

Event date： 2021.8

Language：English  

Venue：Dagstuhl, Wadern (Online)   Country：Germany  

Event date： 2021.7

Language：English  

Venue：Dagstuhl, Wadern (Online)   Country：Germany  

Event date： 2021.6

Venue：City University of Hong Kong (Online)  

Event date： 2021.6

Language：Japanese  

Venue：オンライン  

Event date： 2021.6

Language：Japanese  

Venue：オンライン  

Event date： 2021.3

Language：Japanese  

Venue：オンライン   Country：Japan  

Event date： 2021.3

Language：Japanese  

Venue：オンライン   Country：Japan  

Event date： 2020.9

Language：Japanese  

Venue：オンライン   Country：Japan  

Event date： 2020.9

Language：Japanese  

Venue：オンライン   Country：Japan  

Event date： 2020.9

Language：Japanese  

Venue：オンライン   Country：Japan  

Event date： 2020.6

Language：Japanese  

Venue：オンライン   Country：Japan  

Event date： 2020.6

Language：Japanese   Presentation type：Oral presentation (general)  

Venue：オンライン   Country：Japan  

Event date： 2020.6

Language：Japanese  

Venue：オンライン   Country：Japan  

Event date： 2020.6