Envy-free matching
Envy-free matching
In economics and social choice theory, an envy-free matching (EFM) is a matching between people to "things", which is envy-free in the sense that no person would like to switch their "thing" with that of another person. This term has been used in several different contexts.
In unweighted bipartite graphs In an unweighted bipartite graph G = (X+Y, E), 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 they do 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)| ≥ |X| ≥ 1 (where NG(X) is the set of neighbors of X in Y), then G admits a nonempty EFM. An example of this setting is the rental-harmony problem - matching tenants (the agents) to rooms (the items) while setting a price to each room.
An [[envy-free-pricing|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; see envy-free-pricing for more details.