No Justified Envy

In economics and social choice theory, a no-justified-envy matching is a matching in a two-sided market, in which no agent prefers the assignment of another agent and is simultaneously preferred by that assignment.

Consider, for example, the task of matching doctors for residency in hospitals. Each doctor has a preference relation on hospitals, ranking the hospitals from best to worst. Each hospital has a preference relation on doctors, ranking the doctors from best to worst. Each doctor can work in at most one hospital, and each hospital can employ at most a fixed number of doctors (called the ''capacity'' of the hospital). The goal is to match doctors to hospitals, without monetary transfers.

''Envy'' is a situation in which some doctor ''d''₁, employed in some hospital ''h''₁, prefers some other hospital ''h''₂, which employs some other doctor ''d''₂ (we say that ''d₁ envies d₂''). The envy is ''justified'' if, at the same time, ''h''₂ prefers ''d''₁ over ''d''₂. Note that, if ''d''₁ has justified envy w.r.t. ''h''₂, then ''h''₂ has justified envy w.r.t. ''d''₁ (''h''₂ envies ''h''₁). In this case, we also say that ''d''₁ and ''h''₂ are a ''blocking pair''. A matching with no blocking pairs is called a no-justified-envy (NJE) matching, or a matching that eliminates justified envy.

Related terms

No-justified-envy matching is a relaxation of two different conditions:

* Envy-free matching is a matching in which there is no envy at all, whether justified or not.
* Stable matching is a matching in which there is no justified envy, and in addition, there is no ''waste''. A matching has waste if there is a doctor ''d'' and a hospital ''h'', such that d prefers h over his or her current employer, ''h'' has some vacant positions, and ''h'' prefers ''d'' over a vacant position.

Lattice structure

In a many-to-one matching problem, stable matchings exist and can be found by the Gale–Shapley algorithm. Therefore, NJE matchings exist too. In general there can be many different NJE matchings. The set of all NJE matchings is a lattice. The set of stable matchings (which are a subset of the NJE matchings) is a fixed point of a Tarsky operator on that lattice.

Both upper and lower quotas

Often, the hospitals have not only upper quotas (capacities), but also ''lower quotas'' – each hospital must be assigned at least some minimum number of doctors. In such problems, stable matchings may not exist (though it is easy to check whether a stable matching exists, since by the rural hospitals theorem, in all stable matchings, the number of doctors assigned to each hospital is identical). In such cases it is natural to check whether an NJE matching exists. A necessary condition is that the sum of all lower quotas is at most the number of doctors (otherwise, no feasible matching exist at all). In this case, if all doctor-hospital pairs are acceptable (every doctor prefers any hospital to unemployment, and any hospital prefers any doctor to a vacant position), then an NJE matching always exists.

If not all pairs are acceptable, then an NJE matching might not exist. It is possible to decide the existence of an EFM in the following way. Create a new instance of the problem, in which the upper quotas are the lower quotas of the original problem, and the lower quotas are 0. In the new problem, a stable matching always exists and can be found efficiently. The original problem has an NJE matching if-and-only-if, in the stable matching of the new problem, every hospital is full.

The algorithm can be improved to find a maximal NJE matching.

Minimizing the unjustified envy

By definition, in an NJE matching, there may be a doctor ''d'' and a hospital ''h'' such that ''d'' prefers ''h'' over his current employer, but ''h'' does not prefer ''d'' over any of its current employees. This may be called an "unjustified envy". A matching with no envy at all exists only in the rare case in which each doctor can be matched to his first choice. When such a "totally envy-free matching" does not exist, it is still reasonable to find matchings that minimize the "envy amount". There are several ways in which the envy amount may be measured, for example: the total amount of envy-instances over all doctors, or the maximum amount of envy-instances per doctor.{{Citation, last=Tadenuma, first=Koichi, title=Social Ethics and Normative Economics, date=2011, pages=155–167, editor-last=Fleurbaey, editor-first=Marc, series=Studies in Choice and Welfare, chapter=Partnership, Solidarity, and Minimal Envy in Matching Problems, publisher=Springer Berlin Heidelberg, language=en, doi=10.1007/978-3-642-17807-8_6, isbn=9783642178078, editor2-last=Salles, editor2-first=Maurice, editor3-last=Weymark, editor3-first=John A.

See also

* Envy-freeness
*Envy-free pricing - a different concept related to envy-freeness and matching.

References

Stable matching
Fair division
Market (economics)