Hospitals and Residents

Although the one-to-one stable matching problem is most frequently known as the marriage problem, the Gale-Shapley algorithm is not particularly well suited to predict actual marriages. The original algorithm depends on requiring participants to rank each other, and on the assumptions that anyone would be happier married to someone undesirable than unmarried, that preferences never change, and that no two potential mates can be tied in the rankings. Love does not conform to such conditions. It is interesting to note that researchers compared the results of an online dating service, judging ranking by the order in which a participant e-mailed potential mates and a matching as the exchange of phone numbers. When they ran the Gale-Shapley algorithm, they found that the results were not appreciably different from the predicted Gale-Shapley results.[VH1]
There are, however, numerous real-life situations in which the Gale-Shapley algorithm, or some modification thereof, is extremely useful. When medical students finish their academic training, for example, they enter a residency at a hospital. For a long time, no coordinated system existed for resident-hospital matching. Hospitals would offer residents positions, giving them increasingly short periods of time to respond, for fear of losing that resident if a more desirable hospital offered a job during the response period and also worrying that other desirable residents would be “snatched up” by other programs and therefore unavailable if the original medical student declined the offer. In 1952, the National Residency Matching Program (NRMP) was established to help standardize the process. The NRMP now uses an algorithm similar to the Gale-Shapley algorithm to make matches between residents and hospitals. The major difference between the Stable Marriage algorithm and an algorithm like the one used by the NRMP is that a hospital in the NRMP algorithm frequently accepts more than a single resident, whereas a participant in the GS algorithm is only entitled to a single partner. The matching in this case is one to many, instead of one to one. A simple modification to the Gale-Shapley stable marriage algorithm solves this problem. Gale and Shapley referred to the modified algorithm as a solution to the college admission problem for obvious reasons. At the beginning of the algorithm, if a hospital has q places, the hospital is divided into q “subhospitals,” each willing to accept a single applicant. Each resident’s ranking list is then changed so that if that hospital is ranked nth on the resident’s list, it will be removed and subhospital 1 will replace it in the nth place. Then subhospital 2 will be ranked in place n+1, subhospital 3 in place n+2, and so on until subhospital q is ranked in place n+q-1. Consider the following example:

Resident’s original list:
1. University Hospital
2. Children’s Hospital
3. City Hospital
4. General Hospital

University Hospital will accept 3 residents
Children’s Hospital will accept 2 residents
City Hospital will accept 4 residents
General Hospital will accept 2 residents and a daytime television spot

Resident’s new preference list:
1. University 1
2. University 2
3. University 3
4. Children’s 1
5. Children’s 2
6. City 1
7. City 2
8. City 3
9. City 4
10. General 1
11. General 2

Each subhospital has exactly the same preference list as the original hospital. This setup now closely resembles the original Gale-Shapley algorithm for stable marriages. At least originally, the NRMP ran the algorithm with hospitals proposing to residents and residents accepting or rejecting. This algorithm terminates in a stable resident matching. The proof is omitted, as it is almost identical to the proof of the GS algorithm. The NRMP not describe the exact algorithm it uses, but it does provide detailed examples and regulations of the process at www.nrmp.org.[NR1]

 

contents