A single pile of identical goods can be mathematically impossible to divide fairly, even if everyone involved agrees exactly on what those goods are worth.
Fairness researchers have long searched for a way to split items so that no person feels another person got a better deal. This specific scenario uses submodular valuations to prove that a perfect split often cannot exist. Most people assume that if we all agree on the value of the items, there must be a logical way to share them that keeps everyone happy. The math proves that envy is a structural certainty in certain complex economies. This means policy makers cannot always rely on market-clearing logic to solve social disputes over resources.
Counterexamples to EFX for Submodular and Subadditive Valuations
arXiv · 2605.06451
The existence of EFX allocations is a fundamental question in fair division. In this paper, we construct a three-agent, eight-good instance with monotone subadditive valuations such that no allocation satisfies $\alpha$-EFX for any $\alpha > \frac{1}{\sqrt[6]{2}} \approx 0.89$. We also provide a closely related three-agent, eight-good instance with submodular (in fact weighted coverage) valuations for which no EFX allocation exists.A key feature of our construction is its symmetry: the agents' v