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: There are two variants of the egalitarian rule:[1] 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.
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[4] present a randomized algorithm that attains an egalitarian item allocation in expectation.
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.
An ordinally-egalitarian allocation is one that maximizes the vector t in the leximin order.
When all agents have identical valuations with nonzero marginal utilities, any relative-leximin allocation is PO and EFX.
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.
Note that the valuations are normalized (the total value is 3), so absolute-leximin and relative-leximin are equivalent.