In centralized labour markets such as the US National Resident Matching Program, doctors are assigned to hospital residency positions by a mechanism that produces a stable matching. There are more positions than doctors, so some hospitals end up with empty positions; these are typically rural hospitals, which are less sought after than urban ones. This raised the question of whether a different mechanism could help these hospitals (Roth 1986). The rural hospitals theorem answers this negatively, provided all preferences are strict.
Timeline.
A market has a finite set of doctors and a finite set of hospitals; hospital has positions. Every doctor strictly ranks the hospitals together with the option of staying unmatched, and every hospital strictly ranks the doctors together with the option of leaving a position empty. An assignment sends each doctor to a hospital or to nothing; is the set of doctors at . It is a matching if for every .
A matching is stable if (i) no doctor is placed at a hospital she ranks below staying unmatched, and no hospital holds a doctor it ranks below an empty position, and (ii) there is no blocking pair : a doctor who prefers to her assignment, while finds acceptable and either has an empty position or prefers to one of its current doctors.
For any two stable matchings :
The result itself. Changing the matching mechanism, as long as it outputs stable matchings, cannot give under-subscribed hospitals more doctors or different doctors, and cannot change which doctors are employed. Hence policy aimed at rural hospitals must change preferences, capacities, or abandon stability, not merely switch between stable mechanisms.
Formalizing it. The theorem is classical and proved in the cited papers; this mission asks for a machine-checked proof in Lean 4 with Mathlib, for the general many-to-one model with capacities and acceptability, together with the one-position special case.
Comparing two stable matchings one agent at a time does not work: a single doctor moving between hospitals says nothing about how many positions each hospital fills, and the statements concern every agent of the market simultaneously. Stability of both matchings has to be used at once, and Part 2 is strictly stronger than Part 1 (equal numbers of doctors at an under-filled hospital do not imply equal sets of doctors). The existence of a stable matching is not needed for these statements.
Doctors and hospitals are finite types D, H. Preferences are injective rank functions on Option H (for a doctor) and Option D (for a hospital), smaller rank meaning more preferred and none meaning unmatched or an empty position; injectivity encodes strictness. Hospital preferences over groups are responsive. Capacities are natural numbers and may be zero. An assignment is μ : D → Option H. Stability is Market.IsStable: capacity constraints, individual rationality, and no blocking pair. All statements quantify over arbitrary stable matchings, so they are not vacuous: stable matchings exist in every such market (Gale–Shapley), though existence is not part of this mission.
Contributions welcome: proofs of the milestones, an existence theorem for stable matchings in this model, and lemmas about stable matchings reusable in other matching missions.
namespace RuralHospitals
theorem rural_hospitals_theorem {D H : Type*} [Fintype D] [Fintype H] [DecidableEq H]
(M : Market D H) (μ ν : Assignment D H) (hμ : M.IsStable μ) (hν : M.IsStable ν) :
(∀ d, (μ d).isSome = (ν d).isSome) ∧
(∀ h, (assigned μ h).card = (assigned ν h).card) ∧
∀ h, (assigned μ h).card < M.capacity h → assigned ν h = assigned μ h := by sorry
end RuralHospitals
Consider a many-to-one matching market with a finite set of doctors and a finite set of hospitals, where hospital has positions and all preferences are strict. For a matching , write for the set of doctors assigned to . Let and be any two stable matchings. Then
This is the rural hospitals theorem (Roth 1984, 1986): as long as the mechanism produces stable matchings, changing it cannot give under-subscribed ("rural") hospitals more doctors or different doctors.
Formalization Note Uses the model RuralHospitals.Market (definition RuralHospitals_Market): finite types D (doctors) and H (hospitals); strict preferences given by injective rank functions on Option H / Option D (smaller rank = preferred, none = unmatched / empty position); responsive hospital preferences; capacities capacity : H → ℕ. An assignment is a map μ : D → Option H, and assigned μ h is the finite set of doctors placed at h.
No open leaves. Every sub-goal is proved or awaiting decomposition.