# Hospital Resident Matching Algorithm with Incomplete Preferences

Consider a set of doctors $$D$$ and hospitals $$H$$ such that each doctor $$d \in D$$ has a rank ordered strict preference over a subset of hospitals, $$H_d \subseteq H$$. Similarly, each hospital $$h \in H$$ has a strict rank ordered preference over a subset of the candidates, $$D_h \subseteq D$$. That is, the doctors and residents want to remain unmatched rather than be matched to someone who is not in their preference list. Further, each hospital $$h \in H$$ may have multiple identical positions, $$k_h \geq 1$$. That is, the doctors have no preference over the

Can the Gale-Shapley algorithm be modified to accommodate this extension naturally?

• Seems like a nice homework problem. – Neal Young Aug 14 at 20:42

Yes, in straightforward ways. To accommodate partial lists, the doctors stop proposing after they've been rejected from every hospital in their order, and remain unmatched. The hospitals automatically reject any proposing doctor who's not in their list, even if it means remaining unmatched. You can picture these as preference lists $$h_1 \succeq h_2 \succeq \cdots \succeq \text{UNMATCHED} \succeq h_j \succeq \cdots$$.
To accommodate hospitals with multiple slots, you can just create $$k_h$$ copies of hospital $$h$$, all sharing the preferences of hospital $$h$$ and compared by doctors in the same way (e.g. my preference ordering could go $$h_1 \sim \cdots \sim h_{k_h} \succeq \cdots$$ where $$\sim$$ means indifference).
Here's one example if you need some help https://i.stack.imgur.com/Dsq6j.png. Only look after giving it a good try though! The agents $$c_i$$ represent "colleges" (i.e. hospitals) and $$c_1$$ has a capacity of two students $$s_i$$ (i.e. residents).