Rural hospitals theorem

The theorem has two parts: 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.

[2] 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] We will prove the theorem for the special case in which each hospital has only one position.

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.