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 ${\displaystyle i}$ receives a share ${\displaystyle X_{i}}$. Every agent ${\displaystyle i}$ has a personal preference relation ${\displaystyle \succeq _{i}}$ over different possible shares. The division is called envy-free (EF) if for all ${\displaystyle i}$ and ${\displaystyle j}$:

${\displaystyle X_{i}\succeq _{i}X_{j}}$

Another term for envy-freeness is no-envy (NE).

If the preference of the agents are represented by a value functions ${\displaystyle V_{i}}$, then this definition is equivalent to:

${\displaystyle V_{i}(X_{i})\geq V_{i}(X_{j})}$

Put another way: we say that agent ${\displaystyle i}$envies agent ${\displaystyle j}$ if ${\displaystyle i}$ prefers the piece of ${\displaystyle j}$ over his own piece, i.e.:

${\displaystyle X_{i}\prec _{i}X_{j}}$

${\displaystyle V_{i}(X_{i})<V_{i}(X_{j})}$

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. ^[1] They asked whether it is always possible to divide a cake (a heterogeneous resource) among n children with different tastes, such that no child envies another one. For n=2 children this can be done by the Divide and choose algorithm, but for n>2 the problem is much harder. See envy-free cake-cutting.

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. ^[2] 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. ^[3] 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. ^[4]

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. ^{[4] [5]} 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. ^[6]

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 ^{[7] [8]} (also called: networked envy-freeness ^[9] or social envy-freeness ^{[10] [11]} ) 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. ^[12] 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.

Relations to other fairness criteria

Implications between proportionality and envy-freeness

Proportionality (PR) and envy-freeness (EF) are two independent properties, but in some cases one of them may imply the other.

When all valuations are additive set functions and the entire cake is divided, the following implications hold:

• With two partners, PR and EF are equivalent;
• With three or more partners, EF implies PR but not vice versa. For example, it is possible that each of three partners receives 1/3 in his subjective opinion, but in Alice's opinion, Bob's share is worth 2/3.

When the valuations are only subadditive, EF still implies PR, but PR no longer implies EF even with two partners: it is possible that Alice's share is worth 1/2 in her eyes, but Bob's share is worth even more. On the contrary, when the valuations are only superadditive, PR still implies EF with two partners, but EF no longer implies PR even with two partners: it is possible that Alice's share is worth 1/4 in her eyes, but Bob's is worth even less. Similarly, when not all cake is divided, EF no longer implies PR. The implications are summarized in the following table:

Valuations	2 partners	3+ partners
Additive	${\displaystyle EF\implies PR}$ ${\displaystyle PR\implies EF}$	${\displaystyle EF\implies PR}$
Subadditive	${\displaystyle EF\implies PR}$	${\displaystyle EF\implies PR}$
Superadditive	${\displaystyle PR\implies EF}$	-
General	-	-

See also

• Inequity aversion
• Fair division experiments, studying the relative importance of envy-freeness vs. other fairness criteria.

References

1. Gamow, George; Stern, Marvin (1958). Puzzle-math. Viking Press. ISBN   0670583359.
2. Foley, Duncan (1967). "Resource allocation and the public sector". Yale Econ Essays. 7 (1): 45–98.
3. David Schmeidler and Menahem Yaari (1971). "Fair allocations". Mimeo.
4. Barbanel, Julius B. (1996-01-01). "Super Envy-Free Cake Division and Independence of Measures". Journal of Mathematical Analysis and Applications. 197 (1): 54–60. doi: 10.1006/S0022-247X(96)90006-2 . ISSN   0022-247X.
5. Webb, William A. (1999-11-01). "An Algorithm For Super Envy-Free Cake Division". Journal of Mathematical Analysis and Applications. 239 (1): 175–179. doi: 10.1006/jmaa.1999.6581 . ISSN   0022-247X.
6. Zhou, Lin (1992-06-01). "Strictly fair allocations in large exchange economies". Journal of Economic Theory. 57 (1): 158–175. doi: 10.1016/S0022-0531(05)80046-8 . ISSN   0022-0531.
7. Abebe, Rediet; Kleinberg, Jon; Parkes, David C. (2017-05-08). "Fair Division via Social Comparison". Proceedings of the 16th Conference on Autonomous Agents and MultiAgent Systems. AAMAS '17. São Paulo, Brazil: International Foundation for Autonomous Agents and Multiagent Systems: 281–289. arXiv: 1611.06589 .
8. Beynier, Aurélie; Chevaleyre, Yann; Gourvès, Laurent; Harutyunyan, Ararat; Lesca, Julien; Maudet, Nicolas; Wilczynski, Anaëlle (2019-09-01). "Local envy-freeness in house allocation problems". Autonomous Agents and Multi-Agent Systems. 33 (5): 591–627. doi:10.1007/s10458-019-09417-x. ISSN   1573-7454. S2CID   51869987.
9. Bei, Xiaohui; Qiao, Youming; Zhang, Shengyu (2017-07-07). "Networked Fairness in Cake Cutting". arXiv: 1707.02033 [cs.DS].
10. Flammini, Michele; Mauro, Manuel; Tonelli, Matteo (2019-04-01). "On social envy-freeness in multi-unit markets". Artificial Intelligence. 269: 1–26. doi:10.1016/j.artint.2018.12.003. ISSN   0004-3702. S2CID   19205358.
11. Bredereck, Robert; Kaczmarczyk, Andrzej; Niedermeier, Rolf (2020-11-23). "Envy-Free Allocations Respecting Social Networks". arXiv: 2011.11596 [cs.GT].
12. Manabe, Yoshifumi; Okamoto, Tatsuaki (2010). Hliněný, Petr; Kučera, Antonín (eds.). "Meta-Envy-Free Cake-Cutting Protocols". Mathematical Foundations of Computer Science 2010. Lecture Notes in Computer Science. Berlin, Heidelberg: Springer. 6281: 501–512. Bibcode:2010LNCS.6281..501M. doi:10.1007/978-3-642-15155-2_44. ISBN   978-3-642-15155-2.