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! :)


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.