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
[edit]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.[1] 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/she 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)| ≥ |X| ≥ 1 (where NG(X) is the set of neighbors of X in Y), then G admits a nonempty EFM.[1] 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.
In markets with money
[edit]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.[2] 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
[edit]The term envy-free matching is often used to denote a weaker condition - no-justified-envy matching.
In cake-cutting
[edit]The term envy-free matching has also been used in a different context: an algorithm for improving the efficiency of envy-free cake-cutting.[3]
See also
[edit]References
[edit]- ^ a b Segal-Halevi, Erel; Aigner-Horev, Elad (2022). "Envy-free matchings in bipartite graphs and their applications to fair division". Information Sciences. 587: 164–187. arXiv:1901.09527. doi:10.1016/j.ins.2021.11.059. S2CID 170079201.
- ^ Alaei, Saeed; Jain, Kamal; Malekian, Azarakhsh (24 June 2010). "Competitive Equilibria in Two Sided Matching Markets with Non-transferable Utilities". arXiv:1006.4696 [cs.GT].
- ^ Sen, Sandip; Nuchia, Stephen W. (1 August 2001). "Improving Optimality of n Agent Envy-Free Divisions". Intelligent Agents VIII. Lecture Notes in Computer Science. Vol. 2333. Springer, Berlin, Heidelberg. pp. 277–289. doi:10.1007/3-540-45448-9_20. ISBN 978-3-540-43858-8.