This article has multiple issues. Please help
improve it or discuss these issues on the
talk page. (
Learn how and when to remove these template messages)
|
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:
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. 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 [4] 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.
For the special case of the santa claus problem:
For the general case, for agents with additive valuations:
For agents with submodular utility functions:
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]
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.
1. When all agents have identical valuations with nonzero marginal utilities, any relative-leximin allocation is PO and EFX.
2. For two agents with additive valuations, any relative-leximin allocation is EF1. [20]: Thm.5.5 However:
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]
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 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.
The leximin rule has been used for fairly allocating unused classrooms in public schools to charter schools. [24]
This article has multiple issues. Please help
improve it or discuss these issues on the
talk page. (
Learn how and when to remove these template messages)
|
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:
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. 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 [4] 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.
For the special case of the santa claus problem:
For the general case, for agents with additive valuations:
For agents with submodular utility functions:
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]
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.
1. When all agents have identical valuations with nonzero marginal utilities, any relative-leximin allocation is PO and EFX.
2. For two agents with additive valuations, any relative-leximin allocation is EF1. [20]: Thm.5.5 However:
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]
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 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.
The leximin rule has been used for fairly allocating unused classrooms in public schools to charter schools. [24]