Numb3rs 317: One Hour

The team has an hour to track down a kidnapper who is carefully eliminating their surveillance. Charlie uses the idea of cake cutting algorithms

The Cake Cutting Problem

Imagine you and a friend have a cake and want to divide it between the two of you. One way to do this is to let your friend cut the cake into two pieces, and then you pick a piece leaving your friend with the other piece. If your friend made one piece bigger than the other then you get to take that piece, leaving your friend with the smaller piece. This forces your friend to cut the cake fairly so that he doesn't get shorted.

This is just the simplest version of the cake cutting problem. As Charlie points out, your cake may have chocolate and vanilla layers, and you might like chocolate much more than your friend does. In this case fairness does not equate to equal amounts, as you may be as happy with a small portion of chocolate cake as your friend is with the rest of the cake. You may also have to divide the cake between more than two people. If you and your friend baked the cake then how you divide the cake might also take into account how much work each of you put into making the cake.

Generalizing, the cake cutting (a.k.a. fair division) problem is really about how we divide resources fairly between multiple parties. Be aware that the resource may be continuous or discrete. A continuous resource can be cut in any fashion, so that the ratio between portions can have any positive value. A discrete resource comes in indivisible portions, so that the ratio between portions is always a rational number. You can think of this as the difference between dividing a cake with a knife or splitting up cupcakes. Cake cutting is a very important problem in everyday life. The following examples can be viewed as cake cutting problems:

• How a company decides to pay its workers
• How a timber company chooses the price and quantity of logs to sell to different clients
• Dividing inherited land between siblings
• Assigning m jobs to n people
• How pirates divide their booty.

Of course it is important to remember that these are real-world situations, so fairness may not be achieved. However, it is often approximated, as workers who aren't paid fairly tend to quit or strike, and clients who feel cheated will look for different suppliers.

Sealed Bids

Suppose your local radio station is having a contest for teams of three people. The top prize is a package consisting of a CD, a concert ticket, a movie ticket and a video game. You and a couple of friends enter and win. How do you fairly divide the prizes? One method is to use sealed bids. Each of you writes down a price you would be willing to pay for each prize without knowing what prices the others write down. You then reveal all the prices simultaneously. For each prize the highest bidder gets to keep the prize. Players then make monetary payments to each other to ensure fairness.

In general suppose there are n players and m prizes. To formalize the above procedure we calculate each player's fair share as the average of the player's bids on the m prizes. Next we calculate the difference between the value, V, in prizes that each player received and that player's fair share, f, that is d_player=V-f. We then add up the value d for every player to get d_total. Say we have n players, then d_total/n-d_player is the amount of money the player is owed. If m is negative then the player must pay that much money to the other players. You can read more about sealed bids and fair division in general here.