No-justified-envy matching

In economics and social choice theory, a no-justified-envy matching is a matching in a two-sided market, in which no agent prefers the assignment of another agent and is simultaneously preferred by that assignment.

Consider, for example, the task of matching doctors for residency in hospitals. Each doctor has a preference relation on hospitals, ranking the hospitals from best to worst. 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). The goal is to match doctors to hospitals, without monetary transfers.

Envy is a situation in which some doctor d1, employed in some hospital h1, prefers some other hospital h2, which employs some other doctor d2 (we say that d1 envies d2). The envy is justified if, at the same time, h2 prefers d1 over d2. Note that, if d1 has justified envy w.r.t. h2, then h2 has justified envy w.r.t. d1 (h2 envies h1). In this case, we also say that d1 and h2 are a blocking pair. A matching with no blocking pairs is called a no-justified-envy (NJE) matching, or a matching that eliminates justified envy.[1][2]

No-justified-envy matching is a relaxation of two different conditions:

  • Envy-free matching is a matching in which there is no envy at all, whether justified or not.
  • Stable matching is a matching in which there is no justified envy, and in addition, there is no waste. A matching has waste if there is a doctor d and a hospital h, such that d prefers h over his or her current employer, h has some vacant positions, and h prefers d over a vacant position.

Lattice structure

In a many-to-one matching problem, stable matchings exist and can be found by the Gale–Shapley algorithm. Therefore, NJE matchings exist too. In general there can be many different NJE matchings. The set of all NJE matchings is a lattice. The set of stable matchings (which are a subset of the NJE matchings) is a fixed point of a Tarsky operator on that lattice.[3]

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.[4] 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 NJE 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 NJE matching always exists.[4]

If not all pairs are acceptable, then an NJE 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 NJE matching if-and-only-if, in the stable matching of the new problem, every hospital is full.[5]

The algorithm can be improved to find a maximal NJE matching.[6]

Minimizing the unjustified envy

By definition, in an NJE matching, 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.[7]

See also

References
  1. Abdulkadiroğlu, Atila; Sönmez, Tayfun (2003-06-01). "School Choice: A Mechanism Design Approach". American Economic Review. 93 (3): 729–747. doi:10.1257/000282803322157061. hdl:10161/2090. ISSN 0002-8282.
  2. Abdulkadiroglu, Atila; Che, Yeon-Koo; Pathak, Parag A.; Roth, Alvin E.; Tercieux, Olivier (2017-03-27). "Minimizing Justified Envy in School Choice: The Design of New Orleans' OneApp". doi:10.3386/w23265. S2CID 9497845. {{cite journal}}: Cite journal requires |journal= (help)
  3. 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.
  4. 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.
  5. Yokoi, Yu (17 April 2017). "Envy-free Matchings with Lower Quotas". arXiv:1704.04888 [cs.GT].
  6. "How good are Popular Matchings?" (PDF). www.cse.iitm.ac.in. Archived from the original (PDF) on 17 January 2019. Retrieved 16 January 2019.
  7. 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
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.