No-justified-envy matching

No-justified-envy matching

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 d1, employed in some hospital h1, prefers some other hospital h2, which employs some other doctor d2 (we say that d1 envies d2). The envy is justified if, at the same time, h2 prefers d1 over d2. Note that, if d1 has justified envy w.r.t. h2, then h2 has justified envy w.r.t. d1 (h2 envies h1). In this case, we also say that d1 and h2 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.

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.

See also * [[envy-freeness]] *[[envy-free-pricing]] - a different concept related to envy-freeness and matching.

References <references />