Given n men and n women, preference rankings for the women, does Gale-Shapley still find a stable matching if the men only rank a subset of women.
From this variation, it's possible that we end up with single people, but that's ok as this situation is still stable.
- In this variation, some men may not be matched to a woman
- But in that case, the man is content being single
- Since women rank all men, some woman preferred that man, but that man didn't prefer that woman
- Therefore having unmatched men and women is stable since
My problem is justifying the rest of the matching is also stable
Do I prove it by contradiction?
Best Answer
Imagine you're the president-for-life and you've decided that your population is too small and needs to grow, so you've made it a crime to be single!
Whenever someone, man or woman, refuses to rank everyone of the opposite sex, you simply invent a ranking for him, putting those he doesn't like below those that he does. Go by alphabetical order or draw lots, that doesn't matter. Then run the algorithm and force-marry everybody to whom the algorithm decides they should marry. Some of the marriages will be unhappy. Tough luck -- what are they gonna do, sue the president-for-life?
Now in reality those that ended up in an unhappy marriage in the thought experiment will instead be single. But the partial matching you have after dissolving the unhappy marriages will still be stable.
Namely if there's any pair of people who would choose to elope in reality, those two people would still choose to elope in the imaginary world. (They must like each other, so even if one or both of them is single, they would just be unhappily married in the imaginary world and therefore willing to elope with anyone they do like).
But Gale and Shapley tell us that the matching in the imaginary world; therefore nobody will elope in reality either.