How to I prove that the algorithm for the Rural Hospital Problem is valid ( i.e. its finite and leads to a stable assignment of physicians to rural hospitals ) ?.
Here is how the algorithm works:
- There is a set of doctors and hospitals.
- Each doctor has a preference list for which hospitals they would want to work at and each hospital has a preference list for doctors and a maximum capacity of doctors.
- Doctors go to their first choice, if a hospital exceeds its capacity ( say the capacity is $\mbox{$k$ )}$, it will reject all but its top $k$ doctors ( according to its ranking ).
- Rejected doctors apply to their next choice, and the process continues as usual.
- Let's assume that the sum of the hospital capacities is at least the size of the set of physicians, but we do not need to assume that each hospital has the same capacity.
Any help will be appreciated.
Note that there are $K$ doctors and $H$ hospitals, but a doctor can only propose to each hospital once, so the algorithm ends in at most $K*H$ rounds.
When the algorithm terminates, note that each doctor $d$ that proposed to a hospital $h$ was either conditionally accepted at $h$, or was eventually released due to capacity constraints. If a doctor was released from hospital $h$, it means that in some round $r$, $d$ was less preferred by $h$ than some doctor $d'$. But the hospitals retain their most preferred slate of applicants at each moment in time, so whoever hospital $h$ ended up with, $h$ prefers all of those people to $d$. Therefore the matching exists and is stable, since anyone a doctor already proposed to any hospital he prefers to his final partner, and each hospital retains only the top $k$ candidates who ever proposed, so there are no blocking pairs who prefer one another to the results of the Gale-Shapley algorithm or whatever you've decided to call it.