Hospital Resident Matching Algorithm with Incomplete Preferences

Question

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?

Answer 1

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).

You should be able to find details pretty easily by searching. (By the way, the USA National Residency Matching Program uses a version of deferred acceptance that works with all these constraints, and more besides.)

Answer 2

It's worth noting that some of the great properties that the stable marriage problem has fail in the hospitals and resident model (many-to-one matching). For example, hospital-proposing differed acceptance is not strategyproof for the hospitals. It's a really useful exercise to come up with an input where this happens. Intuitively, it can occur when a hospital ends up causing a chain of proposals which leads to one of their favorite candidates (which they were previously matched to) getting a proposal from a better hospital.

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).