# Does Gale-Shapley work when the number of men and women are not equal?

According to the Wikipedia page on the Stable Marriage Problem, the problem is presented in a way in which the number of men and women are both the same.

Given n men and n women, where each person has ranked all members of the opposite sex in order of preference, marry the men and women together such that there are no two people of opposite sex who would both rather have each other than their current partners. When there are no such pairs of people, the set of marriages is deemed stable.

And then later on the Gale-Shapley algorithm is presented as a solution. However, based on my thinking, I believe the Gale-Shapley algorithm would work on inputs where the number of men and women do not have a 1:1 ratio. The reasoning for this is because by definition, if you look at the while loop's predicate, the men keep on proposing until they have either proposed to all of their preferences or are matched. This means that the algorithm will necessarily terminate as the men have a finite number of preferences. In the end, the men only end up matched to a woman if another man couldn't "out-bid" them for that woman. Thus it must be stable as if it were not we would have a contradiction as that man/woman that is unmatched should have proposed or been proposed to. (In general, it may be useful to let the side with a smaller number of people propose since the while loop would terminate sooner in expectation).

Overall, I'm just wondering whether the condition that the number of men and women are the same for the GS algorithm is superfluous.

First thing is algorithm will definitely terminate in the case even when number of men are not equal to women. Now at the end of Gale-Shapley algorithm for the case when number of men$(m)$ and women$(w)$ are equal.
• If $m > w$ then algorithm will terminate but at the end there are going to be some men left out without matching
• If $m < w$ then algorithm will terminate then at the end, each man can have the best partner that he can have in any stable matching.
• @ somil yes stable matching imply a perfect matching ($m = w$) – Shiv Mar 25 '17 at 10:04