Chapter 11 Simple Graphs316
Case 2: wwas crossed offm’s list prior to daydC 1. SincePis true at the end of
dayd, this means thatwhas a suitor she prefers tomon dayd. She therefore
has the same suitor or someone she prefers better at the end of daydC 1.
In both cases,Pis true at the end of daydC 1 and soPmust be an invariant.
With Lemma 11.6.4 in hand, we can now prove:Theorem 11.6.5.Everyone is married by the Mating Ritual.
Proof. By contradiction. Assume that it is the last day of the Mating Ritual and
someone does not get married. Since there are an equal number of men and women,
and since bigamy is not allowed, this means that at least one man (call him Bob)
and at least one woman do not get married.
Since Bob is not married, he can’t be serenading anybody and so his list must
be empty. This means that Bob has crossed every woman off his list and so, by
invariantP, every woman has a suitor whom she prefers to Bob. Since it is the last
day and every woman still has a suitor, this means that every woman gets married.
This is a contradiction since we already argued that at least one woman isnot
married. Hence our assumption must be false and so everyone must be married.
Theorem 11.6.6.The Mating Ritual produces a stable matching.
Proof. Let Brad and Jen be any man and woman, respectively, that arenotmarried
to each other on the last day of the Mating Ritual. We will prove that Brad and Jen
are not a rogue couple, and thus that all marriages on the last day are stable. There
are two cases to consider.
Case 1: Jen is not on Brad’s list by the end. Then by invariantP, we know that
Jen has a suitor (and hence a husband) that she prefers to Brad. So she’s not
going to run off with Brad—Brad and Jen cannot be a rogue couple.
Case 2: Jen is on Brad’s list. But since Brad is not married to Jen, he must be
choosing to serenade his wife instead of Jen, so he must prefer his wife. So
he’s not going to run off with Jen—once again, Brad and Jen are not a rogue
couple.
11.6.4... Especially the Men
Who is favored by the Mating Ritual, the men or the women? The womenseem
to have all the power: they stand on their balconies choosing the finest among
their suitors and spurning the rest. What’s more, we know their suitors can only
change for the better as the Ritual progresses. Similarly, a man keeps serenading