Envy that any single item would cure

A cake can be cut anywhere, and every classical guarantee of fair cutting depends on that freedom. Indivisible items take it away. Two people and one painting cannot be made envy-free: whoever does not get the painting envies whoever does, and no division of one thing into whole things helps. So fair division of items weakened the standard: an allocation is envy-free up to one item — EF1 — if, whenever one person envies another, removing some single item from the envied bundle would cure the envy. Taking turns in order achieves it, always.

EF1 is a weak excuse. It lets the envy be cured by removing the most valuable item in the other bundle, which may be most of what makes the bundle enviable. A stronger standard asks for more: whenever one person envies another, removing any single item from the envied bundle — even the one the envious person values least — would cure it. That is envy-free up to any item, EFX, introduced by Ioannis Caragiannis and colleagues in 2016. It is close to as fair as whole items allow, and whether it can always be achieved is one of the best-known open problems in fair division.

One item or any item #

The figure’s first allocation gives A items 1 and 2. Person C values those at 35 and 10, forty-five in all, and its own bundle, item 5, at 20: C envies A by 25. Remove item 1 — worth 35 to C — and A’s bundle drops to 10, below C’s 20; the envy is cured, so the allocation is EF1. Remove item 2 instead — worth only 10 to C — and A’s bundle is still 35, above 20; the envy is not cured, so the allocation is not EFX.

The difference matters because of who gets to choose the excuse. Under EF1 the envy is excused by the item that most offends; under EFX even the least offending item must be enough. An EFX allocation says that every person’s envy is smaller than the smallest thing in the envied bundle — that the envy is, in a precise sense, about individual items rather than about the bundles as a whole.

Of the 243 allocations of these five items, 48 pass the weak test, 11 pass the strong one and only 2 are envy-free outright. The counts are nested, as they must be: envy-free implies EFX, which implies EF1, and the figure checks the implications on every allocation.

When no envy-free allocation exists #

The interest of EFX is in the instances where envy-freeness is impossible.

When one item is worth more than half of everything to everybody, envy-freeness cannot hold — a pigeonhole argument in miniature, three people and one prize: the two people without that item each value the holder’s bundle at more than half and their own at less. Every one of the 81 allocations was checked and none escapes. But EFX allocations still exist — six of them — and they share a pattern: whoever gets the prized item gets nothing else. Then removing any item from that bundle removes the prized item itself, and the envy it caused disappears. The remaining items are shared between the other two so that neither envies the other up to any item. The holder of the prize envies nobody, since the prize alone is worth more to it than anything else could be; the other two envy the holder, but only for the prize, and the prize is the one thing any removal takes away.

That is the characteristic shape of an EFX allocation: a bundle that is enviable must be enviable only because of each of its items separately, so that none of them is along for the ride.

Why taking turns is not enough #

The standard way to reach EF1 is to take turns: the people pick items one at a time in a fixed order, each taking its favourite of what remains. Round-robin guarantees that nobody envies anybody by more than one item, because between any two of a person’s picks, the envied person made at most one pick that came earlier. But it cannot guarantee EFX, and the reason shows exactly what EFX asks for.

Suppose the first picker takes the item everybody prizes, and then, on its later turns, takes items that it values but that the others think trivial. The others envy the first picker’s bundle for the prized item, and removing any of the trivial items does not cure that envy — the prized item is still there. Round-robin let the prize carry passengers. EFX forbids passengers: a bundle containing an item that everybody envies must contain nothing else that anybody could do without. The allocations in the second figure are exactly the ones in which the prized item travels alone.

That is also why EFX is hard. Taking turns is a local rule — each pick is made without regard to what it does to anybody else’s envy later — and EFX is a global property of how items are grouped. Every known way of achieving it looks at the whole allocation and repairs it, rather than building it item by item.

A census of random instances #

Envy-free allocations are often missing when items are few: only 39% of the three-person, four-item instances have one, because with four items and three people somebody holds two and the other two usually cannot both be content. With more items per person, envy-freeness becomes common again — 97% at six items — because there is enough to go round in small pieces. EFX allocations were found in all 1,500 instances.

The census is evidence, not proof, and for three people the proof exists. For four or more it does not, and exhaustive searches like this one are exactly how the question has been probed: every small instance anyone has searched has an EFX allocation, and nobody has a proof that every instance does.

The contrast between the two colours is the practical argument for EFX. Envy-freeness is not merely hard to achieve; for a large share of real instances it is impossible, and a standard that is often impossible is no use as a promise. EF1 is always possible but often too lax to be convincing. EFX appears to be always possible — and, where it has been proved, is — while being strict enough that an allocation meeting it is hard to object to.

Cut and choose, with items #

For two people there is a procedure, and it is the oldest rule in fair division adapted to items.

The cutter divides the items into two bundles it considers as even as possible; the chooser takes the one it prefers; the cutter gets the other. The chooser never envies anybody, having chosen. The cutter must be content with either bundle up to any item, and that constrains how it cuts. Benjamin Plaut and Tim Roughgarden showed in 2018 that it suffices for the cutter to choose the split that maximises the value of its worse bundle and, among those, breaks ties so that the worse bundle is as large as possible — a rule they called leximin++. With that cut, whichever bundle is left to the cutter, removing any item from the other leaves it no more valuable than the one kept.

In the figure the cutter’s best split happens to be exactly even, 50 and 50, so the cutter envies nobody at all. The chooser, valuing the halves at 44 and 56, takes the larger. The same procedure works for any two people with any valuations of the items — additive or not — which is why the two-person case was settled first.

With only two people the gap between the two standards is easy to see in the counts: most allocations that are EF1 are not EFX, because an unbalanced split can always be excused by removing its biggest item and rarely by removing its smallest. Cut and choose lands in the small set of allocations that pass the stronger test because the cutter’s even split leaves no bundle with a passenger in it.

Three people, and the proof that took until 2020 #

For three people there is no cutting procedure. Bhaskar Ray Chaudhury, Jugal Garg and Kurt Mehlhorn proved in 2020 that every instance with three people and additive valuations has an EFX allocation. The proof is not a formula but a process: start from a partial allocation that is EFX for the items allocated so far, and show that as long as items remain, some sequence of exchanges between bundles either allocates another item or improves a carefully chosen potential function without breaking EFX. The potential cannot improve for ever, so the process ends with everything allocated.

The argument runs to dozens of pages of case analysis, most of it about which of the three people envies which bundle after an exchange and how a cycle of envy can be broken by rotating bundles. With four people the case analysis multiplies, the potential function that works for three stops working, and nobody has found a replacement.

The shape of that history is familiar from cake cutting. Two people have had a one-line procedure for millennia; three needed the trimming and residue of Selfridge and Conway; four had no bounded envy-free procedure at all until 2016, and the one found then needs an astronomical number of cuts. Fairness for three is a construction and for four is a research programme, in cake and in items alike, and nobody has explained why the step from three to four should be where things get hard in both.

Giving something to charity #

A partial answer exists for every number of people. Chaudhury and colleagues also showed that one can always find an EFX allocation of most of the items, leaving a small number unallocated — donated to charity — such that nobody envies the charity’s pile, and the number of donated items is less than the number of people. Later work reduced the donation further. So the obstacle, if there is one, involves only a handful of items at the margin: an allocation that is EFX for everything but a few leftovers always exists, and the question is whether the leftovers can always be placed. The donated items are not worthless either — the charity result guarantees that each person values the donated pile at no more than their own bundle — so giving them away costs everyone something they would not trade for what they hold.

There are also restricted versions that are fully solved. When everybody values the items identically, EFX allocations always exist, by a greedy argument. When each person’s values take only two distinct levels, they exist. The open question is the general additive case with four or more people, and for valuations that are not additive the picture is less clear still — for some non-additive valuations with many people, it is not even known whether the answer should be yes.

What the searches establish #

Every count is exhaustive for its instance. The first two figures check every allocation of their items — 243 and 81 — and the census checks every allocation of every one of 1,500 random instances. Within those instances the counts are facts, not estimates.

The instances are small. Three people and at most six items is far from where the open problem lives. EFX allocations are guaranteed for three people by the 2020 theorem, so the census is confirming a theorem rather than testing a conjecture; the conjecture is about four or more people, where exhaustive search becomes expensive quickly and random instances are known to be easy.

Values are whole numbers, and ties are real. Every instance uses integer values, so comparisons are exact and an allocation that ties is counted as envy-free for that pair. Instances with exact ties are special — they are where EF and EFX are most often achievable — and the random census draws values from a range wide enough that ties are uncommon but not absent.

The cutter’s rule in the figure is a simplification. The figure’s cutter maximises its worse bundle and breaks ties by fewer items; Plaut and Roughgarden’s leximin++ is a refinement of that which is guaranteed to work in every case. The figure checks that its split is EFX for the cutter on this instance, and does not claim the simplified rule always is.

Where EFX sits among the other guarantees #

Fair division for items has several standards, and they do not line up neatly. Proportionality — everyone getting at least a $1/n$ share by their own measure — fails for items for the same reason envy-freeness does, and is relaxed in the same ways. The maximin share asks that each person get at least what they could guarantee themselves by dividing the items into $n$ bundles and receiving the worst one; it is known that allocations meeting it exactly need not exist, and that a constant fraction of it always can be met. Maximum Nash welfare — maximising the product of everyone’s values — delivers EF1 and efficiency together, which is the unexpected strength of the product, but Caragiannis and colleagues showed that it does not always deliver EFX.

EFX implies EF1 and, for additive values, implies a fixed fraction of the maximin share, so it sits near the top of the hierarchy of guarantees for whole items. What it gives up, compared with Nash welfare, is any promise of efficiency: an EFX allocation may leave value on the table that a reallocation could capture. Whether both can always be had at once is part of what is still open.

There is also the option of randomness. A lottery over allocations can be envy-free in expectation — each person preferring its own expected bundle to anybody else’s — and every table of fractional shares is a lottery over whole assignments. The best current results combine the two: a lottery that is envy-free before the draw and EF1 after it. Adding EFX after the draw is, again, open.

Still open: four people #

For four or more people with additive valuations, nobody knows whether an allocation envy-free up to any item always exists. Counterexamples have been sought by computer and not found; proofs have been sought by extending the three-person argument and have not closed. A related question is whether EFX can be achieved together with efficiency — whether some EFX allocation is also Pareto-optimal, so that no reallocation makes everybody at least as well off and somebody better. For EF1 the answer is yes, and the maximum Nash welfare allocation achieves both at once; for EFX it is open even for three people.

The problem also has a practical side. Websites that divide inheritances, household goods and course places among real people use EF1 or maximum Nash welfare, because EFX cannot yet be guaranteed. If EFX were proved for all numbers of people, the proof would likely come with an algorithm, and the fairest standard available for whole items would become usable. If instead a counterexample were found, it would have to be a large and intricate instance — every small one has been checked — and it would show that the gap between EF1 and envy-freeness cannot be closed by any rule stated item by item.

The smallest excuse there is #

EF1 excuses envy by the item that causes most of it; EFX by the item that causes least. Put another way, EF1 asks whether some item could be blamed, and EFX whether every item could. The difference sounds like a technicality and is not: an EFX allocation guarantees that no bundle is envied for more than the smallest thing in it, which for whole items is as close to envy-free as the items allow. That such an allocation exists for two people is an afternoon’s work, once the right way to cut is seen, for three a long paper, and for four a problem that has resisted every approach — a measure of how much harder fairness becomes when there is nothing to cut.

The searches drawn here add one small observation to that history. In every instance they examined, however hostile to envy-freeness, the allocations that passed the strict test were there — a handful out of hundreds, found only by looking at all of them. Existence has run ahead of proof for this standard since it was defined, and the question is whether it will run ahead for ever.