SCIENCE@home

Social Decision with Minimal Efficiency Loss: An Automated Mechanism Design Approach

M. Guo,Hong Shen,Taiki Todo,Y. Sakurai,M. Yokoo

Published 2015 in Adaptive Agents and Multi-Agent Systems

ABSTRACT

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.

PUBLICATION RECORD

  • Publication year

    2015

  • Venue

    Adaptive Agents and Multi-Agent Systems

  • Publication date

    2015-05-04

  • Fields of study

    Computer Science, Economics

  • Identifiers
    DOI 10.65109/qfom1922
  • External record

    Open on Semantic Scholar

  • Source metadata

    Semantic Scholar

CITATION MAP

EXTRACTION MAP

CLAIMS

  • No claims are published for this paper.

CONCEPTS

  • No concepts are published for this paper.

REFERENCES

Showing 1-15 of 15 references · Page 1 of 1

CITED BY