Stable Matching

Every year, thousands of new doctors must obtain internships at hospitals around the United States. During the first half of the 20th century, competition among hospitals for the best doctors led to earlier and earlier offers of internships, sometimes as early as the second year of medical school, along with tighter deadlines for acceptance. In the 1940s, medical schools agreed not to release information until a common date during their students’ fourth year. In response, hospitals began demanding faster decisions. By 1950, hospitals would regularly call doctors, offer them internships, and demand immediate responses. Interns were forced to gamble if their third-choice hospital called first—accept and risk losing a better opportunity later, or reject and risk having no position at all.

Finally, a central clearing house for internship assignments, now called the National Resident Matching Program (NRMP), was established in the early 1950s. Each year, doctors submit a ranked list of all hospitals where they would accept an internship, and each hospital submits a ranked list of doctors they would accept as interns. The NRMP then computes a matching between doctors and hospitals that satisfies the following stability requirement. A matching is unstable if there is a doctor α and hospital B that would be both happier with each other than with their current match; that is,

• $α$ is matched with some other hospital $A$, even though she prefers $B$.
• B is matched with some other doctor $β$, even though they prefer $α$.

In this case, we call $(α, B)$ an unstable pair for the matching. The goal of the Resident Match is a stable matching, which matches with no unstable pairs.

For simplicity, let’s assume from now on that there is exactly the same number of doctors and hospitals; each hospital offers exactly one internship; each doctor ranks all hospitals and vice versa; and finally, there are no ties in the doctors’ or hospitals’ rankings.

Some bad ideas

At first glance, it is not even clear that stable matching always exists! Certainly, not every matching of doctors and hospitals is stable. Suppose there are three doctors (Dr. Quincy, Dr. Rotwang, Dr. Shephard, represented by lower-case letters) and three hospitals (Arkham Asylum, Bethlem Royal Hospital, and County General Hospital, represented by upper-case letters) who rank each other as follows:

$\hspace{6.5cm} \underline{q \hspace{0.4cm} r \hspace{0.4cm} s } \hspace{1cm} \underline{A \hspace{0.4cm} B \hspace{0.4cm} C } \\ \hspace{6.4cm} A \hspace{0.34cm} C \hspace{0.248cm} A \hspace{1.05cm} r \hspace{0.49cm} s \hspace{0.51cm} q \\ \hspace{6.4cm} C \hspace{0.34cm} A \hspace{0.248cm} B \hspace{1.05cm} q \hspace{0.49cm} q \hspace{0.51cm} r \\ \hspace{6.39cm} B \hspace{0.34cm} B \hspace{0.248cm} C \hspace{1.05cm} s \hspace{0.49cm} r \hspace{0.51cm} s \\$

The matching ${Aq,Br,Cs}$ is unstable because Arkham would rather hire Dr. Rotwang than Dr. Quincy, and Dr. Rotwang would rather work at Arkham than at Bedlam. $(A, r)$ ...