Fair Division Is Hard Even for Amicable Agents

We consider the problem of distributing a collection of indivisible objects among agents in a manner that satisfies some desirable notions of fairness and efficiency. We allow agents to “share” goods in order to achieve efficiency and fairness goals which may be otherwise impossible to attain. In this context, our goal is to find allocations that minimize the “amount of sharing”. We follow up on recent work demonstrating that finding fair allocations with minimum sharing is tractable when valuations are non-degenerate, a notion which captures scenarios that are “far from identical”. This result holds for any fixed number of agents. We show that the usefulness of non-degeneracy does not scale to the setting of many agents. In particular, we demonstrate that the problem of finding fractionally Pareto optimal and envy-free allocations is NP-complete even for instances with constant degeneracy and no sharing. We also demonstrate an alterate approach to enumerating distinct consumption graphs for allocations with a small number of sharings.