Students who go to medical school complete their training to become physicians with clinical work called residencies in hospitals. Hospitals need residents for carrying out their medical missions, and students need hospital assignments to finish their clinical training to become physicians. Rather than develop the theory in detail, we will describe what Shapley and Gale discovered, and what Roth did to embellish what they had done, for the greater effectiveness of this system. The example will of necessity be small whereas the practical version is quite a bit more complex, but all of the essential ideas will be described.

Imagine there are five hospitals that need residents and five residents who need hospital residency assignments. We will assume that the students can rank the hospitals from their first choice to their least favorite (fifth choice) and that hospitals can rank the residents from 1 to 5 (1 being high and 5 being low) without ties. Hospitals might be indifferent among residents, and students might be indifferent among some hospital choices. While this more general possibility is allowed in the actual system Roth helped develop, here we make a simpler assumption. It might also be that some students would rather not have a residency at all than go to a particular hospital, and some hospitals might rather have no resident join their facility than accept a particular resident.

We will make the modeling assumption that this will not be permitted for hospitals or residents. In our example, shown below, we have generated two tables, one for the five hospitals and one for the five residents, which show each hospital’s preferences for residents and each resident’s preferences for the hospitals, without ties.

How can one interpret Table 1 below? Resident 3, for example, likes Hospital 1 the best and Hospital 4 the least. Resident 3’s fourth choice is Hospital 5. Similarly, Hospital 2 likes resident 4 the least and Resident 1 the most. Hospital 2 likes Resident 2 second. Note that residents can have identical views about the hospitals and hospitals can have identical views about some of the residents, though that does not occur in this example.

175

What is wrong with just matching any hospital with any student, as long as each of the hospitals is assigned one student and one student is assigned one hospital?

For example, what about the matching (a particular way of pairing hospitals to residents), where Resident 1 (r1) is paired with Hospital 4 (h4), r2 with h5, r3 with h1, r4 with h2, and r5 with h3? Since h4 is r1’s last choice, and h4 prefers r4 or r5 to r1, we see that r1 would rather be paired with h1 than h4 and that h1 would rather be paired with r1 than r3, who is its partner in the current assignment. Thus, r1 and h1 would rather be paired with each other than with their current “mates.” The proposed set of assignments is not “stable” because there is a pair (in this example, r1 and h1) who would rather be together than with the “mate” to whom each is assigned in . in the language of the mathematics of two-sided markets, which is what we are dealing with here, r1 and h1 are called a blocking pair for matching . They would be happier together than with their assigned partners in .

So is not an ideal matching, and we have come up with one notion of what makes one matching better than some others: the idea of a stable matching. Summarizing what we learned from the example, a Hospital -Resident pair is called a blocking pair for matching if and are not paired in but would prefer to be paired to each other than to whom they are paired in . A matching is unstable if there is some blocking pair for . A matching * is stable if there are no blocking pairs for *. What David Gale and Lloyd Shapely showed is that for any hospitals and residents with tables such as those above (strict rankings and no one would rather be unpaired than paired with someone in particular), there must always be at least one stable matching. Not only did they show this, but they showed an easy-to-understand procedure for finding, typically, at least two different such matchings (though in some cases there is only one stable matching).

While the problem being discussed has been described in terms of matching hospitals and residents, more often than not the problem is often described in terms of pairing men and women—perhaps as dancing partners at a college dance—a setting with suggestive terminology if lacking the “seriousness” of the setting we started with. So in describing the procedure, or algorithm, that Gale and Shapley developed, i will use a blend of terminology suggestive of matching men and women and/or hospitals and residents.

Gale-Shapley Deferred Acceptance Procedure (Algorithm)

Before starting the details of the procedure, here is a very brief description of the idea. in “rounds,” the women (men) make proposals to the men (women). if a man (woman) gets one or more proposals, he (she) will temporarily accept the best of these proposals based on the rankings that he (she) has. Those who don’t get matched in some round try again in the next round.

Think of the hospitals as setting up tables in front of a room. The process will proceed in rounds, with the residents “proposing” to the hospitals based on their preferences in Table 1 above. The algorithm is known as the deferred acceptance algorithm, and the idea is that at each stage (round), if more than one “suitor” shows up at a hospital desk, the hospital selects the highest- ranked resident from the hospital’s point of view, on a “temporary” basis, and the rejected students will move on to the next round. if in a future round a resident “proposes” who is superior to the currently accepted choice, the hospital will accept temporarily the highest-ranking choice available and send other “suitors” to the next round. The procedure terminates when there is one resident located at each hospital desk; when this happens, one will have a stable matching. it is worth noting at the start that if all of the residents have different first choices of hospitals, then the procedure terminates right in the first round.

So let us carry out this process for the example above.

Round 1

Residents 1 and 2 (r1 and r2) head for the table of Hospital 2 (h2); r3 heads for the table of h1; r4 goes to h5’s table and r5 to h3’s table. Note that no one appears at the table of h3. For the moment, h1, h4, and h5 accept r3, r5, and r4, respectively. What does h2 do? it is tickled pink to see its first choice, r1, arrive among the two people who would be pleased to come to h2, so it accepts r1 and sends r2 into the second round. So at this stage, the result of Round 1 can be expressed as follows:

176

Note that r2 and h3 are unmatched.

Round 2

Resident 2 (r2) is disappointed about being rejected by his/her first choice, h2, but in Round 2 proceeds to the next highest choice on his/her list, which is h1.

Hospital 1 (h1) is pleased to have r3 at its table and the newly arrived r2. Since h1 prefers r2 to r3, it chooses r2 over r3 and sends r3 “packing”—off to the next round. Thus, at the end of Round 2 we have the following situation:

Note that r3 and h3 are unmatched.

Round 3

At the start of Round 3, only r3 is not yet matched. So r3 goes to the next highest choice in his/her ranking after h1, namely h2.

Now, h2 has the choice of r3 or r1. From h2’s perspective, r1 is better than r3, so again r1 is temporarily accepted and r3 is sent out to find another hospital. We now have the following:

Note that r3 and h3 are unmatched.

Round 4

At this point, r3 is unmatched, so r3 goes to his next highest choice after h2, which is h3. Since h3 had no resident, h3 gladly accepts r3. At this stage, each hospital has a resident and each resident has a hospital.

The matching of h1 to r2, h2 to r1, h3 to r3, h4 to r5, and h5 to r4 is stable! The reason is that no resident has any hope of having a hospital ranked higher than the one he/she is matched with—because at every stage, residents try to form a match with the hospital highest on their list and only go on to other hospitals when they are rejected. So we cannot have any blocking pairs for this matching. in this example, at the end of all rounds except the last, we had only one resident who was unmatched; but often there will be several residents seeking a hospital in the next round.

Why can’t we run this algorithm with the residents manning the tables and the hospitals proposing? The answer is we can! Here, in fewer words, are the results of doing that:

Everyone is matched because there were different first choices by each of the hospitals. Thus, we have the matching (hospitals propose) that pairs h1 to r2, h2 to r1, h3 to r5, h4 to r4, and h5 to r3.

This matching must be stable in that no hospital can do better in this process because at each stage it goes on to a lower choice only if a high choice has rejected the hospital. in fact, here, each hospital got its first choice.

We can see that the two matchings are not the same, though sometimes they can be identical. Can anything be said about these two stable matchings?

First of all, it is worth observing that although the Gale–Shapley deferred acceptance algorithm can be used to find two special stable matchings, there can be many more stable matchings. The details of an algorithm to find all stable matchings are not outlandishly complex, but they will not be discussed here.

To see the special nature of the two matchings we have found, let us look at how pleased the matched parties are with the choice they got.

177

Residents Propose

Hospitals Propose

What is going on? Among all stable matchings, the one in which the hospitals propose is the very best one from the hospitals’ perspectives but the worst stable marriage from the residents’ perspectives. Among all stable marriages, the one in which the residents propose is the best that the residents can do but the worst from the hospitals’ perspectives. Here, best and worst are measured in terms of the ranks of the hospitals and residents for the “other side” of the market.

The National Residents Matching Program (NRMP) was a voluntary, two-sided market system to match hospitals to residents. Though it was established prior to the work of Gale and Shapley, it used an algorithm that produced stable marriages. In Great Britain, similar matching markets sometimes broke down because they did not produce stable marriages. Alvin Roth’s major contribution was to deal with complications that were causing the NRMP difficulties. In particular, many married medical students wanted residencies in the same hospital or at hospitals in the same city, and this caused difficulties for the way the NRMP operated. Roth helped develop an algorithm that overcame the “couples” issue and used matching market ideas to match students with schools (“school choice”).

The algorithm is also used for pairing kidneys that become available (due to an organ donor’s death or a volunteer donor) to people in need of a transplant. New uses of two-sided markets are being developed regularly. For example, recently these ideas are being used to pair computers to Wi-Fi networks.

Practice

Below are the rankings of four men and four women.

Men Rank the Women

Women Rank the Men

Note that there are in fact eight other stable marriages for this example!

Suggested Reading and Website

To learn more about the mathematical ideas discussed here, and their applications, consult the following:

ROTH, A. and M. SOTOMAYOR. Two-Sided Matching: 4 Study in Game-Theoretic Modeling and Analysis, Cambridge University Press, New York, 1992.

www.nrmp.org This web page describes the National Resident Matching Program that is used to match hospitals with residents in the United States.