Cake cutting: Not just cool titles

I have recently written two survey articles about cake cutting:

1. Cake Cutting: Not Just Child’s Play, a popular (as opposed to scholarly) article published in the July issue of the Communications of the ACM.
2. Cake Cutting Algorithms, draft (comments welcome!) of chapter 13 of the upcoming Handbook of Computational Social Choice (which I am editing with Felix Brandt, Vince Conitzer, Ulle Endriss, and Jerome Lang).

These articles explain at length why I think cake cutting is cool. Here I’ll try to convince you in a few paragraphs.

Imagine that the cake is rectangular and heterogeneous, i.e., players have different values for pieces of cake. Each player has a valuation function that maps a given piece of cake to its value; assume that the valuations are additive and the value of the whole cake is 1. An allocation is proportional if each player has value at least 1/n for its piece, where n is the number of players.

Consider the following cake cutting algorithm. Each player makes a mark at the point such that the piece of cake to the left of the mark is worth 1/n to that player. The player who made the leftmost mark gets the piece, and the satisfied player and allocated piece are removed from the game. We repeat this process until there is only one player, who gets the remaining piece. This algorithm is clearly proportional: Each player before the last player has value exactly 1/n for his piece, while the last player has value at most 1/n for each piece that was allocated to another player, and therefore value at least 1-(n-1)/n=1/n for his own piece. Notice that this algorithm requires operations: In round k, the n-k+1 remaining players make marks.

Let us now slightly modify the algorithm. Initially, each player makes a mark such that the piece of cake to the left (and to the right) of the mark is worth 1/2. Suppose for ease of exposition that n is a power of 2. We recursively call the algorithm with the “owners” of the first n/2 marks from the left, and the piece of cake to the left of their rightmost mark; and with the remaining players and remaining cake. When there is only one player, he gets the piece. Each recursive call includes half of the players and a piece of cake whose value for these players is at least half the value of the previous piece, so after calls the value a player receives is at least . By examining the recursion tree, whose height is , it is easy to see that the number of operations is . Strikingly, in a concrete complexity model for cake cutting it is possible to show that no algorithm can do better. How? Read the chapter.

Cake cutting is great because it calls for algorithmic insights and computational thinking, yet relatively few computer scientists have so far been involved. And the best thing about cake cutting? How else would you write papers with cool titles like Cake Cutting is Not a Piece of Cake and Throw One’s Cake – and Eat It Too.

Advertisement