EFX Need Not Exist
summary
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…
In short
The paper investigates whether EFX allocations exist in discrete fair division problems. It demonstrates that EFX allocations are not guaranteed for instances with three agents and eight or more goods, providing counterexamples. However, it proves that for three agents and seven goods, a relaxation of the EFX allocation (tEFX or EF1&EEFX) always exists.
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 used across episodes
This episode discusses
The paper
EFX Need Not Exist · Read on arXiv
Max Planck Institute for Informatics Saarland Informatics Campus Germany · CISPA Helmholtz Center for Information Security Saarbrücken CISPA Helmholtz Center for Information Security
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.
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.
More episodes
- 2511.04088-Efficient and rate-optimal list-decoding in the presence of minimal feedback
- 2511.17264-Notes on Stack Machines and Quantum Stack Machines
- 2601.15318-On the closest balanced game
- 1905.10490-Finding new routes for integrating Multi-Agent Systems using Apache Camel
- 2401.10816-Co-Pilot for Health: Personalized Algorithmic AI Nudging to Improve Health Outcomes
- 2503.01935-MultiAgentBench: Evaluating the Collaboration and Competition of LLM agents
- 2509.19405-Improving Outdoor Multi-cell Fingerprinting-based Positioning via Mobile Data Augmentation
- 2602.15198-Colosseum: Auditing Collusion in Cooperative Multi-Agent Systems
- 2602.21456-Revisiting Text Ranking in Deep Research
- 2606.02883-LLM-Assisted Reranking to Operationalize Nuanced Objectives in Recommender Systems