On Regular and Approximately Fair Allocations of Indivisible Goods

摘要

An active stream of research is devoted to the design of polynomial approximation algorithms for the fair allocation of indivisible goods. Central to this field is the MAXMIN AL-LOCATION problem, for which there is a significant gap between known approximation and inapproximability results. Closing this gap is a stimulating challenge. To this end, we consider a regular version of MAXMIN AL-LOCATION where each agent must receive exactly k goods, for a given integer k. We call this problem k-DIVISION. The analysis of this problem allows us to highlight two interesting features of the classical MAXMIN ALLOCATION problem. First, we show a close connection of the problem with matroid theory. This connection provides us an exact algorithm for a special case of k-DIVISION and a 1/k-approximation algorithm for general inputs. Moreover, we show that the difficulty of the MAXMIN ALLOCATION may be caught by an apparently simpler problem, namely the k-DIVISION problem in which an agent's utility for a single good can only take one value out of three.