Envy-free, up to one item

A cake yields to any procedure because it yields to a knife. One cuts and the other chooses works because the cut can go anywhere; the trimmed piece works because the trimming can be any size at all. Remove the knife — leave three objects that cannot be halved — and every guarantee those two essays established stops being available at once.

The thing that cannot be cut #

Two words carry this anchor and both are properties of a valuation measure rather than of a procedure. A division is proportional when each of $n$ people receives a share worth at least a fraction $1/n$ of the whole by that person’s own measure. It is envy-free when nobody values another’s share above their own. For two people the words coincide, and divide-and-choose delivers both.

The cut lands at $4/9$ because that is where it has to land, and the whole of the guarantee rests on the fact that a cut may land there. Nothing in the procedure requires a special cake, a special measure, or any agreement between the two people at all.

Now replace the cake with a single object. One item, two people, both valuing it at 100. Whoever receives it holds a share worth 100 and the other holds a share worth nothing. Proportionality asks for at least 50 apiece; one person has 0. There is no proportional allocation, there is no envy-free allocation, and there is no clever procedure that will find one, because the whole set of allocations has two members and both fail.

This is not an edge case tidied away by adding items. It is the shape of the problem.

Eight allocations, and none of them will do #

The figure at the head of this essay is the smallest instance where the failure is worth drawing. Three items — $a$, $b$, $c$ — and two people, each of whom has stated what the items are worth out of 100 for the whole set. Person 1 says $40$, $35$, $25$; person 2 says $30$, $45$, $25$.

Every item goes to one of two people, so there are $2^3 = 8$ allocations, and all eight were formed and tested. None is envy-free. That is not a theorem being quoted. It is a count, and it is the only honest picture of an impossibility: the search that was performed and that found nothing, in the same register as the thirty-six officers, where every arrangement was walked and none of them worked.

That second figure is the one-item case with the smallest possible fig leaf on it. Item $b$ is worth $10$ to both, item $a$ is worth $90$ to both, and whichever way the two objects fall somebody is looking at a bundle nine times the value of their own. Four allocations, none envy-free.

The control is why the zero counts #

A search that reports nothing looks exactly like a search that never ran. Both print zero, both pass every assertion about the numbers they did produce, and neither can be told from the other by looking at the picture.

So the items mode carries a second value matrix and searches it with the same code. In the opening figure that control is person 1 valuing the items at $50$, $30$, $20$ and person 2 at $20$, $30$, $50$ — two measures that disagree in the useful direction — and the same enumeration finds 2 envy-free allocations of the 8. The machinery has been seen to say yes. Only then is its no worth printing.

That is the discipline this whole field is written to, and it is worth naming because it is easy to skip. An assertion that has never rejected anything proves nothing; a search that has never found anything reports nothing. The control matrix is the second half of the same habit, and the caption on every one of these figures states its result alongside the finding, so that a reader is never asked to trust a zero on its own.

Weakening a word until it is reachable #

Faced with a property that most instances cannot satisfy, a subject has two moves available. It can search harder — and here there is nothing to search, since exhaustion has already been achieved. Or it can ask for less.

An allocation is envy-free up to one item when, for every pair of people, some single item can be removed from the envied bundle to remove the envy.

Formally: for every $i$ and $j$ there is an item $t$ in person $j$’s bundle with person $i$’s value of the rest of that bundle no greater than person $i$’s value of their own. If nobody envies, the condition holds with nothing to remove.

The weakening is strikingly small. It does not permit envy of two items, or of a fixed fraction, or of anything measured in the units of the valuation. It permits envy that a single object accounts for. And in the opening figure it takes the count from 0 to 4 — half of the eight allocations satisfy it.

Half, and not all: this matters. A weakened property that everything satisfies has said nothing, and the count is the check. Four of eight allocations are refused by the weakened word in the opening figure, and in the five-item case below, 62 of 243 survive while $243 - 62 = 181$ are refused. Envy-freeness up to one item is a real condition that real allocations fail.

The generator also checks the direction the definition needs: every envy-free allocation is envy-free up to one item, asserted on every allocation of both matrices in every placement here. A weakening that failed to contain what it weakens would be a different property wearing the same name.

Taking turns, and why it works #

Now the surprise, and it is the reason the weakening was worth making rather than merely available.

Round-robin picking: person 1 takes the item they value most, then person 2, then person 3, and round again until nothing is left. No trimming, no residue, no contrived choosing order — nothing resembling the four-stage construction the previous rung needed. This procedure is always envy-free up to one item.

The proof is an availability argument and it fits in a paragraph. Compare person $i$ with person $j$. If $i$ picks before $j$ in every round, then at the moment person $i$ makes their $k$-th pick, person $j$’s $k$-th pick is still on the table — so person $i$ preferred what they took, round by round, and adding up the rounds gives no envy at all. If instead $j$ picks first, discard person $j$’s very first item and re-index: person $i$’s $k$-th pick is made while person $j$’s $(k+1)$-th pick is still available, so person $i$’s bundle beats what is left of person $j$’s once that first item is gone. That single item is the witness, and the definition asks for exactly one.

The figures find that witness rather than asserting it. In the opening figure, person 2 envies person 1’s bundle of $a$ and $c$ — worth $30 + 25 = 55$ against $45$ for item $b$ — and stops envying once item $a$ is set aside. Item $a$ is person 1’s first pick. In the five-item figure the witness is again item $a$, and again it is the first pick of the person envied. The general argument names which item the witness will be, and every placement here reports the item the search found; they agree.

When the count is not zero #

Envy-freeness is not always unreachable, and a section that only ever showed zeros would be describing the search rather than the subject.

Person 1 values the items at $50$, $30$, $20$ and person 2 at $20$, $30$, $50$. The disagreement is total and it is exactly what makes the instance solvable: giving each the end of the list they care about leaves both holding more than half by their own measure. Round-robin picking, which knows nothing about the other person’s numbers, lands on such an allocation anyway — person 1 takes $a$ and $b$ for $50 + 30 = 80$, person 2 takes $c$ for $50$, and no pair envies.

So the count of envy-free allocations is a property of the matrix and not of the number of items. What decides it is how far the two measures disagree.

Agreement is the worst case #

Push that observation to its end. When two people’s measures are identical, envy-freeness demands that each bundle be worth exactly half to both — because $v(A_1) \ge v(A_2)$ and $v(A_2) \ge v(A_1)$ together force equality, and the two bundles account for the whole set.

That reduces the question to arithmetic. With values $34, 33, 11, 11, 11$, is there a sub-collection summing to 50? Every subset sum is one of $34$ and $33$ taken or left, plus some number of elevens, and the near misses are quick to list: $34 + 11 = 45$, $33 + 11 = 44$, $11 + 11 + 11 = 33$, $33 + 11 + 11 = 55$, $34 + 11 + 11 = 56$, $34 + 33 = 67$. Nothing reaches 50, so nothing is envy-free, and the exhaustive search over all $2^5 = 32$ allocations confirms it by construction rather than by argument.

This is a counting argument of a familiar shape — the pigeonhole family, where a target is missed not because the search was poor but because the arithmetic leaves no room for it. And it explains why zero is the common answer: two people who broadly agree about what things are worth are precisely the two people for whom no even split exists.

The other weakening, and the one that fails #

Envy-freeness is not the only word the knife bought, and it is not the only one that had to be weakened. Proportionality has its own indivisible descendant, and its story ends differently.

Ask what a person could guarantee themselves if they had to do the cutting. Let them divide the items into as many bundles as there are people, knowing they will be handed the worst one by their own measure, and let them choose the division that makes that worst bundle as good as possible. The value they reach is their maximin share, and it is the discrete form of the half a cake-cutter cuts to: with two people it is exactly what divide-and-choose delivers to the cutter, computed over the finitely many splits available rather than over every cut.

Run it on the identical-valuation example above, where the values are $34, 33, 11, 11, 11$ and nothing is envy-free. Splitting off $34 + 11 = 45$ leaves $33 + 11 + 11 = 55$; splitting off $34 + 33 = 67$ leaves $11 + 11 + 11 = 33$; and no split does better than the first, so the maximin share is $45$ rather than the $50$ an even halving would give. The five short of half is exactly what indivisibility costs, and it is a number rather than a failure — and an allocation reaching it exists, handing one person the $45$ and the other the $55$.

That is the encouraging case. With two people it always works, by the cut-and-choose argument transplanted whole: one person names the split achieving their maximin share, the other takes the bundle they prefer, and the first is left with something worth at least what they promised themselves.

With three people it can fail. Procaccia and Wang produced an instance in 2014 — three people, twelve items, values chosen with some care — in which no allocation at all gives every person their own maximin share. Not that no procedure finds one; that none exists, over every way of handing out the items. The natural discrete analogue of proportionality is therefore not a guarantee, and the failure is not visible at any small size, which is why it took until 2014 to be written down.

What survives is an approximation. Every instance admits an allocation giving each person at least two-thirds of their maximin share, and later work raised the constant to three-quarters and a little beyond; the exact best constant is not known.

So the two words weaken differently, and the contrast is the point. Envy-freeness weakened to up to one item is reachable by taking turns. Proportionality weakened to the maximin share is not reachable at all, and has to be weakened a second time, by a multiplicative constant nobody can yet pin down. A weakening is not guaranteed to land somewhere reachable, and which of the two happened is decided by the mathematics rather than by how modest the weakening looked.

What the drawings settle, and what they do not #

The distinction has to be stated plainly, because the figures on this page are doing two different jobs and only one of them is finished by drawing.

What is settled. Every count above is exhaustive over the matrix printed beside it. “No allocation of these three items between these two people is envy-free” is decided, completely, by forming all eight and testing each. That claim needs no theorem and admits no doubt, exactly as four circles cannot show sixteen regions is decided by counting the regions four circles actually cut.

What is not. “Round-robin picking is always envy-free up to one item” quantifies over every value matrix, every number of people and every number of items. No finite collection of drawings touches it. The availability argument in the section above is the proof, it is prose, and the figure does not contain it — what the figure contributes is a witness item on five specific matrices, which is corroboration and not demonstration.

Three further restrictions are invisible in the tables. The valuations are additive: a bundle is worth the sum of its items, which excludes any interaction between them. Each row sums to 100, which is a normalisation and not a constraint on the ranking. And exhaustion is a report about a finite object — how much work such a search takes as the instance grows is a question about cost, which another site in this fleet owns, and no claim about it is made here.

There is also a question the drawings cannot even pose. Envy-free up to any item — where removing the envy must work for every item in the envied bundle, not merely some one of them — is the stronger relative, and whether an allocation satisfying it always exists is known for three people and open for four or more. That is a live gap, of the kind this collection likes to point at rather than paper over.

Two ways to answer an impossibility #

There is a move being made here that is worth isolating, because it recurs across this whole collection and it is not always honest.

When a stated goal turns out to be unreachable under stated means, two responses are available: change what is allowed, or change what is asked.

The first response is the classical one. The angle that will not divide by three is impossible with straightedge and compass, and the answer the subject gave was to widen the instrument — a marked ruler, a folded sheet — while leaving the goal exactly where it was. The trisection is still a trisection; only the permitted moves changed.

Indivisible goods rule that response out. The instrument is the allocation, and there is nothing to widen: an item goes to one person or another, and no enlargement of the procedure creates a half-item. So the second response is forced, and the goal is what moves.

That is the response Russell’s paradox drew too. Unrestricted comprehension is inconsistent, as the list that cannot contain itself shows, and the repair was to weaken the axiom until it was satisfiable rather than to abandon set theory. Dropping the excluded middle is the same manoeuvre from the other direction. And when an irrational cannot be hit by a fraction at all, the subject stops asking for equality and bounds the shortfall instead.

Three conditions separate an honest weakening from moving the goalposts, and EF1 meets all three. It contains what it weakens — every envy-free allocation is EF1, and the generator checks this on every allocation of every matrix drawn here. It still refuses things: four of eight, and 181 of 243. And it was stated before the answer was known, as a property, rather than reverse-engineered from whatever round-robin happened to produce.

The honest cost should be stated too. On a single item the property is satisfied vacuously — remove the one object and the envy is gone — so EF1 promises nothing at all in the case that motivated it. A weakening that is reachable everywhere is reachable in the places where it means least.

Where this anchor ends #

Three rungs, and the shape of the ladder is the shape of one distinction. Divide-and-choose gives two people proportionality and envy-freeness together. Trimming gives three people envy-freeness at the cost of a residue and a choosing order. Both spend the same currency: a knife that may fall anywhere.

That figure is the honest bridge to this one. Proportionality survives at four people for the price of one sweep, and envy-freeness does not survive at all — three of the four would rather hold another’s piece. The gap between the two words opens before divisibility is even removed, and removing divisibility closes the stronger word entirely.

What replaced it is a definition small enough to be reached by taking turns and strict enough to reject most allocations, together with an existence result whose proof is four lines of availability rather than a construction anybody had to invent. The subject did not find a better procedure. It found a better question, and then found that the dullest procedure already answered it.