705:
550:
Using the IA procedure, the main BTP procedure creates IAs for all ordered pairs of partners. For example, when there are 4 partners, there are 12 ordered pairs of partners. For each such pair (X,Y), we run a sub-procedure which guarantees that partner X has an IA over partner Y. After every partner
546:
If we want to make sure that Alice gets an IA over a specific player (e.g. Bob), then a much more complicated procedure is required. It successively divides the cake to smaller and smaller pieces, always giving Alice a piece that she values more than Bob's, so that an IA is maintained. This might
703:, Steven J. Brams & Alan D. Taylor, "Computer-based method for the fair division of ownership of goods", issued 1999-11-09, assigned to New York University
341:
521:
429:
373:
294:
225:
541:
489:
469:
449:
397:
268:
248:
181:
161:
141:
114:
91:
39:
contended that the problem solved by the theorem, namely n-person envy-free cake-cutting, was among the most important problems in 20th century mathematics.
551:
has an IA over every other partner, we can just give the remainder to an arbitrary partner and the result is an envy-free division of the entire cake.
593:
27:. It explicated the first finite procedure to produce an envy-free division of a cake among any positive integer number of players.
188:
560:
575:– procedure designed by Brams and Taylor addressing the similar, but distinct, problem of dividing goods between two agents.
684:
725:
620:
51:
302:
572:
494:
402:
346:
273:
566:
24:
69:
The BTP divides the cake part-by-part. A typical intermediate state of the BTP is as follows:
730:
597:
198:
8:
657:
526:
474:
454:
434:
382:
253:
233:
166:
146:
126:
99:
76:
680:
399:
is divided in an envy-free way. Additionally, Alice now has an IA over whoever took
649:
700:
624:
47:
563:– a moving-knife procedure for 4 partners, which uses a finite number of cuts.
719:
627:
547:
take an unbounded time – depending on the exact valuations of Alice and Bob.
187:
As an example of how an IA can be generated, consider the first stage of the
36:
195:
Alice divides the cake to 3 parts she considers equal; let's call the parts
640:
Brams, S. J.; Taylor, A. D. (1995). "An Envy-Free Cake
Division Protocol".
43:
617:
661:
58:
653:
250:) to make it equal to the second-largest; let's call the trimmings
699:
677:
Fair division: from cake-cutting to dispute resolution
50:. It was first published in the January 1995 issue of
529:
497:
491:
in her opinion. So, in Alice's opinion, whoever took
477:
457:
437:
405:
385:
349:
305:
276:
256:
236:
201:
169:
149:
129:
102:
79:
123:(IA) over another partner, say Bob, with respect to
93:, is divided in an envy-free way among all partners.
569:– older and newer procedures for the same problem.
535:
515:
483:
463:
443:
423:
391:
367:
335:
288:
262:
242:
219:
175:
155:
135:
108:
85:
717:
679:. Cambridge University Press. pp. 138–143.
596:. Discover Magazine. 1995-03-01. Archived from
230:Bob trims the piece he considers largest (say,
379:After this stage is done, all the cake except
183:entirely to Bob, Alice still doesn't envy Bob.
668:
693:
35:In 1988, prior to the discovery of the BTP,
674:
639:
675:Brams, Steven J.; Taylor, Alan D. (1996).
54:, and later in 1996 in the authors' book.
630:. For All Practical Purposes. COMAP. 1988
618:More Equal than Others: Weighted Voting
718:
375:if it is available); and lastly Alice.
143:. This means that, regardless of how
189:Selfridge–Conway discrete procedure
13:
336:{\displaystyle (A\setminus Y),B,C}
14:
742:
642:The American Mathematical Monthly
504:
431:. Why? because Alice took either
412:
356:
343:; then Bob chooses (he must take
312:
280:
471:, and both of them are equal to
16:Envy-free cake-cutting procedure
543:– this will not make her envy.
299:Charlie chooses a piece out of
119:One partner, say Alice, has an
633:
611:
586:
561:Brams–Taylor–Zwicker procedure
516:{\displaystyle (A\setminus Y)}
510:
498:
424:{\displaystyle (A\setminus Y)}
418:
406:
368:{\displaystyle (A\setminus Y)}
362:
350:
318:
306:
64:
61:from 1999 related to the BTP.
57:Brams and Taylor hold a joint
1:
579:
52:American Mathematical Monthly
289:{\displaystyle A\setminus Y}
163:is divided, even if we give
7:
554:
10:
747:
116:, remains undivided, but -
96:The rest of the cake, say
42:The BTP was discovered by
30:
573:Adjusted winner procedure
23:(BTP) is a procedure for
73:A part of the cake, say
726:Fair division protocols
567:Envy-free cake-cutting
537:
517:
485:
465:
445:
425:
393:
369:
337:
290:
270:and the trimmed piece
264:
244:
221:
177:
157:
137:
110:
87:
25:envy-free cake-cutting
21:Brams–Taylor procedure
701:US patent 5983205
594:"Dividing the Spoils"
538:
518:
486:
466:
446:
426:
394:
370:
338:
291:
265:
245:
222:
220:{\displaystyle A,B,C}
178:
158:
138:
121:Irrevocable Advantage
111:
88:
527:
495:
475:
455:
435:
403:
383:
347:
303:
274:
254:
234:
199:
167:
147:
127:
100:
77:
623:2019-12-05 at the
533:
513:
481:
461:
441:
421:
389:
365:
333:
286:
260:
240:
217:
173:
153:
133:
106:
83:
536:{\displaystyle Y}
484:{\displaystyle A}
464:{\displaystyle C}
444:{\displaystyle B}
392:{\displaystyle Y}
263:{\displaystyle Y}
243:{\displaystyle A}
176:{\displaystyle Y}
156:{\displaystyle Y}
136:{\displaystyle Y}
109:{\displaystyle Y}
86:{\displaystyle X}
738:
710:
709:
708:
704:
697:
691:
690:
672:
666:
665:
637:
631:
615:
609:
608:
606:
605:
590:
542:
540:
539:
534:
522:
520:
519:
514:
490:
488:
487:
482:
470:
468:
467:
462:
450:
448:
447:
442:
430:
428:
427:
422:
398:
396:
395:
390:
374:
372:
371:
366:
342:
340:
339:
334:
295:
293:
292:
287:
269:
267:
266:
261:
249:
247:
246:
241:
226:
224:
223:
218:
182:
180:
179:
174:
162:
160:
159:
154:
142:
140:
139:
134:
115:
113:
112:
107:
92:
90:
89:
84:
746:
745:
741:
740:
739:
737:
736:
735:
716:
715:
714:
713:
706:
698:
694:
687:
673:
669:
654:10.2307/2974850
638:
634:
625:Wayback Machine
616:
612:
603:
601:
592:
591:
587:
582:
557:
528:
525:
524:
496:
493:
492:
476:
473:
472:
456:
453:
452:
436:
433:
432:
404:
401:
400:
384:
381:
380:
348:
345:
344:
304:
301:
300:
275:
272:
271:
255:
252:
251:
235:
232:
231:
200:
197:
196:
168:
165:
164:
148:
145:
144:
128:
125:
124:
101:
98:
97:
78:
75:
74:
67:
33:
17:
12:
11:
5:
744:
734:
733:
728:
712:
711:
692:
685:
667:
632:
610:
584:
583:
581:
578:
577:
576:
570:
564:
556:
553:
532:
523:can also have
512:
509:
506:
503:
500:
480:
460:
440:
420:
417:
414:
411:
408:
388:
377:
376:
364:
361:
358:
355:
352:
332:
329:
326:
323:
320:
317:
314:
311:
308:
297:
285:
282:
279:
259:
239:
228:
216:
213:
210:
207:
204:
185:
184:
172:
152:
132:
117:
105:
94:
82:
66:
63:
48:Alan D. Taylor
32:
29:
15:
9:
6:
4:
3:
2:
743:
732:
729:
727:
724:
723:
721:
702:
696:
688:
686:0-521-55644-9
682:
678:
671:
663:
659:
655:
651:
647:
643:
636:
629:
628:Sol Garfunkel
626:
622:
619:
614:
600:on 2012-03-10
599:
595:
589:
585:
574:
571:
568:
565:
562:
559:
558:
552:
548:
544:
530:
507:
501:
478:
458:
438:
415:
409:
386:
359:
353:
330:
327:
324:
321:
315:
309:
298:
283:
277:
257:
237:
229:
214:
211:
208:
205:
202:
194:
193:
192:
190:
170:
150:
130:
122:
118:
103:
95:
80:
72:
71:
70:
62:
60:
55:
53:
49:
45:
40:
38:
37:Sol Garfunkel
28:
26:
22:
731:Cake-cutting
695:
676:
670:
645:
641:
635:
613:
602:. Retrieved
598:the original
588:
549:
545:
378:
186:
120:
68:
56:
44:Steven Brams
41:
34:
20:
18:
648:(1): 9–18.
65:Description
720:Categories
604:2015-05-02
580:References
505:∖
413:∖
357:∖
313:∖
281:∖
59:US patent
621:Archived
555:See also
662:2974850
31:History
707:
683:
660:
658:JSTOR
681:ISBN
46:and
19:The
650:doi
646:102
451:or
722::
656:.
644:.
191::
689:.
664:.
652::
607:.
531:Y
511:)
508:Y
502:A
499:(
479:A
459:C
439:B
419:)
416:Y
410:A
407:(
387:Y
363:)
360:Y
354:A
351:(
331:C
328:,
325:B
322:,
319:)
316:Y
310:A
307:(
296:.
284:Y
278:A
258:Y
238:A
227:.
215:C
212:,
209:B
206:,
203:A
171:Y
151:Y
131:Y
104:Y
81:X
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.