Английская Википедия:Envy-freeness

Содержание

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Шаблон:Short description 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 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.

See also

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