EFX allocations exist for multigraph instances under cancelable valuations and can be computed in polynomial time.
A Counterexample to EFX $n \ge 3$ Agents, $m \ge n + 5$ Items, Submodular Valuations via SAT-Solving
5 Pith papers cite this work. Polarity classification is still indexing.
5
Pith papers citing it
abstract
The existence of EFX allocations is a central open problem in discrete fair division. An allocation is EFX (envy-free up to any good) if no agent envies another agent after the removal of any single good from the other agent's bundle. We resolve this longstanding question by providing the \textbf{first-ever counterexample} to the existence of EFX allocations for agents with monotone valuations, which in turn immediately implies a counterexample for submodular valuations. Specifically, we show that EFX allocations need not exist for instances with $n \ge 3$ agents and $m \ge n+5$ goods. In contrast, we prove that every instance with three agents and seven goods admits an EFX allocation. Both results are obtained via SAT solving. We encode the negation of EFX existence as a SAT instance: satisfiability yields a counterexample, while unsatisfiability establishes universal existence. The correctness of the encoding is formally verified in Lean. Finally, we establish positive guarantees for fair allocations with three agents and an arbitrary number of goods. Although EFX allocations may fail to exist, we prove that every instance with three agents and monotone valuations admits at least one of two natural relaxations of EFX: tEFX, or EF1 and EEFX.
years
2026 5verdicts
UNVERDICTED 5representative citing papers
Introduces EPMMS and shows 4/5-EPMMS exists for additive valuations, full EPMMS (and EGMMS) for bivalued valuations, plus existence for three additive agents or two agent types.
Existence of epistemic EF1 partitions is shown for arbitrary additive valuations over abstract independence structures, plus EF1 for common valuations when agent count meets arboricity, with algorithms and matroid connections.
Existence of EF1 and constant-ρ MMS allocations proven for submodular valuations.
Simpler poly-time constructions for EF2X/EF3X and improved √2/2-EFX and 2/3-EFX approximations for monotone and additive valuations in restricted hypergraphs.
citing papers explorer
-
EFX Allocations Exist on Multi-Graphs
EFX allocations exist for multigraph instances under cancelable valuations and can be computed in polynomial time.
-
Epistemic Pairwise Maximin Share
Introduces EPMMS and shows 4/5-EPMMS exists for additive valuations, full EPMMS (and EGMMS) for bivalued valuations, plus existence for three additive agents or two agent types.
-
Epistemic fair division of independence structures
Existence of epistemic EF1 partitions is shown for arbitrary additive valuations over abstract independence structures, plus EF1 for common valuations when agent count meets arboricity, with algorithms and matroid connections.
-
Simultaneous EF1 and approximate MMS allocations for submodular valuations
Existence of EF1 and constant-ρ MMS allocations proven for submodular valuations.
-
Almost EFX in Hypergraphs
Simpler poly-time constructions for EF2X/EF3X and improved √2/2-EFX and 2/3-EFX approximations for monotone and additive valuations in restricted hypergraphs.