Chapter 11 Simple Graphs314
Robin Bobby JoeAlexMergatroid3
3
2
1
1
2
(^213)
Figure 11.12 Some preferences with no stable buddy matching.
the triangle are symmetric, we may assume in particular, that Robin and Alex are
matched. Then the other pair must be Bobby-Joe matched with Mergatroid.
But then there is a rogue couple: Alex likes Bobby-Joe best, and Bobby-Joe
prefers Alex to his buddy Mergatroid. That is, Alex and Bobby-Joe are a rogue
couple, contradicting the assumed stability of the matching.
So getting a stablebuddymatching may not only be hard, it may be impossible.
But when men are only allowed to marry women, and vice versa, then it turns out
that a stable matching can always be found.^6
11.6.1 The Mating Ritual
The procedure for finding a stable matching involves aMating Ritualthat takes
place over several days. The following events happen each day:
Morning: Each woman stands on her balcony. Each man stands under the bal-
cony of his favorite among the women on his list, and he serenades her. If a man
has no women left on his list, he stays home and does his math homework.
Afternoon: Each woman who has one or more suitors serenading her, says to
her favorite among them, “We might get engaged. Come back tomorrow.” To the
other suitors, she says, “No. I will never marry you! Take a hike!”
Evening: Any man who is told by a woman to take a hike, crosses that woman
off his list.
Termination condition: When a day arrives in which every woman has at most
one suitor, the ritual ends with each woman marrying her suitor, if she has one.
There are a number of facts about this Mating Ritual that we would like to prove:
(^6) Once again, we disclaim any political statement here —it’s just the way that the math works out.