13.8 13.7 Cake-Division Procedures: The Problem of Envy

Divide-and-choose has a property that neither of the last two procedures possesses: It can ensure that each player receives a piece of cake he or she considers the largest or tied for the largest. In the case of only two players, this means that each player can get what he or she perceives to be at least half the cake, no matter what the other player does. Thus, divide-and-choose is an envy-free procedure.

Steinhaus’s proportional procedure (the lone-divider method) is not envy-free. For example, consider the case where Carol and Ted both find one piece unacceptable (and this piece is given to Bob). Carol and Ted will not envy each other when one divides and the other chooses, but Bob may think that this is not a 50-50 split. Indeed, if Bob divided the cake initially into what he thought was three equal pieces, an unequal split of the remaining two-thirds of the cake by Carol and Ted means that Bob will prefer the larger of these two pieces to the one-third he got. Consequently, Bob will envy the person who got this larger piece.

The last-diminisher method is also not envy-free. For example, if Bob initially cuts a piece of cake of size one-fourth, and no one else trims it, then Bob receives this piece and exits the game. If Carol is the one to make the next initial cut, she may well cut a piece from the cake that she thinks is of size one-fourth but that Bob thinks is of size considerably more than one-fourth. But Bob is out of the game. Thus, if Ted and Alice think this piece is of size less than one-fourth, then Carol receives it, and so Bob will envy Carol.

556

Nevertheless, there do exist cake-division procedures that are envy-free. We present one of these in what follows.

EXAMPLE 5 The Selfridge-Conway Envy-Free Procedure for Three Players

We start with a cake and three people. The point we wish to arrive at is an envy-free allocation of the entire cake among the three people in a finite number of steps. This task may seem formidable, but quite often in mathematics, an important part of solving a problem involves breaking the problem into identifiable parts. In this case, let’s call our starting point and the final point that we want to reach . Now let’s identify an appropriate in-between point that makes going from to —via —more manageable. Our in-between point stands for getting a constructive procedure that gives an envy-free allocation of part of the cake.

Can we constructively obtain three pieces of cake, whose union may not be the whole cake, which can be given to the three people so that each thinks he or she received a piece at least tied for largest? This turns out to be quite easy with the solution given by John Selfridge and John Conway.

  1. Player 1 cuts the cake into three pieces that he considers to be the same size. He hands the three pieces to Player 2.
  2. Player 2 trims at most one of the three pieces to create at least a two-way tie for largest. Setting the trimmings aside, Player 2 hands the three pieces (one of which may have been trimmed) to Player 3.
  3. Player 3 now chooses, from among the three pieces, one that he considers to be at least tied for largest.
  4. Player 2 next chooses, from the two remaining pieces, one that she considers to be at least tied for largest, with the proviso that if she trimmed a piece in Step 2, and Player 3 did not choose this piece, then she must now choose it.
  5. Player 1 receives the remaining piece.

Let’s reconsider the five steps of this trimming procedure to assure ourselves that each player experiences no envy. Recall that Player 1 cuts the cake into three pieces, and Player 2 trims one of these three pieces. Now Player 3 chooses, and, as the first to choose, he certainly envies no one. Player 2 created a two-way tie for largest, and at least one of these two pieces is still available after Player 3 selects his piece. Hence, Player 2 can choose one of the tied pieces she created and will envy no one. Finally, Player 1 created a three-way tie for largest, and because of the proviso in Step 4, the trimmed piece is not the one left over. Thus, Player 1 can choose an untrimmed piece and therefore will envy no one.

So far we have gone from point to point : Starting with a cake and three players, we have constructively obtained (in finitely many steps) an envy-free allocation of all the cake, except the part that Player 2 trimmed from one of the pieces. We will now describe how can be allocated among the three players in such a way that the resulting allocation of the whole cake is envy-free. (This is the rest of the Selfridge-Conway envy-free procedure.)

The key observation for the case is that Player 1 will not envy the player who received the trimmed piece, even if that player were to be given all of . Recall that Player 1 created a three-way tie and received an untrimmed piece. The union of the trimmed piece and the trimmings yields a piece that Player 1 considers to be exactly the same size as the one he received. thus, assume that it is Player 3 who received the trimmed piece. (It could as well be Player 2.) Player 1 will not envy Player 3, no matter how is allocated.

557

The next step ensures that neither Player 2 nor Player 3 will envy another player when it comes time to allocate . Let Player 2 cut into three pieces she considers to be the same size. Let the players choose which of the three pieces they want in the following order: Player 3, Player 1, Player 2.

To see that this yields an envy-free allocation, notice that Player 3 envies no one, because he is choosing first. Player 1 does not envy Player 2, because he is choosing ahead of her; and Player 1 does not envy Player 3 because, as pointed out earlier, Player 1 will not envy the player who received the trimmed piece. Finally, Player 2 envies no one because she made all three pieces of the same size.

Hence, for , the Selfridge-Conway procedure will give an envy-free allocation of all the cake except , followed by an allocation of that gives an envy-free allocation of all the cake.

A naïve attempt to generalize to what we have done for would proceed as follows: We would begin by having Player 1 cut the cake into four pieces he considers to be the same size. We would then have Players 2 and 3 trim some pieces (but how many?) to create ties for the largest. Finally, we would have the players choose from among the pieces—some of which would have been trimmed—in the following order: Player 4, Player 3, Player 2, Player 1.

This approach fails because Player 1 could be left in a position of envy. To understand how the approach could fail, consider how many pieces Player 3 might have to trim to create a sufficient supply of pieces tied for largest so that he is guaranteed to have one available when it is his turn to choose. Player 3 might have to trim one piece to create a two-way tie for largest. Player 2 might need to trim two pieces to create a three-way tie for largest (because if there were only a two-way tie for largest, Player 3 might further trim one of these pieces and Player 4 might choose the other). This leaves Player 1 in a possible position of envy because we could have a situation where Player 2 trims two pieces and Player 3 trims a third piece, and Player 4 then chooses the only untrimmed piece. If this happens, Player 1, by being forced to choose a trimmed piece, will definitely envy Player 4.

All is not lost, however, because there are modifications of the Selfridge- Conway procedure that will work for arbitrary . For more on this, see Fair Division (cited in the Suggested Readings).

Although we have used the metaphor of cake cutting throughout our discussion of the problem of envy, the idea of successive trimming is nonetheless applicable to problems of fair division other than parceling out the last crumbs of a cake. The main practical problem in applying the trimming procedure is that many fair-division problems involve goods that cannot be divided up at all, much less trimmed in fine amounts. Such goods are said to be indivisible.

It is interesting to recall that when the Allies agreed in 1944 to partition Germany into sectors after World War II (Stage 1), they initially did not reach an agreement about what to do with Berlin (see the figure on the next page). Subsequently, they decided to partition Berlin itself into sectors (Stage 2), even though this city fell 110 miles within the Soviet sector. Berlin was simply too valuable a “piece” for the western Allies (Great Britain, France, and the United States) to cede to the Soviets, which suggests how, after a leftover piece is trimmed off, it can be divided subsequently under the trimming procedure.

558

image

Yet, what if a large piece like Berlin is not divisible? In the settlement of an estate, this might be the house, which may be worth half the estate to the claimants. In this situation, there may be no alternative but to sell this big item and use the proceeds to make the remaining estate more liquid or, in our terms, “trimmable.”