# cake-cutting problem

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.^{1} 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.

## The 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.^{4}

## 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.