Rural hospitals theorem

Last updated

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

Contents

The rural hospitals theorem answers this question negatively assuming all preferences are strict (i.e., no doctor is indifferent between two hospitals and no hospital is indifferent between two doctors). The theorem has two parts:

  1. The set of assigned doctors, and the number of filled positions in each hospital, are the same in all stable matchings.
  2. Any hospital that has some empty positions in some stable matching, receives exactly the same set of doctors in all stable matchings.

In other words: changing the matching mechanism (as long as it produces stable matchings) will not help the rural hospitals in any way: they will not receive more doctors, nor better doctors.

The theorem is robust in two-sided matching, since it applies to one-to-one and many-to one matchings, and can be extended to many-to-many matching. [2]

History

A special case of the theorem where each hospital has only one position ("stable marriage") was proven by computer scientists McVitie and Wilson in 1970. [3]

In the 1980s economist Alvin E. Roth proved the two parts of the full theorem in two respective papers. [4] [1]

Proof of a special case

A cycle of length 4 in the stable matchings graph Different stable matchings.png
A cycle of length 4 in the stable matchings graph

We will prove the theorem for the special case in which each hospital has only one position. In this case, Part 1 says that all stable matchings have the same set of matched hospitals and the same set of matched doctors, and Part 2 is trivial.

It is useful to first visualize what different stable matchings look like (refer to the graphs on the right). Consider two different stable matchings, A and B. Consider a doctor d0 whose hospitals in A and B are different. Since we assume strict preferences, d0 prefers either his hospital in A or his hospital in B; suppose w.l.o.g. that he prefers his hospital in B, and denote this hospital by h1. All this is summarized by the green arrow from d0 to h1.

A cycle of length 6 Different stable matchings 3.png
A cycle of length 6

Now, since matching A is stable, h1 necessarily prefers its doctor in A over d0 (otherwise d0 and h1 would de-stabilize matching A); denote this doctor by d2, and denote the preference of h1 by a red arrow from h1 to d2.

Similarly, since matching B is stable, d2 prefers its hospital in B over h1; denote this hospital by h3, and denote the prefererence by a green arrow from d2 to h3.

Since the number of doctors and hospitals is finite, at some point the red arrow from a hospital must land at d0, closing a directed cycle in the graph. The graph at the top-right shows a cycle of length 4; the graph at the bottom-right shows a cycle of length 6. In these cycles, all doctors point to hospitals they prefer and are matched to in B, and all hospitals point to doctors they prefer and are matched to in A.

An infinite cycle Matching-3x3-unmatched.png
An infinite cycle

Now, consider what happens when the doctor d0 is unmatched in A. Now, the cycle cannot close since no hospital can be matched to d0 in A. It is also impossible that some hospital h3 in this cycle is unmatched in A, since if the hospital preferred to be unmatched than to be matched to its doctor in B, then B could not have been stable. This means that we have an infinite cycle, which cannot be. Hence, if d0 is unmatched in A, he must be unmatched in B too.

The same is true for the hospitals: any hospital that is unmatched in A, must be unmatched in B too.

See also

Related Research Articles

In graph theory, a perfect matching in a graph is a matching that covers every vertex of the graph. More formally, given a graph G =, a perfect matching in G is a subset M of E, such that every vertex in V is adjacent to exactly one edge in M.

In social choice theory, Arrow's impossibility theorem, the general possibility theorem or Arrow's paradox is an impossibility theorem stating that when voters have three or more distinct alternatives (options), no ranked voting electoral system can convert the ranked preferences of individuals into a community-wide ranking while also meeting a specified set of criteria: unrestricted domain, non-dictatorship, Pareto efficiency, and independence of irrelevant alternatives. The theorem is often cited in discussions of voting theory as it is further interpreted by the Gibbard–Satterthwaite theorem. The theorem is named after economist and Nobel laureate Kenneth Arrow, who demonstrated the theorem in his doctoral thesis and popularized it in his 1951 book Social Choice and Individual Values. The original paper was titled "A Difficulty in the Concept of Social Welfare".

In mathematics, Hall's marriage theorem, proved by Philip Hall (1935), is a theorem with two equivalent formulations:

This is a glossary of graph theory. Graph theory is the study of graphs, systems of nodes or vertices connected in pairs by lines or edges.

In the mathematical discipline of graph theory, a matching or independent edge set in an undirected graph is a set of edges without common vertices. Finding a matching in a bipartite graph can be treated as a network flow problem.

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:

In the mathematical discipline of graph theory the Tutte theorem, named after William Thomas Tutte, is a characterization of graphs with perfect matchings. It is a generalization of Hall's marriage theorem from bipartite to arbitrary graphs. It is a special case of the Tutte–Berge formula.

Kőnigs theorem (graph theory) Theorem showing that maximum matching and minimum vertex cover are equivalent for bipartite graphs

In the mathematical area of graph theory, Kőnig's theorem, proved by Dénes Kőnig (1931), describes an equivalence between the maximum matching problem and the minimum vertex cover problem in bipartite graphs. It was discovered independently, also in 1931, by Jenő Egerváry in the more general case of weighted graphs.

Tutte–Berge formula Characterization of the size of a maximum matching in a graph

In the mathematical discipline of graph theory the Tutte–Berge formula is a characterization of the size of a maximum matching in a graph. It is a generalization of Tutte theorem on perfect matchings, and is named after W. T. Tutte and Claude Berge.

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".

Alvin E. Roth 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 Economics Association in 2017.

Market design

Market design is a practical methodology for creation of markets of certain properties, which is partially based on mechanism design. In some markets, prices may be used to induce the desired outcomes — these markets are the study of auction theory. In other markets, prices may not be used — these markets are the study of matching theory.

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 graph theory, Berge's theorem states that a matching M in a graph G is maximum if and only if there is no augmenting path with M.

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 who had described it as solving both the college admission problem and the stable marriage problem. 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.

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.

In graph theory, a Hall violator is a set of vertices in a graph, that violate the condition to Hall's marriage theorem.

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

References

  1. 1 2 Roth, Alvin E. (1986-03-01). "On the Allocation of Residents to Rural Hospitals: A General Property of Two-Sided Matching Markets". Econometrica. 54 (2): 425–427. doi:10.2307/1913160. ISSN   0012-9682. JSTOR   1913160.
  2. ↑ Klijn, Flip; Yazıcı, Ayşe (2014-10-01). "A many-to-many 'rural hospital theorem'" (PDF). Journal of Mathematical Economics. 54: 63–73. doi:10.1016/j.jmateco.2014.09.003. ISSN   0304-4068.
  3. ↑ McVitie, D. G.; Wilson, L. B. (1970-09-01). "Stable marriage assignment for unequal sets". BIT Numerical Mathematics. 10 (3): 295–309. doi:10.1007/BF01934199. ISSN   1572-9125. S2CID   122319782.
  4. ↑ Roth, Alvin (1984). "The evolution of the labor market for medical interns and residents: a case study in game theory". Journal of Political Economy. 92 (6): 991–1016. doi:10.1086/261272.
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.