One cuts and the other chooses

The rule fits in one line. One person cuts the cake in two; the other picks a piece. It is the oldest procedure in fair division, it is usually offered as though the matter ended there, and what it actually guarantees is both narrower and stranger than the offer suggests.

The two objects, stated exactly #

Nothing below is about a dessert. The cake is the interval, and a person’s valuation is a measure on it: a rule that assigns a number to every sub-interval, additive over disjoint pieces, giving 100 to the whole.

In the figures the interval is divided into equal segments and each person’s measure is a list of whole numbers, one per segment, summing to 100. The value of a piece is then the sum of the whole-number densities weighted by how much of each segment the piece covers — a step density integrated, in the sense that a Riemann sum makes precise, and exact because every weight is a rational. It is worth insisting on the word measure rather than preference: what each person supplies is an additive assignment of numbers to sets, the same kind of object as an area, which is why drawing a probability as a region of a square works and why drawing a valuation as a bar works here.

Two consequences follow immediately from additivity and are used constantly. Whatever the cut, each person’s two numbers sum to 100 — the piece and the rest are complementary, and there is nothing else to be worth anything. And the two people need not agree about a single sub-interval; the measures are independent objects that happen to share a total.

That shared total is the reason the total is 100 rather than 1. It makes every number on every table a percentage of that person’s own cake, and it makes “at least half” the number 50.

What the cutter is promised #

The cutter’s instruction is not “cut it in half”. It is cut it into two pieces of equal value under the cutter’s own measure, which is a completely different instruction, because it refers to nothing outside the cutter.

In the hero figure the cutter’s running total goes 5, 30, 60. It crosses 50 inside the third segment, two thirds of the way through it, so the cut lands at 4/9 of the cake. The generator computes that point as a rational and then asserts both halves — that the left piece is worth 50 and that the right piece is worth 50 — rather than computing one and subtracting. The distinction matters because half the claims in this subject are equalities, and an equality decided by comparing two floating-point numbers against a small threshold is not an equality at all.

What the cutter has bought with that cut is a floor of 50 that no subsequent event can lower. The chooser takes a piece; whichever piece is left is worth 50 to the cutter; so the cutter ends with 50 regardless. The guarantee does not consult the chooser’s measure, does not depend on the chooser being sensible, and would survive the chooser picking at random.

It is also a ceiling. The cutter ends with exactly 50 and can never end with more, because the cutter made the two pieces equal and one of them is what is left. That asymmetry is the whole of the essay’s second half.

What the chooser takes #

The chooser’s rule is to take whichever piece is worth more under the chooser’s own measure. Since the chooser’s two numbers sum to 100, the larger of them is at least 50, and the chooser’s floor follows in one line with no reference to the cut at all.

So both people end with at least half by their own measure. That property has a name — a division is proportional when every person values their own share at least $1/n$ of the whole — and for divide-and-choose it is airtight.

The interesting part is that only one of the two floors is tight.

Here the cutter has done nothing wrong and has no complaint available: 50 was the instruction and 50 is the result. The chooser walks off with 91 out of 100 by the chooser’s own accounting, and $9 + 91 = 100$ confirms that nothing has been invented — the surplus comes entirely from the cutter having drawn the line in a place the chooser’s measure regards as lopsided.

Two words that are not the same word #

There is a second thing a division can be, and it is the property most people actually mean by fairness.

A division is envy-free when nobody values another person’s share above their own. Proportionality is a statement about each person and a number; envy-freeness is a statement about each person and every other person. One is a claim about a diagonal, the other a claim about a whole matrix, and they are not obviously related.

For two people they are the same claim, and the reason is arithmetic rather than insight. Each person’s two numbers sum to 100. So for any person,

$$\text{own share} \ge 50 \iff \text{own share} \ge \text{other share},$$

because the other share is $100 -$ the own share and the inequality flips across 50 in both directions at once. Proportional and envy-free are one condition read two ways — a counting argument of the plainest kind, the same total counted as what was received and as what was not, in the manner of counting one rectangle along its rows and then along its columns.

This is where the essay’s central point sits. The coincidence is an accident of the number two. It uses the fact that “the rest” is a single piece belonging to a single person, and that fact is gone the moment a third person exists, because then the rest splits into two pieces which need not be equal and a person can be above their proportional share while still preferring somebody else’s.

There is a complementary observation from the other side, and it is a second counting argument over the same total — the pigeonhole, in the averaging form it usually wears. In any division whatsoever, at least one person values their own share at most $1/n$, since the $n$ shares add to 100 under that person’s measure and they cannot all exceed the average. Proportionality is therefore not a modest demand that leaves room above it. It is the demand that everybody sits at or above a ceiling that somebody must sit at or below — which is exactly why it is achievable and exactly why it is tight.

When the surplus is exactly nothing #

A figure that always reports a gain is indistinguishable from a figure whose subtraction is broken, so the claim that the chooser strictly gains needs a case where it must report nothing.

That is the obvious control, and it is not the sharp one. Identical measures are far more than is needed for a zero surplus.

The condition is therefore not the two measures differ but the two measures disagree across the cut. Disagreement confined to one side of the line is invisible to the procedure: the chooser is comparing two totals, and moving value about within a piece changes neither total. A surplus of zero is not evidence that the two people see the cake alike; it is evidence about one number.

Between the extremes the surplus takes whatever value the profile dictates, and the generator does not smooth it. The hero figure’s chooser gains 20/3; the near-disjoint profile’s gains 41; a finer grid produces yet another number.

The cut has to be there #

One step has been assumed and is worth pulling out, because it is the only place the argument touches anything infinite.

Let $F(x)$ be the cutter’s value of the interval from the left end to $x$. Then $F(0) = 0$, $F$ of the whole cake is 100, and $F$ never decreases. If the measure has no atoms — no single point carrying value — then $F$ is continuous, and a continuous function that starts at 0 and finishes at 100 takes the value 50 somewhere. The halving cut exists because of a crossing that has to happen.

That is precisely the shape of argument that something always stays put is built from, and it comes with the same limitation: the crossing is proved to exist and is not thereby located. On a step measure the location is easy, and the generator walks the segments, subtracts whole segment values until the remainder fits inside one, and lands at an exact rational whose denominator records how awkward the cut is — 4/9, 7/15, 11/24. On an arbitrary non-atomic measure there is no such walk, and the existence proof produces a cut without producing it, exactly as the counting argument for a primitive element produces a generator nobody can point at.

The crossing need not be unique, either. If the cutter’s measure gives zero value to some stretch, every point of that stretch halves the cake, and the procedure has to pick one. The generator picks the leftmost, visibly and by rule, which is the only place in the whole family where a tie is broken at all.

The asymmetry nobody can remove #

Divide-and-choose is symmetric in its guarantee and asymmetric in everything else, and the two facts are easy to run together.

Both roles are promised at least 50. Neither promise depends in any way on the other person’s measure, which is unusual and is the procedure’s real strength: a person carrying out their own half of the rule correctly cannot be harmed by anything the other person does, believes, or misreports. There is nothing to be gained by studying the opponent, because the floor is not a function of them.

But the cutter’s 50 is a floor and a ceiling at once, while the chooser’s 50 is only a floor. Under any pair of measures the chooser does at least as well as the cutter would have done in the chooser’s position, and strictly better whenever the two measures disagree across the cut. The symmetry of the guarantee is real and the symmetry of the outcome is not, and no relabelling of the two people repairs it, because the asymmetry is in the roles rather than in the persons.

This is a good place to note what the essay is not doing. How many cuts a procedure needs, and how much work it takes to find them, are questions about cost; another site in this fleet owns computation read as cost, and nothing here states a bound of any kind. What belongs here is the structural statement, which is complete on its own terms: the cutter’s value of their own share is exactly 50 on every profile, and the chooser’s is at least 50 on every profile.

Where the coincidence dies #

At three people the two words come apart, and not in some contrived corner. The natural generalisation of divide-and-choose to $n$ people is a knife sweeping the cake from one end, each person calling out when the piece behind it is worth $1/n$ to them, the first caller taking that piece and leaving.

Proportionality survives, and the two-line argument for it is worth having: whoever calls receives a piece worth exactly $1/n$ by construction, and whoever is still waiting valued every departed piece at no more than $1/n$ — that is precisely why they had not called — so at least $(n-k)/n$ of their measure remains after $k$ departures, and the last person takes all of it.

Envy-freeness does not survive. In the figure three of the four people can point at somebody whose piece they would rather have, and the person who never called ends holding 117/2 while every caller holds 25. Nothing has gone wrong; the procedure never promised otherwise. The complement argument that made the two words identical at two people needed “the rest” to be one piece owned by one person, and here the rest is three pieces owned by three people.

Repairing this is the subject of the next rung, and the repair is not a small adjustment. Envy-freeness for three requires a trimming, a set-aside residue, and a choosing order contrived so that whoever was handed an advantage cannot subsequently lose it — the whole of which is a matrix of nine comparisons rather than a claim about three.

What the drawing settles, and what it does not #

The figures on this page decide five valuation profiles for divide-and-choose. Proportionality is a claim about every pair of measures, and five is not every.

The distinction is the order of two quantifiers, and it is exactly the one that every row against one column is about. “For every profile there is a cut that halves the cake for the cutter” is a claim with a fresh cut for each profile, and each figure exhibits one instance of it: this profile, this cut, these four numbers. The proof that the claim holds for all profiles is the continuity argument above and the two lines of complement arithmetic, neither of which any picture contains. What the pictures settle is that the arithmetic is exact on the cases drawn, that the cut really is where the caption says, and — the point of the control figures — that the surplus machinery reports zero when zero is correct.

They settle one thing more, which is easy to overlook: the surplus is not a fixed quantity. Seeing it come out at 20/3, then 41, then 10, then 0 twice for different reasons, is evidence that “the chooser does at least as well” cannot be sharpened into any particular number.

There is also a restriction hiding in plain sight. Every measure drawn here is piecewise constant on a fixed grid. The theorems hold for arbitrary non-atomic measures; the step profiles are a picture of one countable family of them, and nothing on this page is evidence about a valuation that varies continuously.

It is worth marking which figures on this page are of a genuinely different kind. The two below have finite search spaces and are exhausted rather than sampled — all the allocations, every comparison — which is the epistemic status that a proof carried out by machine and the twenty-four syllogisms found rather than listed both have, and which the continuous cake cannot have at all.

Where this ladder goes #

The cake was divisible anywhere, and that is what made a floor of 50 reachable. Remove it and the guarantee goes with it.

Three items handed out to two people admit $2^3 = 8$ allocations, and there is a pleasing coincidence in that number: those eight allocations are the eight corners of a cube with a coordinate per item, the very same object on which a formula about three letters lives as a set of corners. A search for an envy-free allocation is a search for a corner satisfying a condition, and it is the identical search — over an identical cube — that a satisfiability question runs. Fair division of goods and propositional logic turn out to be walking the same vertices for different reasons.

At the defaults no corner works. The subject’s response is not to search harder but to weaken the word: an allocation is envy-free up to one item when every envy can be removed by setting aside a single good from the envied bundle, and four of the eight are.

So the ladder from here has two rungs and they diverge. One keeps the cake and adds people, buying envy-freeness back at the price of a much longer procedure. The other keeps two people and takes away the knife, and finds that the exact property is usually unreachable — not because a theorem says so, but because every allocation was formed and every one of them failed.