88:"The partners being ranged A, B, C,.. N, A cuts from the cake an arbitrary part. B has now the right, but is not obliged, to diminish the slice cut off. Whatever he does, C has the right (without obligation) to diminish still the already diminished (or not diminished) slice, and so on up to N. The rule obliges the "last diminisher" to take as his part the slice he was the last to touch. This partner being thus disposed of, the remaining
270:. For example, suppose the first partner Alice receives a piece (which she values as 1/3 of the total). Then, the other two partners Bob and Charlie divide the remainder in such a way that is fair in their opinion, but in Alice's opinion Bob's share is worth 2/3 while Charlie's share is worth 0. Then Alice envies Bob.
277:. I.e, a partner that won a piece by being the last diminisher, does not have to leave the game, but may rather stay and participate in further steps. If he wins again, he must release his current piece and it is returned to the cake. In order to make sure that the protocol terminates, we select a certain constant
257:
of the cake is to the left of the knife, the cake is cut and the player who spoke gets that piece. Repeat with the remaining cake and players, the last player gets the remainder of the cake. Similar to the last diminisher procedure, it can be used to cut the cake into contiguous parts for each
190:
The procedure is very liberal regarding the cuts. the cuts made by the partners can have any shape; they can even be disconnected. On the other hand, it is possible to restrict the cuts in order to guarantee that the pieces have a nice shape. In particular:
40:
of the total value according to his own subjective valuation. For example, if Alice values the entire cake as $ 100 and there are 5 partners then Alice can receive a piece that she values as at least $ 20, regardless of what the other partners think or do.
132:
The algorithm simplifies in the degenerate case that all partners have the same preference function because the partner that optimally first cuts a slice will also be its last diminisher. Equivalently, each partner 1, 2, ...,
183:) actions are not actual cuts, i.e. Alice can mark her desired slice on a paper and have the other players diminish them on the same paper etc.; only the "last diminisher" has to actually cut the cake. So, only
229:. It was the first example of a continuous procedure in fair division. The knife is passed over the cake from the left end to the right. Any player may say stop when they think
92:−1 persons start the same game with the remainder of the cake. After the number of participants has been reduced to two, they apply the classical rule for halving the remainder."
464:
517:
A disadvantage of the approximate-envy-free variant is that the pieces are not necessarily connected, since pieces are constantly returned to the cake and re-divided. See
492:
323:
426:
406:
386:
366:
346:
295:
255:
512:
104:
for you. There are two options: either you receive the slice that you have cut, or another person receives a smaller slice, whose value for you is less than 1/
328:
In the reentrant version, each partner has a method that guarantees that he receives a slice with a value of at least the largest value minus
628:
650:
145:−1, ..., 1 in turn selects a slice that has not yet been claimed. The first partner who cut a slice other than of value 1/
72:
This publication has initiated a new research topic which is now studied by many researchers in different disciplines; see
57:, who was hiding from the Nazis, occupied himself with the question of how to divide resources fairly. Inspired by the
195:
If the original cake is connected, then it is possible to guarantee that each piece is connected (contiguous).
518:
267:
226:
655:
530:
33:
266:
When there are 3 or more partners, the division obtained by the last-diminisher protocol is not always
434:
66:
36:, i.e., divide the cake among them such that each person receives a piece with a value of at least 1/
601:
559:
469:
300:
411:
391:
371:
351:
331:
280:
624:
96:
Each partner has a method that guarantees that he receives a slice with a value of at least 1/
58:
21:
593:
69:, to find a procedure that can work for any number of people, and published their solution.
24:. It involves a certain heterogenous and divisible resource, such as a birthday cake, and
232:
157:
The last-diminisher protocol is discrete and can be played in turns. In the worst case,
497:
348:. The method is: always cut the current slice such that the remainder has a value of
100:. The method is: always cut the current slice such that the remainder has a value of 1/
54:
137:−1 in turn cuts a slice from the remaining cake. Then in reverse order, each partner
644:
581:
577:
529:
The last diminisher procedure has been improved later in many ways. For details, see
73:
62:
225:
A continuous-time version of this protocol can be executed using the Dubins-Spanier
28:
partners with different preferences over different parts of the cake. It allows the
120:. Hence by induction it is possible to prove that the received value is at least 1/
50:
199:
388:
each time you win, and if you don't win - the value of the winner is at most
84:
This is the description of the division protocol in the words of the author:
206:
61:
procedure for dividing a cake between two brothers, he asked his students,
149:
would be envious of another partner who ended up with more than they did.
213:
112:−1 partners remaining and the value of the remaining cake is more than (
605:
563:
597:
368:
plus your current value. This guarantees that your value grows by
209:, then it is possible to guarantee that each piece is a rectangle.
216:, then it is possible to guarantee that each piece is a triangle.
408:
more than your own value. Thus, the level of envy is at most
202:, then it is possible to guarantee that each piece is convex.
297:
and add a rule that allows each partner to re-enter at most
550:
Steinhaus, Hugo (1948). "The problem of fair division".
621:
Fair division: from cake-cutting to dispute resolution
500:
472:
437:
414:
394:
374:
354:
334:
303:
283:
235:
172:
actions are needed: one action per player per turn.
506:
486:
458:
420:
400:
380:
360:
340:
317:
289:
249:
623:. Cambridge University Press. pp. 130–131.
128:Degenerate case of a common preference function
8:
494:steps and at each step we query each of the
619:Brams, Steven J.; Taylor, Alan D. (1996).
499:
476:
471:
448:
442:
436:
413:
393:
373:
353:
333:
307:
302:
282:
239:
234:
542:
519:envy-free cake-cutting#Connected pieces
521:for other solutions to this problem.
7:
584:(1961). "How to Cut a Cake Fairly".
53:, the Polish-Jewish mathematician
14:
586:The American Mathematical Monthly
108:. In the latter case, there are
459:{\displaystyle n^{2}/\epsilon }
273:A simple solution is to allow
1:
262:Approximate-envy-free version
20:procedure is a procedure for
487:{\displaystyle n/\epsilon }
318:{\displaystyle 1/\epsilon }
672:
466:, since there are at most
212:If the original cake is a
205:If the original cake is a
198:If the original cake is a
421:{\displaystyle \epsilon }
401:{\displaystyle \epsilon }
381:{\displaystyle \epsilon }
361:{\displaystyle \epsilon }
341:{\displaystyle \epsilon }
290:{\displaystyle \epsilon }
431:The run-time is at most
428:(an additive constant).
651:Fair division protocols
175:However, most of these
508:
488:
460:
422:
402:
382:
362:
342:
319:
291:
251:
227:Moving-knife procedure
531:proportional division
509:
489:
461:
423:
403:
383:
363:
343:
320:
292:
252:
34:proportional division
582:Spanier, Edwin Henry
498:
470:
435:
412:
392:
372:
352:
332:
301:
281:
233:
187:−1 cuts are needed.
32:people to achieve a
250:{\displaystyle 1/n}
578:Dubins, Lester Eli
504:
484:
456:
418:
398:
378:
358:
338:
315:
287:
247:
221:Continuous version
507:{\displaystyle n}
67:Bronisław Knaster
59:divide and choose
22:fair cake-cutting
663:
635:
634:
616:
610:
609:
574:
568:
567:
547:
513:
511:
510:
505:
493:
491:
490:
485:
480:
465:
463:
462:
457:
452:
447:
446:
427:
425:
424:
419:
407:
405:
404:
399:
387:
385:
384:
379:
367:
365:
364:
359:
347:
345:
344:
339:
324:
322:
321:
316:
311:
296:
294:
293:
288:
256:
254:
253:
248:
243:
171:
671:
670:
666:
665:
664:
662:
661:
660:
641:
640:
639:
638:
631:
618:
617:
613:
598:10.2307/2311357
576:
575:
571:
549:
548:
544:
539:
527:
496:
495:
468:
467:
438:
433:
432:
410:
409:
390:
389:
370:
369:
350:
349:
330:
329:
299:
298:
279:
278:
264:
231:
230:
223:
158:
155:
130:
82:
47:
18:last diminisher
12:
11:
5:
669:
667:
659:
658:
653:
643:
642:
637:
636:
629:
611:
569:
541:
540:
538:
535:
526:
523:
503:
483:
479:
475:
455:
451:
445:
441:
417:
397:
377:
357:
337:
314:
310:
306:
286:
263:
260:
246:
242:
238:
222:
219:
218:
217:
210:
203:
196:
162:× (n−1) / 2 =
154:
151:
129:
126:
94:
93:
81:
78:
55:Hugo Steinhaus
46:
43:
13:
10:
9:
6:
4:
3:
2:
668:
657:
654:
652:
649:
648:
646:
632:
630:0-521-55644-9
626:
622:
615:
612:
607:
603:
599:
595:
591:
587:
583:
579:
573:
570:
565:
561:
557:
553:
546:
543:
536:
534:
532:
524:
522:
520:
515:
501:
481:
477:
473:
453:
449:
443:
439:
429:
415:
395:
375:
355:
335:
326:
312:
308:
304:
284:
276:
271:
269:
261:
259:
244:
240:
236:
228:
220:
215:
211:
208:
204:
201:
197:
194:
193:
192:
188:
186:
182:
178:
173:
169:
165:
161:
152:
150:
148:
144:
140:
136:
127:
125:
123:
119:
115:
111:
107:
103:
99:
91:
87:
86:
85:
79:
77:
75:
74:fair division
70:
68:
64:
63:Stefan Banach
60:
56:
52:
44:
42:
39:
35:
31:
27:
23:
19:
656:Cake-cutting
620:
614:
589:
585:
572:
558:(1): 101–4.
555:
552:Econometrica
551:
545:
528:
525:Improvements
516:
430:
327:
274:
272:
265:
224:
189:
184:
180:
176:
174:
167:
163:
159:
156:
146:
142:
138:
134:
131:
121:
117:
113:
109:
105:
101:
97:
95:
89:
83:
71:
51:World War II
48:
37:
29:
25:
17:
15:
592:(1): 1–17.
275:re-entrance
80:Description
645:Categories
537:References
514:partners.
200:convex set
482:ϵ
454:ϵ
416:ϵ
396:ϵ
376:ϵ
356:ϵ
336:ϵ
313:ϵ
285:ϵ
268:envy-free
207:rectangle
258:player.
214:triangle
153:Analysis
606:2311357
564:1914289
325:times.
49:During
45:History
627:
604:
562:
602:JSTOR
560:JSTOR
625:ISBN
116:−1)/
65:and
16:The
594:doi
647::
600:.
590:68
588:.
580:;
556:16
554:.
533:.
141:,
124:.
76:.
633:.
608:.
596::
566:.
502:n
478:/
474:n
450:/
444:2
440:n
309:/
305:1
245:n
241:/
237:1
185:n
181:n
179:(
177:O
170:)
168:n
166:(
164:O
160:n
147:n
143:n
139:n
135:n
122:n
118:n
114:n
110:n
106:n
102:n
98:n
90:n
38:n
30:n
26:n
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.