How can a group of people cut up a cake so that each gets what they consider to be a fair share? In its modern mathematical form, this classic problem of fair division dates from the Second World War when Hugo Steinhaus tackled it using a game theory approach.¹ Any number of "players" are allowed. They agree on rules for dividing the cake, and then everyone follows those rules. In the end, each player must get what he or she perceives to be a fair share. In the simplest case, involving just two people, there is an easy, well-known strategy: one cuts, the other chooses. Can this method be extended to three people? Can it be extended so that each person, according to his own judgment, receives the biggest piece? Steinhaus was able to prove that a so-called envy-free division, where everyone believes they got the best deal exists in every case, for any number of players. However, it was left for others to find actual algorithms that worked for three or more players.

 

Three-person case

A three-person envy-free method was first devised by John Selfridge and John Conway. Suppose the players are called Alice, Bob, and Carol. Then the method goes like this. (1) Alice cuts the cake into what she thinks are thirds. (2) Bob trims one piece to create a two-way tie for largest, and sets the trimmings aside. (3) Carol picks a piece, then Bob, then Alice. Bob has to take a trimmed piece if Carol does not. Call the person who took the trimmed piece T, and the other (of Bob and Carol) NT. (4) To deal with the trimmings, NT cuts them into what she thinks are thirds. (5) The players pick pieces in this order: T, Alice, NT. The key to the success of the Selfridge-Conway strategy is that for the trimmings, Alice has an "irrevocable advantage" with respect to T, since Alice will never envy T even if T gets all the trimmings. Thus Alice can pick after T and allow the method to end in a finite number of steps.

 

Cake-cutting involving four or more people

For four or more cake-cutters, envy-free solutions are very complex and can take arbitrarily long to resolve. However, a general solution of the problem of fair, envy-free division was eventually found in 1992 by the Americans Steven Brams, a political scientist at New York University, and Alan Taylor, a mathematician at Union College in Schenectady, New York.^{2, 3} With two players, the first player cuts the cake in half. With three players, the first player cuts the cake into thirds. With four players, Brams and Taylor showed, the first player, say Bob, cuts the cake into five equal-looking pieces. He passes them to Carol, who trims two at most to create a three-way tie for largest in her eyes. She sets the trimmings aside and gives the five pieces to Don, who trims one at most to create a two-way tie for largest in his eyes. Alice, the fourth player, now selects the piece she likes best. Choosing proceeds in the reverse order from cutting, with the proviso that anyone who trimmed one or more pieces must take one of them if any are still available when it's his or her turn to choose. The extra piece to begin with assures that no player gets second-best. If someone takes a piece she likes before it's her turn to choose, an equivalent piece or better always remains on the table. According to a formula Brams and Taylor developed, Bob must cut the cake into at least 2^(n-2)+1 pieces at the start. This amounts to nine pieces for five players, 17 pieces for six, and so on. Bob has to cut all these extra pieces to make sure that, when he finally gets to choose at the end, there will be a piece left that hasn't been either trimmed or chosen by one of the many other players. With 22 players, Bob has to divide the cake into over a million pieces – small crumbs of comfort in the quest for a fairer world.⁴

 

References

1. Steinhaus, H. "Sur la division pragmatique." Ekonometrika (Supp.), 17: 315-319, 1949.
2. Brams, S. J. and Taylor, A. D. "An Envy-Free Cake Division Protocol." Amer. Math. Monthly, 102: 9-19 (1995).
3. Brams, S. J., and Taylor, A. D. Fair Division: From Cake-Cutting to Dispute Resolution. New York: Cambridge University Press, 1996.
4. Robertson, J., and Webb, W. Cake-cutting Algorithms. Natick, MA: AK Peters, 1998.