I am currently reading an Algorithm's book and came across the Stable Matching Problem. And a question came to mind that I'm curious about, but the book doesn't answer. In every SMP is it possible to always have one pair where each prefers the other one the most? Like in the classic marriage example. Is there always a pair that have one women and one man where both rank each other at the top of their preference?
+5
A:
A counter example:
M1 prefers W1.
M2 prefers W2.
W1 prefers M2.
W2 prefers M1.
There is no possible pairing where both members of the pair get their highest preference.
aschepler
2010-10-01 00:03:16
+1 Why do they have to get married if they don't care about partner? :)
Nikita Rybak
2010-10-01 00:04:11
Thank you, I would thinking about how to prove it right instead of just coming up with one counter example.
2010-10-01 00:14:52
+1, inversing the logic is always a very good trick for these logical problems.
Wrikken
2010-10-01 00:41:22