A Counterexample to EFX n ≥ 3 n\geq 3 Agents, m ≥ n + 5 m\geq n+5 Items, Monotone Valuations via SAT-Solving

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

Read A Counterexample to EFX n ≥ 3 n\geq 3 Agents, m ≥ n + 5 m\geq n+5 Items, Monotone Valuations via SAT-Solving by Hannaneh Akrami, Alexander Mayorov, Kurt Mehlhorn, Shreyas Srinivas, Christoph Weidenbach (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-18216.txt.

Introduction

Akrami, Mayorov, Mehlhorn, Srinivas, and Weidenbach present a counterexample to EFX fair division for three or more agents. An allocation is EFX when no agent envies another after removing any single good from the other's bundle. Using SAT solving, they show such allocations need not exist once goods reach five more than agents, while every three-agent, seven-good instance does admit one. The encoding is verified in Lean, and every three-agent instance admits at least one of two relaxations, tEFX or EF1 plus EEFX.

Catalog record

CREATORHannaneh Akrami, Alexander Mayorov, Kurt Mehlhorn, Shreyas Srinivas, Christoph Weidenbach
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE79283
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2604.18216

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

A Counterexample to EFX n ≥ 3 n\geq 3 Agents, m ≥ n + 5 m\geq n+5 Items, Monotone Valuations via SAT-Solving Hannaneh Akrami, Alexander Mayorov, Kurt Mehlhorn, Shreyas Srinivas, Christoph Weidenbach Abstract SAT solving has recently been proven effective in tackling open combinatorial problems. We contribute two additional results in the context of fair distribution of indivisible goods. Specifically, we demonstrate that EFX (envy-freeness up to any good) allocations always exist for three agents and seven goods, while we provide a counterexample for the case of n ≥ 3 n\geq 3 agents and m ≥ n + 5 m\geq n+5 goods. An allocation is EFX if no agent would envy the allocation of any other agent if any single item were to be removed from the other agent’s bundle of goods. Each agent’s preferences are modeled by a monotone valuation function on all potential bundles. After analyzing theoretical aspects of the problem, we encode the negation of the EFX instances into SAT. Satisfiability of the respective SAT formula constitute a counter-example to EFX, unsatisfiability of the respective SAT formula implies that EFX holds. The theoretical foundations of the encoding are proven correct in LEAN. For the three agents and seven goods case, we obtained a proof of unsatisfiability using SPASS-SAT of size about 30 GB in about 30 hours. It was shown to be correct by DRAT-trim. In the case of three agents and eight goods, SPASS-SAT computed satisfiability indicating a counterexample in the form of three specific agent valuations in about 20 hours. It was verified by probing all possible bundle assignments; the verification takes seconds. The extension of the counterexample to n ≥ 4 n\geq 4 agents and m ≥ n + 5 m\geq n+5 goods does not involve SAT-solving. This counterexample resolves, in the negative, one of the central questions in the theory of discrete fair division. 1 Introduction Fair division is a central problem lying at the intersection of computer science, economics, and social choice theory. Fairness considerations are central to the design of many social institutions and arise naturally in diverse allocation settings, including inheritance disputes, spectrum allocation, air traffic management, and public housing [ 14 ] . A set of m indivisible goods (or items) is to be allocated to a set of n agents. Each agent i has a monotone non-negative valuation v_{i} over sets of goods: v_{i}:2^{m}\mapsto\mathbb{R}_{\geq 0} with v_{i}(\emptyset)=0 and v_{i}(A)<v_{i}(B) if A\not=B and A\subset B . 1 1 1 It is no restriction to assume that distinct sets have distinct values for any agent. An allocation of the goods to the agents is a partition (X_{1},\ldots,X_{n}) of the set of goods, i.e., \cup_{i}X_{i}=[m] and X_{j}\cap X_{j}=\emptyset for i\not=j . We refer to X_{i} as the bundle assigned to agent i . An agent i envies an agent j if they value j ’s bundle higher than their own bundle, i.e., v_{i}(X_{j})>v_{i}(X_{i}) . In general, envy is unavoidable. Imagine two agents and one good that both like. The good has to be allocated to one of the agents, and the other will be envious. An agent i strongly envies an agent j if there is a good g in j ’s bundle such that i envies j ’s bundle even after the removal of g from it, i.e., v_{i}(X_{j}\setminus g)>v_{i}(X_{i}) for some g\in X_{j} . Is there always an allocation in which there is no strong envy? Such an allocation is called an EFX-allocation ( envy-free up to any good ). In his editorial (CACM April 2020) “An Answer to Fair Division’s Most Enigmatic Question”, Ariel Procaccia writes, Is an EFX allocation guaranteed to exist? This fundamental and deceptively accessible question is open. Note that EFX is a quite demanding notion. Imagine the following dialogue in a case of succession. Brother, I envy you. You are getting a house, a car, and a toothbrush, and I prefer your bundle over mine. However, this is fine. If I discount the toothbrush, I prefer my bundle over yours. What is known? It is known that EFX-allocations exist in some situations: • any number of agents and identical valuations [ 17 ] , • two agents and any number of goods [ 17 ] , • three agents, two general and one MMS-feasible 2 2 2 A valuation v is MMS-feasible if for all sets A , B , C , D of goods such that A\cap B=\emptyset=C\cap D and A\cup B=C\cup D , \min(v(A),v(B))\leq\max(v(C),v(D)) . In words, in two partitions (A,B) and (C,D) of the same set, the more valuable set in one partition has at least the value of the less valuable set in the other partition. The condition holds for additive valuations (a valuation v is additive if v(S)=\sum_{g\in S}v(\{\hskip 0.50003ptg\hskip 0.50003pt\}) ), but there are also very natural valuations where the condition does not hold. Imagine two pairs of shoes, A and B being one pair each, and C and D being the two left or the two right shoes, respectively. Then the MMS-condition will not hold. valuation [ 2 ] , • any number n of agents and at most n+3 goods [ 13 ] , in particular three agents and six goods, and • any number of agents and additive valuations specified by a (multi-)graph, where the vertices represent the agents, the edges represent the goods, and a good has positive value only for the endpoints of the corresponding edge [ 9 , 1 ] . Our Results: The smallest case that is open for unrestricted monotone valuations is three agents and seven goods. We show that an EFX-allocation always exists in this situation. We also show that this is no longer true for eight goods by exhibiting three valuations v_{0} , v_{1} , and v_{2} over eight goods for which there is no EFX-allocation. The construction extends to more agents. A counterexample exists as long as the number of goods is at least five more than the number of agents. Our Approach: We obtain our results by theoretical analysis and computer-assisted SAT solving. A first formulation of the problem for three agents and seven goods as a (un)-satisfiability problem leads to a CNF-formula with approximately 25000 variables and more than 6 million clauses. After some preliminary experiments investigating the impact of the number of goods and the eventual time to solve the respective CNF by a SAT solver, we decided to investigate properties of the problem, helping us to obtain smaller and easier-to-solve CNFs. We used the case of three agents and six goods for the analysis where EFX is known to exist [ 13 ] . This is the content of Section 2 for the applied theory and Section 3 for the encoding. The theoretical analysis reduced the formula to about 12000 variables and 2.5 million clauses for three agents and seven goods. Using SAT reduction techniques we, in particular unit (clauses of length one) removal and subsumption resolution, reduced the number of clauses further to about 700000. For example, fixing the item order for agent zero, Section 2.1 and Section 3.3 , results in unit clauses. Every clause containing the propositional literal of a unit clause can therefore be removed from the clause set

Read the complete text