HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Woman optimal Gale Shapley Stable Matching

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
optimalstableshapleymatchinggalewoman

Problem

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?

Solution

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

Context

StackExchange Computer Science Q#53932, answer score: 3

Revisions (0)

No revisions yet.