arXiv:2604.18216 · v4

EFX Need Not Exist

首次提交 2026-04-20 21:01

版本更新 2026-11-10 22:08

雷达观测 2026-11-11 13:08

摘要

The existence of envy-free up to any good (EFX) allocations has long been a central open problem in discrete fair division. We resolve it in the negative by constructing a counterexample with three agents and eight goods. The instance is invariant under every simultaneous permutation of the agents and their associated good types, and this symmetry yields a short, self-contained proof of nonexistence. The counterexample can be realized with weighted-coverage, and hence submodular, valuations, and it extends to $n$ agents and $m$ goods for all $n\ge3$ and $m\ge n+5$. For three agents, eight goods is the minimum: every instance with three agents and at most seven goods admits an EFX allocation under arbitrary monotone valuations. The proof relies on a new analysis, valid for any number of goods, of when the invariant-based technique of [AACGMM25] produces an EFX allocation. This analysis strictly extends the class of MMS-feasible valuations. We also give explicit bounds for approximate EFX. For subadditive valuations, $α$-EFX allocations need not exist for any $α>2^{-1/6}\approx0.891$, and for submodular valuations for any $α>0.958$. On the positive side, if two of three agents have arbitrary monotone valuations and the third has a subadditive valuation, there is always an allocation that is EFX for the first two and $2^{-1/3}$-EFX ($\approx0.794$) for the third. A first version of the counterexample and of the seven-goods result was obtained using SAT/SMT solving, and the insights it provided guided our classical, pen-and-paper proofs. We also describe the encoding, which we believe is a valuable tool in its own right: to our knowledge, this is the first use of SAT/SMT solving for EFX.

作者备注：Substantially revised and expanded version, consolidating arXiv:2604.18216v3 and arXiv:2605.06451 with further joint results