Envy-free item assignment (EF assignment) is a fair item assignment problem, in which the fairness criterion is envy-freeness - each agent should receive a bundle that he believes to be at least as good as the bundle of any other agent.
Contents
- Preference orderings on bundles envy freeness
- Preference orderings on items necessarypossible envy freeness
- Finding a partial envy free allocation
- Bounding the maximum envy
- Round robin protocol
- Unenvied agent protocol
- A CEEI protocol
- Maximum Nash Welfare
- EF1 vs EFx
- Minimizing the envy ratio
- General valuations
- Additive and identical valuations
- Additive and different valuations
- Dividing one item
- Deciding whether an EF allocation exists
- Existence of EF allocations with random valuations
- Envy freeness vs other fairness criteria
- Summary table
- References
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. Therefore, the division procedures provide various kinds of relaxations.
Preference-orderings on bundles: envy-freeness
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.
Preference-orderings on items: necessary/possible envy-freeness
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 beteen {w,z} and {x,y}, between {x} and {y,z}, etc.
Given an item-ranking:
Bouveret and Endriss and Lang study the algorithmic questions of finding a NEF/PEF allocation with an additional efficiency condition, particularly, completeness or NPE or PPE. In general, PEF is computationally easy while NEF is computationally hard.
Finding a partial envy-free allocation
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).
Bounding the maximum envy
Several procedures find an allocation that is Envy-free except one item (EF1): for each two agents A and B, there exists an item that can be removed from the bundle of B such that A does not envy B.
Round-robin protocol
When all agents have weakly additive utilities, the following protocol (which is similar to Round-robin scheduling) attains a complete EF1 allocation:
- Order the agents arbitrarily.
- While there are unassigned items:
- Let each agent from 1 to
n pick an item.
The round-robin protocol requires weak additivity, since it requires each agent to pick his "best item" without knowing what other items he is going to get. In other words, it assumes that the items are independent goods.
Unenvied-agent protocol
The unenvied-agent procedure returns a complete EF1 allocation for arbitrary preference relations. The only requirement is that the agents can rank bundles of items.
If the agents' valuations are represented by a cardinal utility function, then the EF1 guarantee has an additional interpretation: the numeric envy-level of each agent is at most the maximal-marginal-utility - the largest marginal utility of a single item for that agent.
A-CEEI protocol
The A-CEEI mechanism returns a partial EF1 allocation for arbitrary preference relations. The only requirement is that the agents can rank bundles of items.
A small number of items might remain unallocated; the allocation is Pareto-efficient with respect to the allocated items. Moreover, the A-CEEI mechanism is approximately strategyproof when the number of agents is large.
Maximum-Nash-Welfare
The Maximum-Nash-Welfare (MNW) algorithm selects a complete allocation that maximizes the product of utilities. It requires each agent to provide a numeric valuation of each item, and assumes that the agents' utilities are additive. The resulting allocation is EF1 and Pareto-efficient.
If the agents' utilities are not additive, the MNW solution is not necessarily EF1; but if the agents' utilities are at least submodular, the MNW solution satisfies a weaker property called Marginal-Envy-Freeness except-1-item (MEF1).
EF1 vs EFx
There is an alternative criterion called Envy-freeness-except-cheapest (EFx): For each two agents A and B, if we remove from the bundle of B any item, then A does not envy B. EFx is strictly stronger than EF1. As of this writing, it is not known whether EFx allocations always exist.
Minimizing the envy-ratio
Given an allocation X, define the envy ratio of i in j as:
so the ratio is 1 if i does not envy j, and it is larger when i envies j. Define the envy ratio of an assignment as:
The envy ratio minimization problem is the problem of finding an allocation X with smallest envy ratio.
General valuations
With general valuations, any deterministic algorithm that computes an alloation with minimum envy-ratio requires a number of queries which is exponential in the number of goods in the worst case.
Additive and identical valuations
With additive and identical valuations:
- Order the items by descending value;
- While there are more items, give the next item to an agent with the smallest total value.
Additive and different valuations
With additive and different valuations:
Dividing one item
The Adjusted winner procedure returns a complete and efficient EF allocation for two agents, but it might have to divide a single item. It requires the agents to report a numeric value for each item, and assumes that they have additive utilities.
Deciding whether an EF allocation exists
The empty allocation is always EF. But if we want some efficiency in addition to EF, then the decision problem becomes computationally hard:
Existence of EF allocations with random valuations
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:
Envy-freeness vs. other fairness criteria
See Fair item assignment for details and references.
Summary table
Below, the following shorthands are used: