Computer Science Department
School of Computer Science, Carnegie Mellon University
Max-Min Fair Allocation of Indivisible Goods
Daniel Golovin
June 2005
CMU-CS-05-144.ps
CMU-CS-05-144.pdf
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 This page maintained by [email protected]
School of Computer Science homepage