Posted on 13th March 2019

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.

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

- A pair (r
*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.