In problems of envy-free division

Envy-free

In mathematical sociology and especially game theory, envy-free is a property of certain fair division algorithms for a divisible heterogeneous good over which different players may have different preferences....

, the Selfridge–Conway discrete procedure presents a solution for three players. It is named after John Selfridge and John Horton Conway

John Horton Conway

John Horton Conway is a prolific mathematician active in the theory of finite groups, knot theory, number theory, combinatorial game theory and coding theory...

who discovered it independently in 1960. This procedure was the first envy-free discrete procedure devised for three players.

A procedure is envy-free if each recipient believes that (according to its measure) no other recipient has received more than he has.

The maximal number of cuts in the procedure is 5. The division is not always contiguous.

The Procedure

Suppose we have three players P1, P2 and P3. Where the procedure gives a criterion for a decision it means that criterion gives an optimum choice for the player.

1. P1 divides the cake into three pieces he considers of equal size.
2. Let's call A the largest piece according to P2.
3. P2 cuts off a bit of A to make it the same size as the second largest. Now A is divided into: the trimmed piece A1 and the trimmings A2. Leave the trimmings A2 to one side.
   • If P2 thinks that the two largest parts are equal, then each player chooses a part in this order: P3, P2 and finally P1.
4. P3 chooses a piece among A1 and the two other pieces.
5. P2 chooses a piece with the limitation that if P3 didn't choose A1, P2 must choose it.
6. P1 chooses the last piece leaving just the trimmings A2 to be divided.

Now, the cake minus the trimmings A2 has been divided in an envy free manner. The trimmed piece A1 has been chosen by either P2 or P3. Let's call the player who chose it PA and the other one Player PB.

1. PB cuts A2 into three equal pieces.
2. PA chooses a piece of A2 - we name it A21.
3. P1 chooses a piece of A2 - we name it A22.
4. PB chooses the last remaining piece of A2 - we name it A23.

Analysis

Let's see why the procedure is envy-free. It must be shown that each player believes that no other player received more than he had. Without loss of generality, we can write (see illustration above):

• PA received: A1 + A21.
• PB received: B + A23.
• P1 received: C + A22.

In the following analysis "largest" means "largest according to the player":

• PA received A1 + A21 (the largest piece of A2). For him, A1 ≥ B and A1 ≥ C. So obviously, no other player received more than he did: A1 + A21  ≥  B + A23, A1 + A21.
• PB received B + A23. For him, B ≥ A1 and B ≥ C. Also, he is the one that cut A2 in 3 pieces, so for him all the pieces are equal.
• P1 received C + A22. For him, C ≥ A1 and C = B.
  • P1 believes that PB didn't receive more than he did. In other words: C + A22  ≥ B + A23. Remember that P1 chose his piece of A2 before PB thus A22  ≥ A23.
  • P1 believes that PA didn't receive more than he had. In other words: C + A22  ≥ A1 + A21. Remember for P1, C is equal to A (he cut the cake in the first round). Also, A = A1 + A2; therefore C  ≥ A1 + A21. (Even if PA took the whole A2, P1 would not envy PA.)