25:
203:. The goal is to maximize the minimum value of an agent. That is, among all possible allocations, the goal is to find an allocation in which the smallest value of an agent is as large as possible. In case there are two or more allocations with the same smallest value, then the goal is to select, from among these allocations, the one in which the second-smallest value is as large as possible, and so on (by the
121:
66:
529:-factor approximation to the optimal egalitarian value. The second finds an allocation that is egalitarian up-to one good, that is, each agent receives his value in the optimal egalitarian allocation minus at most a single item. Their algorithm is based on a previous algorithm by Lenstra, Shmoys and Tardos, which essentially finds an allocation that is egalitarian up-to one
308:
3,3,3,3, then the absolute-leximin rule would give three items to Alice and one item to George, since the utility profile in this case is (3,3), which is optimal. In contrast, the relative-leximin rule would give two items to each agent, since the normalized utility profile in this case, when the total value of both agents is normalized to 1, is (0.5,0.5), which is optimal.
1227:
The relative-leximin allocation might not be EF1 for three or more agents. For example, suppose there are four goods and three agents who value them at {30,0,0,0} {20,5,5,0} and {0,12,12,6}. Note that the valuations are normalized (the total value is 30). In a leximin allocation, the first good must
1262:
However, when agents have different valuations, the problems are different. The maximin-share allocation is a satisfaction problem: the goal is to guarantee that each agent receives a value above the identical-valuations threshold. In contrast, the egalitarian allocation is an optimization problem:
1221:
The absolute-leximin allocation might not be EF1 even for two agents with additive valuations. For example, suppose there are four goods and two agents who value them at {0,1,1,1} and {3,3,3,3}. The unique absolute-leximin allocation gives {1,1,1} to the first agent and {3} to the second agent, but
307:
The two rules are equivalent when the agents' valuations are already normalized, that is, all agents assign the same value to the set of all items. However, they may differ with non-normalized valuations. For example, if there are four items, Alice values them at 1,1,1,1 and George values them at
749:
1263:
the goal is to give each agent as high value as possible. In some instances, the resulting allocations might be very different. For example, suppose there are four goods and three agents who value them at {3,0,0,0}, {3-2
1036:
445:
751:. For the special case in which every item has nonzero utility for at most two agents, they gave a 2-factor approximation algorithm, and proved that it is hard to approximate to any better factor.
1187:
Whenever a proportional allocation exists, the relative-leximin allocation is proportional. This is because, in a proportional allocation, the smallest relative value of an agent is at least 1/
590:
2094:
Nguyen, Nhan-Tam; Nguyen, Trung Thanh; Roos, Magnus; Rothe, Jörg (2013). "Computational complexity and approximability of social welfare optimization in multiagent resource allocation".
1228:
be allocated to agent 1. Then, the second and third goods must be allocated to agent 2, and the good remains for agent 3. But then agent 3 envies agent 2 even after removing an item.
2049:
Nguyen, Trung Thanh; Roos, Magnus; Rothe, Jörg (2013). "A survey of approximability and inapproximability results for social welfare optimization in multiagent resource allocation".
683:
639:
1236:(i.e., submodular with binary marginals), the set of absolute-leximin allocations is equivalent to the set of max-product allocations; all such allocations are max-sum and EF1.
273:
is a different problem, in which the goal is not to attain an optimal solution, but rather to find any solution in which each agent receives a value above a certain threshold.
879:
848:. This result is obtained from rounding a suitable linear programming relaxation of the problem, and is the best possible result for this linear program. He also gave an
1287:): the first item must go to agent 1 - otherwise the smallest utility is 0. Then, the second and third items must go to agent 2 - otherwise the next-smallest utility is
1191:, so the same must hold when we maximize the smallest relative value. However, the absolute-leximin allocation might not be proportional, as shown in the example above.
940:
812:
527:
846:
772:
1719:. Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics, 2020. pp. 2748–2757.
537:
of the linear program for finding a fractional egalitarian allocation, and round it such that each agent loses at most one good, or gains at most one chore.
1279:
is a small positive constant). Note that the valuations are normalized (the total value is 3), so absolute-leximin and relative-leximin are equivalent.
688:
84:
139:
2231:
Benabbou, Nawal; Chakraborty, Mithun; Igarashi, Ayumi; Zick, Yair (2020). "Finding Fair and
Efficient Allocations when Valuations Don't Add up".
1298:, 1. Therefore, a maximin-share allocation must give agent 3 one of the first three items; some possible utility profiles in this case are (0,
948:
229:: santa claus has a fixed set of gifts, and wants to allocate them among children such that the least-happy child is as happy as possible.
38:
241:
with the max-min objective corresponds to a special case in which all agents have the same valuations. An even more special case is the
1259:
When all agents have identical valuations, the egalitarian allocation, by definition, gives each agent at least his/her maximin share.
885:
1245:(items with negative utilities), with 3 or 4 agents with additive valuations, any leximin-optimal allocation is PROP1 and PO; with
373:
1952:"When Does a Dynamic Programming Formulation Guarantee the Existence of a Fully Polynomial Time Approximation Scheme (FPTAS)?"
2373:
2258:
2020:
1900:
1642:
1050:
The standard egalitarian rule requires that each agent assigns a numeric value to each object. Often, the agents only have
2403:
1201:
1. When all agents have identical valuations with nonzero marginal utilities, any relative-leximin allocation is PO and
328:-optimal solutions to discrete constraint-satisfaction problems. They present max-min item allocation as a special case.
2282:
Caragiannis, Ioannis; Kurokawa, David; Moulin, Hervé; Procaccia, Ariel D.; Shah, Nisarg; Wang, Junxing (2019-09-24).
175:
157:
102:
52:
543:
44:
1586:
200:
2413:
1378:
The leximin rule has been used for fairly allocating unused classrooms in public schools to charter schools.
1167:
331:
Dall'Aglio and Mosca gave an exact, branch-and-bound algorithm for two agents, based on an adaptation of the
253:
600:. They also provide better bounds when it is allowed to exclude a small fraction of people from the problem.
1181:
644:
237:
344:
Demko and Hill present a randomized algorithm that attains an egalitarian item allocation in expectation.
1099:
608:
454:
Feige proved that a polynomial-time constant-factor approximation algorithm exists, but the proof used
2331:
Chen, Xingyu; Liu, Zijie (2020-05-11). "The
Fairness of Leximin in Allocation of Indivisible Chores".
2130:
1195:
332:
135:
80:
2063:
1951:
1507:
851:
303:) where the maximization uses their normalized values - bundle value divided by value of all items.
1629:. Lecture Notes in Computer Science. Vol. 5171. Berlin, Heidelberg: Springer. pp. 10–20.
1752:
2408:
1103:
finds an ordinally-egalitarian allocation for any number of agents with any ordering of bundles.
897:
534:
462:
1622:
2058:
1747:
1610:. SODA '08. San Francisco, California: Society for Industrial and Applied Mathematics: 287–293.
1502:
317:
1172:
with equal eating speeds is the unique rule that returns an ordinally-egalitarian allocation.
1233:
1217:
2. For two agents with additive valuations, any relative-leximin allocation is EF1. However:
907:
777:
494:
1990:
455:
942:-approximation algorithm, and some inapproximability results for general utility functions.
889:
817:
196:
8:
1989:
Goemans, Michel X.; Harvey, Nicholas J. A.; Iwata, Satoru; Mirrokni, Vahab (2009-01-04),
1202:
597:
593:
461:
Asadpour, Feige and Saberi gave an actual constant-factor approximation algorithm, using
2360:. EC '15. Portland, Oregon, USA: Association for Computing Machinery. pp. 345–362.
2379:
2332:
2313:
2264:
2236:
2210:
2184:
2111:
2076:
2026:
1906:
1878:
1812:
1765:
1697:
1671:
1571:
Proceedings of the thirty-eighth annual ACM symposium on Theory of computing - STOC '06
1434:
1408:
757:
476:
448:
1627:
Approximation, Randomization and
Combinatorial Optimization. Algorithms and Techniques
1531:
2369:
2317:
2305:
2268:
2254:
2214:
2202:
2150:
2016:
1971:
1896:
1851:
1804:
1689:
1638:
1603:
1582:
1551:
1547:
1516:
1475:
1426:
1051:
242:
2172:
2030:
1816:
1701:
468:
Annamalai, Kalaitzis and
Svensson gave a polynomial-time 13-approximation algorithm.
2383:
2361:
2295:
2246:
2194:
2142:
2103:
2080:
2068:
2006:
1998:
1963:
1888:
1843:
1831:
1796:
1769:
1757:
1720:
1681:
1630:
1574:
1543:
1512:
1465:
1418:
484:
2115:
1910:
1493:
Dall'Aglio, Marco; Mosca, Raffaele (2007). "How to allocate hard candies fairly".
1438:
592:-approximation algorithm. Their algorithm uses an iterative method for rounding a
471:
Davies, Rothvoss and Zhang improved the approximation factor to 4 by introducing
316:
Although the general problem is NP-hard, small instances can be solved exactly by
1997:, Proceedings, Society for Industrial and Applied Mathematics, pp. 535–544,
1470:
1453:
1249:
agents with general identical valuations, any leximin-optimal allocation is EFX.
744:{\displaystyle \varepsilon \in \Omega \left({\frac {\log \log m}{\log m}}\right)}
2250:
1634:
2002:
1967:
1870:
1625:. In Goel, Ashish; Jansen, Klaus; Rolim, José D. P.; Rubinfeld, Ronitt (eds.).
2146:
2107:
2072:
1608:
Proceedings of the
Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms
1422:
2397:
2309:
2206:
2154:
1975:
1855:
1832:"An Approximation Algorithm for Max-Min Fair Allocation of Indivisible Goods"
1808:
1693:
1555:
1479:
1430:
1253:
1054:. There are two generalizations of the egalitarian rule to ordinal settings.
325:
269:
204:
2365:
1761:
1724:
1578:
1396:
2353:
1928:
1892:
1658:
Annamalai, Chidambaram; Kalaitzis, Christos; Svensson, Ola (2017-05-26).
1031:{\displaystyle O({\sqrt {m}}\cdot n^{1/4}\cdot \log n\cdot \log ^{3/2}m)}
245:, which corresponds to the case of two agents. Even this special case is
2358:
Proceedings of the
Sixteenth ACM Conference on Economics and Computation
2011:
1995:
Proceedings of the 2009 Annual ACM-SIAM Symposium on
Discrete Algorithms
881:-approximation algorithm for the special case with two classes of goods.
2198:
1800:
2235:. Lecture Notes in Computer Science. Vol. 12283. pp. 32–46.
1847:
1738:
Bezáková, Ivona; Dani, Varsha (2005). "Allocating indivisible goods".
1785:"Approximation algorithms for scheduling unrelated parallel machines"
1784:
1569:
Bansal, Nikhil; Sviridenko, Maxim (2006). "The Santa Claus problem".
465:. They could not prove that it converges in a finite number of steps.
2300:
2283:
1685:
324:
Bouveret and Lemaître present five different algorithms for finding
2337:
2241:
2189:
1413:
207:). Therefore, an egalitarian item allocation is sometimes called a
75:
provides insufficient context for those unfamiliar with the subject
2281:
1883:
1875:
2009 50th Annual IEEE Symposium on
Foundations of Computer Science
1676:
1659:
2352:
Kurokawa, David; Procaccia, Ariel D.; Shah, Nisarg (2015-06-15).
472:
246:
1783:
Lenstra, Jan Karel; Shmoys, David B.; Tardos, Éva (1990-01-01).
1660:"Combinatorial Algorithm for Restricted Max-Min Fair Allocation"
293:), where the maximization uses the nominal values of the agents;
2230:
1213:
guarantees EFX (but not PO) with general identical valuations.
1041:
Nguyen, Roos and Rothe present some stronger hardness results.
491:
Bezakova and Dani presented two algorithms. The first gives a
1110:. Given any discrete or fractional allocation, for any agent
1454:"Computing leximin-optimal solutions in constraint networks"
1715:
Davies, Sami; Rothvoss, Thomas; Zhang, Yihao (2018-07-18).
533:. Both algorithms are based on a similar idea. They find a
1988:
1657:
1397:"Monotonicity and competitive equilibrium in cake-cutting"
1106:
2. Suppose agents have an ordinal ranking over the set of
1057:
1. Suppose agents have an ordinal ranking over the set of
440:{\displaystyle O(\log {\log {n}}/\log {\log {\log {n}}})}
1868:
1175:
1093:
allocation is one that minimizes the largest element in
1869:
Chakrabarty, D.; Chuzhoy, J.; Khanna, S. (2009-10-01).
1283:
The leximin allocation yields the utility profile (3,
754:
Golovin gave an algorithm by which, for every integer
2351:
2093:
1395:
Segal-Halevi, Erel; Sziklai, Balázs R. (2019-09-01).
1073:) as the rank of agent i's bundle, so that r(i)=1 if
951:
910:
854:
820:
780:
760:
691:
647:
611:
546:
497:
376:
199:
problem, in which the fairness criterion follows the
1621:
Asadpour, Arash; Feige, Uriel; Saberi, Amin (2008).
1045:
2284:"The Unreasonable Fairness of Maximum Nash Welfare"
1782:
1714:
1620:
1492:
1394:
130:
may be too technical for most readers to understand
1452:Bouveret, Sylvain; Lemaître, Michel (2009-02-01).
1030:
934:
884:When the number of agents is constant there is an
873:
840:
806:
766:
743:
677:
633:
584:
521:
439:
2051:Annals of Mathematics and Artificial Intelligence
363:For the special case of the santa claus problem:
214:The special case in which the value of each item
2395:
2171:Plaut, Benjamin; Roughgarden, Tim (2020-01-01).
2170:
1568:
1530:Demko, Stephen; Hill, Theodore P. (1988-10-01).
1451:
814:fraction of the agents receive utility at least
282:There are two variants of the egalitarian rule:
2131:"Random assignment: Redefining the serial rule"
2048:
1991:"Approximating Submodular Functions Everywhere"
1717:A tale of Santa Claus, hypergraphs and matroids
1532:"Equitable distribution of indivisible objects"
1241:4. In the context of indivisible allocation of
1061:. Given any discrete allocation, for any agent
2173:"Almost Envy-Freeness with General Valuations"
1929:"Max-min fair allocation of indivisible goods"
1829:
1294:The maximin-share values of the agents are 0,
585:{\displaystyle O({\sqrt {n}}\cdot \log ^{3}n)}
447:-approximation algorithm, based on rounding a
2288:ACM Transactions on Economics and Computation
1326:+1 goods and three agents who value them at {
1830:Asadpour, Arash; Saberi, Amin (2010-01-01).
1737:
1291:or less; so agent 3 gets only the last item.
1232:3. When all agents have valuations that are
1162:allocation is one that maximizes the vector
641:-approximation algorithm with a run-time of
2128:
945:Goemans, Harvey, Iwata and Mirrkoni give a
347:
257:is a dual problem, in which the goal is to
218:to each agent is either 0 or some constant
53:Learn how and when to remove these messages
1871:"On Allocating Goods to Maximize Fairness"
2336:
2299:
2240:
2188:
2096:Autonomous Agents and Multi-Agent Systems
2062:
2010:
1949:
1882:
1751:
1675:
1529:
1506:
1469:
1412:
1373:
176:Learn how and when to remove this message
158:Learn how and when to remove this message
142:, without removing the technical details.
103:Learn how and when to remove this message
1623:"Santa Claus Meets Hypergraph Matchings"
1358:}. The leximin utility profile must be (
1314:The example can be extended to 1-out-of-
339:
2354:"Leximin Allocations in the Real World"
2330:
1926:
1604:"On allocations that maximize fairness"
605:Chakrabarty, Chuzoy and Khanna gave an
2396:
2087:
1922:
1920:
1081:got his second-best bundle, etc. This
483:For the general case, for agents with
2226:
2224:
2166:
2164:
2042:
1601:
1176:Comparison to other fairness criteria
678:{\displaystyle O(m^{1/\varepsilon })}
140:make it understandable to non-experts
85:providing more context for the reader
2177:SIAM Journal on Discrete Mathematics
1950:Woeginger, Gerhard J. (2000-02-01).
1731:
114:
59:
18:
1917:
1562:
1486:
1138:topmost indifference classes. This
1130:) as the total fraction that agent
634:{\displaystyle O(m^{\varepsilon })}
311:
13:
2221:
2161:
1943:
1180:
698:
14:
2425:
1445:
1209:An improvement of leximin called
1046:Ordinally egalitarian allocations
34:This article has multiple issues.
2129:Bogomolnaia, Anna (2015-07-01).
1517:10.1016/j.mathsocsci.2007.04.008
1252:
1194:
277:
119:
64:
23:
2345:
2324:
2275:
2122:
1982:
1862:
1823:
1776:
1077:got his best bundle, r(i)=2 if
42:or discuss these issues on the
1708:
1664:ACM Transactions on Algorithms
1651:
1614:
1595:
1523:
1388:
1025:
955:
929:
911:
874:{\displaystyle O({\sqrt {n}})}
868:
858:
801:
781:
672:
651:
628:
615:
579:
550:
516:
498:
434:
380:
1:
1381:
1222:then the second agent envies.
1169:Simultaneous Eating algorithm
270:Maximin share item allocation
254:Unrelated-machines scheduling
1956:INFORMS Journal on Computing
1548:10.1016/0165-4896(88)90047-9
1536:Mathematical Social Sciences
1495:Mathematical Social Sciences
1471:10.1016/j.artint.2008.10.010
1154:is the number of agents and
1142:is a vector of size at most
898:submodular utility functions
356:is the number of agents and
238:Multiway number partitioning
16:Fair item allocation problem
7:
2251:10.1007/978-3-030-57980-7_3
1635:10.1007/978-3-540-85363-3_2
1602:Feige, Uriel (2008-01-20).
1158:is the number of items. An
1100:Decreasing Demand procedure
1089:(the number of agents). An
540:Asadpour and Saberi gave a
232:Some related problems are:
189:Egalitarian item allocation
10:
2430:
2404:Combinatorial optimization
2135:Journal of Economic Theory
2003:10.1137/1.9781611973068.59
1968:10.1287/ijoc.12.1.57.11901
1166:in the leximin order. The
2147:10.1016/j.jet.2015.04.008
2108:10.1007/s10458-013-9224-2
2073:10.1007/s10472-012-9328-4
1836:SIAM Journal on Computing
1423:10.1007/s00199-018-1128-6
475:constraints to the basic
458:and was non-constructive.
360:is the number of items.
333:Adjusted winner procedure
1927:Golovin, Daniel (2005).
1789:Mathematical Programming
1038:-approximation algorithm
348:Approximation algorithms
2366:10.1145/2764468.2764490
2233:Algorithmic Game Theory
1762:10.1145/1120680.1120683
1725:10.1137/1.9781611975994
1579:10.1145/1132516.1132522
1458:Artificial Intelligence
935:{\displaystyle (m-n+1)}
807:{\displaystyle (1-1/k)}
535:basic feasible solution
522:{\displaystyle (m-n+1)}
209:leximin item allocation
193:max-min item allocation
1374:Real-world application
1234:matroid rank functions
1032:
936:
875:
842:
808:
768:
745:
679:
635:
586:
523:
441:
318:constraint programming
1740:ACM SIGecom Exchanges
1370:MMS of agent 3 is 1.
1366:) while the 1-out-of-
1160:ordinally-egalitarian
1114:and positive integer
1091:ordinally-egalitarian
1033:
937:
876:
843:
841:{\displaystyle OPT/k}
809:
769:
746:
680:
636:
587:
524:
442:
367:Bansal and Sviridenko
340:Randomized algorithms
2414:Fair item allocation
1893:10.1109/FOCS.2009.51
1877:. pp. 107–116.
1085:is a vector of size
949:
908:
852:
818:
778:
758:
689:
645:
609:
544:
495:
374:
297:relative egalitarian
287:absolute egalitarian
197:fair item allocation
594:fractional matching
485:additive valuations
463:hypergraph matching
227:santa claus problem
81:improve the article
2199:10.1137/19M124397X
1801:10.1007/BF01585745
1134:receives from his
1028:
932:
871:
838:
804:
764:
741:
675:
631:
582:
519:
456:Lovász local lemma
437:
2375:978-1-4503-3410-5
2294:(3): 12:1–12:32.
2260:978-3-030-57979-1
2022:978-0-89871-680-1
1902:978-1-4244-5116-6
1848:10.1137/080723491
1670:(3): 37:1–37:28.
1644:978-3-540-85363-3
1322:>3. There are
1052:ordinal utilities
963:
866:
767:{\displaystyle k}
735:
558:
243:partition problem
186:
185:
178:
168:
167:
160:
113:
112:
105:
57:
2421:
2388:
2387:
2349:
2343:
2342:
2340:
2328:
2322:
2321:
2303:
2279:
2273:
2272:
2244:
2228:
2219:
2218:
2192:
2183:(2): 1039–1068.
2168:
2159:
2158:
2126:
2120:
2119:
2091:
2085:
2084:
2066:
2046:
2040:
2039:
2038:
2037:
2014:
1986:
1980:
1979:
1947:
1941:
1940:
1938:
1936:
1924:
1915:
1914:
1886:
1866:
1860:
1859:
1842:(7): 2970–2989.
1827:
1821:
1820:
1780:
1774:
1773:
1755:
1735:
1729:
1728:
1712:
1706:
1705:
1679:
1655:
1649:
1648:
1618:
1612:
1611:
1599:
1593:
1592:
1566:
1560:
1559:
1527:
1521:
1520:
1510:
1490:
1484:
1483:
1473:
1449:
1443:
1442:
1416:
1392:
1037:
1035:
1034:
1029:
1018:
1017:
1013:
985:
984:
980:
964:
959:
941:
939:
938:
933:
904:Golovin gave an
896:For agents with
880:
878:
877:
872:
867:
862:
847:
845:
844:
839:
834:
813:
811:
810:
805:
797:
773:
771:
770:
765:
750:
748:
747:
742:
740:
736:
734:
723:
706:
684:
682:
681:
676:
671:
670:
666:
640:
638:
637:
632:
627:
626:
591:
589:
588:
583:
572:
571:
559:
554:
528:
526:
525:
520:
446:
444:
443:
438:
433:
432:
431:
406:
401:
400:
312:Exact algorithms
301:relative leximin
291:absolute leximin
201:egalitarian rule
181:
174:
163:
156:
152:
149:
143:
123:
122:
115:
108:
101:
97:
94:
88:
68:
67:
60:
49:
27:
26:
19:
2429:
2428:
2424:
2423:
2422:
2420:
2419:
2418:
2394:
2393:
2392:
2391:
2376:
2350:
2346:
2329:
2325:
2301:10.1145/3355902
2280:
2276:
2261:
2229:
2222:
2169:
2162:
2127:
2123:
2092:
2088:
2064:10.1.1.671.3497
2047:
2043:
2035:
2033:
2023:
1987:
1983:
1948:
1944:
1934:
1932:
1925:
1918:
1903:
1867:
1863:
1828:
1824:
1781:
1777:
1736:
1732:
1713:
1709:
1686:10.1145/3070694
1656:
1652:
1645:
1619:
1615:
1600:
1596:
1589:
1567:
1563:
1528:
1524:
1508:10.1.1.330.2617
1491:
1487:
1450:
1446:
1401:Economic Theory
1393:
1389:
1384:
1376:
1330:, 0, ..., 0}, {
1257:
1199:
1185:
1182:Proportionality
1178:
1048:
1009:
1005:
1001:
976:
972:
968:
958:
950:
947:
946:
909:
906:
905:
861:
853:
850:
849:
830:
819:
816:
815:
793:
779:
776:
775:
759:
756:
755:
724:
707:
705:
701:
690:
687:
686:
662:
658:
654:
646:
643:
642:
622:
618:
610:
607:
606:
567:
563:
553:
545:
542:
541:
496:
493:
492:
427:
420:
413:
402:
396:
389:
375:
372:
371:
350:
342:
314:
280:
223:
182:
171:
170:
169:
164:
153:
147:
144:
136:help improve it
133:
124:
120:
109:
98:
92:
89:
78:
69:
65:
28:
24:
17:
12:
11:
5:
2427:
2417:
2416:
2411:
2409:Egalitarianism
2406:
2390:
2389:
2374:
2344:
2323:
2274:
2259:
2220:
2160:
2121:
2086:
2057:(1–3): 65–90.
2041:
2021:
1981:
1942:
1916:
1901:
1861:
1822:
1795:(1): 259–271.
1775:
1730:
1707:
1650:
1643:
1613:
1594:
1587:
1573:. p. 31.
1561:
1542:(2): 145–158.
1522:
1485:
1464:(2): 343–364.
1444:
1407:(2): 363–401.
1386:
1385:
1383:
1380:
1375:
1372:
1354:, 1, 1, ..., k
1312:
1311:
1292:
1256:
1251:
1230:
1229:
1225:
1215:
1214:
1198:
1193:
1184:
1179:
1177:
1174:
1047:
1044:
1043:
1042:
1039:
1027:
1024:
1021:
1016:
1012:
1008:
1004:
1000:
997:
994:
991:
988:
983:
979:
975:
971:
967:
962:
957:
954:
943:
931:
928:
925:
922:
919:
916:
913:
894:
893:
882:
870:
865:
860:
857:
837:
833:
829:
826:
823:
803:
800:
796:
792:
789:
786:
783:
763:
752:
739:
733:
730:
727:
722:
719:
716:
713:
710:
704:
700:
697:
694:
674:
669:
665:
661:
657:
653:
650:
630:
625:
621:
617:
614:
602:
601:
581:
578:
575:
570:
566:
562:
557:
552:
549:
538:
518:
515:
512:
509:
506:
503:
500:
481:
480:
477:linear program
469:
466:
459:
452:
449:linear program
436:
430:
426:
423:
419:
416:
412:
409:
405:
399:
395:
392:
388:
385:
382:
379:
349:
346:
341:
338:
337:
336:
329:
320:techniques.
313:
310:
305:
304:
294:
279:
276:
275:
274:
266:
250:
225:is called the
221:
191:, also called
184:
183:
166:
165:
127:
125:
118:
111:
110:
72:
70:
63:
58:
32:
31:
29:
22:
15:
9:
6:
4:
3:
2:
2426:
2415:
2412:
2410:
2407:
2405:
2402:
2401:
2399:
2385:
2381:
2377:
2371:
2367:
2363:
2359:
2355:
2348:
2339:
2334:
2327:
2319:
2315:
2311:
2307:
2302:
2297:
2293:
2289:
2285:
2278:
2270:
2266:
2262:
2256:
2252:
2248:
2243:
2238:
2234:
2227:
2225:
2216:
2212:
2208:
2204:
2200:
2196:
2191:
2186:
2182:
2178:
2174:
2167:
2165:
2156:
2152:
2148:
2144:
2140:
2136:
2132:
2125:
2117:
2113:
2109:
2105:
2101:
2097:
2090:
2082:
2078:
2074:
2070:
2065:
2060:
2056:
2052:
2045:
2032:
2028:
2024:
2018:
2013:
2008:
2004:
2000:
1996:
1992:
1985:
1977:
1973:
1969:
1965:
1961:
1957:
1953:
1946:
1930:
1923:
1921:
1912:
1908:
1904:
1898:
1894:
1890:
1885:
1880:
1876:
1872:
1865:
1857:
1853:
1849:
1845:
1841:
1837:
1833:
1826:
1818:
1814:
1810:
1806:
1802:
1798:
1794:
1790:
1786:
1779:
1771:
1767:
1763:
1759:
1754:
1753:10.1.1.436.18
1749:
1745:
1741:
1734:
1726:
1722:
1718:
1711:
1703:
1699:
1695:
1691:
1687:
1683:
1678:
1673:
1669:
1665:
1661:
1654:
1646:
1640:
1636:
1632:
1628:
1624:
1617:
1609:
1605:
1598:
1590:
1584:
1580:
1576:
1572:
1565:
1557:
1553:
1549:
1545:
1541:
1537:
1533:
1526:
1518:
1514:
1509:
1504:
1500:
1496:
1489:
1481:
1477:
1472:
1467:
1463:
1459:
1455:
1448:
1440:
1436:
1432:
1428:
1424:
1420:
1415:
1410:
1406:
1402:
1398:
1391:
1387:
1379:
1371:
1369:
1365:
1361:
1357:
1353:
1349:
1345:
1341:
1337:
1333:
1329:
1325:
1321:
1317:
1309:
1305:
1301:
1297:
1293:
1290:
1286:
1282:
1281:
1280:
1278:
1274:
1270:
1266:
1260:
1255:
1254:Maximin share
1250:
1248:
1244:
1239:
1238:
1235:
1226:
1224:
1220:
1219:
1218:
1212:
1208:
1207:
1206:
1204:
1197:
1196:Envy-freeness
1192:
1190:
1183:
1173:
1171:
1170:
1165:
1161:
1157:
1153:
1149:
1145:
1141:
1137:
1133:
1129:
1125:
1121:
1117:
1113:
1109:
1104:
1102:
1101:
1096:
1092:
1088:
1084:
1080:
1076:
1072:
1068:
1064:
1060:
1055:
1053:
1040:
1022:
1019:
1014:
1010:
1006:
1002:
998:
995:
992:
989:
986:
981:
977:
973:
969:
965:
960:
952:
944:
926:
923:
920:
917:
914:
903:
902:
901:
899:
891:
887:
883:
863:
855:
835:
831:
827:
824:
821:
798:
794:
790:
787:
784:
761:
753:
737:
731:
728:
725:
720:
717:
714:
711:
708:
702:
695:
692:
667:
663:
659:
655:
648:
623:
619:
612:
604:
603:
599:
595:
576:
573:
568:
564:
560:
555:
547:
539:
536:
532:
513:
510:
507:
504:
501:
490:
489:
488:
486:
478:
474:
470:
467:
464:
460:
457:
453:
450:
428:
424:
421:
417:
414:
410:
407:
403:
397:
393:
390:
386:
383:
377:
369:
366:
365:
364:
361:
359:
355:
345:
334:
330:
327:
323:
322:
321:
319:
309:
302:
298:
295:
292:
288:
285:
284:
283:
278:Normalization
272:
271:
267:
264:
260:
256:
255:
251:
248:
244:
240:
239:
235:
234:
233:
230:
228:
224:
217:
212:
210:
206:
205:leximin order
202:
198:
194:
190:
180:
177:
162:
159:
151:
148:November 2020
141:
137:
131:
128:This article
126:
117:
116:
107:
104:
96:
93:November 2020
86:
82:
76:
73:This article
71:
62:
61:
56:
54:
47:
46:
41:
40:
35:
30:
21:
20:
2357:
2347:
2326:
2291:
2287:
2277:
2232:
2180:
2176:
2138:
2134:
2124:
2099:
2095:
2089:
2054:
2050:
2044:
2034:, retrieved
2012:1721.1/60671
1994:
1984:
1962:(1): 57–74.
1959:
1955:
1945:
1933:. Retrieved
1874:
1864:
1839:
1835:
1825:
1792:
1788:
1778:
1743:
1739:
1733:
1716:
1710:
1667:
1663:
1653:
1626:
1616:
1607:
1597:
1570:
1564:
1539:
1535:
1525:
1498:
1494:
1488:
1461:
1457:
1447:
1404:
1400:
1390:
1377:
1367:
1363:
1359:
1355:
1351:
1350:, 0} and {1-
1347:
1343:
1339:
1335:
1331:
1327:
1323:
1319:
1318:MMS for any
1315:
1313:
1307:
1303:
1302:, 1) or (3,
1299:
1295:
1288:
1284:
1276:
1272:
1268:
1267:,0} and {1-2
1264:
1261:
1258:
1246:
1242:
1240:
1237:
1231:
1223:
1216:
1210:
1200:
1188:
1186:
1168:
1163:
1159:
1155:
1151:
1147:
1143:
1139:
1135:
1131:
1127:
1123:
1119:
1115:
1111:
1107:
1105:
1098:
1094:
1090:
1086:
1082:
1078:
1074:
1070:
1066:
1062:
1058:
1056:
1049:
895:
530:
482:
368:
362:
357:
353:
351:
343:
315:
306:
300:
296:
290:
286:
281:
268:
262:
258:
252:
236:
231:
226:
219:
215:
213:
208:
192:
188:
187:
172:
154:
145:
129:
99:
90:
79:Please help
74:
50:
43:
37:
36:Please help
33:
2141:: 308–318.
249:in general.
2398:Categories
2338:2005.04864
2242:2003.07060
2190:1707.04769
2102:(2): 256.
2036:2020-11-22
1588:1595931341
1501:(3): 218.
1414:1510.05229
1382:References
892:technique.
685:, for any
39:improve it
2318:202729326
2310:2167-8375
2269:208328700
2215:216283014
2207:0895-4801
2155:0022-0531
2059:CiteSeerX
1976:1091-9856
1935:27 August
1884:0901.0205
1856:0097-5397
1809:1436-4646
1748:CiteSeerX
1746:(3): 11.
1694:1549-6325
1677:1409.0607
1556:0165-4896
1503:CiteSeerX
1480:0004-3702
1431:1432-0479
1275:} (where
1211:leximin++
1118:, define
1065:, define
1020:
999:⋅
993:
987:⋅
966:⋅
918:−
890:Woeginger
788:−
729:
718:
712:
699:Ω
696:∈
693:ε
668:ε
624:ε
574:
561:⋅
505:−
425:
418:
411:
394:
387:
45:talk page
2031:14308006
1817:52867171
1702:14749011
1150:, where
259:minimize
2384:1060279
2081:6864410
1770:1176760
1059:bundles
473:matroid
370:gave a
352:Below,
326:leximin
263:maximum
247:NP-hard
134:Please
2382:
2372:
2316:
2308:
2267:
2257:
2213:
2205:
2153:
2116:442666
2114:
2079:
2061:
2029:
2019:
1974:
1911:165160
1909:
1899:
1854:
1815:
1807:
1768:
1750:
1700:
1692:
1641:
1585:
1554:
1505:
1478:
1439:179618
1437:
1429:
1364:kε, kε
1285:2ε, 2ε
1271:,1,1,2
1243:chores
888:using
265:value.
2380:S2CID
2333:arXiv
2314:S2CID
2265:S2CID
2237:arXiv
2211:S2CID
2185:arXiv
2112:S2CID
2077:S2CID
2027:S2CID
1931:. CMU
1907:S2CID
1879:arXiv
1813:S2CID
1766:S2CID
1698:S2CID
1672:arXiv
1435:S2CID
1409:arXiv
1346:...,
1265:ε,ε,ε
1108:items
886:FPTAS
596:on a
531:chore
195:is a
2370:ISBN
2306:ISSN
2255:ISBN
2203:ISSN
2151:ISSN
2017:ISBN
1972:ISSN
1937:2016
1897:ISBN
1852:ISSN
1805:ISSN
1690:ISSN
1639:ISBN
1583:ISBN
1552:ISSN
1476:ISSN
1427:ISSN
1306:, 1+
1097:The
774:, a
598:tree
299:(or
289:(or
261:the
2362:doi
2296:doi
2247:doi
2195:doi
2143:doi
2139:158
2104:doi
2069:doi
2007:hdl
1999:doi
1964:doi
1889:doi
1844:doi
1797:doi
1758:doi
1721:doi
1682:doi
1631:doi
1575:doi
1544:doi
1513:doi
1466:doi
1462:173
1419:doi
1338:-1)
1205:.
1203:EFX
1003:log
990:log
726:log
715:log
709:log
565:log
422:log
415:log
408:log
391:log
384:log
211:.
138:to
83:by
2400::
2378:.
2368:.
2356:.
2312:.
2304:.
2290:.
2286:.
2263:.
2253:.
2245:.
2223:^
2209:.
2201:.
2193:.
2181:34
2179:.
2175:.
2163:^
2149:.
2137:.
2133:.
2110:.
2100:28
2098:.
2075:.
2067:.
2055:68
2053:.
2025:,
2015:,
2005:,
1993:,
1970:.
1960:12
1958:.
1954:.
1919:^
1905:.
1895:.
1887:.
1873:.
1850:.
1840:39
1838:.
1834:.
1811:.
1803:.
1793:46
1791:.
1787:.
1764:.
1756:.
1742:.
1696:.
1688:.
1680:.
1668:13
1666:.
1662:.
1637:.
1606:.
1581:.
1550:.
1540:16
1538:.
1534:.
1511:.
1499:54
1497:.
1474:.
1460:.
1456:.
1433:.
1425:.
1417:.
1405:68
1403:.
1399:.
1362:,
1352:kε
1344:ε,
1342:,
1334:-(
1310:).
1308:2ε
1300:2ε
1095:r.
900::
487::
48:.
2386:.
2364::
2341:.
2335::
2320:.
2298::
2292:7
2271:.
2249::
2239::
2217:.
2197::
2187::
2157:.
2145::
2118:.
2106::
2083:.
2071::
2009::
2001::
1978:.
1966::
1939:.
1913:.
1891::
1881::
1858:.
1846::
1819:.
1799::
1772:.
1760::
1744:5
1727:.
1723::
1704:.
1684::
1674::
1647:.
1633::
1591:.
1577::
1558:.
1546::
1519:.
1515::
1482:.
1468::
1441:.
1421::
1411::
1368:k
1360:k
1356:ε
1348:ε
1340:ε
1336:k
1332:k
1328:k
1324:k
1320:k
1316:k
1304:ε
1296:ε
1289:ε
1277:ε
1273:ε
1269:ε
1247:n
1189:n
1164:t
1156:m
1152:n
1148:m
1146:*
1144:n
1140:t
1136:k
1132:i
1128:k
1126:,
1124:i
1122:(
1120:t
1116:k
1112:i
1087:n
1083:r
1079:i
1075:i
1071:i
1069:(
1067:r
1063:i
1026:)
1023:m
1015:2
1011:/
1007:3
996:n
982:4
978:/
974:1
970:n
961:m
956:(
953:O
930:)
927:1
924:+
921:n
915:m
912:(
869:)
864:n
859:(
856:O
836:k
832:/
828:T
825:P
822:O
802:)
799:k
795:/
791:1
785:1
782:(
762:k
738:)
732:m
721:m
703:(
673:)
664:/
660:1
656:m
652:(
649:O
629:)
620:m
616:(
613:O
580:)
577:n
569:3
556:n
551:(
548:O
517:)
514:1
511:+
508:n
502:m
499:(
479:.
451:.
435:)
429:n
404:/
398:n
381:(
378:O
358:m
354:n
335:.
222:j
220:v
216:j
179:)
173:(
161:)
155:(
150:)
146:(
132:.
106:)
100:(
95:)
91:(
87:.
77:.
55:)
51:(
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.