Chapter 11 Simple Graphs318
By the definition of an optimal spouse, there must be some stable set of marriages in
which Keith gets his optimal spouse, Nicole. But then the preferences given in ()
and () imply that Nicole and Tom are a rogue couple within this supposedly
stable set of marriages (think about it). This is a contradiction.
Theorem 11.6.9.The Mating Ritual marries every woman to her pessimal spouse.
Proof. By contradiction. Assume that the theorem is not true. Hence there must
be a stable set of marriagesMwhere some woman (call her Nicole) is married to
a man (call him Tom) that she likes less than her spouse in The Mating Ritual (call
him Keith). This means that
Nicole prefers Keith to Tom. (+)By Theorem 11.6.8 and the fact that Nicole and Keith are married in the Mating
Ritual, we know that
Keith prefers Nicole to his spouse inM. (++)This means that Keith and Nicole form a rogue couple inM, which contradicts the
stability ofM.
11.6.5 Applications
The Mating Ritual was first announced in a paper by D. Gale and L.S. Shapley in
1962, but ten years before the Gale-Shapley paper was published, and unknown
by them, a similar algorithm was being used to assign residents to hospitals by
the National Resident Matching Program (NRMP)^7. The NRMP has, since the turn
of the twentieth century, assigned each year’s pool of medical school graduates to
hospital residencies (formerly called “internships”) with hospitals and graduates
playing the roles of men and women. (In this case, there may be multiple women
married to one man, a scenario we consider in the problem section at the end of the
chapter.). Before the Ritual-like algorithm was adopted, there were chronic disrup-
tions and awkward countermeasures taken to preserve assignments of graduates to
residencies. The Ritual resolved these problems so successfully, that it was used
essentially without change at least through 1989.^8
(^7) Of course, there is no serenading going on in the hospitals—the preferences are submitted to a
program and the whole process is carried out by a computer.
(^8) Much more about the Stable Marriage Problem can be found in the very readable mathematical
monograph by Dan Gusfield and Robert W. Irving, The Stable Marriage Problem: Structure and
Algorithms, MIT Press, Cambridge, Massachusetts, 1989, 240 pp.