Stable marriages

In class today, we proved that the Gale-Shapley algorithm always finds a stable matching.  As a consequence, we learn something that is not at all obvious:  For every set of preferences for the men and women, there exists a stable matching.  After class today, someone asked if the proof had to be algorithmic; is there a proof of the existence of a stable matching which doesn’t actually find the matching?

It turns out that there is.  I’ll give some hints, and an adventurous student can see if they are able to find the proof.

A non-constructive argument

First, we will have to allow people to be single (not in the eventual stable matching, obviously, but as part of the proof).  Let’s also agree that a person prefers to be with anyone rather than be single.  Now, say that a matching is simple if, whenever the pair is unstable, it is because is single, and prefers to to his current situation.

Say that a matching   is weakly optimal for the men if it is simple, and there is no simple matching with the properties that: (1) Every man is at least as happy with as with , and (2) there exists a man that is happier in than in .

First: Show that there always exists a matching that is weakly optimal for the men.

Second: Show that if a matching is weakly optimal for the men, then it is stable.

Feel free to leave a proof (or proof ideas, where you got stuck, etc.) in the comments.

The last slide from the demo: