A Counterexample to EFX $n \ge 3$ Agents, $m \ge n + 5$ Items, Submodular Valuations via SAT-Solving

Hannaneh Akrami, Alexander Mayorov, Kurt Mehlhorn, Shreyas Srinivas, Christoph WeidenbacharXiv 2026 · arXiv

TL;DR

This paper settles a long-standing open problem in economic theory and computer science by proving that EFX (envy-free up to any good) allocations of indivisible items are not guaranteed to exist. Using advanced SAT-solving techniques, the authors discovered the first-ever counterexample consisting of 3 agents and 8 goods, while simultaneously proving that an EFX allocation is always guaranteed if there are 3 agents and 7 or fewer goods.

What Problem Does This Paper Address?

The paper tackles a fundamental question in discrete fair division: how do we fairly divide a set of indivisible goods (like houses, cars, or tasks) among a group of agents?

A classic goal is envy-freeness, where no agent prefers someone else's bundle over their own. Because goods are indivisible, perfect envy-freeness is often impossible (e.g., two people fighting over a single diamond). To handle this, researchers introduced relaxations. The most famous is EF1 (envy-free up to one good), where envy can be eliminated by removing the most valuable good from the envied agent's bundle.

A stricter, more desirable relaxation is EFX (envy-free up to any good). Under EFX, envy must vanish even if you remove the least valuable good from the envied agent's bundle. For years, determining whether an EFX allocation always exists for general, monotone valuations was considered one of the most enigmatic open problems in fair division. This paper finally provides an answer.

Methods

The authors resolved this theoretical question using a computer-assisted approach: SAT-solving.

  1. The Negation Trick: Instead of trying to prove EFX exists, they encoded the negation of EFX existence into a propositional logic formula (CNF). If the formula is satisfiable (SAT), the solver outputs a model that serves as a concrete counterexample. If it is unsatisfiable (UNSAT), it mathematically proves that an EFX allocation always exists.
  2. Search Space Reduction: A naive encoding for 3 agents and 7 goods yields over 6 million clauses—too massive for standard solvers to handle efficiently. The authors introduced crucial domain-specific optimizations:
  3. Item Ordering: They fixed the item preferences for Agent Zero to break symmetries.
  4. Leveled Valuations: They proved that the values of very large subsets are irrelevant to the EFX condition, allowing them to flatten the valuation space.
  5. Verification Pipeline: To ensure absolute correctness, the authors formally verified their SAT encoding logic using the Lean theorem prover. When the solver returned an UNSAT result, the proof was verified using DRAT-trim. When it returned a SAT result (the counterexample), the resulting valuations were double-checked using independent C++ scripts.

Datasets

This paper does not use traditional empirical datasets. Instead, the authors generated synthetic mathematical instances by translating fair division constraints into CNF formulas. The resulting SAT models and the formal Lean proofs have been made publicly available as open-source artifacts.

Key Insights and Ideas

  • The 7-vs-8 Sharp Boundary: For three agents, there is a strict phase transition. At 7 goods, an EFX allocation is mathematically guaranteed to exist. At 8 goods, the guarantee completely breaks down.
  • Monotone to Submodular Equivalence: The authors highlight a powerful mathematical property (Proposition 1): any monotonic total ordering over subsets can be scaled into a submodular valuation function. This means their counterexample for general monotone valuations automatically applies to the narrower, highly studied class of submodular valuations.
  • The Power of Computer-Aided Social Choice: The paper demonstrates that when human intuition stalls on complex combinatorial problems in economics, framing the problem as a constraint-satisfaction task for modern SAT solvers can break the deadlock.

Key Results

  • Theorem 1 (Universal Existence): For 3 agents and 7 goods, an EFX allocation always exists. The SAT solver proved this instance UNSAT in approximately 30 hours using SPASS-SAT.
  • Theorem 2 (The Counterexample): For $n \ge 3$ agents and $m \ge n + 5$ goods, an EFX allocation may fail to exist. The solver found a satisfying assignment (the counterexample) for 3 agents and 8 goods in roughly 20 hours.
  • Theorem 3 (Positive Relaxations): Recognizing that EFX can fail, the authors proved that for 3 agents and any number of goods, you can always achieve at least one of two strong alternative fairness relaxations: tEFX (envy-free up to transferring any good) or a combination of EF1 & EEFX (Epistemic EFX).

Limitations and Future Work

While the paper successfully provides a counterexample, the resulting valuation functions are incredibly intricate and non-intuitive, making them difficult for a human to interpret without a computer. (Though the authors note that subsequent work by other researchers has since found simpler, human-verifiable counterexamples inspired by this discovery).

Key open questions remain:

  1. Does an EFX allocation always exist if agents have strictly additive valuations (where the value of a bundle is exactly the sum of the values of its individual items) for 4 or more agents?
  2. What happens in the gap where the number of goods $m = n + 4$? (Existence is known for $m \le n + 3$ and non-existence is now proven for $m \ge n + 5$).

Summary updated

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.
BibTeX
@misc{akrami2026counterexample,
  author = {Hannaneh Akrami and Alexander Mayorov and Kurt Mehlhorn and Shreyas Srinivas and Christoph Weidenbach},
  title = {{A Counterexample to EFX $n \textbackslash\{\}ge 3$ Agents, $m \textbackslash\{\}ge n + 5$ Items, Submodular Valuations via SAT-Solving}},
  year = {2026},
  eprint = {2604.18216},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2604.18216},
}

Loading related content...

Figure