Mechanism design for fair division: Allocating divisible items without payments

Richard Cole, Vasilis Gkatzelis, Gagan Goel

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

We revisit the classic problem of fair division from a mechanism design perspective and provide an elegant truthful mechanism that yields surprisingly good approximation guarantees for the widely used solution of Proportional Fairness. This solution, which is closely related to Nash bargaining and the competitive equilibrium, is known to be not implementable in a truthful fashion, which has been its main drawback. To alleviate this issue, we propose a new mechanism, which we call the Partial Allocation mechanism, that discards a carefully chosen fraction of the allocated resources in order to incentivize the agents to be truthful in reporting their valuations. This mechanism introduces a way to implement interesting truthful outcomes in settings where monetary payments are not an option. For a multi-dimensional domain with an arbitrary number of agents and items, and for the very large class of homogeneous valuation functions, we prove that our mechanism provides every agent with at least a 1=e ≈ 0:368 fraction of her Proportionally Fair valuation. To the best of our knowledge, this is the first result that gives a constant factor approximation to every agent for the Proportionally Fair solution. To complement this result, we show that no truthful mechanism can guarantee more than 0:5 approximation, even for the restricted class of additive linear valuations. In addition to this, we uncover a connection between the Partial Allocation mechanism and VCG-based mechanism design. We also ask whether better approximation ratios are possible in more restricted settings. In particular, motivated by the massive privatization auction in the Czech republic in the early 90s we provide another mechanism for additive linear valuations that works really well when all the items are highly demanded.

Original languageEnglish (US)
Title of host publicationEC 2013 - Proceedings of the 14th ACM Conference on Electronic Commerce
Pages251-268
Number of pages18
StatePublished - 2013
Event14th ACM Conference on Electronic Commerce, EC 2013 - Philadelphia, PA, United States
Duration: Jun 16 2013Jun 20 2013

Publication series

NameProceedings of the ACM Conference on Electronic Commerce

Other

Other14th ACM Conference on Electronic Commerce, EC 2013
Country/TerritoryUnited States
CityPhiladelphia, PA
Period6/16/136/20/13

Keywords

  • Competitive equilibrium from equal incomes
  • Fair division
  • Mechanism design
  • Proportional fairness

ASJC Scopus subject areas

  • Software
  • Computer Science Applications
  • Computer Networks and Communications

Fingerprint

Dive into the research topics of 'Mechanism design for fair division: Allocating divisible items without payments'. Together they form a unique fingerprint.

Cite this