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.

For the general case, for agents with additive valuations:

• Bezakova and Dani^[9] 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,^[10] 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^[11] 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^[12] 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^[13] 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.^[14]

For agents with submodular utility functions:

• Golovin^[13] gave an ${\displaystyle (m-n+1)}$ -approximation algorithm, and some inapproximability results for general utility functions.
• Goemans, Harvey, Iwata and Mirrkoni^[15] give a ${\displaystyle O({\sqrt {m}}\cdot n^{1/4}\cdot \log n\cdot \log ^{3/2}m)}$-approximation algorithm
• Nguyen, Roos and Rothe^[16][17] 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.^[18]

Comparison to other fairness criteria

Real-world application

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

References