algorithmpattern-matchingproofstable-marriage

Stable Matching Problem

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?

Solution

  • 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.