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.
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.