Chapter 11 Simple Graphs446
to handle it.
Problem 11.24.
Give an example of a stable matching between 3 boys and 3 girls where no person
gets their first choice. Briefly explain why your matching is stable. Can your
matching be obtained from the Mating Ritual or the Ritual with boys and girls
reversed?
Problem 11.25.
In a stable matching betweennboys and girls produced by the Mating Ritual, call
a personluckyif they are matched up with one of theirdn=2etop choices. We will
prove:
Theorem.There must be at least one lucky person.
To prove this, define the following derived variables for the Mating Ritual:
q.B/Dj, where j is the rank of the girl that boyBis courting. That is to say,
boyBis always courting thejth girl on his list.
r.G/is the number of boys that girlGhas rejected.
(a)Let
SWWDX
B 2 Boysq.B/ X
G 2 Girlsr.G/: (11.5)Show thatSremains the same from one day to the next in the Mating Ritual.
(b)Prove the Theorem above. (You may assume for simplicity thatnis even.)Hint:A girl is sure to be lucky if she has rejected half the boys.
Problem 11.26.
Suppose there are two stable sets of marriages. So each man has a first wife and a
second wife , and likewise each woman has a first husband and a second husband.
Someone in a given marriage is awinnerwhen they prefer their current spouse
to their other spouse, and they are aloserwhen they prefer their other spouse to
their current spouse. (If someone has the same spouse in both of their marriages,
then they will be neither a winner nor a loser.)
We will show that
In every marriage, someone is a winner iff their spouse is a loser. (11.6)