Egalitarian item allocation
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 vj 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|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:
- 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. They present max-min item allocation as a special case.
- Dall'Aglio and Mosca gave an exact, branch-and-bound algorithm for two agents, based on an adaptation of the adjusted-winner-procedure.
Randomized algorithms Demko and Hill 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***' gave a <math>O(\log{\log{n}}/\log{\log{\log{n}}})</math>-approximation algorithm, based on rounding a linear program.
- Feige 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 proved that the integrality gap of the configuration linear program is 1/4. The implies a 1/4-approximation algorithm, using hypergraph matching. However, they could not prove that the algorithm converges in a polynomial number of steps.
- Polacek and Svensson gave a Quasi-polynomial time 4-approximation algorithm.
- Annamalai, Kalaitzis and Svensson gave a polynomial-time 13-approximation algorithm.
- Davies, Rothvoss and Zhang 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 presented two algorithms. The first gives a <math>(m - n + 1)</math>-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 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 gave a <math>O(\sqrt{n} \cdot \log^3 n)</math>-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 gave an <math>O(m^{\varepsilon})</math> -approximation algorithm with a run-time of <math>O(m^{1/\varepsilon})</math> , for any <math>\varepsilon\in \Omega\left(\frac{\log\log m}{\log m}\right)</math> . 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 gave an algorithm by which, for every integer <math>k</math>, a <math>(1 - 1/k)</math> fraction of the agents receive utility at least <math>OPT/k</math>. 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 <math>O(\sqrt{n})</math> -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.
For agents with submodular utility functions:
- Golovin give a <math>O(\sqrt{m} \cdot n^{1/4} \cdot \log n\cdot \log^{3/2} m)</math>-approximation algorithm
- Nguyen, Roos and Rothe 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 nm*, 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|Simultaneous Eating algorithm**]] with equal eating speeds is the unique rule that returns an ordinally-egalitarian allocation.
Online egalitarian allocation In the online setting, the items come one by one. Each item must be allocated immediately when it arrives.
Kawase and Sumita study two variants: for the adversarial variant, they give an algorithm with competitive ratio 1/n, and show that it is the best possible. For the i.i.d. variant, they give a nearly-optimal algorithm.
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.
2. For two agents with additive valuations, any relative-leximin allocation is EF1. 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.***'
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.
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.