1
$\begingroup$

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})$?

$\endgroup$
  • $\begingroup$ If it is "boy optimal", shouldn't the girls be the ones proposing? $\endgroup$ – JMoravitz Mar 22 '15 at 3:52
  • $\begingroup$ 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. $\endgroup$ – Tyler Seacrest Mar 24 '15 at 19:44
  • $\begingroup$ @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. $\endgroup$ – bof Nov 26 '15 at 0:00
1
$\begingroup$

Think about the termination condition. To generate a boy-optimal matching one runs the Gale-Shapley algorithm with the boys making proposals. It's easy to see that the algorithm terminates as soon as every girl has received a proposal (single girls are obliged to accept any proposal and, once every girl has received a proposal, no single boys remain).

In order for a boy to end up matched with his least favourite girl he must first propose to all the others. Thus, before he makes his final proposal, all girls save his least favourite have already received a proposal (his, and at least one other boy's) and so aren't single. And as soon as he proposes to his least favourite, she too has a partner and so the algorithm terminates. This means that no other boy will get to the end of his preference list.

$\endgroup$

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.