In economics and social choice theory, an envy-freematching is a matching between people to "things", which is envy-free in the sense that no person would like to switch his "thing" with that of another person. This term has been used in several different contexts.
In markets with money
Consider a market in which there are several buyers and several goods, and each good may have a price. Given a price-vector, each buyer has a demand set - a set of bundles that maximize the buyer's utility over all bundles. An envy-free matching is a matching in which each agent receives a bundle from his demand-set. This means that no agent would like to get the bundle of another agent with the same prices. An example of this setting is the rental harmony problem - matching tenants to rooms while setting a price to each room. An envy-free price is a price-vector for which an envy-free matching exists. It is a relaxation of a Walrasian equilibrium: a Walrasian equilibrium consists of an EF price and EF matching, and in addition, every item must either be matched or have zero price. It is known that, in a Walrasian equilibrium, the matching maximizes the sum of values, i.e., it is a maximum-weight matching. However, the seller's revenue might be low. This motivates the relaxation to EF pricing, in which the seller may use reserve prices to increase the revenue.
In markets without money
Consider the problem of matching doctors for residency in hospitals. Each doctor has a preference relation on hospitals, and each hospital has a preference relation on doctors. Each doctor can work in at most one hospital, and each hospital can employ at most a fixed number of doctors. We want to match doctors to hospitals. Monetary transfers are not allowed. There are two ways in which such a matching can be "bad":
A matching has justified envy if there is a doctor d and a hospital h, such that d prefers h over his current employer, and h prefers d over one of its current employees.
A matching has waste if there is a doctor d and a hospital h, such that d prefers h over his current employer, h has some vacant positions, and h prefers d over a vacant position.
An envy-free matching is a matching with no justified envy. It is a relaxation of stable matching: a stable matching is a matching that is both envy-free and has no waste.
In a many-to-one matching problem, stable matchings exist and can be found by the Gale–Shapley algorithm. Therefore, EF matchings exist too. In general there can be many different EF matchings. The set of all EF 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 EF 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 EF matching always exists. If not all pairs are acceptable, then an EF 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 EF 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 EF matching.
Minimizing envy
As defined above, envy-free matching only eliminates justified envy, where a doctor d envies another doctor who is matched to a hospital h that prefers d. However, even in an EFM, 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.
In an unweighted bipartite graph G =, an envy-free matching is a matching in which no unmatched vertex in X is adjacent to a matched vertex in Y. Suppose the vertices of X represent people, the vertices of Y represent houses, and an edge between a person x and a house y represents the fact that x is willing to live in y. Then, an EFM is a partial allocation of houses to people such that each house-less person does not envy any person with a house, since he does not like any allocated house anyway. Every matching that saturates X is envy-free, and every empty matching is envy-free. Moreover, if |NG| ≥ |X| ≥ 1, then G admits a nonempty EFM. This is a relaxation of Hall's marriage condition, which says that, if |NG| ≥ |X'| for every subset X' of X, then an X-saturating matching exists.
In cake-cutting
The term envy-free matching has also been used in a different context: an algorithm for improving the efficiency of envy-free cake-cutting.
