The Selfridge–Conway procedure is a discrete procedure that produces an envy-free cake-cutting for three partners.[1]: 13–14  It is named after John Selfridge and John Horton Conway. Selfridge discovered it in 1960, and told it to Richard Guy, who told many people, but Selfridge did not publish it. John Conway later discovered it independently, and also never published it.[2] This procedure was the first envy-free discrete procedure devised for three partners, and it paved the way for more advanced procedures for n partners (see envy-free cake-cutting).

A procedure is envy-free if each recipient believes that (according to their own measure) no other recipient has received a larger share. The maximal number of cuts in the procedure is five. The pieces are not always contiguous.

The Procedure

Selfridge–Conway division

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 they consider 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 the side for now.
    • If P2 thinks that the two largest parts are equal (such that no trimming is needed), 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.

It remains to divide the trimmings A2. The trimmed piece A1 has been chosen by either P2 or P3; let's call the player who chose it PA and the other 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 a larger share. 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 that player":

  • PA received A1 + A21. For them, A1 ≥ B and A1 ≥ C. And they consider their choice A21 to be the largest piece of A2. So no other player received a larger share: A1 + A21  ≥  B + A23, C + A22.
  • PB received B + A23. For them, B ≥ A1 and B ≥ C since they chose B. Also, they are the one that cut A2 in 3 pieces, so for them all those pieces are equal.
  • P1 received C + A22. For them, C ≥ A1 and C = B.
    • P1 believes that PB didn't receive a larger share. In other words: C + A22  ≥ B + A23. Remember that P1 chose their piece of A2 before PB, thus A22  ≥ A23 in their view.
    • P1 believes that PA didn't receive a larger share. In other words: C + A22  ≥ A1 + A21. Remember that for P1, C is equal to A since they cut the cake in the first round. Also, A = A1 + A2 = A1 + (A21 + A22 + A23); therefore C  ≥ A1 + A21. (Even if PA took the whole A2 and P1 did not receive A22, P1 would not envy PA.)

Generalizations

Note that if all we want is an envy-free division for a part of the cake (i.e. we allow free disposal), then we only need to use the first part of the Selfridge–Conway procedure, i.e.:

  • P1 divides the cake into three equal pieces;
  • P2 trims at most one piece such that the two largest pieces are equal;
  • P3 takes a piece, then P2, then P1.

This guarantees that there is no envy.

This procedure can be generalized to 4 partners in the following way:[3]

  • P1 divides the cake into 5 equal pieces;
  • P2 trims at most 2 pieces, such that the 3 largest pieces are equal;
  • P3 trims at most 1 piece, such that the 2 largest pieces are equal;
  • P4 takes a piece, then P3, then P2, then P1.

This guarantees that there is no envy.

By induction, the procedure can be generalized to n partners, the first one dividing the cake to equal pieces and the other partners follow by trimming. The resulting division is envy-free.

We can apply the same procedure again on the remainders. By doing so an infinite number of times, we get an envy-free division of the entire cake.[4] A refinement of this infinite procedure yields a finite envy-free division procedure: the Brams–Taylor procedure.

References

  1. ↑ Robertson, Jack; Webb, William (1998). Cake-Cutting Algorithms: Be Fair If You Can. Natick, Massachusetts: A. K. Peters. ISBN 978-1-56881-076-8. LCCN 97041258. OL 2730675W.
  2. ↑ Brams, Steven J.; Taylor, Alan D. (1996). Fair Division [From cake-cutting to dispute resolution]. pp. 116–120. ISBN 0521556449.
  3. ↑ Brams, Steven J.; Taylor, Alan D. (1996). Fair Division [From cake-cutting to dispute resolution]. pp. 131–137. ISBN 0521556449.
  4. ↑ Brams, Steven J.; Taylor, Alan D. (1996). Fair Division [From cake-cutting to dispute resolution]. p. 137. ISBN 0521556449.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.