Social decision with minimal efficiency loss: An automated mechanism design approach

Simple item page
dc.contributor.authorGuo, M.
dc.contributor.authorShen, H.
dc.contributor.authorTodo, T.
dc.contributor.authorSakurai, Y.
dc.contributor.authorYokoo, M.
dc.contributor.conference14th International Conference on Autonomous Agents and Multiagent Systems (AAMAS '15) (4 May 2015 - 8 May 2015 : Istanbul, Turkey)
dc.date.issued2015
dc.description.abstractWe 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.
dc.description.statementofresponsibilityMingyu Guo, Hong Shen, Taiki Todo, Yuko Sakurai, Makoto Yokoo
dc.identifier.citationProceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS, 2015, vol.1, pp.347-355
dc.identifier.isbn9781450337694
dc.identifier.issn1548-8403
dc.identifier.issn1558-2914
dc.identifier.orcidGuo, M. [0000-0002-3478-9201]
dc.identifier.orcidShen, H. [0000-0002-3663-6591] [0000-0003-0649-0648]
dc.identifier.urihttp://hdl.handle.net/2440/108876
dc.language.isoen
dc.publisherACM
dc.rightsCopyright © 2015, International Foundation for Autonomous Agents and Multiagent Systems (www.ifaamas.org). All rights reserved.
dc.source.urihttp://www.ifaamas.org/Proceedings/aamas2015/forms/index.htm
dc.subjectGroves mechanisms, automated mechanism design, social decision
dc.titleSocial decision with minimal efficiency loss: An automated mechanism design approach
dc.typeConference paper
pubs.publication-statusPublished

Files

Original bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
RA_hdl_108876.pdf
Size:
387.46 KB
Format:
Adobe Portable Document Format
Description:
Restricted Access
Download

Collections

Computer Science publications