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. 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. 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. 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 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 is a fixed point of a Tarsky operator on that lattice.

Both upper and lower quotas

Often, the hospitals have not only upper quotas, but also lower quotas – each hospital must be assigned at least some minimum number of doctors. In such problems, stable matchings may not exist. 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. In this case, if all doctor-hospital pairs are acceptable, 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.