Erel Segal: /* top */
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 raises 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. <ref>Liquid error: wrong number of arguments (1 for 2)</ref>
# Any hospital that has some empty positions in some stable matching, receives exactly the same set of doctors in ''all'' stable matchings. <ref>Liquid error: wrong number of arguments (1 for 2)</ref>
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 was proved by [[Alvin E. Roth]]. See <ref>Liquid error: wrong number of arguments (1 for 2)</ref> for detailed proofs.
The theorem can be extended to many-to-many matching.<ref>Liquid error: wrong number of arguments (1 for 2)</ref>
== See also ==
* [[Envy-free matching]]
== References ==
[[Category: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 raises 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. <ref>Liquid error: wrong number of arguments (1 for 2)</ref>
# Any hospital that has some empty positions in some stable matching, receives exactly the same set of doctors in ''all'' stable matchings. <ref>Liquid error: wrong number of arguments (1 for 2)</ref>
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 was proved by [[Alvin E. Roth]]. See <ref>Liquid error: wrong number of arguments (1 for 2)</ref> for detailed proofs.
The theorem can be extended to many-to-many matching.<ref>Liquid error: wrong number of arguments (1 for 2)</ref>
== See also ==
* [[Envy-free matching]]
== References ==
[[Category:Matching]]
from Wikipedia - New pages [en] http://bit.ly/2RL3xRJ
via IFTTT
No comments:
Post a Comment