Knife Fight

How can three people divide a cake so that none feels that another has a larger piece than his own? The Selfridge–Conway procedure, devised by mathematicians John Selfridge and John Horton Conway, will solve the problem in at most 5 cuts; it’s been called “one of the prettiest in the subject of cake cutting.”

Call the three participants Tom, Dick, and Harry. Tom begins by cutting the cake into three pieces that he regards as equal. Tom will be free of envy no matter how these are distributed, because he thinks they’re all the same. Now if Dick and Harry have different opinions as to which piece is largest, then everyone’s happy; we can divide the cake with no conflict.

But if both Dick and Harry both have their eyes on the same piece, then we have a problem — one of them is going to envy the other. The answer is to do some trimming: Dick trims the largest piece (in his eyes) until it matches the second-largest piece in size. Set the trimmings aside for the moment. (If Dick thinks the top two pieces are equal then no trimming is necessary.)

Now both Tom and Dick feel there’s more than one piece tied for biggest. So let Harry have his choice; this guarantees that he’ll be satisfied. This will leave behind at least one of Dick’s top two pieces, which he can have (if both are available then we insist he take the one he trimmed). And now Tom gets the remaining piece, which must be an untrimmed one, so he can have no objection.

What about the trimmings? Well, Tom got one of the untrimmed pieces, and he thought he made the inital cuts equitably, so he can have no objection if the trimmings (or any portion of them) go to the person who got the trimmed piece. Suppose that’s Dick. Have Harry divide the trimmings into three equal portions, and then have Dick choose first, Tom second, and Harry third. Dick is happy because he gets first choice, Tom can’t envy him for the reason just stated, and Harry cut the pieces to be equal, so he can’t feel envy either. Each of the three should be happy with his lot.

(Jack Robertson and William Webb, Cake-Cutting Algorithms, 1998.)