Mechanism Design for Fair Division: Allocating Divisible Items without Payments
Venue
EC 2013, ACM
Publication Year
2013
Authors
Richard Cole, Vasilis Gkatzelis, Gagan Goel
BibTeX
Abstract
We revisit the classic problem of fair division from a mechanism design
perspective, using Proportional Fairness as a benchmark. In particular, we aim to
allocate a collection of divisible items to a set of agents while incentivizing the
agents to be truthful in reporting their valuations. For the very large class of
homogeneous valuations, we design a truthful mechanism that provides every agent
with at least 0.368 fraction of her Proportionally Fair valuation. To complement
this result, we show that no truthful mechanism can guarantee more than a 0.5
fraction, even for the restricted class of additive linear valuations. We also
propose another mechanism for additive linear valuations that works really well
when every item is highly demanded. To guarantee truthfulness, our mechanisms
discard a carefully chosen fraction of the allocated resources; we conclude by
uncovering interesting connections between our mechanisms and known mechanisms that
use money instead.
