Envy-freeness · Lablypedia

Related on Lably

Through Fair division, Preference (economics) and Social network

Lab · Class 11–12Bonds & Fixed Income Lab · Class 11Stocks And Mutual Funds Lab · Class 10–12Recommendation Engine

General definitions

Suppose a certain resource is divided among several agents, such that every agent $i$ receives a share $X_{i}$ . Every agent $i$ has a personal preference relation $⪰_{i}$ over different possible shares. The division is called envy-free (EF) if for all $i$ and $j$ :

X_{i} ⪰_{i} X_{j}

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

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} ≺_{i} X_{j}

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

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

3 more chapters are free with a Lably account.

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 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. 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.

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:

More in Computing and communication

ISBNUnique numeric book identifier since 1970 X (social network)American social networking service Wayback MachineDigital archive by the Internet Archive Python (programming language)General-purpose programming language MacOSOperating system for Apple computers UnicodeCharacter encoding standard