CMU-CS-05-144
Computer Science Department
School of Computer Science, Carnegie Mellon University



CMU-CS-05-144

Max-Min Fair Allocation of Indivisible Goods

Daniel Golovin

June 2005

CMU-CS-05-144.ps
CMU-CS-05-144.pdf


Keywords: Fair Allocation, Indivisibilities, Discrete Allocation, Approximation Algorithms, Generalized Assignment, Lexicographic Matchings


We consider the problem of fairly allocating a set of m indivisible goods to n agents, given the agents' utilities for each good. Fair allocations in this context are those maximizing the minimum utility received by any agent. We give hardness results and polynomial time approximation algorithms for several variants of this problem. Our main result is a bicriteria approximation in the model with additive utilities, in which a (1 − 1⁄k) fraction of the agents receive utility at least OPT/k, for any integer k. This result is obtained from rounding a suitable linear programming relaxation of the problem, and is the best possible result for our LP. We also give an O(√n) approximation for a special case with only two classes of goods, an (m − n + 1) approximation for instances with submodular utilities, and extreme inapproximability results for the most general model with monotone utilities.

22 pages


Return to: SCS Technical Report Collection
School of Computer Science homepage

This page maintained by reports@cs.cmu.edu