3
$\begingroup$

I am learning about Gale Shapley Algorithm now, and I understand that it is Man Optimal and that all possible executions will yield a stable matching where each man gets the best partner that he can have. I was thinking is it possible to have a woman optimal solution with a guaranteed stable matching? Let's say each woman has a different man as her most preferred partner. Then can we say that we can ensure stable matching by simply assigning the most preferred man to each woman?

I am having problem understanding that, since by definition the matching is stable if no man or woman prefer another to their current situation. Wouldn't it give as stable matching if each woman has the most preferred man, considering they all unique?

$\endgroup$
3
$\begingroup$

Yes, of course you can switch the roles of men and women in the algorithm and you'll get a woman-optimal solution. It's just convention that we call one side of the graph "men" and the other side "women" but the algorithm itself doesn't care what names we use. We could just as well call them "horse" and "blueberry".

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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