Max-min fair allocation of indivisible goods

Abstract: "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([square root of 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.