Envy-free (EF) item allocation is a fair item allocation problem, in which the fairness criterion is envy-freeness - each agent should receive a bundle that they believe to be at least as good as the bundle of any other agent. [1]: 296–297
Since the items are indivisible, an EF assignment may not exist. The simplest case is when there is a single item and at least two agents: if the item is assigned to one agent, the other will envy.
One way to attain fairness is to use monetary transfers. When monetary transfers are not allowed or not desired, there are allocation algorithms providing various kinds of relaxations.
The undercut procedure finds a complete EF allocation for two agents, if-and-only-if such allocation exists. It requires the agents to rank bundles of items, but it does not require cardinal utility information. It works whenever the agents' preference relations are strictly monotone, but does not need to assume that they are responsive preferences. In the worst case, the agents may have to rank all possible bundles, so the run-time might be exponential in the number of items.
It is usually easier for people to rank individual items than to rank bundles. Assuming all agents have responsive preferences, it is possible to lift the item-ranking to a partial bundle-ranking. For example, if the item-ranking is w>x>y>z, then responsiveness implies that {w,x}>{y,z} and {w,y}>{x,z}, but does not imply anything about the relation between {w,z} and {x,y}, between {x} and {y,z}, etc. Given an item-ranking:
The following results are known:
The empty allocation is always EF. But if we want some efficiency in addition to EF, then the decision problem becomes computationally hard: [1]: 300–310
The decision problem may become tractable when some parameters of the problem are considered fixed small constants: [8]
Many procedures find an allocation that is "almost" envy-free, i.e., the level of envy is bounded. There are various notions of "almost" envy-freeness:
An allocation is called EF1 if for every two agents A and B, if we remove at most one item from the bundle of B, then A does not envy B. [9] An EF1 allocation always exists and can be found efficiently by various procedures, particularly:
An allocation is called EFx if for every two agents A and B, if we remove any item from the bundle of B, then A does not envy B. [14] EFx is strictly stronger than EF1: EF1 lets us eliminate envy by removing the item most valuable (for A) from B's bundle; EFx requires that we eliminate envy by removing the item least valuable (for A). An EFx allocation is known to exist in some special cases:
Some approximations are known:
It is an open question whether an EFx allocation exists in general. The smallest open case is 4 agents with additive valuations.
In contrast to EF1, which requires a number of queries logarithmic in the number of items, computing an EFx allocation may require a linear number of queries even when there are two agents with identical additive valuations. [11]
Another difference between EF1 and EFx is that the number of EFX allocations can be as few as 2 (for any number of items), while the number of EF1 allocations is always exponential in the number of items. [24]
Some division scenarios involve both divisible and indivisible items, such as divisible lands and indivisible houses. An allocation is called EFm if for every two agents A and B: [25]
An EFm allocation exists for any number of agents. However, finding it requires an oracle for exact division of a cake. Without this oracle, an EFm allocation can be computed in polynomial time in two special cases: two agents with general additive valuations, or any number of agents with piecewise-linear valuations.
In contrast to EF1, which is compatible with Pareto-optimality, EFm may be incompatible with it.
Rather than using a worst-case bound on the amount of envy, one can try to minimize the amount of envy in each particular instance. See envy minimization for details and references.
The AL procedure finds an EF allocation for two agents. It may discard some of the items, but, the final allocation is Pareto efficient in the following sense: no other EF allocation is better for one and weakly better for the other. The AL procedure only requires the agents to rank individual items. It assumes that the agents have responsive preferences and returns an allocation that is necessarily envy-free (NEF).
The Adjusted winner procedure returns a complete and efficient EF allocation for two agents, but it might have to cut a single item (alternatively, one item remains in shared ownership). It requires the agents to report a numeric value for each item, and assumes that they have additive utilities.
When each agent may get at most a single item, and the valuations are binary (each agent either likes or dislikes each item), there is a polynomial-time algorithm that finds an envy-free matching of maximum cardinality. [26]
If the agents have additive utility functions that are drawn from probability distributions satisfying some independence criteria, and the number of items is sufficiently large relative to the number of agents, then an EF allocation exists with high probability. Particularly:
On the other hand, if the number of items is not sufficiently large, then, with high probability, an EF allocation does not exist.
See Fair item allocation for details and references.
Below, the following shorthands are used:
Name | #partners | Input | Preferences | #queries | Fairness | Efficiency | Comments |
---|---|---|---|---|---|---|---|
Undercut | 2 | Bundle ranking | Strictly monotone | EF | Complete | If-and-only-if a complete EF allocation exists | |
AL | 2 | Item ranking | Weakly additive | Necessarily EF | Partial, but not Pareto-dominated by another NEF | ||
Adjusted winner | 2 | Item valuations | Additive | EF and equitable | PE | Might divide one item. | |
Round-robin | Item ranking | Weakly additive | Necessarily EF1 | Complete | |||
Envy-graph | Bundle ranking | Monotone | EF1 | Complete | |||
A-CEEI | Bundle ranking | Any | ? | EF1, and -maximin-share | Partial, but PE w.r.t. allocated items | Also approximately strategyproof when there are many agents. | |
Maximum-Nash-Welfare [14] | Item valuations | Additive | NP-hard (but there are approximations in special cases) | EF1, and approximately -maximin-share | PE |
With submodular utilities, allocation is PE and MEF1. |
Envy-free (EF) item allocation is a fair item allocation problem, in which the fairness criterion is envy-freeness - each agent should receive a bundle that they believe to be at least as good as the bundle of any other agent. [1]: 296–297
Since the items are indivisible, an EF assignment may not exist. The simplest case is when there is a single item and at least two agents: if the item is assigned to one agent, the other will envy.
One way to attain fairness is to use monetary transfers. When monetary transfers are not allowed or not desired, there are allocation algorithms providing various kinds of relaxations.
The undercut procedure finds a complete EF allocation for two agents, if-and-only-if such allocation exists. It requires the agents to rank bundles of items, but it does not require cardinal utility information. It works whenever the agents' preference relations are strictly monotone, but does not need to assume that they are responsive preferences. In the worst case, the agents may have to rank all possible bundles, so the run-time might be exponential in the number of items.
It is usually easier for people to rank individual items than to rank bundles. Assuming all agents have responsive preferences, it is possible to lift the item-ranking to a partial bundle-ranking. For example, if the item-ranking is w>x>y>z, then responsiveness implies that {w,x}>{y,z} and {w,y}>{x,z}, but does not imply anything about the relation between {w,z} and {x,y}, between {x} and {y,z}, etc. Given an item-ranking:
The following results are known:
The empty allocation is always EF. But if we want some efficiency in addition to EF, then the decision problem becomes computationally hard: [1]: 300–310
The decision problem may become tractable when some parameters of the problem are considered fixed small constants: [8]
Many procedures find an allocation that is "almost" envy-free, i.e., the level of envy is bounded. There are various notions of "almost" envy-freeness:
An allocation is called EF1 if for every two agents A and B, if we remove at most one item from the bundle of B, then A does not envy B. [9] An EF1 allocation always exists and can be found efficiently by various procedures, particularly:
An allocation is called EFx if for every two agents A and B, if we remove any item from the bundle of B, then A does not envy B. [14] EFx is strictly stronger than EF1: EF1 lets us eliminate envy by removing the item most valuable (for A) from B's bundle; EFx requires that we eliminate envy by removing the item least valuable (for A). An EFx allocation is known to exist in some special cases:
Some approximations are known:
It is an open question whether an EFx allocation exists in general. The smallest open case is 4 agents with additive valuations.
In contrast to EF1, which requires a number of queries logarithmic in the number of items, computing an EFx allocation may require a linear number of queries even when there are two agents with identical additive valuations. [11]
Another difference between EF1 and EFx is that the number of EFX allocations can be as few as 2 (for any number of items), while the number of EF1 allocations is always exponential in the number of items. [24]
Some division scenarios involve both divisible and indivisible items, such as divisible lands and indivisible houses. An allocation is called EFm if for every two agents A and B: [25]
An EFm allocation exists for any number of agents. However, finding it requires an oracle for exact division of a cake. Without this oracle, an EFm allocation can be computed in polynomial time in two special cases: two agents with general additive valuations, or any number of agents with piecewise-linear valuations.
In contrast to EF1, which is compatible with Pareto-optimality, EFm may be incompatible with it.
Rather than using a worst-case bound on the amount of envy, one can try to minimize the amount of envy in each particular instance. See envy minimization for details and references.
The AL procedure finds an EF allocation for two agents. It may discard some of the items, but, the final allocation is Pareto efficient in the following sense: no other EF allocation is better for one and weakly better for the other. The AL procedure only requires the agents to rank individual items. It assumes that the agents have responsive preferences and returns an allocation that is necessarily envy-free (NEF).
The Adjusted winner procedure returns a complete and efficient EF allocation for two agents, but it might have to cut a single item (alternatively, one item remains in shared ownership). It requires the agents to report a numeric value for each item, and assumes that they have additive utilities.
When each agent may get at most a single item, and the valuations are binary (each agent either likes or dislikes each item), there is a polynomial-time algorithm that finds an envy-free matching of maximum cardinality. [26]
If the agents have additive utility functions that are drawn from probability distributions satisfying some independence criteria, and the number of items is sufficiently large relative to the number of agents, then an EF allocation exists with high probability. Particularly:
On the other hand, if the number of items is not sufficiently large, then, with high probability, an EF allocation does not exist.
See Fair item allocation for details and references.
Below, the following shorthands are used:
Name | #partners | Input | Preferences | #queries | Fairness | Efficiency | Comments |
---|---|---|---|---|---|---|---|
Undercut | 2 | Bundle ranking | Strictly monotone | EF | Complete | If-and-only-if a complete EF allocation exists | |
AL | 2 | Item ranking | Weakly additive | Necessarily EF | Partial, but not Pareto-dominated by another NEF | ||
Adjusted winner | 2 | Item valuations | Additive | EF and equitable | PE | Might divide one item. | |
Round-robin | Item ranking | Weakly additive | Necessarily EF1 | Complete | |||
Envy-graph | Bundle ranking | Monotone | EF1 | Complete | |||
A-CEEI | Bundle ranking | Any | ? | EF1, and -maximin-share | Partial, but PE w.r.t. allocated items | Also approximately strategyproof when there are many agents. | |
Maximum-Nash-Welfare [14] | Item valuations | Additive | NP-hard (but there are approximations in special cases) | EF1, and approximately -maximin-share | PE |
With submodular utilities, allocation is PE and MEF1. |