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]