Selfridge–Conway procedure
Introduction The '''Selfridge–Conway procedure''' is a discrete procedure that produces an envy-free cake-cutting for three partners. 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. 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 divisionSuppose 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.# '''P1''' divides the cake into three pieces they consider of equal size.#Let's call '''A''' the largest piece according to '''P2'''.#'''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'''.#'''P3''' chooses a piece among '''A1''' and the two other pieces.#'''P2''' chooses a piece with the limitation that if '''P3''' didn't choose '''A1''', '''P2''' must choose it.#'''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'''. #'''PB''' cuts '''A2''' into three equal pieces.#'''PA''' chooses a piece of '''A2''' - we name it '''A21'''.#'''P1''' chooses a piece of '''A2''' - we name it '''A22'''.#'''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:* '''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. A refinement of this infinite procedure yields a finite envy-free division procedure: the Brams–Taylor procedure.
References