How many cuts a fair share costs

For two people, one cuts and the other chooses, and each is guaranteed half the cake by their own measure. The procedure asks exactly two things: the cutter where half of the cake ends, and the chooser which of two pieces is worth more. Two questions buy a guarantee that no amount of arguing about whose measure is right could improve on.

For many people the guarantee generalises naturally. A division is proportional when each of $n$ people receives a piece worth at least $1/n$ of the whole cake by their own measure. It is weaker than envy-freeness — a proportional share can still be envied — and it is always achievable. The question this essay is about is not whether but how cheaply: how many questions does a procedure have to ask the people before it can hand out proportional pieces?

Counting questions rather than steps #

To count, the questions have to be fixed, and the standard choice is due to Jack Robertson and William Webb. A procedure may ask a person two kinds of question. A cut query asks where, starting at a given point, the person would place a knife so that the piece up to it is worth a given amount to them. An evaluation query asks how much a given piece is worth to that person. Everything else — sorting answers, comparing numbers, deciding who gets what — is free.

That model separates the part of a procedure that needs the people from the part a clerk could do with a pencil. Cut and choose uses one cut query and two evaluations, or one comparison of two evaluations. And the model makes a cleanly posed question out of what could otherwise be a matter of taste: the query complexity of proportional division among $n$ people.

The cakes drawn below are exact. Each person’s measure is a step function over twelve segments, adding to 100, and every cut is placed at the exact rational point where a person’s running total reaches the target. So a claim that someone receives at least $100/n$ is checked in fractions, not approximated.

The last diminisher #

The oldest procedure for many people was described by Hugo Steinhaus in 1948, crediting his students Stefan Banach and Bronisław Knaster.

Take a slice from the left end of the cake, and pass it round the people who have not yet been served. The first marks the point where the slice is worth exactly their share of what is left — a $1/k$ share, when $k$ people remain. Each subsequent person looks at the slice as it now stands: if it is worth more than their share to them, they trim it back to their own mark; if not, they pass. The last person to trim takes the slice and leaves. The remaining cake goes round again among the remaining people.

The guarantee rests on one observation. The person who takes the slice values it at exactly their share of what was left, by their own mark. Everyone who remains either trimmed it themselves at some earlier point in the pass, and so values the final slice at no more than their share, or passed on a slice worth no more than their share to them. So every remaining person values what remains at no less than their share of it, and the induction goes through: when one person is left, they take the rest, which is worth at least what their share has been all along.

The cost is easy to count. In the round with $k$ people remaining, each of them is asked one question — a cut query if they trim, an evaluation if they pass. The rounds have $n, n-1, \dots, 2$ people, and the total is

$$n + (n-1) + \cdots + 2 = \frac{n(n+1)}{2} - 1,$$

which is nine for four people and grows like $n^2/2$.

Halving the people, and the cake at a median #

In 1984 Shimon Even and Azaria Paz found a procedure that asks far fewer questions, and it works by the same idea as every fast algorithm that divides a problem in half.

With $m$ people claiming a stretch of cake, let $k = \lfloor m/2 \rfloor$. Ask every person where the first $k/m$ of the stretch ends by their own measure. Sort the marks and cut at the $k$-th smallest. The $k$ people whose marks are at or left of the cut get the left part; the other $m - k$ get the right. Then each group divides its part the same way, until every group has one person.

The guarantee is immediate at each cut. A person sent left marked at or left of the cut, so the left part contains everything up to their own mark and is worth at least $k/m$ of the stretch to them. A person sent right marked at or right of the cut, so the right part contains everything after their own mark and is worth at least $(m-k)/m$. Each group inherits exactly the share its size entitles it to, and when the groups reach size one, each person holds at least $1/n$ of the whole cake.

The seven-person run shows the one subtlety the four-person run hides. When the group has an odd number of people it cannot be halved, and the marks are not at the halfway point: with seven people each marks where the first three-sevenths of the cake ends by their own measure, so that the three people sent left inherit exactly three shares’ worth and the four sent right inherit four. A cut at the halfway point would short-change the larger group. The fractions $k/m$ are the whole of the bookkeeping, and they are what makes the guarantee exact at every level rather than approximately right.

Counting is again a matter of adding up the rounds. Every round asks each person with a claim for one mark, and every person has a claim in every round until their group is a single person. The groups halve each time, so each person is asked about $\log_2 n$ times, and the total is about $n \log_2 n$ — twenty marks for seven people, where the last diminisher would ask twenty-seven.

Where the difference shows #

At four people the two procedures ask nine and eight questions, and the difference is a curiosity. At sixty-four it is 2,079 against 384, and at a thousand people it is about half a million against about ten thousand. The last diminisher’s cost is dominated by its later rounds being almost as long as its first; halving’s cost is controlled because no person is asked more than a logarithmic number of times.

The same contrast turns up wherever a problem can be split. Comparing every pair of items is quadratic; splitting them in halves, solving each half and merging is $n \log n$. Even and Paz’s procedure is exactly that shape, with a group of people in place of a list and a median mark in place of a median value.

A lower bound that says halving is best #

A faster procedure than halving would need a new idea, and in 2006 Jeff Edmonds and Kirk Pruhs proved that no new idea can exist. Every proportional procedure in the Robertson–Webb model must, for some valuations, ask a constant times $n \log n$ questions. Halving is optimal up to a constant factor.

The proof is an adversary argument. The procedure asks its questions one at a time, and an adversary answers them, choosing valuations consistent with every answer so far that keep as much uncertainty as possible about where each person’s valuable cake is. A proportional division has to pin down, for every person, a piece of cake that person values at $1/n$ — and the adversary can arrange that pinning down $n$ such pieces, each consistent with every other person’s answers, needs about $\log n$ questions per person, for the same information-theoretic reason that sorting $n$ items needs about $n \log n$ comparisons. There are $n!$ orderings of $n$ items, and a comparison halves the possibilities at best, so $\log_2 n! \approx n \log_2 n$ comparisons are needed. The adversary builds a cake with that many essentially different ways to be divided.

The lower bound is about the questions and nothing else. A procedure may do unlimited computation between questions, may choose its next question in the light of every previous answer, and may hand out pieces in any shape; none of that helps, because the obstacle is how little each answer can reveal about valuations the procedure has not yet asked about. What the $\log n$ measures is the cost of pinning down an exact $1/n$ threshold for every person at once, which is why it matches the cost of sorting so closely.

Why the pieces come out contiguous #

A detail of both procedures is easy to pass over and matters. Every piece is a single interval of cake. Neither rule ever gives a person two disconnected slices.

That is a genuine restriction, and for proportional division it costs nothing: halving is contiguous and already optimal. For envy-free division among three or more people it costs everything. There is no finite procedure at all that produces an envy-free division into contiguous pieces for three people in the Robertson–Webb model, a result of Stromquist in 2008 — the envy-free procedures that exist, like the three-person trimming, give some people several slices. Contiguity is free for proportionality and impossible for envy-freeness, which is a crisp way of measuring how much further the stronger guarantee reaches.

The moving knife, and why it does not count #

There is a procedure for proportional division that asks no questions at all in the Robertson–Webb sense, and it is worth seeing why it does not break the lower bound.

A referee moves a knife slowly and continuously from the left end of the cake. Any person may shout stop the moment the piece to the left of the knife is worth a $1/n$ share to them; the first to shout takes that piece, and the knife continues over the rest for the remaining people. This is Dubins and Spanier’s moving-knife procedure from 1961, and the knife-and-shout versions of cut and choose are its two-person case. It is plainly proportional, by the same argument as the last diminisher: nobody who stays quiet values the departing piece at more than their share.

It escapes the count because a continuously moving knife is not a finite sequence of questions. At every instant every person is implicitly answering an evaluation query — is the piece to the left worth my share yet? — and there are uncountably many instants. Converted into discrete queries, the moving knife becomes the last diminisher, with each shout replaced by a cut query and each silence by an evaluation, and its cost becomes quadratic. The moving knife is a way of describing a procedure elegantly, not a way of running one cheaply, and the query model exists precisely to tell those apart.

Finding a median without asking everyone everything #

The halving procedure has one step that looks as though it might hide a cost the count leaves out: sorting the marks and taking the $k$-th. That is free in the query model, since it involves no person, and it is cheap in any other sense too — a median of $m$ numbers can be found in time proportional to $m$.

What the step does conceal is a use of the people’s answers that the last diminisher never makes. The last diminisher compares each person only with the current slice. Halving compares every person’s mark with every other’s, and uses the order of the marks to decide which people belong together. The information the last diminisher throws away — who wants the left end more than whom — is exactly what halving spends, and it is why halving needs fewer questions: each question’s answer is used for two decisions at once, the cut and the grouping.

What honest answers are assumed #

Every argument above assumes that people answer queries truthfully — that a person asked where half their share ends marks the true point. A person who misreports can sometimes gain.

Proportionality is robust to that in one direction: a person who answers truthfully is guaranteed their share whatever the others do, because the guarantee to each person depends only on that person’s own marks. So honesty is a safe strategy. It is not always the best one. A person who knows the others’ valuations can shift a mark to steer the cut towards a part they value highly, and end with more than their share at nobody’s cost but the neighbours’. The procedures promise a floor and not an equilibrium, which is the same distinction a stable-matching rule runs into when it asks people for their rankings, and a voting rule runs into when it asks for ballots. In all three the procedure is a function of reported preferences, and in all three a person who can predict the others’ reports can sometimes do better by not reporting their own.

What the counted pictures leave out #

The figures run each procedure on four and seven people with step valuations over twelve segments, and on those valuations the pieces are checked exactly. The guarantee that every piece is worth at least $1/n$ for every possible valuation is the argument in the text, which the pictures instantiate and cannot establish.

The question counts in the chart are exact for the procedures as described, and they are counts of worst-case-independent kind: both procedures ask the same number of questions whatever the valuations. The lower bound is a different sort of statement — about every procedure on its worst valuations — and nothing drawn shows the adversary at work.

And the valuations are generated from a seed. They are ordinary in the sense of being uneven and unrelated, and nothing about them is extreme; a picture of the valuations the lower bound constructs would show cakes whose value is concentrated in places the procedure has been forced to guess at, which is exactly what makes them hard to draw.

Still open: what envy-freeness costs #

Proportional division’s query complexity is settled: $\Theta(n \log n)$. Envy-free division’s is not, and the gap is one of the largest in the subject.

Haris Aziz and Simon Mackenzie showed in 2016 that envy-free division among $n$ people can be achieved by a bounded procedure — the first for four or more people — but their bound is a tower of exponentials: $n$ raised to $n$ raised to $n$ raised to $n$, and then more. The best lower bound, due to Ariel Procaccia in 2009, is proportional to $n^2$. Somewhere between $n^2$ and a tower of exponentials is the true number of questions envy-freeness costs, and nobody knows whether it is closer to the polynomial or to the tower. Even for four people the best known procedure asks hundreds of questions where the lower bound asks for a few dozen. The gap is the divisible counterpart of the one indivisible goods face more starkly: there envy-freeness can be outright impossible and the word had to be weakened, while here it is always possible and nobody knows what it costs.

A price that can be counted #

Fairness among many people sounds like something that should get arbitrarily expensive, and for proportionality it does not. A division that guarantees everyone their share, by their own measure, whatever those measures are, costs about $n \log n$ questions — a handful per person — and no procedure can do better.

The two procedures drawn above show where that price comes from. Passing a slice round everyone who is left spends a question on each person in each round, and the rounds barely shrink. Splitting the people in half at a median mark spends a question on each person in each round too, but there are only logarithmically many rounds, because each cut and choose at the bottom of the recursion is reached by halving rather than by peeling people off one at a time.