So I was asked to prove (or not) whether, in gale shapley algorithm, everyone can end up married to their second partner of choice or not. I think not but then I am not able to come up with a proof.
Thanks! :)
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this communitySo I was asked to prove (or not) whether, in gale shapley algorithm, everyone can end up married to their second partner of choice or not. I think not but then I am not able to come up with a proof.
Thanks! :)
Let us number the men $1,2,3,4$ and the women $a,b,c,d$ (the men propose to the women), with the following preferences: $$ \begin{align*} &1\colon b \succ c \succ d \succ a & a\colon 1 \succ 2 \succ 3 \succ 4 \\ &2\colon b \succ a \succ d \succ c & b\colon 3 \succ 4 \succ 1 \succ 2 \\ &3\colon a \succ d \succ c \succ b & c\colon 2 \succ 1 \succ 4 \succ 3 \\ &4\colon a \succ b \succ c \succ d & d\colon 4 \succ 3 \succ 2 \succ 1 \end{align*} $$ Let us trace the Gale-Shapley algorithm:
In the end, everyone is married to their second choice.