q ) Consider a town with n men and n women seeking to get married to one another
ID: 3627252 • Letter: Q
Question
q ) Consider a town with n men and n women seeking to get married to oneanother. Each man has a preference list that ranks all the women, and each
woman has a preference list that ranks all the men.
The set of all 2n people is divided into two categories: good people and
bad people. Suppose that for some number k, 1 < k < n - 1, there are k good
men and k good women; thus there are n - k bad men and n - k bad women.
Everyone would rather marry any good person than any bad person.
Formally, each preference list has the property that it ranks each good person
of the opposite gender higher than each bad person of the opposite gender: its
first k entries are the good people (of the opposite gender) in some order, and
its next n - k are the bad people (of the opposite gender) in some order.
Show that in every stable matching, every good man is married to a good
woman.
Explanation / Answer
proof by contradiction What would it mean for the claim to be false? There would exist some stable matching M in which a good man m was married to a bad woman w. Now, let’s consider what the other pairs in M look like. There are k good men and k good women. Could it be the case that every good woman is married to a good man in this matching M? No: one of the good men (namely, m) is already married to a bad woman, and that leaves only k - ! other good men. So even if all of them were married to good women, that would still leave some good woman who is married to a bad man. Let w’ be such a good woman, who is married to a bad man. It is now easy to identify an instability in M: consider the pair (m, w’). Each is good, but is married to a bad partner. Thus, each of m and w’ prefers the other to their current partner, and hence (m, w’) is an instability. This contradicts our assumption that M is stable, and hence concludes the proof.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.