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! :)
$\begingroup$
$\endgroup$
$\begingroup$
$\endgroup$
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:
- Round 1M: $1,2$ propose to $b$; $3,4$ propose to $a$.
- Round 1W: $b$ accepts $1$; $a$ accepts $3$.
- Round 2M: $2$ proposes to $a$; $4$ proposes to $b$.
- Round 2W: $a$ accepts $2$, throwing $3$; $b$ accepts $4$, throwing $1$.
- Round 3M: $3$ proposes to $d$; $1$ proposes to $c$.
- Round 3W: $d$ accepts $3$; $c$ accepts $1$.
In the end, everyone is married to their second choice.
answered Sep 26 '17 at 8:07
