Abstract
We study a fair division problem, where a set of indivisible goods is to be allocated to a set of n agents. In the continuous case, where goods are infinitely divisible, it is well known that proportional allocations always exist, i.e., allocations where every agent receives a bundle of goods worth to him at least \(\frac{1}{n}\). With indivisible goods however, this is not the case and one would like to find worst case guarantees on the value that every agent can have. We focus on algorithmic and mechanism design aspects of this problem.
An explicit lower bound was identified by Hill [5], depending on n and the maximum value of any agent for a single good, such that for any instance, there exists an allocation that provides at least this guarantee to every agent. The proof however did not imply an efficient algorithm for finding such allocations. Following upon the work of [5], we first provide a slight strengthening of the guarantee we can make for every agent, as well as a polynomial time algorithm for computing such allocations. We then move to the design of truthful mechanisms. For deterministic mechanisms, we obtain a negative result showing that a truthful \(\frac{2}{3}\)-approximation of these guarantees is impossible. We complement this by exhibiting a simple truthful algorithm that can achieve a constant approximation when the number of goods is bounded. Regarding randomized mechanisms, we also provide a negative result, under the restrictions that they are Pareto-efficient and satisfy certain symmetry requirements.
Research supported by the Basic Research Funding Program of the Athens University of Economics and Business. A version with all missing proofs is available at the authors’ webpages.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Asadpour, A., Saberi, A.: An approximation algorithm for max-min fair allocation of indivisible goods. In: ACM Symposium on Theory of Computing (STOC), pp. 114–121 (2007)
Brams, S.J., Taylor, A.D.: Fair Division: from Cake Cutting to Dispute Resolution. Cambrige University press (1986)
Chen, Y., Lai, J., Parkes, D., Procaccia, A.: Truth, justice, and cake cutting. In: AAAI, pp. 756–761 (2010)
Demko, S., Hill, T.: Equitable distribution of indivisible items. Mathematical Social Sciences 16, 145–158 (1988)
Hill, T.: Partitioning general probability measures. The Annals of Probability 15(2), 804–813 (1987)
Lenstra, J.K., Shmoys, D.B., Tardos, E.: Approximation algorithms for scheduling unrelated parallel machines. Mathematical Programming 46, 259–271 (1990)
Mossel, E., Tamuz, O.: Truthful Fair Division. In: Kontogiannis, S., Koutsoupias, E., Spirakis, P.G. (eds.) SAGT 2010. LNCS, vol. 6386, pp. 288–299. Springer, Heidelberg (2010)
Robertson, J.M., Webb, W.A.: Cake Cutting Algorithms: be fair if you can. AK Peters (1998)
Steinhaus, H.: The problem of fair division. Econometrica 16, 101–104 (1948)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2011 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Markakis, E., Psomas, CA. (2011). On Worst-Case Allocations in the Presence of Indivisible Goods. In: Chen, N., Elkind, E., Koutsoupias, E. (eds) Internet and Network Economics. WINE 2011. Lecture Notes in Computer Science, vol 7090. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-25510-6_24
Download citation
DOI: https://doi.org/10.1007/978-3-642-25510-6_24
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-25509-0
Online ISBN: 978-3-642-25510-6
eBook Packages: Computer ScienceComputer Science (R0)