11.11. References 445
(a)Extend the definition ofrogue coupleso it covers the case of unmarried men
and women. Verify that in a stable set of marriages, either all the men are married
or all the women are married.
(b)Explain why even in the case of unequal numbers of men and women, applying
the Mating Ritual will yield a stable matching.
Homework Problems
Problem 11.22.
Suppose we want to assign pairs of “buddies,” who may be of the sex, where each
person has a preference rank for who they would like to be buddies with. For
the preference ranking given in Figure 11.26, show that there is no stable buddy
assignment. In this figure Mergatroid’s preferences aren’t shown because they don’t
even matter.
Robin Bobby JoeAlexMergatroid3
3
2
1
1
2
(^213)
Figure 11.26 Some preferences with no stable buddy matching.
Problem 11.23.
The most famous application of stable matching was in assigning graduating med-
ical students to hospital residencies. Each hospital has a preference ranking of
students, and each student has a preference ranking of hospitals, but unlike finding
stable marriages between an equal number of boys and girls, hospitals generally
have differing numbers of available residencies, and the total number of residen-
cies may not equal the number of graduating students.
Explain how to adapt the Stable Matching problem with an equal number of boys
and girls to this more general situation. In particular, modify the definition of stable
matching so it applies in this situation, and explain how to adapt the Mating Ritual