3
$\begingroup$

In the context of stable matchings I am currently trying to understand the Gale-Shapely Algorithm (traditional marriage algorithm).

I have proved it s correctness and I have shown that its male optimal in the sense that each boy will end up in the best stable match. (i.e. any matching where he would be with a girl he prefers would not be stable), however I am struggling a little to come up with a good strategy to show the algorithm will return a female pessimal matching. (i.e. among all stable matchings each female will be matched to the least preferred boy)

A hint to get me started would be very appreciated.

2 Answers 2

5

Let $M_1$ be the male-optimal matching, and suppose that $M_1$ was not female-pessimal. By definition this would mean that there is some girl (call her Alice) who could be worse off with some other stable matching $M_2$. Let's say that $M_1$ pairs Alice with Bob, and $M_2$ pairs Alice with Charles. By assumption Alice likes Bob better than she likes Charles.

However, since $M_2$ pairs Alice to Charles, it must pair Bob with some other girl, Denise. However, since $M_1$ is assumed male-optimal, Alice is the girl Bob likes best among those he has any chance with. We can conclude that Bob likes Alice better than he likes Denise. But that means that under matching $M_2$, Alice and Bob ought to elope together rather than stay with Charles and Denise. In other words, $M_2$ cannot be stable after all.

-1

I think that if Alice is paired to another boy, Bob has to find another girl. Then it isn't male-optimal for Bob since Alice is the optimal girl.