Posted on 13th March 2019

---

---

What is HR?

In an instance of the Hospitals/Residents problem HR we have a set of hospitals H and a set of residents R. Each resident ranks a subset of hospitals in strict preference order and vice versa. Each resident may be assigned to a maximum of 1 hospital, whereas each hospital h_j in H may be assigned multiple residents up to some predetermined capacity c_j.

A matching M in this context is an assignment of residents to hospitals such that no resident is assigned more than 1 hospital and no hospital exceeds their capacity. Let M(r_i) denote the hospital that r_i is assigned to in M (if any), and letM(h_j) denote the set of residents h_j is assigned to in M. A blocking pair is a resident-hospital pair (r_i,h_j) such that r_i is either unassigned or would rather be assigned to h_j than M(r_i), and, h_j is either undersubscribed, or would prefer to be assigned r_i than their worst assigned resident in M(h_j). A matching M is stable if M contains no blocking pairs.

Extensions

• The Hospitals/Residents problem with Ties (HRT): An instance I of HRT extends HR by allowing preferences of residents or hospitals (or both) to contain ties, that is, a resident may be indifferent between one or more hospitals on their preference list (and vice versa). In this setting there are three possible definitions of blocking pair which in turn give rise to different stability definitions:
  • Weak stability: A blocking pair (r_i,h_j) has the same definition as in the HR setting.
  • Strong stability: Either:
    • A pair (r_i,h_j) is a blocking pair of M if (1) r_i is either unassigned in M or prefers h_j to M(r_i), and, (2) h_j is undersubscribed or prefers r_i to their worst assigned resident in M(h_j) or is indifferent between them.
    • A pair (r_i,h_j) is a blocking pair of M if (1) r_i is either unassigned in M or prefers h_j to M(r_i) or is indifferent between them, and, (2) h_j is undersubscribed or prefers r_i to their worst assigned resident in M(h_j).
  • Super stability: A pair (r_i,h_j) is a blocking pair of M if (1) r_i is either unassigned in M or prefers h_j to M(r_i) or is indifferent between them, and, (2) h_j is undersubscribed or prefers r_i to their worst assigned resident in M(h_j) or is indifferent between them.
• The Hospitals/Residents problem with Couples (HRC): An instance I of HRC extends HR by allowing residents to apply to hospitals in couples. Each couple has a joint preference list in which they rank pairs of hospitals in preference order.

---