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 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 (this set might include the empty bundle, in case the buyer considers all bundles as too expensive).

An 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 like to get the bundle of another agent with the same prices.[1] 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.[2][3][4][5][6][7]

In markets without money

Consider the problem of matching doctors for residency in hospitals. Each doctor has a preference relation on hospitals (ranking the hospitals from best to worst), and 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). We want to match doctors to hospitals. Monetary transfers are not allowed. There are two ways in which such a matching can be "bad":

  1. 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.
  2. 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.

Lattice structure

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 (which are a subset of the EF matchings) is a fixed point of a Tarsky operator on that lattice.[8]

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.[9] In such problems, stable matchings may not exist (though it is easy to check whether a stable matching exists, since by the rural hospitals theorem, in all stable matchings, the number of doctors assigned to each hospital is identical). 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 (otherwise, no feasible matching exist at all). In this case, if all doctor-hospital pairs are acceptable (every doctor prefers any hospital to unemployment, and any hospital prefers any doctor to a vacant position), then an EF matching always exists.[9]

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.[10]

The algorithm can be improved to find a maximal EF matching.[11]

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.[12]

In 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.[13] 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)| ≥ |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.

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.[14]

See also

References
  1. 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].
  2. Guruswami, Venkatesan; Hartline, Jason D.; Karlin, Anna R.; Kempe, David; Kenyon, Claire; McSherry, Frank (2005). On Profit-maximizing Envy-free Pricing. Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms. SODA '05. Philadelphia, PA, USA: Society for Industrial and Applied Mathematics. pp. 1164–1173. ISBN 9780898715859.
  3. Briest, Patrick (2008). "Uniform Budgets and the Envy-Free Pricing Problem". In Aceto, Luca; Damgård, Ivan; Goldberg, Leslie Ann; Halldórsson, Magnús M.; Ingólfsdóttir, Anna; Walukiewicz, Igor (eds.). Automata, Languages and Programming. Lecture Notes in Computer Science. 5125. Springer Berlin Heidelberg. pp. 808–819. CiteSeerX 10.1.1.205.433. doi:10.1007/978-3-540-70575-8_66. ISBN 9783540705758. Missing or empty |title= (help)
  4. Chen, Ning; Ghosh, Arpita; Vassilvitskii, Sergei (2011). "SIAM (Society for Industrial and Applied Mathematics)". SIAM Journal on Computing. 40 (3): 623–645. CiteSeerX 10.1.1.193.6235. doi:10.1137/080740970.
  5. Wang, Yajun; Lu, Pinyan; Im, Sungjin (13 December 2010). Envy-Free Pricing with General Supply Constraints. Internet and Network Economics. Lecture Notes in Computer Science. 6484. Springer, Berlin, Heidelberg. pp. 483–491. doi:10.1007/978-3-642-17572-5_41. ISBN 978-3-642-17571-8.
  6. Feldman, Michal; Fiat, Amos; Leonardi, Stefano; Sankowski, Piotr (2012). Revenue Maximizing Envy-free Multi-unit Auctions with Budgets. Proceedings of the 13th ACM Conference on Electronic Commerce. EC '12. New York, NY, USA: ACM. pp. 532–549. doi:10.1145/2229012.2229052. ISBN 9781450314152. S2CID 15639601.
  7. Chen, Ning; Deng, Xiaotie (1 February 2014). "Envy-free Pricing in Multi-item Markets". ACM Transactions on Algorithms. 10 (2): 7:1–7:15. CiteSeerX 10.1.1.297.784. doi:10.1145/2567923. ISSN 1549-6325. S2CID 15309106.
  8. Wu, Qingyun; Roth, Alvin E. (1 May 2018). "The lattice of envy-free matchings". Games and Economic Behavior. 109: 201–211. doi:10.1016/j.geb.2017.12.016. ISSN 0899-8256.
  9. Fragiadakis, Daniel; Iwasaki, Atsushi; Troyan, Peter; Ueda, Suguru; Yokoo, Makoto (1 January 2016). "Strategyproof Matching with Minimum Quotas". ACM Transactions on Economics and Computation. 4 (1): 6:1–6:40. doi:10.1145/2841226. ISSN 2167-8375. S2CID 1287011.
  10. Yokoi, Yu (17 April 2017). "Envy-free Matchings with Lower Quotas". arXiv:1704.04888 [cs.GT].
  11. "How good are Popular Matchings?" (PDF). www.cse.iitm.ac.in. Archived from the original (PDF) on 17 January 2019. Retrieved 16 January 2019.
  12. Tadenuma, Koichi (2011), "Partnership, Solidarity, and Minimal Envy in Matching Problems", in Fleurbaey, Marc; Salles, Maurice; Weymark, John A. (eds.), Social Ethics and Normative Economics, Studies in Choice and Welfare, Springer Berlin Heidelberg, pp. 155–167, doi:10.1007/978-3-642-17807-8_6, ISBN 9783642178078
  13. Segal-Halevi, Erel; Aigner-Horev, Elad (28 January 2019). "Envy-free Matchings in Bipartite Graphs and their Applications to Fair Division". arXiv:1901.09527 [cs.DS].
  14. Sen, Sandip; Nuchia, Stephen W. (1 August 2001). Improving Optimality of n Agent Envy-Free Divisions. Intelligent Agents VIII. Lecture Notes in Computer Science. 2333. Springer, Berlin, Heidelberg. pp. 277–289. doi:10.1007/3-540-45448-9_20. ISBN 978-3-540-43858-8.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.