Envy-freeness
Envy-freeness
- Envy-freeness, also known as no-envy**, is a criterion for [[fair-division]]. It says that, when resources are allocated among people with equal rights, each person should receive a share that is, in their eyes, at least as good as the share received by any other agent. In other words, no person should feel envy.
General definitions Suppose a certain resource is divided among several agents, such that every agent <math>i</math> receives a share <math>X_i</math>. Every agent <math>i</math> has a personal preference relation <math>\succeq_i</math> over different possible shares. The division is called envy-free (EF) if for all <math>i</math> and <math>j</math>: :::<math>X_i \succeq_i X_j</math>
Another term for envy-freeness is no-envy (NE).
If the preference of the agents are represented by a value functions <math>V_i</math>, then this definition is equivalent to: :::<math>V_i(X_i) \geq V_i(X_j)</math>
Put another way: we say that agent <math>i</math> envies agent <math>j</math> if <math>i</math> prefers the piece of <math>j</math> over his own piece, i.e.: :::<math>X_i \prec_i X_j</math> :::<math>V_i(X_i) < V_i(X_j)</math> A division is called envy-free if no agent envies another agent.
Special cases The notion of envy-freeness was introduced by George Gamow and Marvin Stern in 1958. They asked whether it is always possible to divide the brandy (a heterogeneous resource) among 3 people, such that everyone gets their fair share, which is at least one-third. The difficulty arises from the fact that each person, when brandy has been divided, has their own opinion on which glass has the most brandy. For n=2 this can be done by the divide-and-choose algorithm, but for n=3 the problem has been stated as unsolvable. In later works, this problem has been usually formulated as the envy-free-cake-cutting, where the cake is divided among children with different tastes.
In cake-cutting, EF means that each child believes that their share is at least as large as any other share; in the chore division, EF means that each agent believes their share is at least as small as any other share (the crucial issue in both cases is that no agent would wish to swap their share with any other agent). See chore-division.
Envy-freeness was introduced to the economics problem of resource allocation by Duncan Foley in 1967. In this problem, rather than a single heterogeneous resource, there are several homogeneous resources. Envy-freeness by its own is easy to attain by just giving each person 1/n of each resource. The challenge, from an economic perspective, is to combine it with Pareto-efficiency. The challenge was first defined by david-schmeidler and Menahem Yaari. See efficient-envy-free-division.
When the resources to divide are discrete (indivisible), envy-freeness might be unattainable even when there is one resource and two people. There are various ways to cope with this problem:
- Transferring money among the participants in order to compensate those who get the less valuable items. This solution is used, for example, in the rental-harmony problem, and in envy-free-pricing.
- Sharing a small number of items. This is done, for example, in the adjusted-winner-procedure.
- Finding approximately-fair allocations; see envy-free-item-allocation.
- Finding partial envy-free allocations that are as large as possible; see envy-free-matching.
- Using randomization to find allocations that are envy-free in expectation ("ex-ante"); see fair-random-assignment.
Variants Strong envy-freeness requires that each agent strictly prefers his bundle to the other bundles.
- super-envy-freeness** requires that each agent strictly prefers his bundle to 1/*n* of the total value, and strictly prefers 1/*n* to each of the other bundles. Clearly, super envy-freeness implies strong envy-freeness which implies envy-freeness.
- group-envy-freeness (also called coalitional envy-freeness) is a strengthening of the envy-freeness, requiring that every group of participants feel that their allocated share is at least as good as the share of any other group with the same size. A weaker requirement is that each individual agent not envy any coalition of other agents; it is sometimes called strict envy-freeness**.
- Stochastic-dominance envy-freeness (SD-envy-free, also called necessary envy-freeness**) is a strengthening of envy-freeness for a setting in which agents report ordinal rankings over items. It requires envy-freeness to hold with respect to all additive valuations that are compatible with the ordinal ranking. In other words, each agent should believe that his/her bundle is at least as good as the bundle of any other agent, according to the responsive set extension of his/her ordinal ranking of the items. An approximate variant of SD-EF, called SD-EF1 (SD-EF up to one item), can be attained by the [[round-robin-item-allocation]] procedure.
- No justified envy** is a weakening of no-envy for two-sided markets, in which both the agents and the "items" have preferences over the opposite side, e.g., the market of matching students to schools. Student A feels *justified envy* towards student B, if A prefers the school allocated to B, and at the same time, the school allocated to B prefers A.
- Ex-ante envy-freeness** is a weakening of envy-freeness used in the setting of [[fair-random-assignment]]. In this setting, each agent receives a *lottery* over the items; an allocation of lotteries is called ex-ante envy-free if no agent prefers the lottery of another agent, i.e., no agent assigns a higher expected utility to the lottery of another agent. An allocation is called ex-post envy-free if each and every result is envy-free. Obviously, ex-post envy-freeness implies ex-ante envy-freeness, but the opposite might not be true.
- Local envy-freeness (also called: networked envy-freeness or social envy-freeness**) is a weakening of envy-freeness based on a social network. It assumes that people are only aware of the allocations of their neighbors in the network, and thus they can only envy their neighbors. Standard envy-freeness is a special case of social envy-freeness in which the network is the complete graph.
- Meta envy-freeness** requires that agents do not envy each other, not only with respect to the final allocation, but also with respect to their goals in the protocol. See [[symmetric-fair-cake-cutting]].
- envy-minimization** is an optimization problem in which the objective is to minimize the amount of envy (which can be defined in various ways), even in cases in which envy-freeness is impossible. For approximate variants of envy-freeness used when allocating indivisible objects, see [[envy-free-item-allocation]].