Envy-free matching
Matching where no person wants to switch their thing with someone else's
- 2 min read
- 4 chapters
Related on Lably
Through Economics
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. This is a relaxation of Hall's marriage condition, which says that, if |NG(X')| ≥ |X'| for every subset X' of X, then an X-saturating matching exists.
Sign in to keep reading
3 more chapters are free with a Lably account.
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 (this set might include the empty bundle, in case the buyer considers all bundles as too expensive).
A price-envy-free matching (given a price-vector) is a matching in which each agent receives a bundle from his demand-set. This means that no agent would prefer to get another bundle with the same prices. 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 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.
In markets without money
The term envy-free matching is often used to denote a weaker condition - no-justified-envy matching.
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.