Stable Marriage / Stable Matching / Gale-Shapley where men rank a subset of women 
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?
 A: 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.
A: A more conventional solution here is that the argument for stable matchings in ordinary Gale-Shapley still applies here with essentially no modification. We take a pair $(M_1,W_1)$, and prove that it is not unstable.
We assume that at the end of Gale-Shapley, $M_1$ is not married to $W_1$ (if they were married, they definitely wouldn't be an unstable pair). Also, we assume that $M_1$ prefers $W_1$ to $M_1$'s current arrangement (if not, then the pair is definitely not unstable, since $M_1$ is happier where he is). It's irrelevant here whether $M_1$'s current arrangement is "single" or "married to some other woman $W_2$". Since $M_1$ makes proposals in order from best to worst, $M_1$ must have proposed to $W_1$ at some point before making it this far down the list. 
Since $M_1$ did not end up with $W_1$, at some point $W_1$ must have rejected him in favor of someone better, or in favor of staying single. In Gale-Shapley, women only trade up; once $W_1$ rejects $M_1$, she will only be in situations higher and higher on her preference list. So, at the end of the algorithm, either $W_1$ is single (because she preferred staying single to being engaged to $M_1$) or $W_1$ is married to a man $M_2$ she prefers to $M_1$. In either case, $(M_1,W_1)$ is not an unstable pair: $W_1$ is happier where she is.

In particular, let's look at the situation described in another answer, where the rankings were:


*

*$m_1$: $w_1 > w_2 > \text{single}$

*$m_2$: $w_1 > \text{single} > w_2$

*$w_1$: $m_1 > m_2 > \text{single}$

*$w_2$: irrelevant.


In the first round of Gale-Shapley, $m_1$ and $m_2$ both propose to $w_1$. She picks $m_1$, whom she likes better. In the second round, $m_2$ does not propose to anyone, since he prefers being single to his remaining option $w_2$. So the final matching found by Gale-Shapley is $(m_1,w_1)$ with $m_2$ and $w_2$ remaining single.
There are no unstable pairs here: $m_1$ and $w_1$ got their best options, so they won't be part of any unstable pair, and $(m_2, w_2)$ is not an unstable pair either, since $m_2$ prefers being single to being married to $w_2$.
A: Gayle-Shapely fails to find the matching somteimes
Suppose that we have 2 men and 2 women. Suppose that $m_1$ has preference
ranking $w_1$, $w_2$, and $m_2$ has preference ranking $w_1$ (and vetoes $w_2$).
Also suppose that $w_1$ has ranking $m_1$, $m_2$. The ranking for $w_2$ is unknown but doesn't matter. Now, there is 1 perfect matching of men to women they have not vetoed.
Namely, match $m_2$ to $w_1$ and $m_1$ to $w_2$. However, this is not stable, since $m_1$ and $w_2$ prefer each other over such a matching.
(The matching in which $m_1$ is matched to $w_1$ and $m_2$, $w_2$ remain isolated is stable but Gayle-Shapely fails to find it.)
