Levmore–Cook moving-knives procedure


The Levmore–Cook moving-knives procedure is a procedure for envy-free cake-cutting among three partners. It is named after Saul X. Levmore and Elizabeth Early Cook who presented it in 1981.
It assumes that the cake is two-dimensional. It requires two knives and four cuts, so some partners may receive disconnected pieces.

Procedure

We name the partners Alice, Bob and Carl.
Initially, Alice cuts the cake to three pieces equal in her eyes. Bob and Carl each point to their favorite piece.
Easy case: Bob and Carl point to different pieces. Each receives his favorite piece and Alice the remaining piece.
Hard case: Bob and Carl point to the same piece. Say this is piece X and the other pieces are Y and Z. Now Alice takes two knives and moves them simultaneously over piece X:
Initially XR=X, so for Bob and Carl it is bigger than Y and Z. Moreover, Initially XLT and XLB are empty so XR is bigger than the two pairs: Y+XLT and Z+XLB.
As Knife #1 moves rightwards, XR shrinks while XLT and XLB grows. At some point, either Bob or Carl thinks that XR equals one of the two pairs. The first one that thinks there is equality, shouts "stop!" and receives his chosen pair. Alice receives the other pair, and the non-shouter receive XR.

Analysis

We analyze the case when Bob shouted "stop!" and picked the pair Y+XLT. Alice gets Z+XLB and Carl gets XR. The division is envy-free because:
The other cases are analogous.

Variants

It is possible to let the shouter choose one of the four pairs: Y+XLT, Y+XLB, Z+XLT, Z+XLB.
This modification favors the non-shouter, since the shouter will typically shout "stop"
sooner.
Levmore and Cook presented a generalization of their procedure for 4 partners. However, it was later shown that this generalization does not work in all cases.