Lesson 9

We will prove the theorem on the existence of a stable matching in the special case where the two sides have equal cardinality and each person has a complete preference list. In real life, of course, things are more complex: we may want to construct a stable matching, for example, between students and companies offering internships. In this case, the number of students won't match the number of companies, and not every student will want to join every company, and not every company will consider all students, and some companies may accept multiple students, and so on. We will see that all these natural constraints are easily handled by the algorithm we study.