Positive results for mechanism design without money

Richard Cole, Vasilis Gkatzelis, Gagan Goel

Research output: Contribution to conferencePaperpeer-review

Abstract

Consider the problem of allocating multiple divisible goods to two agents in a strategy-proof fashion without the use of payments or priors. Previous work [1, 2] has aimed at implementing allocations that are competitive with respect to an appropriately defined measure of social welfare. These results have mostly been negative, proving that no dictatorial mechanism can achieve an approximation factor better than 0.5, and leaving open the question of whether there exists a non-dictatorial mechanism that outperforms this bound. We provide a positive answer to this question by presenting an interesting non-dictatorial mechanism that achieves an approximation factor of 2/3 for this measure of social welfare. In proving this bound we also touch on the issue of fairness: we show that the proportionally fair solution, a well known fairness concept for money-free settings, is highly competitive with respect to social welfare. We then show how to use the proportionally fair solution to design our non-dictatorial strategy-proof mechanism.

Original languageEnglish (US)
Pages1165-1166
Number of pages2
StatePublished - 2013
Event12th International Conference on Autonomous Agents and Multiagent Systems 2013, AAMAS 2013 - Saint Paul, MN, United States
Duration: May 6 2013May 10 2013

Other

Other12th International Conference on Autonomous Agents and Multiagent Systems 2013, AAMAS 2013
Country/TerritoryUnited States
CitySaint Paul, MN
Period5/6/135/10/13

Keywords

  • Prior-Free Mechanism Design
  • Proportional Fairness

ASJC Scopus subject areas

  • Artificial Intelligence

Cite this