Allocating indivisible goods

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Allocating indivisible goods

Full text

Pdf (156 KB)

Source

ACM SIGecom Exchanges archive
Volume 5 , Issue 3 (April 2005) table of contents

Pages: 11 - 18

Year of Publication: 2005

Authors

Ivona Bezáková	University of Chicago
Varsha Dani	University of Chicago

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 3, Downloads (12 Months): 28, Citation Count: 4

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1120680.1120683 What is a DOI?

ABSTRACT

The problem of allocating divisible goods has enjoyed a lot of attention in both mathematics (e.g. the cake-cutting problem) and economics (e.g. market equilibria). On the other hand, the natural requirement of indivisible goods has been somewhat neglected, perhaps because of its more complicated nature. In this work we study a fairness criterion, called the Max-Min Fairness problem, for k players who want to allocate among themselves m indivisible goods. Each player has a specified valuation function on the subsets of the goods and the goal is to split the goods between the players so as to maximize the minimum valuation. Viewing the problem from a game theoretic perspective, we show that for two players and additive valuations the expected minimum of the (randomized) cut-and-choose 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 algorithmic perspective when the (true) additive valuation functions are part of the input. 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 with additive error against the fractional optimum bounded by the value of the largest item. The two approximation algorithms are incomparable in the sense that there exist instances when one outperforms the other.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Sanjeev Arora , Carsten Lund , Rajeev Motwani , Madhu Sudan , Mario Szegedy, Proof verification and the hardness of approximation problems, Journal of the ACM (JACM), v.45 n.3, p.501-555, May 1998 [doi>10.1145/278298.278306]
	2	BRAMS, S. J. AND TAYLOR, A. D. 1996. Fair Division : From Cake-Cutting to Dispute Resolution. Cambridge University Press.
	3	Leah Epstein , Jiri Sgall, Approximation Schemes for Scheduling on Uniformly Related and Identical Parallel Machines, Algorithmica, v.39 n.1, p.43-57, January 2004 [doi>10.1007/s00453-003-1077-7]
	4	Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
	5	J. K. Lenstra , D. B. Shmoys , É. Tardos, Approximation algorithms for scheduling unrelated parallel machines, Mathematical Programming: Series A and B, v.46 n.3, p.259-271, Apr. 1990 [doi>10.1007/BF01585745]
	6	R. J. Lipton , E. Markakis , E. Mossel , A. Saberi, On approximately fair allocations of indivisible goods, Proceedings of the 5th ACM conference on Electronic commerce, May 17-20, 2004, New York, NY, USA [doi>10.1145/988772.988792]
	7	MARKAKIS, E. and SABERI, A. 2004. Personal communication.
	8	MOULIN, H. 2002. The proportional random allocation of indivisible units. Social Choice and Welfare 19, 2, 381-413.
	9	ROBERTSON, J. and WEBB, W. 1998. Cake Cutting Algorithms: Be Fair If You Can. A. K. Peters, Ltd.
	10	STEINHAUS, H. 1948. The problem of fair division. Econometrica 16, 1 (January), 101-104.
	11	WOEGINGER, G. J. 1997. A polynomial time approximation scheme for maximizing the minimum machine completion time. Operations Research Letters 20, 149-154.
	12	Gerhard J. Woeginger, When Does a Dynamic Programming Formulation Guarantee the Existence of a Fully Polynomial Time Approximation Scheme (FPTAS)?, INFORMS Journal on Computing, v.12 n.1, p.57-74, January 2000 [doi>10.1287/ijoc.12.1.57.11901]

CITED BY 4

	Nikhil Bansal , Maxim Sviridenko, The Santa Claus problem, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA
	Arash Asadpour , Amin Saberi, An approximation algorithm for max-min fair allocation of indivisible goods, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11-13, 2007, San Diego, California, USA
	Uriel Feige, On allocations that maximize fairness, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.287-293, January 20-22, 2008, San Francisco, California
	Ron Lavi , Chaitanya Swamy, Truthful mechanism design for multi-dimensional scheduling via cycle monotonicity, Proceedings of the 8th ACM conference on Electronic commerce, June 11-15, 2007, San Diego, California, USA