Proving that this matching is stable

Question

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.

Answer 1

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$?)