# Graph Theory - Stable Matchings

Show that in a boy optimal stable matching, no more that one boy ends up with his worst choice.

I know such a matching is created by the Gale-Shapley Algorithm where boys propose to the girls. Here is my attempt at the proof:

I am trying to prove this by proof with contradiction. So assume that there are two boys that end up with their worst choice in this matching, $b_{1}g_{1}$ and $b_{2}g_{1}$. This means that $b_{1}$ prefers all other girls to $g_{1}$ and similar for $b_{2}$ and $g_{2}$. In particular, $b_{2}$ prefers $g_{1}$ over $g_{2}$.

It is also know that a boy optimal stable matching is also a girl pessima. So each girl ends up with her lowest ranked boy out of all possible stable matchings. Let $s(g_{1})$ denote all possible boys that $g_{1}$ could be matched with in a stable matching. So $g_{1}$ prefers all other boys in $s(g_{1})$ over $b_{1}$. In particular $g_{1}$ prefers $b_{2}$ over $b_{1}$. But this contradicts the definition of a stable matching.

The bolded statement is what I am having trouble with. How do I show that $b_{2}$ is in $s(g_{1})$?

• If it is "boy optimal", shouldn't the girls be the ones proposing? – JMoravitz Mar 22 '15 at 3:52
• I'm not sure $b_2$ is always in $s(g_1)$. Suppose there was a $b_3$ who liked $g_1$ the best, and $g_1$ preferred $b_3$ over $b_2$. Then the match $b_2 g_1$ is unstable, since $b_3$ and $g_1$ would always rather be together. Perhaps there can be no such $b_3$, but I'm not sure why not. – Tyler Seacrest Mar 24 '15 at 19:44
• @JMoravitz No, just the opposite. Consider the case where $b_I$'s favorite girl is $g_i$ and $g_i$'s favorite boy is $b _{n+1-i}$ for $i=1,2,\dots,n.$ In this case, obviously the matching is boy-optimal if the boys propose, girl-optimal if the girls propose. – bof Nov 26 '15 at 0:00