No EFX allocation exists for tri-valued additive chore instances with n≥4 agents; EFX is incompatible with Pareto optimality for bi-valued positive-cost instances with n≥4; EFX exists for n=4.
Counterexamples to EFX for Submodular and Subadditive Valuations
2 Pith papers cite this work. Polarity classification is still indexing.
2
Pith papers citing it
abstract
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' 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.
fields
cs.GT 2years
2026 2verdicts
UNVERDICTED 2representative citing papers
Existence of EF1 and constant-ρ MMS allocations proven for submodular valuations.
citing papers explorer
-
EFX for Additive Chores: Nonexistence, Pareto Incompatibility, and Bi-Valued Existence
No EFX allocation exists for tri-valued additive chore instances with n≥4 agents; EFX is incompatible with Pareto optimality for bi-valued positive-cost instances with n≥4; EFX exists for n=4.
-
Simultaneous EF1 and approximate MMS allocations for submodular valuations
Existence of EF1 and constant-ρ MMS allocations proven for submodular valuations.