Rural Hospitals Theorem on:
[Wikipedia]
[Google]
[Amazon]
The rural hospitals theorem (RHT) is a fundamental theorem in the theory of
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 ''d''0 whose hospitals in A and B are different. Since we assume strict preferences, ''d''0 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 ''h''1. All this is summarized by the green arrow from ''d''0 to ''h''1.
Now, since matching A is stable, ''h''1 necessarily prefers its doctor in A over ''d''0 (otherwise ''d''0 and ''h''1 would de-stabilize matching A); denote this doctor by ''d2'', and denote the preference of ''h''1 by a red arrow from ''h''1 to ''d2''.
Similarly, since matching B is stable, ''d2'' prefers its hospital in B over ''h''1; denote this hospital by ''h''3, and denote the prefererence by a green arrow from ''d2'' to ''h''3.
Since the number of doctors and hospitals is finite, at some point the red arrow from a hospital must land at ''d''0, 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.
Now, consider what happens when the doctor ''d''0 is unmatched in A. Now, the cycle cannot close since no hospital can be matched to ''d''0 in A. It is also impossible that some hospital ''h''3 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 ''d''0 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.
stable matching
In mathematics, economics, and computer science, the stable matching 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 ...
.
It considers the problem of matching doctors
Doctor, Doctors, The Doctor or The Doctors may refer to:
Titles and occupations
* Physician, a medical practitioner
* Doctor (title), an academic title for the holder of a doctoral-level degree
** Doctorate
** List of doctoral degrees awarded b ...
to hospitals
A hospital is a healthcare institution providing patient treatment with specialized health science and auxiliary healthcare staff and medical equipment. The best-known type of hospital is the general hospital, which typically has an emergency ...
for residency
Residency may refer to:
* Artist-in-residence, a program to sponsor the residence and work of visual artists, writers, musicians, etc.
* Concert residency, a series of concerts performed at one venue
* Domicile (law), the act of establishing or m ...
, 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.
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:
# The set of assigned doctors, and the number of filled positions in each hospital, are the same in all stable matchings.
# 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.
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. In the 1980s economistAlvin E. Roth
Alvin Eliot Roth (born December 18, 1951) is an American academic. He is the Craig and Susan McCaw professor of economics at Stanford University and the George Gund (philanthropist), Gund professor of economics and business administration emeri ...
proved the two parts of the full theorem in two respective papers.
Proof of a special case
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 ''d''0 whose hospitals in A and B are different. Since we assume strict preferences, ''d''0 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 ''h''1. All this is summarized by the green arrow from ''d''0 to ''h''1.
Now, since matching A is stable, ''h''1 necessarily prefers its doctor in A over ''d''0 (otherwise ''d''0 and ''h''1 would de-stabilize matching A); denote this doctor by ''d2'', and denote the preference of ''h''1 by a red arrow from ''h''1 to ''d2''.
Similarly, since matching B is stable, ''d2'' prefers its hospital in B over ''h''1; denote this hospital by ''h''3, and denote the prefererence by a green arrow from ''d2'' to ''h''3.
Since the number of doctors and hospitals is finite, at some point the red arrow from a hospital must land at ''d''0, 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.
Now, consider what happens when the doctor ''d''0 is unmatched in A. Now, the cycle cannot close since no hospital can be matched to ''d''0 in A. It is also impossible that some hospital ''h''3 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 ''d''0 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
*National Resident Matching Program
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 education in the United States, medical school students into res ...
*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 ...
References
{{Reflist Stable matching Hospitals