Lesson 9

We will prove the theorem on the existence of a stable matching in the special case of equally many students and companies, where each student and company has a complete preference list. In real life, of course, things are more complex: 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.