3/4/2026
Researchers studying how to fairly divide indivisible items — like paintings or laptops — have spent nearly a decade investigating a deceptively simple question: can allocations always be made envy-free up to any item (EFX)? While major breakthroughs from Illinois researchers helped establish when this level of fairness is possible, recent work shows that for three people with complex preferences, EFX allocations do not always exist. Together, these results define the boundary of what fairness can realistically achieve when items cannot be divided.
Written by
Dividing things fairly sounds simple — until you actually try to do it. If three people are sharing a cake, the solution is simple: cut it into three equal slices and everyone gets the same amount. Problem solved. But now imagine they are splitting things that cannot be cut into pieces — like a laptop, a book or a painting. You cannot slice a laptop into thirds or break a painting into equal shares. These are called indivisible items, and once you are dealing with them, dividing them “fairly” becomes much more complicated.
When items can be split in any way you want, a gold-standard notion of fairness called envy- freeness (EF) is usually possible — meaning no one wishes they had someone else’s share. With indivisible items, however, this kind of fairness can completely break down. Imagine Alice and Bob trying to divide three paintings, and suppose they both value all three equally. No matter how the paintings are divided, one person will end up with strictly fewer paintings than the other. The person with fewer paintings will naturally wish they had the other’s bundle, making exact envy-freeness impossible.
This impossibility is not a failure of negotiation but a mathematical reality! Once researchers realized that achieving envy-freeness (EF) might be impossible, the natural question became: what is a closest version of EF that can actually be achieved? Among many candidates, one notion stood out: envy-freeness up to any item (EFX).
The idea is remarkably simple. An allocation is called EFX if no one would feel envious of someone else’s share after removing any single item from it. Here’s how it works: imagine looking at someone else’s set of items, and asking yourself: “If I take away one of their items, would I still want their share more than mine?” If the answer is no for every item, then the allocation is EFX. Going back to the painting example, we can give two paintings to Alice and one to Bob (or the other way around). Since all the paintings are equally valued, Bob would not feel envious once one of Alice’s paintings is removed — so this allocation is EFX.
This definition is so clear and easy to understand that even a high-schooler can grasp it. That’s what makes EFX feel so fundamental: it’s simple to explain, intuitive to think about, and convincing once you see it. But unlike the simple painting example, the problem becomes much harder when everyone values items differently.
The original problem was introduced in 2016 by Ioannis Caragiannis, David Kurokawa, Hervé Moulin, Ariel Procaccia, Nisarg Shah, and Junxing Wang in their influential paper “Unreasonable Fairness of Nash Welfare”, which was later honored with the 2023 Kalai Prize. In their setup, they considered simple preferences (called additive valuations): every person has their own value for each item, and the total value of a set of items is just the sum of the individual values. In the same paper, the authors noted that “despite significant effort,” they were unable to determine whether EFX allocations always exist.
Soon after, Hervé Moulin — one of the pioneers of modern fair-division theory — remarked in Fair Division in the Internet Age, “even after extensive brainstorming and numerous experiments”, the question of whether EFX allocations always exist remained elusive, even with just three people (called agents in the research literature). The first glimmer of progress came in 2018, when Benjamin Plaut and Tim Roughgarden showed that EFX allocations do exist for two agents, even under general valuations, where the value of a set of items can be much more complex than just adding up individual item values — allowing for complementarities and substitutes. However, the same paper emphasized that extending this result to three agents—even with simple additive preferences— seemed highly nontrivial.
That barrier was finally broken in 2020, when ISE professors Bhaskar Ray Chaudhury and Jugal Garg, together with Kurt Mehlhorn, proved that EFX allocations do exist for three agents in the simple additive setting. This result overturned the growing belief that EFX might fail beyond two agents and marked a defining moment in the field—their work was honored with the Exemplary Paper in Theory Track and Best Paper with Student Lead Author awards at the 21st ACM Conference on Economics and Computation (EC), a flagship conference in the field.
In the same year, in another major advance, Bhaskar, along with Kavitha Telikpalli, Kurt Mehlhorn, and Alkmini Sgouritsa, showed that even when agents have general valuations, an almost EFX allocation always exists. In particular, one can guarantee EFX if a small number of items are left unallocated — think of these items as being donated to charity. In 2023, Bhaskar and Jugal, together with Hannaneh Akrami, Noga Alon, Kurt Mehlhorn, and Ruta Mehta, obtained another important result, proving that an EFX allocation always exist when two agents have general preferences and one agent has simple preferences. Together, these results gave the community renewed hope that a complete positive answer might still be possible.
What followed was an explosion of activity. Over 1000 papers have explored EFX under special assumptions, restricted types of preferences and different algorithmic approaches. Remarkably, the definition’s simplicity has made the topic unusually accessible: papers on EFX authored by high-school students have even appeared at top AI conferences — a testament to how approachable the question is, even as it resisted complete resolution by experts.
Very recently, the story came full circle. Alexander Mayorov, Kurt Mehlhorn, Shreyas Srinivas, and Christoph Weidenbach used modern SAT solvers to show that EFX allocations do not always exist for three agents when all of them have general valuations. This settles the problem for general preferences and strikingly confirms what the Illinois work had hinted at six years earlier: the guarantees found by Bhaskar and Jugal are the limit of what can be achieved. Beyond that boundary, these fairness guarantees break down.
In hindsight, the EFX journey is not just a story about solving a hard problem — it is about understanding its limits. What began as an easy-to-state question — simple enough to discuss in a high-school classroom — grew into a decade-long exploration that mapped the exact frontier between where fairness is possible and where it breaks down. Few results stand the test of time so clearly.
Jugal Garg is an Associate Professor in the Department of Industrial and Enterprise Systems Engineering in the Grainger College of Engineering at the University of Illinois Urbana-Champaign. He is also affiliated with The Siebel School of Computing and Data Science. His research lies at the intersection of algorithms, economics, and game theory, with a focus on computational aspects of markets, fair division and resource allocation.
Bhaskar Ray Chaudhury is an Assistant Professor in the Department of Industrial and Enterprise Systems Engineering at the University of Illinois Urbana-Champaign. He is also affiliated with The Siebel School of Computing and Data Science. His research focuses on algorithmic game theory, data economics and the computational foundations of fair and efficient resource allocation.