EFX Need Not Exist
Listen
Radio episode about this paper
Transcript
Introduction to the show: ident: Computer Science. The day in computer science: software, systems and theory on arXiv.
Tom: We're looking at the paper: "EFX Need Not Exist".
Jane: Here's the gist of the paper. The existence of EFX allocations is a central open problem in discrete fair division, and this paper resolves it by providing a counterexample to EFX allocations for agents with monotone valuations, which immediately implies a counterexample for submodular valuations.
Tom: Counterexamples to EFX Existence The authors show that EFX allocations need not exist for instances with three agents and seven goods, while every instance with three agents and seven goods admits an EFX allocation.
Jane: Specifically, they demonstrate that EFX allocations are guaranteed to exist when all agents have monotone valuations and the number of goods satisfies m ≤ n+3.
Tom: In contrast, they construct a counterexample for eight goods by showing no EFX allocation exists for monotone valuations.
Paper summary: Jane: So we’ve gone from a big open question about EFX allocations to concrete counterexamples for eight items with monotone valuations. What does this mean for the fairness community overall?
Tom: It means that when you're designing allocation algorithms, you can't just assume that the envy-free up to any good property will hold universally across all possible inputs.
Lu: The work pushes the theoretical understanding forward by providing a formal structure and tools, using things like non-degenerate instances, to help researchers understand where EFX allocations are likely to fail or succeed.
Meng: For us in production, it’s a warning sign. If we are dealing with scenarios where the number of items is significantly larger than the number of agents, we should expect that a perfect EFX allocation might be computationally infeasible to find at all.
Jane: The paper also settles the three agent case by showing that for those specific conditions, you can always guarantee either a tEFX or an EF1 and EEFX allocation exists.
Tom: That’s the key finding: we trade perfect fairness for something else guaranteed in certain constrained settings, and that's a valuable result.
Lu: The next steps involve exploring whether these guarantees can be strengthened, perhaps by generalizing the notion of feasibility beyond MMS to ensure existence more broadly across different valuation types.
Meng: I’m curious about how much effort it takes to actually implement those tEFX or EF1 and EEFX allocations when they exist for three agents and seven goods.
Jane: That implementation detail is what researchers will have to tackle next, trying to make sure the algorithm actually finds that allocation efficiently in practice.
Conclusion: Tom: So, this paper is called "EFX Need Not Exist," and it's basically saying that for certain setups, those EFX allocations just might not actually exist at all.
Jane: Right, so we're talking about a central open problem in fair division—can we always find an allocation that satisfies EFX conditions—and this paper shows some cases where the answer is no.
Lu: The authors found a counterexample for agents with monotone valuations, which immediately means it also fails for submodular valuations.
Meng: A counterexample for eight goods and monotone valuations? That’s a solid piece of evidence that you can't just assume EFX will always work when you have many items.
Tom: It sounds like they built something using a SAT solver, which is pretty heavy lifting to find those kinds of failures.
Jane: They also showed some positive guarantees, though, for three agents and seven goods, where you're guaranteed to get either a tEFX or an EF1 and EEFX allocation.
Lu: That shows the landscape isn't completely dark; there are always some ways to relax the condition when you stick with a small number of agents.
Meng: But they also pointed out that for eight goods, if you go above three agents, you can find instances where no EFX allocation exists at all.
Tom: So the main thing is that EFX isn't guaranteed across the board; it depends heavily on how many items and how many agents you have.
Jane: Exactly. It shifts the focus from just finding *an* allocation to understanding exactly *when* those perfect fairness conditions are impossible to meet.
Lu: This opens up a lot of theoretical work about what kind of valuation structure is required for EFX to even be possible.
Max Planck Institute for Informatics Saarland Informatics Campus Germany · CISPA Helmholtz Center for Information Security Saarbrücken CISPA Helmholtz Center for Information Security
cs.GT, cs.DS
Submitted: 2026-04-20
Updated: 2026-11-10
Comments: Substantially revised and expanded version, consolidating arXiv:2604.18216v3 and arXiv:2605.06451 with further joint results
License: http://creativecommons.org/licenses/by/4.0/
Importance score: 95/100
The gist: The existence of EFX allocations is a central open problem in discrete fair division, and this paper resolves it by providing a counterexample to EFX allocations for agents with monotone valuations…
Key concepts
- EFX Allocations
- These are specific fair division allocations being studied in this paper. The central problem is determining if such an allocation can always be found given certain conditions on the agents' preferences and the goods available.
- Monotone Valuations
- This refers to a type of preference where an agent's valuation (their worth of a good) consistently increases as they receive more of that good. The paper shows that EFX allocations are guaranteed to exist when all agents have this property and the number of goods is not too large.
- Relaxations (tEFX or EF1&EEFX)
- Since finding a true EFX allocation is hard, the paper proves that for three agents, at least one of two related, easier-to-find allocations—tEFX or EF1&EEFX—must always exist. This provides a positive guarantee even when the original EFX allocation does not.
- SAT Encoding
- The authors use Boolean Satisfiability (SAT) problems to prove their results. They turn the question of whether an EFX allocation exists into a giant logical puzzle, where finding a solution proves existence or non-existence of the allocation.
Terminology
Summary
The existence of EFX allocations is a central open problem in discrete fair division, and this paper resolves it by providing a counterexample to EFX allocations for agents with monotone valuations, which immediately implies a counterexample for submodular valuations. p. 0 A Counterexample to EFX
n ≥ 3 Agents, m ≥ n+5 Items, Submodular Valuations
via SAT-Solving
Hannaneh Akrami1,4, Alexander Mayorov1,3, Kurt Mehlhorn1
, Shreyas Srinivas2
, and
Christoph Weidenbach1
1Max Planck Institute for Informatics, Saarland Informatics Campus, Saarbrücken,
Germany
2CISPA Helmholtz Center for Information Security, Stuhlsatzenhaus 5, Saarbrücken,
Germany
3Saarbrücken Graduate School for Computer Science
4Hertz Chair for Algorithms and Optimization, University of Bonn
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.Where the paper says it
Counterexamples to EFX Existence
The authors show that EFX allocations need not exist for instances with three agents and seven goods, while every instance with three agents and seven goods admits an EFX allocation. Specifically, they demonstrate that EFX allocations are guaranteed to exist when all agents have monotone valuations and the number of goods satisfies m ≤ n+3. p. 1 Under the minimal assumption that valuations are monotone, only a few positive results are known. In
particular, EFX allocations are guaranteed to exist when all agents have identical valuations [PR20]—which
in particular implies existence for two agents2—and when the number of goods satisfies m ≤ n+3 [Mah23]. In contrast, we show that this guarantee breaks down already for eight goods by constructing three
valuations v0, v1, and v2 over eight goods for which no EFX allocation exists. This is the first-ever
counterexample to EFX existence for monotone valuations. This is the first-ever
counterexample to EFX existence for monotone valuations. This construction extends to larger numbers
of agents, yielding counterexamples whenever the number of goods exceeds the number of agents by at least
five. This construction extends to larger numbers
of agents, yielding counterexamples whenever the number of goods exceeds the number of agents by at least
five. Moreover, since the existence of EFX allocations for monotone valuations is equivalent to their existence
for submodular valuations (see Corollary 1), these counterexamples also apply to the class of submodular
valuations.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Relaxations of EFX Guarantees
The paper establishes positive guarantees for fair allocations with three agents and an arbitrary number of goods, proving that every instance with three agents and monotone valuations admits at least one of two natural relaxations of EFX: tEFX or EF1&EEFX. This is shown by Theorem 3, which states that for every fair division instance with three agents, at least one of the following holds: a tEFX allocation exists; an EF1&EEFX allocation exists. p. 2 Theorem 3 For every fair division instance with three agents, at least one of the following holds:
1. a tEFX allocation exists;
2.Where the paper says it
Techniques for Encoding and Verification
The results are obtained through a combination of theoretical analysis and computer-assisted SAT solving. The negation of EFX existence is encoded as a SAT instance, where satisfiability yields a counterexample, while unsatisfiability establishes universal existence. p. 0 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. We encode the negation of EFX existence as a SAT instance: satisfiability yields a counterexample, while
unsatisfiability establishes universal existence. A direct encoding of the three-agent, seven-good case as a
satisfiability problem yields a CNF formula with approximately 25,000 variables and more than 6 million
clauses. In addition to the SAT-based formulation, we also experimented with a modeling approach based on
Satisfiability Modulo Theories (SMT), more specifically SAT modulo Linear Real Arithmetic (LRA), see
Section 10. This encoding is significantly more compact, consisting of only a few thousand constraints.Where the paper says it
Where the paper says it
Where the paper says it
Theoretical Foundations and Formalization
The paper provides theoretical foundations for EFX that will improve the encoding of EFX in SAT, focusing on reducing the size of the CNF and runtime. They introduce concepts such as non-degenerate instances, where valuations are non-degenerate, and leveled valuations. p. 5 A formal development can be found in
the LEAN companion material. 2 Leveled Valuations
Recall that in a non-degenerate instance with seven items, no EFX allocation allocates more than five items
to any agent. ”
Despite a substantial body of work on EFX in recent years, the existence of EFX allocations for m
indivisible goods and n agents remains poorly understood. Positive existence results are currently known only
in highly restricted settings, such as instances with a small number of agents [CGM24, BCFF22, AAC+25a]
or special classes of valuation functions [HPPS20, ABFR+21, CFKS23, AAMM26].Where the paper says it
Where the paper says it
Open Problems
The paper concludes by suggesting several open problems and directions for further work. These include questions about whether EFX allocations exist for four or more agents, whether they exist for additive valuations, and the possibility of replacing the MMS-feasible notion with a more general one to guarantee existence. p. 1 For three agents, existence has been established only under additional structural assumptions on the
valuations, namely when at least one agent’s valuation belongs to the MMS-feasibility class, a superclass of
additive valuations [AAC+25a]. Beyond these settings, the problem remains widely open: for n ≥ 4, it is not
known whether EFX allocations always exist even when all agents have additive valuations. Our counterexample does not rule out the existence of either tEFX or EF1&EEFX allocations. In
Theorem 3, we show that for every instance with three agents, at least one of these two relaxed fairness
guarantees can always be achieved. a tEFX allocation exists;
2. an EF1&EEFX allocation exists.Where the paper says it
Where the paper says it
Where the paper says it
Conclusion
The work concludes by summarizing the findings and pointing towards the next steps in the research trajectory. The authors have shown that EFX exists for three agents and seven goods but does not always exist for three agents and eight or more goods, proving the existence of relaxations of EFX allocation for three agents. p. 1 The smallest open case for (unrestricted) monotone valuations is three agents and seven goods. We show
that in this setting an EFX allocation always exists. In Section 9, we formalize the constructions from Sections 3 and 4 in the Lean theorem prover [MU21]. Our work rises many interesting problems and suggests follow up work which we discuss in Section 12. We then considered the case of three agents and eight goods. In this setting, SPASS-SAT found a
satisfying assignment in approximately 20 hours, which was independently confirmed by CaDiCaL. DRAT-trim is a significantly smaller and simpler piece of software that has
been widely used to certify results in the annual SAT competition over many years. In the case of satisfying
assignments, correctness is checked using lightweight, EFX-specific verification tools.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.
Improvements for AI systems
-
SAT Encoding for EFX Verification: The system can be improved by utilizing the encoding of
the negation of EFX existence as a SAT instance
to systematically search for counterexamples when an allocation is not found, leveragingsatisfiability yields a counterexample, while unsatisfiability establishes universal existence.
-
SMT Encoding for Existence Proofs: The system can be enhanced by employing the Linear Real Arithmetic (LRA) formulation described in Section 4.4 to prove the existence of EFX allocations by checking the
unsatisfiability of Positivity and Monotonicity and Item Order and not EFX.
-
Verification via Formal Methods: The improved system can incorporate formal verification using Lean to check if a given allocation is EFX-feasible, as described in Section 9.2, which involves proving that
if our SAT formula is not satisfiable, then there is no non-degenerate, levelled-valuation, item-ordered, skeletal fair division instance that violates the EFX property.
-
Relaxation Guarantee Implementation: The system can be equipped with an algorithm based on [PR20] to find allocations satisfying relaxations of EFX, specifically implementing the
algorithm PR(X, v)
which outputs a partition that is either tEFX or EF1&EEFX feasible under certain conditions.
Abstract
The existence of envy-free up to any good (EFX) allocations has long been a central open problem in discrete fair division. We resolve it in the negative by constructing a counterexample with three agents and eight goods. The instance is invariant under every simultaneous permutation of the agents and their associated good types, and this symmetry yields a short, self-contained proof of nonexistence. The counterexample can be realized with weighted-coverage, and hence submodular, valuations, and it extends to n agents and m goods for all n at least3 and m at least n+5. For three agents, eight goods is the minimum: every instance with three agents and at most seven goods admits an EFX allocation under arbitrary monotone valuations. The proof relies on a new analysis, valid for any number of goods, of when the invariant-based technique of [AACGMM25] produces an EFX allocation. This analysis strictly extends the class of MMS-feasible valuations. We also give explicit bounds for approximate EFX. For subadditive valuations, α-EFX allocations need not exist for any α>2-1/6 about0.891, and for submodular valuations for any α>0.958. On the positive side, if two of three agents have arbitrary monotone valuations and the third has a subadditive valuation, there is always an allocation that is EFX for the first two and 2-1/3-EFX (about0.794) for the third. A first version of the counterexample and of the seven-goods result was obtained using SAT/SMT solving, and the insights it provided guided our classical, pen-and-paper proofs. We also describe the encoding, which we believe is a valuable tool in its own right: to our knowledge, this is the first use of SAT/SMT solving for EFX.
Related papers
- How Many Votes is a Lie Worth? Measuring Strategyproofness through Resource Augmentation
- Effective Horizons for Prophet Inequalities with Discounted I.I.D. Rewards
- Truthful-in-Expectation Mechanism with Constant Maximin-Share Guarantee
- The Power of Recruiting the Smaller Side: Two Additional Traders Suffice in Two-Sided Markets
- From signaling to interviews in random matching markets
- Optimizing Social Utility in Sequential Experiments