42:
represents a continuous resource (such as land or time), that has to be allocated among people with different valuations over parts of the resource. The goal in egalitarian cake-cutting is to maximize the smallest value of an agent; subject to this, maximize the next-smallest value; and so on. It is
267:
All agents value the entire cake at 15, so absolute-leximin and relative-leximin are equivalent. The largest possible minimum value is 5, so a leximin allocation must give all agents at least 5. This means that the Right must be divided equally among agents C, D, E, and the Middle must be given
426:- an allocation giving each agent an equal utility. Often, the egalitarian allocation coincides with the equitable allocation, since if the utilities are different, the smaller utility can be improved by moving some cake from the agent with larger utility.
369:
86:"), the set of allocations is compact. Therefore, leximin-optimal cake allocations always exist. For this reason, the leximin cake-allocation rule is sometimes called the
378:
On the other hand, they prove that, unless P=NP, it is impossible to approximate the optimal egalitarian value to a factor better than 2, in time polynomial in
98:
When the agents' valuations are not normalized (i.e., different agents may assign a different value to the entire cake), there is a difference between the
174:. For example, suppose there are 5 agents, the cake is piecewise-homogeneous with 3 regions, and the agents' valuations are (missing values are zeros):
74:. This is always the case when allocating discrete objects, and easy to prove when allocating a finite number of continuous homogeneous resources.
664:
406:. They prove that, if the 3DM instance admits a perfect matching, then there exists a cake allocation with egalitarian value at least 1/
271:
Dubins and
Spanier proved that, when all value-measures are strictly positive, every relative-leximin allocation is envy-free.
308:
286:
centered at 1/4, 1/2 and 3/4 respectively. The allocation (,,) has utility profile (3/8,7/16,7/16). It is envy-free and
75:
290:-optimal, hence Pareto-efficient. However, there is another allocation (,,) with a leximin-better utility profile.
282:
cake allocation that is not relative-leximin. The cake is , there are three agents, and their value measures are
155:
287:
686:
429:
283:
659:. AAMAS '13. Richland, SC: International Foundation for Autonomous Agents and Multiagent Systems: 343–350.
423:
383:
275:
171:
691:
513:
143:
591:
565:
479:
151:
660:
633:
583:
531:
279:
83:
31:
657:
Proceedings of the 2013 International
Conference on Autonomous Agents and Multi-agent Systems
625:
575:
521:
471:
35:
305:>0, computes an allocation with egalitarian welfare at least (1-e) of the optimum using
517:
130:
chooses an allocation in which the absolute utility profile is leximin-maximal, and the
526:
501:
298:
Dall'aglio presents an algorithm for computing a leximin-optimal resource allocation.
680:
652:
629:
459:
455:
71:
59:
55:
48:
17:
613:
595:
410:; otherwise, there is no cake-allocation with egalitarian value larger than 1/(2
134:
chooses an allocation in which the relative utility profile is leximin-maximal.
579:
637:
587:
535:
553:
483:
70:
Leximin-optimal allocations exist whenever the set of allocations is a
432:- a similar concept in the context of homogeneous resource allocation.
170:
Both variants of the leximin rule may yield allocations that are not
161:
The relative-leximin rule is proportional but not resource-monotonic.
475:
570:
502:"The Dubins–Spanier optimization problem in fair division theory"
301:
Aumann, Dombb and
Hassidim present an algorithm that, for every
651:
Aumann, Yonatan; Dombb, Yair; Hassidim, Avinatan (2013-05-06).
54:
The concept of egalitarian cake-cutting was first described by
554:"Monotonicity and competitive equilibrium in cake-cutting"
142:
Both variants of the leximin rule are Pareto-optimal and
390:
hyperedges, they construct a cake-cutting instance with
364:{\displaystyle 2^{n}\cdot n\cdot \log _{2}(n/\epsilon )}
552:
Segal-Halevi, Erel; Sziklai, Balázs R. (2019-09-01).
311:
375:, but polynomial in the number of accuracy digits.
363:
506:Journal of Computational and Applied Mathematics
386:(3DM). For every instance of 3DM matching with
653:"Computing socially-efficient cake divisions"
8:
146:. However, they differ in other properties:
268:entirely to agent B. But then A envies B.
47:, since the optimization is done using the
569:
525:
350:
335:
316:
310:
176:
442:
34:in which the fairness criterion is the
62:, who called it "optimal partition".
614:"Fair division of a measurable space"
450:
448:
446:
122:divided by the total value for agent
7:
607:
605:
547:
545:
495:
493:
462:(1961). "How to Cut a Cake Fairly".
25:
618:Journal of Mathematical Economics
464:The American Mathematical Monthly
382:. The proof is by reduction from
500:Dall'Aglio, Marco (2001-05-01).
371:queries. This is exponential in
102:of an allocation (where element
612:Weller, Dietrich (1985-01-01).
358:
344:
51:on the vectors of utilities.
1:
527:10.1016/S0377-0427(99)00393-3
150:The absolute-leximin rule is
106:is just the utility of agent
630:10.1016/0304-4068(85)90023-0
708:
580:10.1007/s00199-018-1128-6
284:trianglular distributions
166:Relation to envy-freeness
76:Dubins and Spanier proved
118:is the utility of agent
112:relative utility profile
100:absolute utility profile
78:that, with a continuous
28:Egalitarian cake-cutting
430:Egalitarian equivalence
424:Equitable cake-cutting
384:3-dimensional matching
365:
366:
132:relative leximin rule
128:absolute leximin rule
460:Spanier, Edwin Henry
309:
144:population monotonic
45:leximin cake-cutting
18:Leximin cake-cutting
518:2001JCoAM.130...17D
88:Dubins–Spanier rule
456:Dubins, Lester Eli
361:
152:resource monotonic
666:978-1-4503-1993-5
274:Weller showed an
265:
264:
32:fair cake-cutting
16:(Redirected from
699:
671:
670:
648:
642:
641:
609:
600:
599:
573:
549:
540:
539:
529:
497:
488:
487:
452:
370:
368:
367:
362:
354:
340:
339:
321:
320:
177:
36:egalitarian rule
21:
707:
706:
702:
701:
700:
698:
697:
696:
677:
676:
675:
674:
667:
650:
649:
645:
611:
610:
603:
558:Economic Theory
551:
550:
543:
499:
498:
491:
476:10.2307/2311357
454:
453:
444:
439:
420:
394:agents, where 4
331:
312:
307:
306:
296:
168:
140:
114:(where element
96:
68:
23:
22:
15:
12:
11:
5:
705:
703:
695:
694:
689:
687:Egalitarianism
679:
678:
673:
672:
665:
643:
601:
564:(2): 363–401.
541:
512:(1–2): 17–40.
489:
441:
440:
438:
435:
434:
433:
427:
419:
416:
360:
357:
353:
349:
346:
343:
338:
334:
330:
327:
324:
319:
315:
295:
292:
263:
262:
259:
257:
255:
249:
248:
245:
243:
241:
235:
234:
231:
229:
227:
221:
220:
217:
214:
212:
206:
205:
203:
200:
197:
191:
190:
187:
184:
181:
167:
164:
163:
162:
159:
139:
136:
95:
92:
67:
64:
24:
14:
13:
10:
9:
6:
4:
3:
2:
704:
693:
690:
688:
685:
684:
682:
668:
662:
658:
654:
647:
644:
639:
635:
631:
627:
623:
619:
615:
608:
606:
602:
597:
593:
589:
585:
581:
577:
572:
567:
563:
559:
555:
548:
546:
542:
537:
533:
528:
523:
519:
515:
511:
507:
503:
496:
494:
490:
485:
481:
477:
473:
469:
465:
461:
457:
451:
449:
447:
443:
436:
431:
428:
425:
422:
421:
417:
415:
413:
409:
405:
401:
397:
393:
389:
385:
381:
376:
374:
355:
351:
347:
341:
336:
332:
328:
325:
322:
317:
313:
304:
299:
293:
291:
289:
285:
281:
277:
272:
269:
260:
258:
256:
254:
251:
250:
246:
244:
242:
240:
237:
236:
232:
230:
228:
226:
223:
222:
218:
215:
213:
211:
208:
207:
204:
201:
198:
196:
193:
192:
188:
185:
182:
179:
178:
175:
173:
165:
160:
157:
153:
149:
148:
147:
145:
137:
135:
133:
129:
125:
121:
117:
113:
109:
105:
101:
93:
91:
89:
85:
81:
80:heterogeneous
77:
73:
72:compact space
65:
63:
61:
57:
52:
50:
49:leximin order
46:
41:
37:
33:
30:is a kind of
29:
19:
692:Cake-cutting
656:
646:
621:
617:
561:
557:
509:
505:
467:
463:
411:
407:
403:
399:
395:
391:
387:
379:
377:
372:
302:
300:
297:
273:
270:
266:
252:
238:
224:
209:
194:
169:
156:proportional
141:
131:
127:
123:
119:
115:
111:
107:
103:
99:
97:
87:
79:
69:
53:
44:
43:also called
39:
27:
26:
624:(1): 5–17.
470:(1): 1–17.
294:Computation
288:utilitarian
110:), and its
82:resource ("
681:Categories
571:1510.05229
437:References
138:Properties
638:0304-4068
588:1432-0479
536:0377-0427
356:ϵ
342:
329:⋅
323:⋅
280:efficient
276:envy-free
172:envy-free
66:Existence
418:See also
154:but not
94:Variants
514:Bibcode
484:2311357
186:Middle
126:). The
60:Spanier
663:
636:
596:179618
594:
586:
534:
482:
189:Right
180:Agent
56:Dubins
38:. The
592:S2CID
566:arXiv
480:JSTOR
183:Left
661:ISBN
634:ISSN
584:ISSN
532:ISSN
278:and
84:cake
58:and
40:cake
626:doi
576:doi
522:doi
510:130
472:doi
414:).
402:≤ 5
333:log
261:15
247:15
233:15
219:10
683::
655:.
632:.
622:14
620:.
616:.
604:^
590:.
582:.
574:.
562:68
560:.
556:.
544:^
530:.
520:.
508:.
504:.
492:^
478:.
468:68
466:.
458:;
445:^
398:≤
216:5
202:9
199:6
90:.
669:.
640:.
628::
598:.
578::
568::
538:.
524::
516::
486:.
474::
412:m
408:m
404:m
400:n
396:m
392:n
388:m
380:n
373:n
359:)
352:/
348:n
345:(
337:2
326:n
318:n
314:2
303:e
253:E
239:D
225:C
210:B
195:A
158:;
124:i
120:i
116:i
108:i
104:i
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.