Fair Division is Hard even for Amicable Agents

Indivisible goods cannot always be split fairly, but letting agents share a small number of goods can bring back both fairness and efficiency. How little sharing actually does the job is the question. Sandomirskiy and Segal-Halevi showed that envy-free, fractionally Pareto-optimal allocations with minimal sharing can be found efficiently for any fixed number of agents whose valuations are far from identical (the "amicable" case). In joint work with Aditi Sethia, I show that this does not scale: with many agents, the problem is NP-complete even at degeneracy one and with no sharing at all. I also give another way to enumerate consumption graphs with few sharings.