No-justified-envy matching

Last updated

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.

Contents

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:

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

Related Research Articles

In mathematics, economics, and computer science, the stable marriage problem is the problem of finding a stable matching between two equally sized sets of elements given an ordering of preferences for each element. A matching is a bijection from the elements of one set to the elements of the other set. A matching is not stable if:

An envy-free cake-cutting is a kind of fair cake-cutting. It is a division of a heterogeneous resource ("cake") that satisfies the envy-free criterion, namely, that every partner feels that their allocated share is at least as good as any other share, according to their own subjective valuation.

In mathematics, economics and computer science, particularly in the fields of combinatorics, game theory and algorithms, the stable-roommate problem (SRP) is the problem of finding a stable matching for an even-sized set. A matching is a separation of the set into disjoint pairs ("roommates"). The matching is stable if there are no two elements which are not roommates and which both prefer each other to their roommate under the matching. This is distinct from the stable-marriage problem in that the stable-roommates problem allows matches between any two elements, not just between classes of "men" and "women".

<span class="mw-page-title-main">Alvin E. Roth</span> American academic (born 1951)

Alvin Eliot Roth is an American academic. He is the Craig and Susan McCaw professor of economics at Stanford University and the Gund professor of economics and business administration emeritus at Harvard University. He was President of the American Economic Association in 2017.

The National Resident Matching Program (NRMP), also called The Match, is a United States-based private non-profit non-governmental organization created in 1952 to place U.S. medical school students into residency training programs located in United States teaching hospitals. Its mission has since expanded to include the placement of U.S. citizen and non-U.S. citizen international medical school students and graduates into residency and fellowship training programs. In addition to the annual Main Residency Match that in 2021 encompassed more than 48,000 applicants and 38,000 positions, the NRMP conducts Fellowship Matches for more than 60 subspecialties through its Specialties Matching Service (SMS). The NRMP is sponsored by a board of directors that includes medical school deans, teaching hospital executives, graduate medical education program directors, medical students and residents, and one public member.

In mathematics, economics, and computer science, the Gale–Shapley algorithm is an algorithm for finding a solution to the stable matching problem, named for David Gale and Lloyd Shapley. It takes polynomial time, and the time is linear in the size of the input to the algorithm. It is a truthful mechanism from the point of view of the proposing participants, for whom the solution will always be optimal.

Parag A. Pathak is Professor of Economics at the Massachusetts Institute of Technology and is affiliated with the National Bureau of Economic Research where he co-founded and directs the working group on market design.

Tayfun Sönmez is a Turkish-American professor of economics at Boston College. He is a Fellow of the Econometric Society and the 2008 winner of the Social Choice and Welfare Prize, which honors scholars under the age of 40 for excellent accomplishment in the area of social choice theory and welfare economics. Sönmez has made significant contributions in the areas of microeconomic theory, mechanism/market design, and game theory. His work has been featured by the U.S. National Science Foundation for its practical relevance.

Envy-freeness, also known as no-envy, is a criterion for fair division. It says that, when resources are allocated among people with equal rights, each person should receive a share that is, in their eyes, at least as good as the share received by any other agent. In other words, no person should feel envy.

Rental harmony is a kind of a fair division problem in which indivisible items and a fixed monetary cost have to be divided simultaneously. The housemates problem and room-assignment-rent-division are alternative names to the same problem.

Top trading cycle (TTC) is an algorithm for trading indivisible items without using money. It was developed by David Gale and published by Herbert Scarf and Lloyd Shapley.

Random priority (RP), also called Random serial dictatorship (RSD), is a procedure for fair random assignment - dividing indivisible items fairly among people.

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.

Rank-maximal (RM) allocation is a rule for fair division of indivisible items. Suppose we have to allocate some items among people. Each person can rank the items from best to worst. The RM rule says that we have to give as many people as possible their best (#1) item. Subject to that, we have to give as many people as possible their next-best (#2) item, and so on.

The rural hospitals theorem (RHT) is a fundamental theorem in the theory of stable matching. It considers the problem of matching doctors to hospitals for residency, where each doctor is matched to a single hospital but each hospital has several positions for doctors. The total number of positions is larger than the total number of doctors, so some hospitals inevitably remain with unfilled positions. Usually, rural hospitals are less wanted than urban hospitals, so they often remain with many empty positions. This raised the question of whether the mechanism used to match doctors to hospitals can be changed in order to help these rural hospitals.

Stable marriage with indifference is a variant of the stable marriage problem. Like in the original problem, the goal is to match all men to all women such that no pair of man and woman who are unmarried to each other, would simultaneously like to leave their present partners and pair with each other instead.

In mathematics, economics, and computer science, the lattice of stable matchings is a distributive lattice whose elements are stable matchings. For a given instance of the stable matching problem, this lattice provides an algebraic description of the family of all solutions to the problem. It was originally described in the 1970s by John Horton Conway and Donald Knuth.

In mathematics, economics, and computer science, the stable matching polytope or stable marriage polytope is a convex polytope derived from the solutions to an instance of the stable matching problem.

In computer science and operations research, the envy minimization problem is the problem of allocating discrete items among agents with different valuations over the items, such that the amount of envy is as small as possible.

In economics and computer science, the house allocation problem is the problem of assigning objects to people with different preferences, such that each person receives exactly one object. The name "house allocation" comes from the main motivating application, which is assigning dormitory houses to students. Other commonly used terms are assignment problem and one-sided matching. When agents already own houses, the problem is often called a housing market. In house allocation problems, it is assumed that monetary transfers are not allowed; the variant in which monetary transfers are allowed is known as rental harmony.

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. 1 2 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 page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.