page_title: Rural hospitals theorem
section_title: Proof of a special case
hierarchical_section_title: Rural hospitals theorem / Proof of a special case
caption_attribution_description: English: Illustration of proof of rural hospitals theorem
context_page_description: The rural hospitals theorem 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.
  The rural hospitals theorem answers this question negatively assuming all preferences are strict. 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 will not help the rural hospitals in any way: they will not receive more doctors, nor better doctors.
context_section_description: 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₀ whose hospitals in A and B are different. Since we assume strict preferences, d₀ 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₁. All this is summarized by the green arrow from d₀ to h₁.
  Now, since matching A is stable, h₁ necessarily prefers its doctor in A over d₀ (otherwise d₀ and h₁ would de-stabilize matching A); denote this doctor by d₂, and denote the preference of h₁ by a red arrow from h₁ to d₂.
  Similarly, since matching B is stable, d₂ prefers its hospital in B over h₁; denote this hospital by h₃, and denote the prefererence by a green arrow from d₂ to h₃.
  Since the number of doctors and hospitals is finite, at some point the red arrow from a hospital must land at d₀, 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₀ is unmatched in A. Now, the cycle cannot close since no hospital can be matched to d₀ in A. It is also impossible that some hospital h₃ 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₀ 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.
caption: An infinite cycle
exif: {}