TR-2004-10
Allocating Indivisible Goods
Ivona Bezakova; Varsha Dani. 14 December, 2004.
Communicated by Lance Fortnow.
Abstract
Given k players, m indivisible goods and a valuation function on the set of the goods for every player, Lipton, Markakis, Mossel and Saberi propose the Max-Min Fairness problem: partition the goods between the players such that the minimum value achieved by every player is maximized. We show that for two players and additive valuation functions, the expected minimum of the (randomized) cut-andchoose mechanism is a 1/2-approximation of the optimum. To complement this result we show that no truthful mechanism can compute the exact optimum.We also consider the case when the algorithm knows the true additive valuations of every player. We present a simple 1/(m − k + 1) approximation algorithm which allocates to every player at least 1/k fraction of the value of all but the k − 1 heaviest items. We also give an algorithm which guarantees every player at least the fractional optimum of the corresponding linear relaxation, minus the largest item. This approximation algorithm has additive error at most the value of the largest item. We conclude with a 1/2 + e factor hardness of approximation result unless P = NP.
Original Document
The original document is available in PDF (uploaded 14 December, 2004 by Lance Fortnow).
Additional Document Formats
The document is also available in Postscript (uploaded 14 December, 2004 by Lance Fortnow).
NOTE: The author warrants that these additional documents are identical with the originial to the extent permitted by the translation between the various formats. However, the webmaster has made no effort to verify this claim. If the authenticity of the document is an issue, please always refer to the "Original document." If you find significant alterations, please report to webmaster@cs.uchicago.edu.