<p>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 <span class="math-container">$h_1 \succeq h_2 \succeq \cdots \succeq \text{UNMATCHED} \succeq h_j \succeq \cdots$</span>.</p>

<p>To accommodate hospitals with multiple slots, you can just create <span class="math-container">$k_h$</span> copies of hospital <span class="math-container">$h$</span>, all sharing the preferences of hospital <span class="math-container">$h$</span> and compared by doctors in the same way (e.g. my preference ordering could go <span class="math-container">$h_1 \sim \cdots \sim h_{k_h} \succeq \cdots$</span> where <span class="math-container">$\sim$</span> means indifference).</p>

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

CC BY-SA 4.0
2019-08-11T03:30:16.260Z
2019-08-11T03:30:16.260Z
usul
<p>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.</p>

<p>Here's one example if you need some help <a href="https://i.sstatic.net/Dsq6j.png" rel="nofollow noreferrer">https://i.sstatic.net/Dsq6j.png</a>. Only look after giving it a good try though!
The agents <span class="math-container">$c_i$</span> represent "colleges" (i.e. hospitals) and <span class="math-container">$c_1$</span> has a capacity of two students <span class="math-container">$s_i$</span> (i.e. residents).</p>

CC BY-SA 4.0
2019-08-12T23:52:17.747Z
2019-08-13T07:22:19.563Z
2019-08-13T07:22:19.563Z
Clay Thomas
<p>Consider a set of doctors <span class="math-container">$D$</span> and hospitals <span class="math-container">$H$</span> such that each doctor <span class="math-container">$d \in D$</span> has a rank ordered strict preference over a subset of hospitals, <span class="math-container">$H_d \subseteq H$</span>. Similarly, each hospital <span class="math-container">$h \in H$</span> has a strict rank ordered preference over a subset of the candidates, <span class="math-container">$D_h \subseteq D$</span>. 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 <span class="math-container">$h \in H$</span> may have multiple identical positions, <span class="math-container">$k_h \geq 1$</span>. That is, the doctors have no preference over the  </p>

<p>Can the Gale-Shapley algorithm be modified to accommodate this extension naturally?  </p>

CC BY-SA 4.0
2019-08-14T20:42:36.370Z
Seems like a nice homework problem.
Neal Young
<ds.algorithms><matching><stable>
Hospital Resident Matching Algorithm with Incomplete Preferences
alcatraz
# Hospital Resident Matching Algorithm with Incomplete Preferences

(Asked by: username_0 on 2019-08-10)

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?

**Tags:** ds.algorithms, matching, stable

> **Comments:**
> **username_1**: Seems like a nice homework problem.  

---

## 2 answers

### Answer by username_2 on 2019-08-11. Score: 1 | Accepted answer

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 by username_3 on 2019-08-12. Score: 1

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.sstatic.net/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).


---

