Tell me more ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.
up vote 7 down vote favorite

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?

share|improve this question
1  
"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. – usul Dec 13 '12 at 4:31

1 Answer

up vote 8 down vote accepted

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.

share|improve this answer
1  
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. – phwd Mar 11 '12 at 21:42

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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