Cake cutting

When two people are to divide up a cake between them, there is a well-known procedure for ensuring fairness: the “I cut, you choose” method, in which one of the players cuts the cake in two, and the other gets to choose first. But how can we do this when there are three or more people who wants a piece of the cake? Wikipedia has a couple of articles on the problem (here is a good place to start). One way to split the cake is to use a moving knife. In the simplest form, one of the players steadily moves a knife across the cake from left to right, and any player may at any point call “cut!”; at that point, the cake is cut, the calling player gets the piece to the left of the knife, and the remaining players continue dividing the cake among themselves.

While this procedure does the job in theory, in the sense that all n players get 1/nth of the cake, in practice it requires the players to make quick judgements about exactly when to call. Here’s an alternative procedure, which I haven’t seen described anywhere else (but I doubt that I was the first to invent it):

  1. If there’s just one player left, she gets the remainder of the cake. Otherwise, pick an arbitrary player, and let her cut a piece of the cake any way she wants.
  2. All players except the one who just cut the cake declare whether they want the piece or not.
  3. If at least one player wanted the piece, it’s randomly given to one of them. If no one wanted it, it’s given to the player who cut it.
  4. The player who was just given a piece of the cake is eliminated, and the remainder of the cake is divided between the remaining players.

Let’s prove that this algorithm is fair, in the sense that any player is assured to get at least 1/nth of the cake, on average. The proof is by induction.

For 1 player, the algorithm is obviously fair, since it allocates the entire cake to the only player.

For n players, there are two cases:

  1. If you are the player chosen to cut a piece of the cake, cut a piece that is precisely 1/nth of the cake. That way, depending on what the other players choose, you either get 1/nth of the cake; or (on average) 1/(n - 1) of the remaining (n - 1)/n cake, since by induction we know that the algorithm works for n - 1 players.
  2. If someone else cuts a piece p of the cake, you have to determine if p is smaller or larger than 1/n.
    • If p < 1/n, choose to not take the piece; by induction, you then get (on average) more than 1/(n - 1) of the remaining (n - 1)/n cake—that is, at least 1/nth of the whole cake.
    • If p > 1/n, choose to take the piece. Let k be the number of players who decide to take it; then 1 ≤ k ≤ n - 1. With probability 1/k you get p cake, and with probability (k - 1)/k you get 1/(n - 1) of the remaining 1 - p cake. The expected value of this is p/k + (k - 1)(1 - p)/k(n - 1) = (pn + k - kp - 1)/k(n - 1). Since p > 1/n, this is greater than (k - k/n)/k(n - 1) = 1/n.
    • If p = 1/n, it doesn’t matter if you take the piece or not; you get 1/n of the cake either way.

So this algorithm has two desirable properties:

  • By always cutting slices of size 1/n, a player is guaranteed to get her fair 1/n of the cake, on average. That is, the algorithm is fair.
  • If any player cuts slices of size other than 1/n, she gets less than 1/n of the cake (by necessity, since the proof says that all the other players get more). This means that all players are motivated to cut slices of the right size, which in turn means that the actual payoff for each player will be close to the average payoff.