Fair Division: Perfect Allocation Possible Up to 7 Items, Impossible at 8
New math reveals the exact threshold where envy-free, efficient sharing breaks down.
Nicholas Teh's new paper on arXiv (2607.23367) tackles a core problem in fair division: when can two agents split indivisible goods in a way that is both envy-free up to one item (EF1) and Pareto optimal (PO)? The author proves that with strictly increasing valuations (each additional item adds strictly more value), the answer depends precisely on the number of goods. Every instance with seven or fewer goods guarantees an EF1+PO allocation, no submodularity assumption needed.
But at eight goods, everything breaks. Teh constructs an explicit counterexample with normalized, integer-valued, strictly increasing, and submodular valuations where every EF1 allocation is strictly Pareto dominated. This shows the threshold is exact. The paper also strengthens known NP-hardness results for three agents, proving that deciding EF1+PO existence remains hard even when zero marginals are restricted to just eight agent-good pairs (all for one agent). These findings provide clear boundaries for algorithm designers building fair resource allocation systems.
- Two agents with 7 or fewer items always have an EF1+PO allocation, with no submodularity needed.
- Eight goods are necessary and sufficient for a two-agent counterexample with strictly increasing, submodular valuations.
- Three-agent EF1+PO decision remains NP-hard even when zero marginals are confined to eight fixed agent-good pairs.
Why It Matters
Settles a fundamental boundary for algorithmic fairness, guiding resource allocation systems in multi-agent environments.