10
$\begingroup$

In the Stable Matching Problem, it is stated that there can exist cases where the $m$ list of men can be content with their decisions, yet the list of $f$ cannot when the algorithm is run with men's proposals.

From what I read, an unstable match occurs when $m$ and $f$ prefer each other to their current partners.

I am a little lost in the definition of Stable Matching for this case. I'm going over the slides here.

Is a pair $(m, f)$ stable as long as the men are content even though the female's preferences have not been matched?

$\endgroup$
1
  • 1
    $\begingroup$ "The men are content" is a bit of a misstatement. If we run the Gale-Shapley algorithm where the men propose, we end up with a "male-optimal" stable matching. This is the matching which is overall best for the set of men among all stable matchings. But that doesn't mean that every man is matched to his first choice. Some of them would still like to switch if they could; it's just that none of their favorites would be willing to switch with them. And some women may be matched to their first choices, it's just not necessarily the best stable matching for women overall. $\endgroup$
    – usul
    Dec 13, 2012 at 4:31

1 Answer 1

8
$\begingroup$

Yes, it is stable. It doesn't need to assign the optimal choices for both sides. To break a marriage you need two willing parties, unhappiness of one side in a marriage doesn't make it unstable here.

$\endgroup$
1
  • 1
    $\begingroup$ Ok I re-read everything now. So stable matching here, when men propose, only allow for optimal choices with men specifically "Man-optimality" as referred to in the slides, so pairs where women get their best preference never arrive in this algorithm but only in a version where women are the ones to propose. I think I wrapped my head around stable matching now. $\endgroup$
    – phwd
    Mar 11, 2012 at 21:42

Your Answer

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

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