Better of the two
Suppose that in the stable marriage problem with $n$ men and $n$ women, we have found two (possibly different) stable matchings $S$ and $T$. We will show how to combine $S$ and $T$ into two new stable matchings $W$ and $M$, which are the best of both worlds for the women and men respectively.
- Each woman is given the name of the man she is matched with in $S$ and the one she is matched with in $T$ (note that they might be the same man). Of the two names each woman receives, she picks the one she prefers the most. Prove that no two women would end up picking the same man. Conclude that if women are matched with the men they pick, the result is a matching. Call this matching $W$.
- Prove that $W$ is a stable matching.
- Another way of combining the matchings $S$ and $T$, is to give each man the names of the women he is matched with in $S$ and $T$ and force each man to pick the woman he prefers the least amongst the two. Prove that this results in the same stable matching $W$ as before.
- How would you combine the matchings $S$ and $T$ to create stable matching $M$, which is the best of both worlds for the men? Just think about how $M$ related to $W$.
I have studied stable marriage algorithm but i do not have a clue on this one.