Suppose we have one hundred pairs of women and men, and there is a man M that is ranked the second highest on every woman's preference rankings. Would it be possible that he ends up with the woman he least prefers on every single stable matching (men-optimal, women-optimal, etc.).
My intuition for this problem is that it is possible. If he is paired with his least preferred woman, that means every other pair (99 pairs) must be paired with their top choice. The left over women could prefer one of the other men over him, but the woman is his worst preference. Hence he could be paired with the worst choice. Could someone give a more elaborate proof?
Best Answer
Suppose the preference orderings are such that all $100$ women prefer this fellow second most.
There are $99$ other men. Pick randomly $99$ other women. Now, make it so that each of the $99$ men has a different favorite woman and that favorite woman also likes that man the best (they are "soulmates"- how sweet).
In any stable match, these soulmates will be paired. Otherwise they would leave their matched partners and find each other.
The remaining woman likes one of these $99$ men best, but she is our first-man's least favorite.
Since the $99$ pairs of soulmates are paired in every stable match, this woman and our first man must be paired in any stable match. Thus, although he is everyone's second favorite, he ends up with his least favorite.