EFX Need Not Exist

arXiv:2604.18216 · cs.GT, cs.DS · Submitted 2026-04-20 · Read on arXiv

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

Where the paper says it

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.

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

Where the paper says it

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, they construct a counterexample for eight goods by showing no EFX allocation exists for monotone valuations. p. 1
Where the paper says it

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 construction extends to larger numbers of agents, yielding counterexamples whenever the number of goods exceeds the number of agents by at least five. p. 1
Where the paper says it

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.

Furthermore, since the existence of EFX allocations for monotone valuations is equivalent to their existence for submodular valuations, these counterexamples also apply to the class of submodular valuations. p. 1
Where the paper says it

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.

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

Where the paper says it

Theorem 3 For every fair division instance with three agents, at least one of the following holds: 1. a tEFX allocation exists; 2.

The authors detail a high-level algorithm that maintains certain invariants throughout its execution to either output a tEFX or EF1&EEFX allocation, or produce another partition with strictly larger potential.

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

Where the paper says it

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.

For the three-agent, seven-good case, the encoding involves approximately 25,000 variables and more than 6 million clauses. p. 2
Where the paper says it

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.

The authors also experimented with a modeling approach based on Satisfiability Modulo Theories (SMT), specifically SAT modulo Linear Real Arithmetic (LRA), which is significantly more compact for encoding the constraints. p. 3
Where the paper says it

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.

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

Where the paper says it

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.

The formalization in Lean is used to verify the correctness of the constructions and to provide a more formal footing for researchers in fair division. This includes defining structures for valuation functions and allocations, as well as a model of SAT formulas. p. 1
Where the paper says it

” 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].

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

Where the paper says it

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.

It is also noted that while Theorem 3 establishes that, for three agents, there always exists an allocation that is either tEFX or EF1&EEFX, it remains open whether either guarantee can always be achieved individually. p. 2
Where the paper says it

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.

The authors suspect that a counterexample to tEFX or EEFX&EF1, if it exists, will have many more items, suggesting an alternative way of identifying difficult instances would be useful. p. 2
Where the paper says it

a tEFX allocation exists; 2. an EF1&EEFX allocation exists.

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

Where the paper says it

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.

They close with some open problems and suggestions for further work. p. 3
Where the paper says it

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.

The authors have found their counterexample for eight items with the help of a SAT-solver and 20 hours of compute time. p. 3
Where the paper says it

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.

The verification of the counterexample takes only a few seconds. p. 2
Where the paper says it

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.

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

  1. 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, leveraging satisfiability yields a counterexample, while unsatisfiability establishes universal existence.

  2. 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.

  3. 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.

  4. 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