Lesson 13

Theorem. For any \(n\) students and \(n\) companies, where each student ranks all companies and each company ranks all students, 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 student crosses the current company off their list. Since the total length of all students' 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 current matching is perfect. If this were not the case, then at the end of the algorithm, there would be a student \(s\) with an empty preference list. Since the matching is not perfect, there would also be an unmatched company \(c\). But \(c\) can remain unmatched only if no student applied to \(c\), while \(s\)'s empty list means that \(s\) applied to every company, including \(c\).

Finally, let us show that the constructed perfect matching is stable. Suppose the contrary: there exist a student \(s\) and a company \(c\) such that \(s\) prefers \(c\) to the current company \(c'\) and \(c\) prefers \(s\) to the current student \(s'\). Student \(s\) did not apply to \(c\): indeed, \(s'\) is the student whom \(c\) prefers most among those who applied to \(c\). On the other hand, \(s\) definitely applied to \(c'\), since that is the only way they could end up paired. It follows that \(s\) applied to \(c'\) while skipping \(c\), although \(s\) prefers \(c\) to \(c'\), a contradiction.◼