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:

There are two variants of the egalitarian rule:

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.

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

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

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