0
$\begingroup$

Consider the stable marriage problem with $n$ men and $n$ women. Let $A$ and $B$ be two stable matchings, and suppose that we form a new matching $C$ by assigning to each men his favorite partner between the ones he gets in $A$ and $B$. Prove that $C$ is also a stable matching.

This is my attempt. I'm stuck at proving that there are no unstable pairs. By contradiction, let $(m_1, w_1)$ and $(m_2, w_2)$ be the unstable pair in $C$, i.e., $m_1$ prefers $w_2$ over $w_1$ and $w_2$ prefers $m_1$ over $m_2$. I think we have to consider two cases: when $(m_1, w_1)$ and $(m_2, w_2)$ happen in the same matching or in different ones, but I don't know what to do from here.

$\endgroup$

1 Answer 1

2
$\begingroup$

First, you need to prove that $C$ is a matching: suppose it is not a matching. That means that there exists two men $m_1$, $m_2$ matched with the same woman $w$.

It follows that, without loss of generality, $m_1$ is matched with $w$ in $A$ and $m_2$ is matched with $w$ in $B$. Without loss of generality again, suppose $w$ prefers $m_1$ to $m_2$.

Then it means that $B$ is not stable, because $m_1$ prefers $w$ to its partner in $B$, and $w$ prefers $m_1$ to $m_2$. We conclude that $C$ is indeed a matching.

Second, you need to prove that $C$ is stable: suppose it is not stable. Let $(m_1, w_1)$ and $(m_2, w_2)$ be the unstable pair in $C$, i.e., $m_1$ prefers $w_2$ over $w_1$ and $w_2$ prefers $m_1$ over $m_2$. WLOG, $(m_1, w_1)$ was a pair in $A$. Two cases are possible:

  • either $(m_2, w_2)$ was also a pair in $A$ (can you see the contradiction?);
  • or $(m_2, w_2)$ was a pair in $B$. Consider then $w_3$ such that $(m_1, w_3)$ is a pair in $B$. Again, can you see the contradiction? (what is the ranking of $w_1$, $w_2$ and $w_3$ for $m_1$?)
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.