Envy-freeness

Envy-freeness (EF) is a criterion of fair division. In an envy-free division, every agent feels that their share is at least as good as the share of any other agent, and thus no agent feels envy.

Definitions

A resource is divided among several agents such that every agent $i$ receives a share $X_{i}$ . Every agent $i$ has a subjective preference relation $\succeq _{i}$ over different possible shares. The division is called envy-free if for all $i$ and $j$ :

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

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

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

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

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

V_{i}(X_{i})<V_{i}(X_{j})

A division is called envy-free if no agent envies another agent.

History

EF was introduced to the problem of fair cake-cutting by George Gamow and Marvin Stern in 1958.[1] In the context of fair cake-cutting, EF means that each agent believes that their share is at least as large as any other share. In the context of chore division, EF means that each agent believes their share is at least as small as any other share. The crucial issue is that no agent would wish to swap their share with any other agent.

See:

Envy-free cake-cutting - a detailed survey of procedures and results related to the envy-free criterion in cake-cutting.
Group-envy-free - a strengthening of the envy-free criterion from individuals to coalitions.

Later, EF was introduced to the economics problem of resource allocation by Duncan Foley in 1967.[2] It became the dominant fairness criterion in economics. See, for example:

Varian's theorems

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	$EF\implies PR$ $PR\implies EF$	$EF\implies PR$
Subadditive	$EF\implies PR$	$EF\implies PR$
Superadditive	$PR\implies EF$	-
General	-	-

gollark: It doesn't matter if it's "not real intelligence" if it is a very effective paperclip-making tool and turns you into paperclips.

gollark: It isn't very fast but at least better than expected.

gollark: My phone mysteriously stopped working, and I'm now actually quite surprised with how well Discord runs on my ancient spare one.

gollark: [SUPERIOR BRAIN SYMBOL] geesegeese, actually.

gollark: The lead probably wouldn't stop neutrinos, but I don't think you can do anything interesting with those with random computing hardware.

References

Gamow, George; Stern, Marvin (1958). Puzzle-math. Viking Press. ISBN 0670583359.
Foley, Duncan (1967). "Resource allocation and the public sector". Yale Econ Essays. 7 (1): 45–98.
Stefan, KOHLER, (2012). "Envy can promote more equal division in alternating-offer bargaining". ISSN 1725-6704. Cite journal requires |journal= (help)CS1 maint: extra punctuation (link)

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[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] Stefan, KOHLER, (2012). "Envy can promote more equal division in alternating-offer bargaining". ISSN 1725-6704. Cite journal requires |journal= (help)CS1 maint: extra punctuation (link)