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

A research team from multiple institutions has used computational methods to resolve one of the central open questions in discrete fair division theory. Their paper, 'A Counterexample to EFX; n ≥ 3 Agents, m ≥ n + 5 Items, Monotone Valuations; via SAT-Solving,' demonstrates that the EFX (envy-freeness up to any good) property—where no agent envies another's allocation after removing any single item—doesn't always exist for three or more agents with at least n+5 items. This finding settles a long-standing theoretical question in the negative.

The researchers employed SAT-solving, encoding the negation of EFX instances into Boolean satisfiability problems. For the three-agent, seven-good case, they generated a 30GB proof of unsatisfiability using SPASS-SAT over 30 hours, verified by DRAT-trim. For three agents and eight goods, SPASS-SAT found satisfiability in 20 hours, indicating a counterexample with specific agent valuations. The team extended this counterexample to n≥4 agents without additional SAT-solving, providing a complete theoretical resolution.

This work represents a significant milestone in computational game theory, demonstrating how automated reasoning tools like SAT-solvers can tackle complex combinatorial problems that resist traditional mathematical approaches. The verification process included both computational proofs and manual verification of all possible bundle assignments, ensuring the counterexample's validity. The research opens new questions about what minimal conditions might guarantee EFX allocations while providing definitive boundaries for when they cannot be guaranteed.