Egalitarian item allocation

Egalitarian item allocation, also called max-min item allocation is a fair item allocation problem, in which the fairness criterion follows the egalitarian rule. 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 leximin order). Therefore, an egalitarian item allocation is sometimes called a leximin item allocation.

The special case in which the value of each item j to each agent is either 0 or some constant v_j is called the santa claus problem: 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.

Some related problems are:

• Multiway number partitioning 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 partition problem, which corresponds to the case of two agents. Even this special case is NP-hard in general.
• Unrelated-machines scheduling is a dual problem, in which the goal is to minimize the maximum value.
• Maximin share item allocation 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.

Normalization

There are two variants of the egalitarian rule: ^[1]

• absolute egalitarian (or absolute leximin), where the maximization uses the nominal values of the agents;
• relative egalitarian (or relative leximin) where the maximization uses their normalized values - bundle value divided by value of all items.

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 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.

Exact algorithms

Although the general problem is NP-hard, small instances can be solved exactly by constraint programming techniques.

• Bouveret and Lemaître present five different algorithms for finding leximin-optimal solutions to discrete constraint-satisfaction problems. ^[2] They present max-min item allocation as a special case.
• Dall'Aglio and Mosca ^[3] gave an exact, branch-and-bound algorithm for two agents, based on an adaptation of the Adjusted winner procedure.

Randomized algorithms

Demko and Hill ^[4] present a randomized algorithm that attains an egalitarian item allocation in expectation.

Approximation algorithms

Below, n is the number of agents and m is the number of items.

For the special case of the santa claus problem:

• Bansal and Sviridenko ^[5] gave a ${\displaystyle O(\log {\log {n}}/\log {\log {\log {n}}})}$-approximation algorithm, based on rounding a linear program.
• Feige ^[6] proved that a polynomial-time constant-factor approximation algorithm exists, but the proof used Lovász local lemma and was non-constructive.
• Asadpour, Feige and Saberi ^[7] gave an actual constant-factor approximation algorithm, using hypergraph matching. They could not prove that it converges in a finite number of steps.
• Annamalai, Kalaitzis and Svensson ^[8] gave a polynomial-time 13-approximation algorithm.
• Davies, Rothvoss and Zhang ^[9] improved the approximation factor to 4 by introducing matroid constraints to the basic linear program.

For the general case, for agents with additive valuations:

• Bezakova and Dani ^[10] presented two algorithms. The first gives a ${\displaystyle (m-n+1)}$-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, ^[11] which essentially finds an allocation that is egalitarian up-to one chore. Both algorithms are based on a similar idea. They find a basic feasible solution 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.
• Asadpour and Saberi ^[12] gave a ${\displaystyle O({\sqrt {n}}\cdot \log ^{3}n)}$-approximation algorithm. Their algorithm uses an iterative method for rounding a fractional matching on a tree. They also provide better bounds when it is allowed to exclude a small fraction of people from the problem.

• Chakrabarty, Chuzoy and Khanna ^[13] gave an ${\displaystyle O(m^{\varepsilon })}$ -approximation algorithm with a run-time of ${\displaystyle O(m^{1/\varepsilon })}$ , for any ${\displaystyle \varepsilon \in \Omega \left({\frac {\log \log m}{\log m}}\right)}$ . 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.
• Golovin ^[14] gave an algorithm by which, for every integer ${\displaystyle k}$, a ${\displaystyle (1-1/k)}$ fraction of the agents receive utility at least ${\displaystyle OPT/k}$. 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 ${\displaystyle O({\sqrt {n}})}$ -approximation algorithm for the special case with two classes of goods.
• When the number of agents is constant there is an FPTAS using Woeginger technique. ^[15]

For agents with submodular utility functions:

• Golovin ^[14] gave an ${\displaystyle (m-n+1)}$ -approximation algorithm, and some inapproximability results for general utility functions.
• Goemans, Harvey, Iwata and Mirrkoni ^[16] give a ${\displaystyle O({\sqrt {m}}\cdot n^{1/4}\cdot \log n\cdot \log ^{3/2}m)}$-approximation algorithm
• Nguyen, Roos and Rothe ^{[17] [18]} present some stronger hardness results.

Ordinally egalitarian allocations

The standard egalitarian rule requires that each agent assigns a numeric value to each object. Often, the agents only have ordinal utilities. There are two generalizations of the egalitarian rule to ordinal settings.

1. Suppose agents have an ordinal ranking over the set of bundles. Given any discrete allocation, for any agent i, define r(i) as the rank of agent i's bundle, so that r(i)=1 if i got his best bundle, r(i)=2 if i got his second-best bundle, etc. This r is a vector of size n (the number of agents). An ordinally-egalitarian allocation is one that minimizes the largest element in r. The Decreasing Demand procedure finds an ordinally-egalitarian allocation for any number of agents with any ordering of bundles.

2. Suppose agents have an ordinal ranking over the set of items. Given any discrete or fractional allocation, for any agent i and positive integer k, define t(i,k) as the total fraction that agent i receives from his k topmost indifference classes. This t is a vector of size at most n*m, where n is the number of agents and m is the number of items. An ordinally-egalitarian allocation is one that maximizes the vector t in the leximin order. The Simultaneous Eating algorithm with equal eating speeds is the unique rule that returns an ordinally-egalitarian allocation. ^[19]

Comparison to other fairness criteria

Proportionality

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/n, 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.

Envy-freeness

1. When all agents have identical valuations with nonzero marginal utilities, any relative-leximin allocation is PO and EFX.

• An improvement of leximin called leximin++ guarantees EFX (but not PO) with general identical valuations. ^[20]

2. For two agents with additive valuations, any relative-leximin allocation is EF1. ^{[20] : Thm.5.5} However:

• 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 then the second agent envies. ^{[21] : 32}
• 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 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. ^{[22] : 22}

3. When all agents have valuations that are matroid rank functions (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. ^[21]

4. In the context of indivisible allocation of chores (items with negative utilities), with 3 or 4 agents with additive valuations, any leximin-optimal allocation is PROP1 and PO; with n agents with general identical valuations, any leximin-optimal allocation is EFX. ^[23]

Maximin share

When all agents have identical valuations, the egalitarian allocation, by definition, gives each agent at least his/her maximin share.

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: 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ε,ε,ε,0} and {1-2ε,1,1,2ε} (where ε is a small positive constant). Note that the valuations are normalized (the total value is 3), so absolute-leximin and relative-leximin are equivalent.

• The leximin allocation yields the utility profile (3, 2ε, 2ε): 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 ε or less; so agent 3 gets only the last item.
• The maximin-share values of the agents are 0, ε, 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, 2ε, 1) or (3, ε, 1+2ε).

The example can be extended to 1-out-of-k MMS for any k>3. There are k+1 goods and three agents who value them at {k, 0, ..., 0}, {k-(k-1)ε, ε, ..., ε, 0} and {1-kε, 1, 1, ..., kε}. The leximin utility profile must be (k, kε, kε) while the 1-out-of-k MMS of agent 3 is 1.

Real-world application

The leximin rule has been used for fairly allocating unused classrooms in public schools to charter schools. ^[24]

References

1. Segal-Halevi, Erel; Sziklai, Balázs R. (2019-09-01). "Monotonicity and competitive equilibrium in cake-cutting". Economic Theory. 68 (2): 363–401. arXiv: 1510.05229 . doi:10.1007/s00199-018-1128-6. ISSN   1432-0479. S2CID   179618.
2. Bouveret, Sylvain; Lemaître, Michel (2009-02-01). "Computing leximin-optimal solutions in constraint networks". Artificial Intelligence. 173 (2): 343–364. doi: 10.1016/j.artint.2008.10.010 . ISSN   0004-3702.
3. Dall'Aglio, Marco; Mosca, Raffaele (2007). "How to allocate hard candies fairly". Mathematical Social Sciences. 54 (3): 218. CiteSeerX   10.1.1.330.2617 . doi:10.1016/j.mathsocsci.2007.04.008.
4. Demko, Stephen; Hill, Theodore P. (1988-10-01). "Equitable distribution of indivisible objects". Mathematical Social Sciences. 16 (2): 145–158. doi:10.1016/0165-4896(88)90047-9. ISSN   0165-4896.
5. Bansal, Nikhil; Sviridenko, Maxim (2006). "The Santa Claus problem". Proceedings of the thirty-eighth annual ACM symposium on Theory of computing - STOC '06. p. 31. doi:10.1145/1132516.1132522. ISBN   1595931341.
6. Feige, Uriel (2008-01-20). "On allocations that maximize fairness". Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms. SODA '08. San Francisco, California: Society for Industrial and Applied Mathematics: 287–293.
7. Asadpour, Arash; Feige, Uriel; Saberi, Amin (2008). "Santa Claus Meets Hypergraph Matchings". In Goel, Ashish; Jansen, Klaus; Rolim, José D. P.; Rubinfeld, Ronitt (eds.). Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques. Lecture Notes in Computer Science. Vol. 5171. Berlin, Heidelberg: Springer. pp. 10–20. doi:10.1007/978-3-540-85363-3_2. ISBN   978-3-540-85363-3.
8. Annamalai, Chidambaram; Kalaitzis, Christos; Svensson, Ola (2017-05-26). "Combinatorial Algorithm for Restricted Max-Min Fair Allocation". ACM Transactions on Algorithms. 13 (3): 37:1–37:28. arXiv: 1409.0607 . doi:10.1145/3070694. ISSN   1549-6325. S2CID   14749011.
9. Davies, Sami; Rothvoss, Thomas; Zhang, Yihao (2018-07-18). A tale of Santa Claus, hypergraphs and matroids. Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics, 2020. pp. 2748–2757. doi:10.1137/1.9781611975994.
10. Bezáková, Ivona; Dani, Varsha (2005). "Allocating indivisible goods". ACM SIGecom Exchanges. 5 (3): 11. CiteSeerX   10.1.1.436.18 . doi:10.1145/1120680.1120683. S2CID   1176760.
11. Lenstra, Jan Karel; Shmoys, David B.; Tardos, Éva (1990-01-01). "Approximation algorithms for scheduling unrelated parallel machines". Mathematical Programming. 46 (1): 259–271. doi:10.1007/BF01585745. ISSN   1436-4646. S2CID   52867171.
12. Asadpour, Arash; Saberi, Amin (2010-01-01). "An Approximation Algorithm for Max-Min Fair Allocation of Indivisible Goods". SIAM Journal on Computing. 39 (7): 2970–2989. doi:10.1137/080723491. ISSN   0097-5397.
13. Chakrabarty, D.; Chuzhoy, J.; Khanna, S. (2009-10-01). "On Allocating Goods to Maximize Fairness". 2009 50th Annual IEEE Symposium on Foundations of Computer Science. pp. 107–116. arXiv: 0901.0205 . doi:10.1109/FOCS.2009.51. ISBN   978-1-4244-5116-6. S2CID   165160.
14. Golovin, Daniel (2005). "Max-min fair allocation of indivisible goods". CMU. Retrieved 27 August 2016.
15. Woeginger, Gerhard J. (2000-02-01). "When Does a Dynamic Programming Formulation Guarantee the Existence of a Fully Polynomial Time Approximation Scheme (FPTAS)?". INFORMS Journal on Computing. 12 (1): 57–74. doi:10.1287/ijoc.12.1.57.11901. ISSN   1091-9856.
16. Goemans, Michel X.; Harvey, Nicholas J. A.; Iwata, Satoru; Mirrokni, Vahab (2009-01-04), "Approximating Submodular Functions Everywhere", Proceedings of the 2009 Annual ACM-SIAM Symposium on Discrete Algorithms, Proceedings, Society for Industrial and Applied Mathematics, pp. 535–544, doi:10.1137/1.9781611973068.59, hdl: 1721.1/60671 , ISBN   978-0-89871-680-1, S2CID   14308006 , retrieved 2020-11-22
17. Nguyen, Trung Thanh; Roos, Magnus; Rothe, Jörg (2013). "A survey of approximability and inapproximability results for social welfare optimization in multiagent resource allocation". Annals of Mathematics and Artificial Intelligence. 68 (1–3): 65–90. CiteSeerX   10.1.1.671.3497 . doi:10.1007/s10472-012-9328-4. S2CID   6864410.
18. Nguyen, Nhan-Tam; Nguyen, Trung Thanh; Roos, Magnus; Rothe, Jörg (2013). "Computational complexity and approximability of social welfare optimization in multiagent resource allocation". Autonomous Agents and Multi-Agent Systems. 28 (2): 256. doi:10.1007/s10458-013-9224-2. S2CID   442666.
19. Bogomolnaia, Anna (2015-07-01). "Random assignment: Redefining the serial rule". Journal of Economic Theory. 158: 308–318. doi:10.1016/j.jet.2015.04.008. ISSN   0022-0531.
20. Plaut, Benjamin; Roughgarden, Tim (2020-01-01). "Almost Envy-Freeness with General Valuations". SIAM Journal on Discrete Mathematics. 34 (2): 1039–1068. arXiv: 1707.04769 . doi:10.1137/19M124397X. ISSN   0895-4801. S2CID   216283014.
21. Benabbou, Nawal; Chakraborty, Mithun; Igarashi, Ayumi; Zick, Yair (2020). "Finding Fair and Efficient Allocations when Valuations Don't Add up". Algorithmic Game Theory. Lecture Notes in Computer Science. Vol. 12283. pp. 32–46. arXiv: 2003.07060 . doi:10.1007/978-3-030-57980-7_3. ISBN   978-3-030-57979-1. S2CID   208328700.
22. Caragiannis, Ioannis; Kurokawa, David; Moulin, Hervé; Procaccia, Ariel D.; Shah, Nisarg; Wang, Junxing (2019-09-24). "The Unreasonable Fairness of Maximum Nash Welfare". ACM Transactions on Economics and Computation. 7 (3): 12:1–12:32. doi: 10.1145/3355902 . ISSN   2167-8375. S2CID   202729326.
23. Chen, Xingyu; Liu, Zijie (2020-05-11). "The Fairness of Leximin in Allocation of Indivisible Chores". arXiv: 2005.04864 [cs.GT].
24. Kurokawa, David; Procaccia, Ariel D.; Shah, Nisarg (2015-06-15). "Leximin Allocations in the Real World". Proceedings of the Sixteenth ACM Conference on Economics and Computation. EC '15. Portland, Oregon, USA: Association for Computing Machinery. pp. 345–362. doi:10.1145/2764468.2764490. ISBN   978-1-4503-3410-5. S2CID   1060279.