Three people and a trimmed piece

Two people dividing something they measure differently have a fair division rule that is four thousand years old and takes one sentence: divide and choose. Three people have a rule that takes four stages, sets a piece aside, and looks — the first time it is read — like an elaborate joke.

It is not a joke. Every stage of it is buying one row of that matrix, and the matrix is the whole subject.

The verdict is a matrix, not a diagonal #

Envy-freeness says: nobody values another person’s share above their own. Written out for three people that is nine statements, one for each ordered pair, and three of the nine are trivial — a person does not envy themselves. The other six are the content.

The mistake worth naming at the start is to read a division as three numbers: what each person got, by their own valuation measure. Three numbers is what proportionality asks about. Proportionality says each person’s own share is worth at least $1/n$ under their own valuation measure, and one number per person settles it.

Envy-freeness is a claim about the whole grid — about what will be called here the envy matrix, the square array whose entry in row $i$ and column $j$ is what person $i$ thinks person $j$’s share is worth. Envy-freeness is the statement that in every row, the diagonal entry is the largest — for each $i$ and each $j$, two quantifiers deep, where proportionality needs only for each $i$. That extra depth is the whole of the difficulty, and it is the distinction a relation drawn as a grid makes visible in a single picture: a claim that runs over rows and a claim that runs over cells look alike written out in words and stop looking alike the moment the grid is drawn. A procedure can satisfy every person about one rival and fail about the other, and nothing in a person’s own number reveals it.

So the figures here do not report three numbers. They report all nine, and the caption reports that all nine comparisons were made. The exhaustion is small — nine cells — but it is the exhaustion that decides, and a drawing that showed only the diagonal would be showing the wrong thing beautifully.

What one cut and one choice already gives #

For two people, divide and choose — one cuts and the other chooses — settles everything at once, and it is worth being exact about why, because the reason does not survive a third person.

The cutter halves by their own valuation measure, so the cutter is indifferent: whichever piece is left is worth exactly the same as the one taken, and the cutter’s row of the matrix reads $50$ and $50$. The chooser takes the larger of the two by their own measure, so the chooser’s own entry is the row maximum by construction. Two rows, two comparisons, both settled — and with two people, proportional and envy-free are the same word, since a share worth at least half is a share worth at least what is left.

Divide and choose is the whole of the two-person case, and the coincidence it rests on evaporates at three. A share worth at least a third does not have to be worth at least as much as either of the other two, because the other two need not be equal. The two words come apart, and everything below is about the gap.

Four stages, and what each one buys #

The procedure is due to John Selfridge, who found it around 1960, and independently to John Conway a few years later; neither published it, and it travelled by word of mouth for two decades before Richard Guy wrote it down. It runs as follows.

1. Person 1 cuts three pieces of equal value to person 1. Whatever happens afterwards, person 1 is indifferent between them.
2. Person 2 trims the largest — largest by person 2’s measure — down to an exact tie with person 2’s second largest. The trimming is set aside.
3. Person 3 chooses first, then person 2, then person 1, with the rule that person 2 must take the trimmed piece if person 3 did not.
4. The trimming is divided in three by whichever of person 2 and person 3 did not take the trimmed piece, and chosen in the order taker, person 1, cutter.

Read against the figure at the top, each stage buys exactly one row. Stage 1 buys person 1’s: three equal pieces means person 1 cannot envy anybody over the main pieces, whatever is left over. Stage 2 and the choosing rule buy person 2’s: the trimmed piece ties person 2’s second largest, so at least two of the three main pieces are tied at the top of person 2’s ranking and person 2 is guaranteed one of them. Stage 3’s ordering buys person 3’s for nothing — choosing first from three pieces is the cheapest guarantee in the subject.

What none of them buys is safety in stage 4, and stage 4 is where the whole construction earns its shape.

The trimming is the disagreement, and it can be empty #

The trimming exists because person 1 and person 2 disagree about which of person 1’s three pieces is biggest. Give the two of them the same measure and the disagreement vanishes: person 2 sees three pieces tied at $100/3$, the largest and the second largest are equal, and the amount to be trimmed is zero.

The procedure then degenerates into three people choosing in turn from three equal pieces, which is envy-free for a reason nobody needs four stages to see. The picture above is worth having precisely because it shows the machinery reporting nothing when there is nothing to report — the residue bar is empty, stage 4 has no work to do, and the matrix still comes out with every comparison satisfied. Four of the nine hold as exact ties, since two people who agree about everything must value every share identically.

The general lesson is that the trimming’s size measures how far person 2’s measure is from person 1’s, restricted to person 1’s own cut points. It is not an artefact of the procedure being clumsy; it is the exact quantity that has to be neutralised.

The advantage that cannot be lost #

Here is the difficulty stage 4 exists to solve. Somebody — person 2 or person 3 — ends up with the trimmed piece. Call that person the taker. The trimming is then divided among all three, so person 1 receives part of it. Person 1 was indifferent among the three original pieces, so a person 1 who gets a share of the trimming plus a full untrimmed piece is fine; but the taker gets a share of the trimming plus the trimmed piece, and if person 1’s share of the trimming is small enough, could person 1 end up envying the taker?

No, and the reason is an accounting fact that no later choice can disturb. Person 1 cut the pieces equal, and the taker holds a piece that is short by the whole trimming. So relative to person 1’s measure, person 1’s main piece exceeds the taker’s main piece by exactly what person 1 values the entire trimming at. Even if the taker were handed every last crumb of the trimming, the two would only draw level. This is called the irrevocable advantage, and it is the one idea in the procedure that has to be invented rather than checked.

Notice what the advantage is an argument about: a quantity that survives every continuation of the process. Nothing is said about how the trimming is cut or who chooses what; the inequality holds for every possible completion at once. That is the same style of argument as a parity that rules out a walk over the bridges — a number computed early that no later move can change.

The branch matters. In the figure at the top of the page, person 3 chose first and did not take the trimmed piece, so person 2 was obliged to take it and person 3 cut the residue. Here person 3 takes the trimmed piece, and now person 2 is the one who cuts the trimming into three and, choosing last, is left with whatever the other two decline.

Both branches are envy-free and neither is a relabelling of the other. That is why the procedure has to name the rule person 2 takes the trimmed piece if person 3 did not: without it, the trimmed piece could end up with person 1, whose advantage would then be over nobody, and the residue would have no safe cutter.

The tie, and whether it has to be there #

At the top of the page exactly one of the nine comparisons is an exact tie: person 2 values person 3’s share at $40$, which is precisely what person 2’s own share is worth to person 2. The definition of envy-freeness says at least as much as, and this is the case that word is carrying.

In the branch where person 3 takes the trimmed piece, that tie is not luck — it is forced. Person 2 is then left with the best of the two untrimmed pieces, which is person 2’s second largest, and the trimmed piece was cut down to tie it exactly. Person 2 also cuts the residue into three parts of equal value to person 2, so whichever part person 3 receives is worth exactly what person 2’s own part is worth. Equal mains plus equal residue shares gives an exact equality, and the figure above prints it: $365/9 \approx 40.56$ in both cells.

But the tie is not a feature of the procedure. On the profile above, the trimming comes to $16$ by person 2’s measure and every one of the nine comparisons holds strictly: person 1 at $1553/36 \approx 43.14$ against $19.06$ and $37.81$, person 2 at $1363/36 \approx 37.86$ against $31.57$ and $30.57$, person 3 at $761/18 \approx 42.28$ against $26.28$ and $31.44$. Nobody is on the edge of envy. The right statement is that envy-freeness permits ties and Selfridge–Conway produces them on some profiles and not others, which is exactly the kind of claim that four drawn profiles can support and one cannot.

Proportional is not envy-free, and the gap is not exotic #

The cheap procedure for any number of people is the moving knife in its last-diminisher form: a knife sweeps the cake from one end, each person calls the moment the piece behind it is worth $1/n$ to them, the first to call takes that piece and leaves, and the last person takes the remainder.

Proportionality follows in two lines. Whoever calls receives exactly $1/n$ by construction. Whoever is still waiting valued each departed piece at no more than $1/n$ — that is precisely why they had not called — so a proportional share always remains for them, and the person left at the end takes all of it. In the figure the three callers each end with exactly $25$ and the last person with $117/2 \approx 58.50$.

And that last number is the trouble. A person who ends with a remainder worth far more than a quarter is a person the others can look at. The envy matrix at the foot of the figure is computed by the same code as the one certifying the Selfridge–Conway division, and here it is used to exhibit a violation rather than to certify: person 1 values person 3’s piece at $26$ against $25$ for their own. Four of the twelve off-diagonal comparisons fail. The moving knife delivers proportionality for any $n$ and nothing more, and the trimming is what the stronger word costs. How many cuts or stages that cost amounts to is a question about the length of a procedure, which belongs to another site in this collection; nothing here states one.

What the picture cannot show #

Four profiles have been drawn and in each of them all nine comparisons hold. That is a report about four triples of measures, and envy-freeness for Selfridge–Conway is a claim about every triple. The drawings settle the finite part and the argument settles the rest, and it is worth saying exactly which is which.

What the drawings settle. That the procedure, run to the end on a stated profile, produces an envy matrix whose nine exact values satisfy nine exact inequalities. No comparison here consults a tolerance: every cut point is a rational — $4/9$, $7/15$, $27/40$ — and the equalities the subject turns on are genuine equalities, decided as such. A tie reported by a subtraction of two floating-point numbers would be a tie only by courtesy, and half the claims here are ties. The awkward denominators are not noise; they are what a cut lands on when a measure is asked for an exact third, and every one of them is an ordinary fraction of the kind the Stern–Brocot tree produces exactly once.

What the drawings do not settle. Three things. First, the quantifier: four profiles are not all profiles, and the general claim rests on the irrevocable-advantage argument above, which mentions no numbers at all. Second, the measures drawn are piecewise constant on a fixed grid of six segments — a countable family — while the theorem holds for any non-atomic measures, and nothing on the page is evidence about a valuation that varies continuously. Third, the pictures cannot show that the procedure is necessary: they exhibit one construction that works, never that a simpler one is unavailable.

That last gap is the honest one, and it is the same defect-by-absence that makes four circles look like a working diagram until somebody counts the regions. A drawing of a procedure that succeeds says nothing whatever about the procedures that were not drawn.

Four people, and a frontier rather than a generalisation #

The natural expectation is that the trick generalises: trim harder, add a stage, and get envy-freeness for four. It does not, and the history is worth stating plainly because it is the rarest thing a settled-looking subject can contain — a gap that stayed open, in full view, for most of the modern life of fair division.

Existence was settled long before any procedure. An envy-free division among $n$ people is known to exist for every $n$, by an argument that produces nothing: the standard proof runs through Sperner’s lemma, the combinatorial statement whose continuous shadow is Brouwer’s theorem, and it therefore has exactly the character of the promise that something always stays put — a guarantee that the object is there, with no information about where. The same shape recurs across this collection whenever counting produces an object nobody can exhibit, as it does for the colourings of a large enough party.

For four people, no finite procedure was known at all until 2016, when Haris Aziz and Simon Mackenzie published one, and then extended it to every $n$. Fifty-six years separate the three-person case from the four-person one. The four-person procedure is not Selfridge–Conway with an extra trimming; it is a different construction of a different order of complication, and describing the interval between them as a gap in the literature would understate it — for half a century the honest position was that nobody knew whether such a procedure existed.

This is the point at which a figure would be dishonest. Nothing on this page is evidence about four people, and the one figure here that does divide a cake among four is the moving knife, which produces a division that is not envy-free and is drawn to show exactly that.

Where the ladder goes #

Everything above depends on the cake being divisible anywhere. Remove that and the guarantee goes with it: two people and one indivisible item cannot be divided envy-freely at all, and with three items and two people at the profile drawn here, all eight allocations were formed and every one of them failed.

The response of the subject is not to search harder but to weaken the word — envy-free up to one item asks only that every envy be removable by setting aside a single good from the envied bundle, and four of the eight allocations above satisfy it. That is the next rung, and it is where the exhaustive search stops being a certificate and becomes the argument itself: with indivisible goods the space of allocations is finite, so an impossibility can be decided rather than proved, the way thirty-six officers and the four-colour theorem were decided.

What survives from this page into that one is the envy matrix. Nine cells for three people, $n^2$ for $n$, every off-diagonal entry compared against the diagonal of its own row — the verdict has the same shape whether the resource is a cake, a pile of goods, or anything else a rule of fair division is asked to split. The procedures change completely. The thing that has to be checked does not.