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)$ is an unstable pair for this matching.

One might imagine using an incremental algorithm that starts with an arbitrary matching and then greedily performs exchanges to resolve instabilities. Unfortunately, resolving one instability can create new ones; in fact, this incremental “improvement” can lead to an infinite loop. For example, if we start with our earlier unstable matching $\left\{ {Aq, B r, C s}\right\}$, each of the following exchanges resolves one unstable pair (indicated over the arrow), but the sequence of exchanges leads back to the original matching:

$\left\{{Aq,Br,Cs}\right\}\overset{Ar}{\rightarrow} \left\{{Ar,Bq,Cs}\right\}\overset{Cr}{\rightarrow} \left\{{As,Bq,Cr}\right\}\overset{Cq}{\rightarrow} \left\{{As,Br,Cq}\right\}\overset{Aq}{\rightarrow} \left\{{Aq,Br,Cs}\right\}$

Alternatively, we might try the following multi-round greedy protocol. In each round, every unmatched hospital makes an offer to their favorite unmatched doctor, then every unmatched doctor with an offer accepts their favorite offer. It’s not hard to prove that at least one new doctor-hospital pair is matched in each round, so the algorithm always ends with a matching. For the previous example input, we already have a stable matching $\left\{ {Ar,Bs,Cq} \right\}$ at the end of the first round! But consider the following input instead:

$\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} C \hspace{0.34cm} A \hspace{0.248cm} A \hspace{1.05cm} q \hspace{0.49cm} q \hspace{0.51cm} s \\ \hspace{6.4cm} B \hspace{0.34cm} C \hspace{0.248cm} B \hspace{1.05cm} s \hspace{0.49cm} r \hspace{0.51cm} r \\ \hspace{6.4cm} A \hspace{0.34cm} B \hspace{0.248cm} C \hspace{1.05cm} r \hspace{0.49cm} s \hspace{0.51cm} q \\$

In the first round, Dr. Shephard accepts an offer from County, and Dr. Quincy accepts an offer from Bedlam (rejecting Arkham’s offer), leaving only Dr. Rotwang and Arkham unmatched. Thus, the protocol ends with the matching $\left\{ {Ar,Bq,Cs} \right\}$ after two rounds. Unfortunately, this match is unstable; Arkham and Dr. Shephard prefer each other to their matches.

The Boston Pool and Gale-Shapley algorithms

In 1952, the NRMP adopted the “Boston Pool” algorithm to assign interns, so named because it had been previously used by a regional clearing house in the Boston area. Ten years later, David Gale and Lloyd Shapley described and formally analyzed a generalization of the Boston Pool algorithm and proved that it computes a stable matching. Gale and Shapley used the metaphor of college admissions. Essentially the same algorithm was independently developed by Elliott Peranson in 1972 for use in medical school admissions. Similar algorithms have since been adopted for many other matching markets, including faculty hiring in France, hiring of new economics PhDs in the United States, university admission in Germany, public school admission in New York and Boston, billet assignments for US Navy sailors, and kidney-matching programs.

Shapley was awarded the 2012 Nobel Prize in Economics for his research on stable matchings, together with Alvin Roth, who significantly extended Shapley’s work and used it to develop several real-world exchanges. (Gale did not share the prize because he died in 2008.)

Like our last failed greedy algorithm, the Gale-Shapley algorithm proceeds in rounds until every position has been accepted. Each round has two stages:

1. An arbitrarily unmatched hospital $A$ offers its position to the best doctor $α$ (according to $A$’s preference list) who has not already rejected it.

2. If $α$ is unmatched, she (tentatively) accepts $A$’s offer. If $α$ already has a match but prefers $A$, she rejects her current match and (tentatively) accepts the new offer from $A$. Otherwise, $α$ rejects the new offer.

All the doctors ultimately accepts the best offer that they receive, according to their preference list. In short, hospitals make offers greedily, and doctors accept offers greedily. The doctors’ ability to reject their current matches in favor of better offers is the key to making this mutually greedy strategy work.

For example, suppose that there are four doctors (Dr. Quincy, Dr. Rotwang, Dr. Shephard, and Dr. Tam) and four hospitals (Arkham Asylum, Bethlem Royal Hospital, County General Hospital, and The Dharma Initiative) who rank each other as follows:

$\hspace{6.5cm} \underline{q \hspace{0.4cm} r \hspace{0.4cm} s \hspace{0.4cm} t } \hspace{1cm} \underline{A \hspace{0.4cm} B \hspace{0.4cm} C \hspace{0.4cm} D } \\ \hspace{6.4cm} A \hspace{0.32cm} A \hspace{0.31cm} B \hspace{0.248cm} D \hspace{1cm} t \hspace{0.55cm} r \hspace{0.51cm} t \hspace{0.51cm} s \\ \hspace{6.4cm} B \hspace{0.32cm} D \hspace{0.31cm} A \hspace{0.248cm} B \hspace{1cm} s \hspace{0.55cm} t \hspace{0.51cm} r \hspace{0.51cm} r \\ \hspace{6.4cm} C \hspace{0.32cm} C \hspace{0.31cm} C \hspace{0.248cm} C \hspace{1cm} r \hspace{0.55cm} q \hspace{0.51cm} s \hspace{0.51cm} q \\ \hspace{6.38cm} D \hspace{0.32cm} B \hspace{0.31cm} D \hspace{0.248cm} A \hspace{1cm} q \hspace{0.55cm} s \hspace{0.51cm} q \hspace{0.51cm} t \\$

Given these preference lists as input, the Gale-Shapley algorithm might proceed as follows:

1. Arkham makes an offer to Dr. Tam.

2. Bedlam makes an offer to Dr. Rotwang.

3. County makes an offer to Dr. Tam, who rejects her earlier offer from Arkham.

4. Dharma makes an offer to Dr. Shephard. (From this point on, there is only one unmatched hospital, so the algorithm has no more choices.)

5. Arkham makes an offer to Dr. Shephard, who rejects his earlier offer from Dharma.

6. Dharma makes an offer to Dr. Rotwang, who rejects her earlier offer from Bedlam.

7. Bedlam makes an offer to Dr. Tam, who rejects her earlier offer from County.

8. County makes an offer to Dr. Rotwang, who rejects it.

9. County makes an offer to Dr. Shephard, who rejects it.

10. County makes an offer to Dr. Quincy.

After the tenth round, all pending offers are accepted, and the algorithm returns the matching $\left\{ {As, Bt, Cq, Dr}\right\}$. We can (and should) verify by brute force that this matching is stable, even though no doctor was hired by their favorite hospital, and no hospital hired their favorite doctor; in fact, County ended up hiring their least favorite doctor. This is not the only stable matching for these preference lists; the matching $\left\{ {Ar, Bs, Cq, Dt}\right\}$ is also stable.