Stable marriage problem with all men having the same preference (2)

1k Views Asked by At

I saw this problem today: Stable marriage problem with all men having the same preference

After look at this problem, I have a feeling that if one side shares the same exact preference, there will only be one possible stable matching. However, I don't know how to prove it.

1

There are 1 best solutions below

0
On BEST ANSWER

Let the men be $M=\{m_1, ..., m_n\}$ and the women be $W=\{w_1, ..., w_n\}$. WLOG, assume that the men preferences are $w_1\geq w_2 \geq ... \geq w_n$.

Claim: If all men have the same preference, then there is a unique stable matching.

Proof: Consider woman $w_1$. If she doesn't get her number one preference $m_{i_1}$, then $(m_{i_1}, w_1)$ would be an unstable (blocking) pair. So $w_1$ must be matched to $m_{i_1}$. Woman $w_2$ must be connected to her number one preference in $M-\{m_{i_1}\}$, since otherwise, again $(m_{i_2}, w_2)$ would be a blocking pair. Repeat this for $w_3, ..., w_n$. This shows that there can only be one matching per women that is overall stable $\implies$ there is a unique stable matching.