Thread: Stable Matching

Prove that if man x is paired with woman a in some stable matching, then a
does not reject x in the proposal algorithm with men proposing. (Hint: Consider the first
occurrence of such a rejection.)

Conclude that among all stable matchings, every man is happiest in the matching
produced by this algorithm.

Thanks for any advice!

I am using w for the woman and m for the man.

Suppose such a rejection occurs. Consider the first such rejection. This means w rejects m because some m' higher on her priority list proposes to her later. Say, in the stable matching S where w was paired with m, m' was paired with w'. Since w prefers m' to m, the matching must have been stable because m' prefers w' to w. So in the algorithm, m' must have proposed to w' first and got rejected. Therefore we get a contradiction to our initial assumption.

The second part is obvious.