How Do You Cut a Cake Fairly for Three?

What “fair” means here

Pieces of the same size aren’t the point. Cut the cake at 4 and 8, and Asha, who likes every strip the same, thinks each piece is a third. But to Bibek the chocolate piece is worth 8 of his 12 points, two thirds, and the strawberry piece nothing at all.

So a share is fair or not in the eyes of the person who gets it. Two ways of being fair will matter in this topic:

• Everyone gets at least a third of the cake, counted in their own points: at least 4 of their 12.
• Nobody would rather have someone else’s share.

Try them on the cake above.

• a.Cut at 4 and 8, give Bibek the chocolate and Chandra the strawberries. Does anyone get less than a third? Would anyone swap?
• b.Leave the cuts and give Asha the chocolate instead. What happens?
• c.Find cuts where everyone gets at least a third, but someone would still rather have another cousin’s share.

Two people: one cuts, the other chooses

Before three, two. Asha and Bibek share the cake. Asha cuts it in two, and Bibek takes whichever piece he likes better.

• a.Where should Asha cut so that, whatever Bibek takes, she gets half? (Hint: what does she know about Bibek’s taste? Suppose nothing.)
• b.Asha does know that Bibek loves chocolate. Where could she cut to get more than half? What goes wrong if she guesses his taste wrongly?
• c.Now Bibek cuts and Asha chooses. Where should he cut to be sure of half? What does Asha get?

Cut and choose works because each person can protect themselves without knowing anything about the other.

• The cutter cuts two pieces that are equal to her. Whichever one is left, she has half.
• The chooser takes the piece that looks bigger to him, so he has at least half too.

Nobody can be cheated, whatever the other does, and nobody wants to swap. When tastes differ, the chooser usually does better.

Cut, then choose in turn

The easy idea for three: Asha cuts three pieces that are equal to her, then Bibek chooses, then Chandra, and Asha takes the last. With our cousins it works: Asha cuts at 4 and 8, Bibek takes the chocolate, Chandra the strawberries, and Asha’s plain piece is still a third to her.

But that was luck. Suppose Chandra were her friend Dipa, who eats only chocolate: all 12 of her points are on the four chocolate strips. Bibek chooses first and takes the chocolate. Dipa is left with plain sponge and strawberries: 0 of her points. Asha and Bibek are fine, and Dipa has been cheated.

The cutter is safe (every piece is a third to her), and so is the first chooser. The second chooser takes what is left, and the first may have taken the only piece she wanted. We need a method in which every step protects whoever it might hurt, as cutting and choosing does.

Here is one, and it needs nobody to know anyone else’s taste. Hold a knife over the left end of the cake and slide it slowly to the right. Whoever first thinks the piece behind the knife is worth a third shouts Stop!, and takes that piece. The other two go on in the same way with the rest: the knife slides on, the first to think the new piece is a third shouts and takes it, and the last cousin gets whatever remains.

Why everyone gets a third

This is the clever part. Follow any one cousin, say Asha.

• If she shouts, the piece behind the knife is worth a third to her at that moment. She has her third.
• If someone else shouts first, Asha hadn’t shouted yet, so that piece is worth no more than a third to her (exactly a third if they shouted together). What is left is worth at least two thirds to her, for the remaining two of them.
• With two left, the same thing again: either she shouts and gets a third of the whole cake, or the other one shouts first, taking no more than a third of the cake by Asha’s points, and she is left with the rest: at least a third.

The same argument works for Bibek and for Chandra, and for 4, 10 or 100 people sharing: with n people, everyone gets at least 1/n of the cake by their own measure, whatever the others like and however they behave. A share like this is called proportional: each of n people gets at least 1/n, as they see it.

Being honest guarantees you a third; keeping quiet past your third, hoping for more, can leave you with less, as a question at the end shows.

Fair, but not free of envy

Look at the table in the widget once the knife has gone all the way. Bibek has his third, but to him Asha’s piece, 2 to 6, holds two chocolate strips and two plain ones: 4 + 2 = 6 of his points, half the cake. He would swap with Asha. And Asha would swap with Chandra, whose piece holds 6 of Asha’s points.

So nobody was cheated of their third, and still two of the three cousins envy somebody. A share where nobody would rather have anyone else’s share is called envy-free. Cut and choose is envy-free for two people: with only two shares, having at least half means the other share is at most half. With three, having a third doesn’t stop you thinking somebody else’s share is bigger than yours.

An envy-free way for three people was found in 1960 by the American mathematician John Selfridge, and again, on his own, years later, by the English mathematician John Conway. Neither published it; it spread from one mathematician to another. It uses at most five cuts. Here it is on the cousins’ cake, with Bibek cutting first.

The rules, for any three people:

1. The cutter (Bibek) cuts three pieces equal to him.
2. The trimmer (Asha) looks at her two biggest pieces. If they are already equal to her, she does nothing. If not, she trims a bit off the biggest so that it equals her second biggest, and the trimmings are put aside.
3. The third person (Chandra) chooses any piece. Then the trimmer chooses, but if the trimmed piece is still there, she must take it. The cutter takes the last piece.
4. The trimmings: whichever of Chandra and the trimmer did not take the trimmed piece cuts them into three pieces equal to them. The one who took the trimmed piece chooses first, the cutter second, and the trimmings’ cutter takes the last.

At the end Asha has 1/3, Bibek 1/2 and Chandra 1/2, each by their own points, and nobody would swap.

Why nobody envies anybody

Follow each person, as with the moving knife.

• Chandra chooses first both times, so she never sees a share she likes better than hers.
• Asha made her two best pieces equal. Chandra could take only one of them, so Asha gets the other: as good as any piece in the first round. In the second round she cut the trimmings into pieces equal to her, so whichever is left for her is as good as the others.
• Bibek cut three equal pieces, and only the trimmed one has lost something, so in the first round he gets a whole third, and Asha’s piece is worth no more to him than his own. In the second round he chooses before Asha, so he doesn’t envy her share of the trimmings. And Chandra? Her trimmed piece plus all the trimmings put back together is just one of Bibek’s three equal pieces, worth exactly what his own first piece is worth to him. So whatever part of the trimmings Chandra gets, her share can’t be worth more to Bibek than the first piece he already has.

That last step is the clever one: the trimmings are never a danger to the cutter, because they came off a piece he thought was only a third.

With other tastes, Chandra might leave the trimmed piece, and then Asha must take it. The same reasons still work, with Asha and Chandra changing places in the second round: Chandra cuts the trimmings into pieces equal to her, so she envies nobody’s share of them, and Asha, who now chooses first, envies nobody’s either. In the first round Asha still has one of her two favorites, and Bibek’s reasons are the same as before with Asha and Chandra’s names swapped.

More than three

For four or more people, envy-free cutting is much harder. Steven Brams and Alan Taylor published a method for any number of people in 1995, but for some tastes it needs as many cuts as you like. A method with a limit came only in 2016, from Haris Aziz and Simon Mackenzie, and its limit is n to the power n to the power n, six n’s high, for n people: for four people, a number with far more digits than there are atoms in the universe. A quick envy-free method for many people is still an open problem.

All of this needs a cake: something you can cut wherever you like, into pieces as small as you like. Many things that people share can’t be cut.

Two sisters are left one bicycle, and both want it. Whoever gets it, the other would rather have it, and there is no second piece to balance it. No share of one bicycle between two people can be envy-free. The way out is to add something that can be cut: one sister takes the bicycle and pays the other money, or they take turns, a month each, cutting time instead of the bicycle. Sharing land, a house or jewelry in a family works the same way, and it has a topic of its own for Grades 9–12, How Do You Share an Inheritance Fairly?.

And some things people share are not wanted at all: chores. Cut and choose still works for two, turned round. One person splits the jobs into two lots that seem the same amount of work to them, and the other takes the lot that looks smaller.

• Is This Game Fair? Another kind of fairness: a game is fair when, on average, nobody wins.
• Who Wins the Race to 20? The other game in this part of the book: one player can always win, and you can find out which.
• How Do You Share an Inheritance Fairly? Land, a house and jewelry that can’t be cut, shared with money, in Grades 9–12.
• Which Voting System Is Fair? When a group must choose one thing, “fair” turns out to be harder still, in Grades 9–12.
• Should You Cooperate or Cheat? What happens when each person does what is best for them, in Grades 9–12.