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.