Envy-free item allocation

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.

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 research on this topic focuses on finding feasible approximations.

Round-robin protocol - EF except one

The simplest protocol for item-assignment is the round-robin protocol (which is similar to Round-robin scheduling):

1. Order the agents arbitrarily.
2. While there are unassigned items:
   • Let each agent from 1 to $n$ pick an item.

The final allocation is not necessarily EF. But, when all agents have weakly additive utilities, it is always envy-free-except-1 (EF1): for each two agents A and B, if we remove from the bundle of B the item most valuable for A, then A does not envy B (in other words, the "envy level" of A in B is at most the value of a single item).

Proof: For every agent $i$, divide the selections made by the agents to sub-sequences: the first subsequence starts at agent 1 and ends at agent $i-1$; the latter subsequences start at $i$ and end at $i-1$. In the latter subsequences, agent $i$ chooses first, so he can choose his best item, so he does not envy any other agent. Agent $i$ can envy only one of the agents $1,...,i-1$, and the envy comes only from an item they selected in the first subsequence. If this item is removed, agent $i$ does not envy.

Note: present an alternative criterion called Envy-freeness-except-cheapest (EFx): For each two agents A and B, if we remove from the bundle of B the item least valuable for A, then A does not envy B. EFx is strictly stronger than EF1. It is not known whether EFx allocations always exist.

Envy-graph protocol - EF except maximal-marginal-utility

The following protocol works even when the agents' utilities are not weakly-additive.

1. Order the items arbitrarily.
2. While there are unassigned items:
   • Ensure that there is an unenvied agent - an agent that no other agent envies.
   • Give the next item to the unenvied agent.

In step 2, if there is no unenvied agent, it means that there is a cycle in the envy graph (a directed graph in which each agent points to all agents he envies). Cycles can be removed by cyclic exchange of bundles. After all cycles are removed, the envy-graph must have a node with no incoming edges; this node represents an unenvied agent.

The resulting allocation is not necessarily EF, but it is envy-free except maximal-marginal-utility (EFM). The maximal-marginal-utility is the largest marginal utility of a single item.

Note that when all agents have weakly additive utilities, an EF1 allocation is EFM, and it can be found by the above round-robin protocol. The advantage of the envy-graph protocol is that it works with arbitrary valuations.

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:

• Deciding whether an EF and complete allocation exists is NP-complete.
• Deciding whether an EF and Pareto efficient allocation exists is above NP: it is $\Sigma _{2}^{\textrm {P}}$-complete even with dichotomous preferences and even with additive utilities.

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:

• If the number of items is sufficiently large: $m=\Omega (n\log n)$, then w.h.p. an EF allocation exists (the probability goes to 1 as m goes to infinity).
• If the number of items is not sufficiently large, i.e, $m=n+o(n)$, then w.h.p. an EF allocation does not exist.

Relations with other fairness criteria

• Every EF allocation is min-max-fair. This follows directly from the ordinal definitions and does not depend on additivity.
• If all agents have additive utility functions, then an EF allocation is also proportional and max-min-fair. Otherwise, an EF allocation may be not proportional and even not max-min-fair.
• Every allocation of a competitive equilibrium from equal incomes is also envy-free. This is true regardless of additivity.
• Every Nash-optimal allocation (allocation that maximizes the product of utilities) is EF1.

See Fair item assignment for details and references.