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.
Terminology in the literature is not uniform:
Wu and Roth use "envy-free matching" for what this article calls an NJE matching, and require in addition that the matching be individually rational. In the school choice literature the same property is usually called fairness, following Balinski and Sönmez, who introduced it as the central normative requirement for centralized student placement and showed that the student-proposing deferred acceptance outcome is the best fair assignment for the students.
Examples The following small instances separate no-justified-envy matchings from envy-free matchings and stable matchings. The first instance shows that an NJE matching need not be envy-free, and that an NJE matching can exist when an envy-free matching does not. The second shows that an NJE matching need not be stable. The third shows that under lower quotas an NJE matching may exist when no stable matching does.
Justified versus unjustified envy Let there be two doctors d1, d2 and two hospitals h1, h2, each of capacity 1, with all pairs acceptable and with the preferences
d1: h1 ≻ h2, and d2: h1 ≻ h2; h1: d1 ≻ d2, and h2: d1 ≻ d2.
In the matching M1 that employs d1 at h1 and d2 at h2, doctor d2 envies d1, since d2 would rather work at h1. The envy is not justified, because h1 prefers the doctor it already has. As there is no other envy, M1 is an NJE matching, and since both positions are filled it is in fact stable. It is not envy-free.
In the matching M2 that employs d1 at h2 and d2 at h1, doctor d1 envies d2, and this time h1 agrees, so (d1, h1) is a blocking pair and M2 is not an NJE matching. In this instance no matching that employs both doctors is envy-free, since h1 has a single position and both doctors rank it first. Totally envy-free matchings are therefore a much more demanding requirement, and one that typically cannot be met.
A no-justified-envy matching that is not stable Let there be two doctors d1, d2, a hospital h1 of capacity 1 and a hospital h2 of capacity 2, with all pairs acceptable and with the preferences
d1: h2 ≻ h1, and d2: h2 ≻ h1; h1: d1 ≻ d2, and h2: d2 ≻ d1.
Consider the matching that employs d1 at h1 and d2 at h2, so that one of h2's two positions stays unfilled. Doctor d1 envies d2, but h2 prefers the doctor it already has, so the envy is unjustified and the matching has no justified envy. It is nevertheless not stable: d1 prefers h2, and h2 would rather fill its second position with d1 than leave it empty, so (d1, h2) is a blocking pair. Note that h2 has no wish to replace d2 by d1; it only wants to hire in addition, and the failure of stability comes entirely from the unfilled position. This is a general fact: NJE means that any blocking pair must involve a hospital with at least one unfilled position.
Lower quotas Let there be two doctors d1, d2; a hospital h1 with capacity 2 and no lower quota; and a hospital h2 with capacity 1 and lower quota 1. Both doctors prefer h1 to h2, h1 prefers d1 to d2, and all pairs are acceptable. Feasibility forces exactly one doctor into h2, so there are only two candidate matchings. Employing d1 at h1 and d2 at h2 leaves d2 with envy that h1 does not endorse, so this matching has no justified envy; but h1 still has a free position that d2 would prefer, so it is wasteful and not stable. Employing d2 at h1 and d1 at h2 gives d1 justified envy toward d2. Hence no feasible stable matching exists, while a feasible NJE matching does — the situation that motivates the study of NJE matchings under lower quotas.
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; Wu and Roth exhibit an instance with two doctors and three hospitals of capacity 1 that admits seven of them.
The set of all NJE matchings is a lattice under the common preferences of the doctors, that is, under the order in which one matching ranks above another when every doctor weakly prefers it. The join is the one familiar from Conway's theorem on stable matchings: assigning every doctor the better of the two hospitals he holds in the two matchings again yields an NJE matching. The meet is not obtained in the dual way, because assigning every doctor the worse of his two hospitals may violate a capacity constraint; the lattice is also not distributive. Its minimum is the empty matching, in which nobody is employed, and its maximum is the doctor-optimal stable matching.
The set of stable matchings, which is a subset of the NJE matchings, is exactly the set of fixed points of a Tarski operator on that lattice. The operator can be read as one round of a vacancy chain: every hospital with an unfilled position makes an offer to the best doctor with whom it blocks, and every doctor accepts the best offer received. Iterating it from an NJE matching µ converges to the join of µ with the hospital-optimal stable matching µH; started from the empty matching it reproduces a version of the hospital-proposing deferred acceptance algorithm. Two consequences are that an NJE matching which all doctors weakly prefer to µH is already stable, and that no NJE matching fills more positions in total than a stable matching does, so relaxing stability to no-justified-envy cannot be used to employ more doctors. The lattice structure depends on the hospitals' preferences being responsive; it fails once they are merely substitutable.
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, because minimum quotas make fairness and non-wastefulness incompatible, as shown by the example above. Fragiadakis, Iwasaki, Troyan, Ueda and Yokoo respond by weakening these axioms, give strategyproof mechanisms for the resulting second-best criteria, and show that when the lower quotas sum to at most the number of doctors and all doctor–hospital pairs are acceptable (every doctor prefers any hospital to unemployment, and any hospital prefers any doctor to a vacant position), an NJE matching always exists. Whether a stable matching exists is easy to check, since by the rural hospitals theorem the number of doctors assigned to each hospital is the same in all stable matchings.
If not all pairs are acceptable, then an NJE matching might not exist. It is possible to decide the existence of an NJE matching 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 same analysis extends to Huang's classified stable matching model, in which each hospital sets lower and upper quotas on subsets of doctors.
The algorithm can be improved to find a maximal NJE matching, that is, one to which no further doctor–hospital pair can be added without creating justified envy. Maximality is weaker than maximum size: Krishnaa, Limaye, Nasre and Nimbhorkar prove that computing an NJE matching of maximum size is NP-hard and hard to approximate within a constant factor, and propose relaxed stability, a further weakening that is guaranteed to be attainable together with the lower quotas.
Justified envy and efficiency Eliminating justified envy has a welfare cost. Kesten showed that the doctor-optimal stable matching — the best NJE matching from the doctors' point of view — can impose large welfare losses on them, traced those losses to priorities that have no effect on the assignment of the doctor holding them, and proposed the efficiency-adjusted deferred acceptance mechanism, under which doctors may consent to waive such priorities and thereby recover the loss. Ehlers and Morrill approach the same trade-off by applying the fairness test to sets of assignments rather than to single ones: they call a set of assignments legal if every assignment outside it has justified envy with respect to some assignment inside it, while no two assignments inside the set block each other, and they show that a unique legal set always exists, that it is a lattice satisfying the rural hospitals theorem, and that its student-optimal element is efficient.
Conversely, one may keep efficiency and give up some justified envy. Abdulkadiroğlu, Che, Pathak, Roth and Tercieux show that among the mechanisms that are both Pareto efficient and strategyproof, top trading cycles minimizes justified envy in one-to-one matching, and admits less of it than serial dictatorship on average in many-to-one matching; using data from the New Orleans OneApp and Boston Public Schools, they find that top trading cycles generates substantially fewer instances of justified envy than serial dictatorship in practice.
Minimizing the 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.