TY - GEN
T1 - Social decision with minimal efficiency loss
T2 - 14th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2015
AU - Guo, Mingyu
AU - Shen, Hong
AU - Todo, Taiki
AU - Sakurai, Yuko
AU - Yokoo, Makoto
N1 - Publisher Copyright:
Copyright © 2015, International Foundation for Autonomous Agents and Multiagent Systems.
PY - 2015
Y1 - 2015
N2 - 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.
AB - 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.
KW - Automated Mechanism Design
KW - Groves Mechanisms
KW - Social Decision
UR - http://www.scopus.com/inward/record.url?scp=84944681151&partnerID=8YFLogxK
M3 - Conference contribution
AN - SCOPUS:84944681151
T3 - Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS
SP - 347
EP - 355
BT - AAMAS 2015 - Proceedings of the 2015 International Conference on Autonomous Agents and Multiagent Systems
A2 - Elkind, Edith
A2 - Bordini, Rafael H.
A2 - Weiss, Gerhard
A2 - Yolum, Pinar
PB - International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS)
Y2 - 4 May 2015 through 8 May 2015
ER -