Envy-free division

Why does letting one child cut the cake and the other choose first end the argument?

Every parent knows the trick: one child cuts, the other picks. The argument stops immediately — without anyone measuring anything, without the parent adjudicating, and without either child having to be honest or generous.

That last part deserves suspicion. Fairness schemes usually depend on someone behaving well; this one works on wholly selfish children. What is it doing, and what standard of fairness is it meeting?

First, be precise about the standard, because there is more than one. Call a division proportional if each of n people thinks their own share worth at least 1/n of the whole, by their own measure. Call it envy-free if no one, looking at what everyone else received, would rather have someone else's share. Envy-freeness is the stronger demand: not about hitting a threshold, but about not preferring a neighbour's plate.

Now watch the cutter reason. He cuts, then waits. Whatever he does, he ends up holding the piece the chooser rejected — so he is not choosing a piece, he is choosing a worst piece. Cut 60/40 by his own valuation and the chooser takes the 60. The only cut whose worst outcome he can tolerate is the one where both pieces are worth the same to him: one half each, by his own measure. Nobody instructed him to be fair; the structure made unfairness self-punishing.

Then the chooser. She faces two pieces which, by her measure, sum to 1. Two numbers summing to 1 cannot both be below a half. So the piece she prefers is worth at least a half to her, and she takes it.

Put the two together. The cutter holds a piece he values at 1/2 and sees the other as worth 1/2, so he does not envy. The chooser holds the piece she values at least as much as the one she left, so she does not envy either. Notice everything this did not need: no agreement on what the cake is worth, no shared units, no truthfulness, no referee.

Notice too a quieter asymmetry. The cutter is guaranteed exactly one half by his own measure and can never do better. The chooser may do far better — if she loves marzipan and the cut happened to isolate it, her piece may be worth 0.8 to her. Cutting is the safe role, choosing the profitable one. "Envy-free" does not mean "equal".

Now push to three people, because that is where the folklore quietly stops. The obvious extension — one cuts three pieces and the others pick in turn — gives proportionality but not envy-freeness. The cutter makes three pieces he values at 1/3 each. Chooser B values them 0.5, 0.3, 0.2 and takes the first. Chooser D values them 0.5, 0.4, 0.1, is left with the second and third, and takes the second at 0.4. D has beaten the proportional threshold of 1/3 comfortably — and D still envies B, whose piece D values at 0.5. Every share is proportional and one person is envious. For two people the two standards coincide, which is why cut-and-choose feels like it settles everything, and why the intuition it builds misleads.

Envy-freeness for three is achievable, but needs a cleverer procedure: the Selfridge-Conway protocol, using up to five cuts, in which a piece is trimmed to create a tie and the trimmings divided afterwards by a rule giving one participant an irrevocable advantage over whoever might otherwise envy them. For four or more, no bounded procedure was known until 2016, when Aziz and Mackenzie gave one — with a query count bounded by a tower of exponentials in n. I state both attributions from recall. The gap between "one cut" and "a tower of exponentials" measures how much cut-and-choose was getting for free.

The assumptions are strong and mostly invisible. The argument used, without saying so, that the cake is infinitely divisible, that each valuation is additive over pieces, and that nobody cares what the other receives except through their own share. Drop divisibility and the result fails outright: two heirs and one indivisible car admit no envy-free allocation, since whoever does not get the car envies whoever does. That is the limiting case that breaks the theorem, and it is not exotic — most real divisions are of houses and paintings, not cake. The standard repair is money as a side payment, restoring divisibility through the back door.

Envy-free is not efficient. Say the cake is half chocolate, half vanilla; the cutter values the flavours equally, the chooser values chocolate at 0.9 and vanilla at 0.1. Cut straight across so each piece holds half of each, and both end at 0.5 with nobody envious — yet giving the chooser all the chocolate and the cutter all the vanilla leaves the cutter at 0.5 and the chooser at 0.9. Envy-freeness is satisfied by an outcome both could improve on.

It is a mechanism, not a moral. Compare the sibling walk-through on cyclic majorities: there a procedure quietly decided the outcome and participants could do nothing. Here the procedure is engineered so that self-interest, followed exactly, produces the property we wanted — the whole discipline of mechanism design.

What would refute it. If a party's valuation is not additive — a slice worth more as part of a whole, or two items that are complements — the cutter's indifference argument collapses, because "half by my measure" is no longer well defined piecewise. Watch for a participant insisting a share must be kept intact to be worth anything: that signals the model does not apply, not that they are being difficult.

• The Selfridge-Conway procedure in detail, and why the trimming step is unavoidable.
• Envy-freeness for indivisible goods, where the standard weakens to envy-freeness up to one item.

Every term the collection defines is gathered in the glossary.