Selfridge–Conway discrete procedure

From Wikipedia, the free encyclopedia
Jump to: navigation, search

In problems of envy-free division, the Selfridge–Conway discrete procedure presents a solution for three players.[1] It is named after John Selfridge and John Horton Conway. Selfridge discovered it in 1960, and told it to Richard Guy, who told it to many people, but Selfridge did not publish it. John Conway discovered it independently in 1993, and also never published it, but the result is attributed to them in a number of books.[2] This procedure was the first envy-free discrete procedure devised for three players. Solutions for n players were later found by Steven Brams and Alan Taylor.

A procedure is envy-free if each recipient believes that (according to its measure) no other recipient has received more than he has. In their solution, the maximal number of cuts in the procedure is five. The pieces are not always contiguous.

The Procedure[edit]

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 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 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[edit]

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. For him, A1 ≥ B and A1 ≥ C. And he considers his choice A21 to be the largest piece of A2. So no other player received more than he did: A1 + A21  ≥  B + A23, C + A22.
  • PB received B + A23. For him, B ≥ A1 and B ≥ C since he chose B. Also, he is the one that cut A2 in 3 pieces, so for him all those 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 in his view.
    • P1 believes that PA didn't receive more than he had. In other words: C + A22  ≥ A1 + A21. Remember that for P1, C is equal to A since he 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.)

Shorter analysis[edit]

The division has two steps and we analyze each step separately: first, the cake without the trimmings; then, the trimmings.

The cake without the trimmings has been divided in an envy free manner, because:

  • P3 is the first to choose, so he must have chosen his preferred piece;
  • P2 is the second to choose, and there are two pieces that he equally prefers, so he must have chosen one of them;
  • P1 initially cut the cake to three equal pieces; one of them was trimmed, but the trimmed piece was taken by either P2 or P3, so now the remaining piece is one of two pieces that he equally prefers (and values as exactly 1/3).

The trimmings have been divided in an envy free manner, because:[3]

  • PA chooses first;
  • P1 chooses second so he cannot envy PB; although P1 might prefer the piece of the trimmings taken by PA, he will not envy PA overall, since the trimmed piece (A1) combined with the entire trimmings (A2)

is worth only 1/3 to agent 1, and agent 1 already has at least 1/3 from the first allocation!

  • PB initially cut the trimmings to three equal pieces, so whatever piece remains, he has no reason to envy the others.

References[edit]

  1. ^ Robertson, Jack; William Webb. Cake-Cutting Algorithms: be fair if you can. A.K.Peters Limited. p. 13. ISBN 1-56881-076-8.  1998.
  2. ^ Fair Division, From cake-cutting to dispute resolution, Steven J. Brams and Alan D. Taylor, Cambridge University Press, 1996, ISBN 978-0521556446
  3. ^ Based on: Procaccia, Ariel (2009). "Thou Shalt Covet Thy Neighbor’s Cake". IJCAI.