68:
47:, 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
58:
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.
280:
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):
764:
17:
769:
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
138:
thinks that the two largest parts are equal (such that no trimming is needed), then each player chooses a part in this order:
803:
87:. Where the procedure gives a criterion for a decision it means that criterion gives an optimum choice for the player.
924:
902:
873:
844:
774:
773:
cake. A refinement of this infinite procedure yields a finite envy-free division procedure: the
730:
52:
32:
929:
766:
equal pieces and the other partners follow by trimming. The resulting division is envy-free.
8:
40:
898:
869:
840:
809:
799:
625:), then we only need to use the first part of the Selfridge–Conway procedure, i.e.:
817:
44:
36:
327:
In the following analysis "largest" means "largest according to that player":
918:
622:
821:
67:
659:
This procedure can be generalized to 4 partners in the following way:
638:
trims at most one piece such that the two largest pieces are equal;
813:
94:
divides the cake into three pieces they consider of equal size.
837:
Fair
Division: From cake-cutting to dispute resolution
617:
Note that if all we want is an envy-free division for
733:
428:
in 3 pieces, so for them all those pieces are equal.
115:
to make it the same size as the second largest. Now
758:
723:By induction, the procedure can be generalized to
542:since they cut the cake in the first round. Also,
186:chooses the last piece leaving just the trimmings
43:. Selfridge discovered it in 1960, and told it to
916:
514:didn't receive a larger share. In other words:
468:didn't receive a larger share. In other words:
366:. So no other player received a larger share:
882:
853:
828:
793:
727:partners, the first one dividing the cake to
168:chooses a piece with the limitation that if
888:
859:
834:
796:Cake-Cutting Algorithms: Be Fair If You Can
889:Brams, Steven J.; Taylor, Alan D. (1996).
860:Brams, Steven J.; Taylor, Alan D. (1996).
835:Brams, Steven J.; Taylor, Alan D. (1996).
632:divides the cake into three equal pieces;
31:is a discrete procedure that produces an
66:
895:From cake-cutting to dispute resolution
866:From cake-cutting to dispute resolution
798:. Natick, Massachusetts: A. K. Peters.
794:Robertson, Jack; Webb, William (1998).
720:This guarantees that there is no envy.
656:This guarantees that there is no envy.
35:for three partners. It is named after
14:
917:
210:; let's call the player who chose it
263:chooses the last remaining piece of
787:
194:It remains to divide the trimmings
119:is divided into: the trimmed piece
24:
18:Selfridge–Conway discrete procedure
612:
424:. Also, they are the one that cut
25:
941:
358:. And they consider their choice
62:
101:the largest piece according to
75:Suppose we have three players
13:
1:
780:
7:
621:of the cake (i.e. we allow
362:to be the largest piece of
275:
10:
946:
202:has been chosen by either
29:Selfridge–Conway procedure
868:]. pp. 131–137.
759:{\displaystyle 2^{n-2}+1}
698:largest pieces are equal;
684:largest pieces are equal;
162:and the two other pieces.
71:Selfridge–Conway division
229:into three equal pieces.
925:Fair division protocols
775:Brams–Taylor procedure
760:
680:pieces, such that the
666:divides the cake into
158:chooses a piece among
127:. Leave the trimmings
72:
53:envy-free cake-cutting
33:envy-free cake-cutting
761:
694:piece, such that the
488:chose their piece of
214:and the other player
198:. The trimmed piece
131:to the side for now.
70:
897:]. p. 137.
839:. pp. 116–120.
731:
704:takes a piece, then
644:takes a piece, then
530:. Remember that for
249:chooses a piece of
235:chooses a piece of
756:
123:and the trimmings
111:cuts off a bit of
73:
41:John Horton Conway
805:978-1-56881-076-8
420:since they chose
16:(Redirected from
937:
909:
908:
886:
880:
879:
857:
851:
850:
832:
826:
825:
791:
765:
763:
762:
757:
749:
748:
594:did not receive
484:. Remember that
21:
945:
944:
940:
939:
938:
936:
935:
934:
915:
914:
913:
912:
905:
887:
883:
876:
858:
854:
847:
833:
829:
806:
792:
788:
783:
738:
734:
732:
729:
728:
615:
613:Generalizations
602:would not envy
586:took the whole
278:
180:must choose it.
65:
23:
22:
15:
12:
11:
5:
943:
933:
932:
927:
911:
910:
903:
881:
874:
852:
845:
827:
804:
785:
784:
782:
779:
755:
752:
747:
744:
741:
737:
718:
717:
699:
690:trims at most
685:
676:trims at most
671:
654:
653:
639:
633:
614:
611:
610:
609:
608:
607:
558: + (
510:believes that
505:
504:in their view.
464:believes that
429:
391:
374: ≥
325:
324:
310:
296:
277:
274:
273:
272:
258:
244:
230:
192:
191:
190:to be divided.
181:
172:didn't choose
163:
153:
152:
151:
106:
95:
64:
61:
51:partners (see
37:John Selfridge
9:
6:
4:
3:
2:
942:
931:
928:
926:
923:
922:
920:
906:
900:
896:
892:
891:Fair Division
885:
877:
871:
867:
863:
862:Fair Division
856:
848:
842:
838:
831:
823:
819:
815:
811:
807:
801:
797:
790:
786:
778:
776:
772:
767:
753:
750:
745:
742:
739:
735:
726:
721:
715:
711:
707:
703:
700:
697:
693:
689:
686:
683:
679:
675:
672:
670:equal pieces;
669:
665:
662:
661:
660:
657:
651:
647:
643:
640:
637:
634:
631:
628:
627:
626:
624:
623:free disposal
620:
605:
601:
597:
593:
589:
585:
581:
577:
574: ≥
573:
570:); therefore
569:
566: +
565:
562: +
561:
557:
554: =
553:
550: +
549:
546: =
545:
541:
537:
533:
529:
525:
522: ≥
521:
517:
513:
509:
506:
503:
500: ≥
499:
495:
491:
487:
483:
479:
476: ≥
475:
471:
467:
463:
460:
459:
457:
454: =
453:
449:
446: ≥
445:
441:
437:
433:
430:
427:
423:
419:
416: ≥
415:
411:
408: ≥
407:
404:. For them,
403:
399:
395:
392:
389:
385:
381:
377:
373:
369:
365:
361:
357:
354: ≥
353:
349:
346: ≥
345:
341:
337:
333:
330:
329:
328:
322:
318:
314:
311:
308:
304:
300:
297:
294:
290:
286:
283:
282:
281:
270:
267:- we name it
266:
262:
259:
256:
253:- we name it
252:
248:
245:
242:
239:- we name it
238:
234:
231:
228:
224:
221:
220:
219:
217:
213:
209:
205:
201:
197:
189:
185:
182:
179:
175:
171:
167:
164:
161:
157:
154:
149:
145:
141:
137:
133:
132:
130:
126:
122:
118:
114:
110:
107:
104:
100:
96:
93:
90:
89:
88:
86:
82:
78:
69:
63:The Procedure
60:
56:
54:
50:
46:
42:
38:
34:
30:
19:
930:Cake-cutting
894:
890:
884:
865:
861:
855:
836:
830:
795:
789:
770:
768:
724:
722:
719:
713:
709:
705:
701:
695:
691:
687:
681:
677:
673:
667:
663:
658:
655:
649:
645:
641:
635:
629:
618:
616:
603:
599:
595:
591:
587:
583:
579:
575:
571:
567:
563:
559:
555:
551:
547:
543:
539:
538:is equal to
535:
531:
527:
523:
519:
515:
511:
507:
501:
497:
493:
489:
485:
481:
477:
473:
469:
465:
461:
455:
451:
447:
443:
442:. For them,
439:
435:
431:
425:
421:
417:
413:
409:
405:
401:
397:
393:
387:
383:
379:
375:
371:
367:
363:
359:
355:
351:
347:
343:
342:. For them,
339:
335:
331:
326:
320:
316:
312:
306:
302:
298:
292:
288:
284:
279:
268:
264:
260:
254:
250:
246:
240:
236:
232:
226:
222:
215:
211:
207:
203:
199:
195:
193:
187:
183:
177:
173:
169:
165:
159:
155:
147:
146:and finally
143:
139:
135:
128:
124:
120:
116:
112:
108:
102:
98:
91:
84:
80:
76:
74:
57:
48:
28:
26:
582:. (Even if
97:Let's call
45:Richard Guy
919:Categories
904:0521556449
875:0521556449
846:0521556449
781:References
315:received:
301:received:
287:received:
743:−
434:received
396:received
334:received
822:2730675W
814:97041258
276:Analysis
712:, then
708:, then
648:, then
496:, thus
492:before
901:
872:
843:
820:
812:
802:
771:entire
619:a part
893:[
864:[
225:cuts
899:ISBN
870:ISBN
841:ISBN
810:LCCN
800:ISBN
590:and
450:and
412:and
350:and
83:and
39:and
27:The
596:A22
580:A21
568:A23
564:A22
560:A21
528:A21
520:A22
502:A23
498:A22
482:A23
474:A22
440:A22
402:A23
388:A22
380:A23
372:A21
360:A21
340:A21
321:A22
307:A23
293:A21
269:A23
255:A22
241:A21
218:.
206:or
134:If
55:).
921::
818:OL
816:.
808:.
777:.
714:P1
710:P2
706:P3
702:P4
688:P3
674:P2
664:P1
650:P1
646:P2
642:P3
636:P2
630:P1
606:.)
604:PA
600:P1
598:,
592:P1
588:A2
584:PA
578:+
576:A1
556:A1
552:A2
548:A1
534:,
532:P1
526:+
524:A1
518:+
512:PA
508:P1
494:PB
490:A2
486:P1
480:+
472:+
466:PB
462:P1
458:.
448:A1
438:+
432:P1
426:A2
410:A1
400:+
394:PB
386:+
382:,
378:+
370:+
368:A1
364:A2
352:A1
344:A1
338:+
336:A1
332:PA
319:+
313:P1
305:+
299:PB
291:+
289:A1
285:PA
265:A2
261:PB
251:A2
247:P1
237:A2
233:PA
227:A2
223:PB
216:PB
212:PA
208:P3
204:P2
200:A1
196:A2
188:A2
184:P1
178:P2
176:,
174:A1
170:P3
166:P2
160:A1
156:P3
148:P1
144:P2
142:,
140:P3
136:P2
129:A2
125:A2
121:A1
109:P2
103:P2
92:P1
85:P3
81:P2
79:,
77:P1
907:.
878:.
849:.
824:.
754:1
751:+
746:2
740:n
736:2
725:n
716:.
696:2
692:1
682:3
678:2
668:5
652:.
572:C
544:A
540:A
536:C
516:C
478:B
470:C
456:B
452:C
444:C
436:C
422:B
418:C
414:B
406:B
398:B
390:.
384:C
376:B
356:C
348:B
323:.
317:C
309:.
303:B
295:.
271:.
257:.
243:.
150:.
117:A
113:A
105:.
99:A
49:n
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
