Envy-Freeness Variants in Fair Division
In the study of fair division, envy-freeness is a fundamental criterion ensuring that no participant prefers another person's share over their own. While the basic concept is straightforward, different scenarios—such as indivisible items, social networks, or random assignments—require more nuanced definitions. These variants allow mathematicians and economists to define "fairness" more precisely depending on the constraints of the allocation process.
Key Facts
- Super envy-freeness is the strongest form, implying both strong envy-freeness and standard envy-freeness.
- Group envy-freeness extends the concept to coalitions, ensuring groups of the same size are treated equitably.
- Ex-ante envy-freeness deals with lotteries and expected utility rather than final outcomes.
- Local envy-freeness limits the scope of envy to an agent's immediate neighbors in a social network.
- Envy minimization is used as an optimization goal when a perfectly envy-free state is mathematically impossible.
Strengthened Versions of Envy-Freeness
Some frameworks require a higher standard of fairness than basic envy-freeness. These variants ensure that agents are not just satisfied, but strictly prefer their own allocation.
Strong and Super Envy-Freeness
Strong envy-freeness occurs when every agent strictly prefers their own bundle to any other bundle. Moving a step further, super envy-freeness requires that an agent strictly prefers their bundle to 1/n of the total value, and strictly prefers that 1/n share to any other agent's bundle. Because of these strict requirements, super envy-freeness implies strong envy-freeness, which in turn implies standard envy-freeness.
Group and Coalitional Envy-Freeness
Group envy-freeness (or coalitional envy-freeness) shifts the focus from individuals to sets of participants. It requires that any group of participants feels their combined allocated share is at least as good as the share of any other group of the same size. A related but weaker version is strict envy-freeness, where an individual agent simply does not envy any coalition of other agents.
[ไม่มีภาพประกอบ]Context-Specific Envy-Freeness
Depending on how items are valued or how they are distributed, different definitions of envy-freeness are applied.
Stochastic-Dominance Envy-Freeness (SD-EF)
In settings where agents provide ordinal rankings (ordered lists of preference) rather than exact values, stochastic-dominance envy-freeness (also known as necessary envy-freeness) is used. This requires envy-freeness to hold across all additive valuations compatible with the agent's ranking. An approximate version, SD-EF1 (SD-EF up to one item), can be achieved using a round-robin item allocation procedure.
Ex-Ante vs. Ex-Post Envy-Freeness
When dealing with fair random assignments, agents receive a lottery over items. Ex-ante envy-freeness means no agent prefers the lottery (and its expected utility) of another agent. In contrast, ex-post envy-freeness is much stricter, requiring that every possible outcome of the lottery be envy-free. While ex-post implies ex-ante, the reverse is not necessarily true.
Local and Meta Envy-Freeness
Local envy-freeness (also called networked or social envy-freeness) assumes that agents only have knowledge of their neighbors' allocations within a social network. In this model, agents can only envy those they are connected to. Standard envy-freeness is essentially a special case of this, where the network is a complete graph (everyone is connected to everyone).
Meta envy-freeness extends the concept beyond the final result, requiring that agents do not envy others regarding their goals within the allocation protocol itself, a concept often seen in symmetric fair cake-cutting.
Market-Based and Optimization Variants
Justified Envy
In two-sided markets—such as matching students to schools—the concept of no justified envy is used. This is a weakening of no-envy. Student A feels justified envy toward Student B if A prefers B's school, and B's school also prefers Student A over Student B.
Envy Minimization
In many real-world scenarios, especially with indivisible objects, a perfectly envy-free allocation is impossible. In these cases, envy minimization is treated as an optimization problem, where the goal is to reduce the total amount of envy as much as possible.
[ไม่มีภาพประกอบ]Summary of Envy-Freeness Variants
| Variant | Core Requirement | Relative Strength |
|---|---|---|
| Super Envy-Freeness | Prefers own bundle > 1/n > others | Strongest |
| Strong Envy-Freeness | Strictly prefers own bundle to others | Strong |
| Group Envy-Freeness | Groups don't envy other groups of same size | Strong (Coalitional) |
| SD-Envy-Freeness | Envy-free across all compatible additive valuations | Ordinal-based |
| Ex-Ante Envy-Freeness | No agent prefers another's lottery/expected utility | Probabilistic |
| Local Envy-Freeness | No envy toward neighbors in a social network | Weakened (Networked) |
| Justified Envy | Envy is only "justified" if the item also prefers the agent | Weakened (Two-sided) |
Frequently Asked Questions
What is the difference between ex-ante and ex-post envy-freeness?
Ex-ante envy-freeness means that before the random draw occurs, no agent prefers another agent's lottery (expected utility). Ex-post envy-freeness means that after the draw is completed, the actual resulting allocation is envy-free.
How does local envy-freeness differ from standard envy-freeness?
Standard envy-freeness assumes every agent compares their share to everyone else's. Local envy-freeness assumes agents only compare their share to those of their neighbors in a social network.
What is SD-EF1?
SD-EF1 is an approximate variant of stochastic-dominance envy-freeness (SD-EF) that allows for envy "up to one item." This specific variant can be achieved using a round-robin allocation method.
When is envy minimization used instead of envy-freeness?
Envy minimization is used as an optimization objective when a perfectly envy-free allocation is mathematically impossible, which frequently happens when allocating indivisible objects.
What constitutes "justified envy" in a two-sided market?
Justified envy occurs when an agent prefers another agent's allocation, and that allocation (e.g., a school) also prefers the first agent over the one currently assigned to it.