Counterexamples to EFX for Submodular and Subadditive Valuations
This resolves a fundamental open question in fair division by proving that EFX allocations are not guaranteed for submodular and subadditive valuations, which are important classes in economics and computer science.
The paper constructs counterexamples showing that EFX allocations do not exist for submodular and subadditive valuations, even with symmetric agents. Specifically, for subadditive valuations, no α-EFX allocation exists for α > 0.89, and for submodular valuations, no EFX allocation exists.
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 $α$-EFX for any $α> \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' valuations are identical up to a relabeling of the goods. Thus, EFX can fail even when agents differ only in how the goods are labeled. This symmetry makes the counterexamples compact and human-verifiable, yielding simple combinatorial obstructions to the existence of EFX.