11.11. References 447
(a)The left to right direction of (11.6) is equivalent to the assertion that married
partners cannot both be winners. Explain why this follows directly from the defini-
tion of rogue couple.
The right to left direction of (11.6) is equivalent to the assertion that a married
couple cannot both be losers. This will follow by comparing the number of winners
and losers among the marriages.
(b)Explain why the number of winners must equal the number of losers among
the two sets of marriages.
(c)Complete the proof of (11.6) by showing that if some married couple were
both losers, then there must be another couple who were both winners.
(d)Conclude that in a stable set of marriages, someone’s spouse is optimal iff they
are pessimal for their spouse.
Problem 11.27.
Suppose there are two stable sets of marriages, a first set and a second set. So
each man has a first wife and a second wife (they may be the same), and likewise
each woman has a first husband and a second husband. We can form a third set
of marriages by matching each man with the wife he prefers among his first and
second wives.
(a)Prove that this third set of marriages is an exact matching: no woman is mar-
ried to two men.
(b)Prove that this third marriage set is stable.Hint:You may assume the following fact from Problem 11.26.
In every marriage, someone is a winner iff their spouse is a loser, (11.7)Exam Problems
Problem 11.28.
Four unfortunate children want to be adopted by four foster families of ill repute.
A child can only be adopted by one family, and a family can only adopt one child.
Here are their preference rankings (most-favored to least-favored):
Child Families
Bottlecap: Hatfields, McCoys, Grinches, Scrooges
Lucy: Grinches, Scrooges, McCoys, Hatfields
Dingdong: Hatfields, Scrooges, Grinches, McCoys
Zippy: McCoys, Grinches, Scrooges, Hatfields