Cutting a Cake Three Ways

  • Medium
  • Game strategy puzzles
  • Tests: Designing a procedure nobody can exploit

The puzzle

Two people can split a cake fairly with "one cuts, the other chooses": the cutter makes two pieces they would be equally happy with, so whichever the chooser takes, the cutter is content. Nobody needs to trust anybody.

Design a procedure for three people that gives each of them a piece they consider to be worth at least a third - even if they value the cake quite differently and everyone acts selfishly.

Stuck?

One at a time, smallest first. Open only as many as you need — the whole point of the puzzle is the part you work out yourself.

Hint 1

Start by having one person cut what they consider a fair third.

Hint 2

The other two may disagree about whether it is a third. Give them a way to cut it down to size.

Show the answer Hide the answer

The Selfridge-Conway trimming method: A cuts three pieces equal in A's eyes; B trims the largest down to tie with the second, setting the trimming aside; C chooses first, then B, then A - with B obliged to take the trimmed piece if C did not. The trimming is then divided by the same idea.

How to get there

A divides the cake into three pieces that A values equally - a third each, by A's own reckoning. If B thinks some piece is too big, B trims it so that it ties with what B considers the second-largest, and the trimming is put aside.

Now C picks any piece, then B picks - but B must take the trimmed piece if C has not taken it - and A takes what is left. C is happy because C chose first. B is happy because B deliberately created a tie for largest and gets one of the tied pieces. A is happy because A only ever loses the trimmed piece, and the two untrimmed pieces are still worth a third each to A.

The trimming is then split: the player among B and C who did not take the trimmed piece divides it into three, and they choose in the order C-or-B, A, then the divider. Each step is built so that the person who could gain by lying is the one who has to act first and has no information to exploit.

The technique worth keeping

Build fair procedures out of two moves: let the person who might cheat do the dividing, and let the person who might be cheated do the choosing. The divider is then forced to make options they would accept themselves.