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.

Activity 1
Suppose you and a friend have a cake that is half chocolate and half vanilla. To quantify how much you and your friend want chocolate or vanilla you have assigned monetary values in dollars to each section of the cake. You have assigned the values $2 for chocolate and $0.75 for vanilla. You friend has assigned the values $1 for chocolate and $1.25 for vanilla. Thus the chocolate part of the cake is worth $2 to you and $1 to your friend.
  1. Divide the chocolate part of the cake so that each of you receives pieces of the same worth.
  2. Divide the vanilla part of the cake so that each of you receives pieces of the same worth.
  3. What fraction of the cake did you receive? What fraction did your friend?

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:

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.

Activity 2: Describe how each scenario above is a cake cutting problem. Also figure out whether the resource in the example is discrete or continuous. Note that this may depend on your interpretation of the example.

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.

The cake cutting problem is an example of an optimization problem. Such problems consist of trying to find inputs for a function which either maximize or minimize the function. Often there is also a constraint placed on the input values as well. Such problems have many applications, from designing assembly lines to determing how a company prices its products to maximize profit.

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 dplayer=V-f. We then add up the value d for every player to get dtotal. Say we have n players, then dtotal/n-dplayer 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.

Activity 1
Let's return to our initial example. Call the players A, B and C. The following table shows what each player bid for each prize:
CD concert movie game
A $10 $10 $0 $19
B $5 $3 $7 $18
C $8 $17 $2 $18
  1. Calculate d for each player.
  2. Calculate how much money each player is owed.
  3. What prizes did each player get, and how much money did they pay/receive?