Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

2 Answers 2

up vote 4 down vote accepted

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 matchinf $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.

share|improve this answer

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.

share|improve this answer

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.