4
$\begingroup$

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.

$\endgroup$

1 Answer 1

3
$\begingroup$

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.

Each man can have the best partner that he can have in any stable matching.

If you only care about men then there are two cases:

  • 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.

$\endgroup$
2
  • $\begingroup$ I agree with everything you say. This may be an unanswerable question, but does stable matching imply a perfect matching (i.e. each man must be matched)? If it does not, then it would be fine for some men to be left without a matching in a stable matching. If this is the case, then the GS algorithm works for all input ratios. $\endgroup$
    – somil
    Mar 21, 2017 at 22:20
  • $\begingroup$ @ somil yes stable matching imply a perfect matching ($m = w$) $\endgroup$
    – user35837
    Mar 25, 2017 at 10:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.