
CMUCS05144
Computer Science Department
School of Computer Science, Carnegie Mellon University
CMUCS05144
MaxMin Fair Allocation of Indivisible Goods
Daniel Golovin
June 2005
CMUCS05144.ps
CMUCS05144.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
