Lesson 13

Theorem. For any set of \(n\) men and \(n\) women (each of whom has their own preference list), the Gale — Shapley algorithm produces a stable matching.

Proof. We immediately show that the algorithm terminates and that there will be no more than \(n^{2}\) iterations. Indeed, at each iteration, the current man crosses out the current woman from his list. Since the total length of all lists is exactly \(n^{2}\), there will be no more than that many iterations.

Now let's show that at the moment the algorithm stops, the set of engaged pairs forms a perfect matching. If this were not the case, then at the end of the algorithm, there would be a man \(m\) with an empty preference list. Since the matching is not perfect, there is a free woman \(w\). But a woman can remain free only if no one proposed to her, while man \(m\)'s list is empty.

Finally, let us show that the constructed perfect matching is stable. Suppose the contrary: there exists a man \(m\) and a woman \(w\) such that \(m\) prefers \(w\) to his wife \(w'\) and \(w\) prefers \(m\) to her husband \(m'\). It is clear that \(m\) did not propose to \(w\): indeed, \(m'\) is the best man, from \(w\)'s point of view, among those who proposed to her. On the other hand, \(m\) definitely proposed to \(w'\), since that’s the only way they could end up married. It follows that \(m\) proposed to \(w'\) while skipping \(w\), although he prefers \(w\) to \(w'\), a contradiction.◼