The Robertson–Webb rotating-knife procedure is a procedure for envy-free cake-cutting of a two-dimensional cake among three partners. It makes only two cuts, so each partner receives a single connected piece. In contrast to the earlier Stromquist moving-knives procedure, it requires only a single moving-knife, utilizing the two-dimensional nature of the cake.
Contents
Procedure
Initially, each partner makes a vertical cut such that the cake to its left is worth for him exactly 1/3. The leftmost cut is selected. Suppose this cut belongs to Alice. So Alice receives the leftmost piece and her value is exactly 1/3. The remainder has to be divided between the remaining partners (Bob and Carl).
Note that Alice's part is worth at most 1/3 and the remainder is worth at least 2/3 for Bob and Carl. So, if Bob and Carl each receive at least half of the remainder, they do not envy. The challenge is to make sure Alice won't envy any of them.
The solution is based on the following observation: For each angle
When the knife is at angle 0, Bob (weakly) prefers either the piece above the knife or the piece below the knife; when the knife is at angle 180, the pieces are reversed. Hence, by the intermediate value theorem, there must be an angle in which Bob thinks the pieces from both sides of the knife are equal. At this angle, Bob shouts "stop!". The cake is cut, Carl chooses a piece and Bob receives the other piece.
Analysis
Alice does not envy because for her, all three pieces are worth exactly 1/3.
Bob and Carl do not envy Alice because her piece is worth at most 1/3 and their piece at least (1/2)*(2/3) = 1/3.
Bob does not envy Carl because their pieces are equal in his eyes; Carl does not envy Bob because he picked the best piece in his eyes.
Dividing a 'bad' cake
The rotating-knife procedure can be adapted for chore division - dividing a cake with a negative value: in the initial step, The rightmost cut should selected, instead of the leftmost cut.