Lesson 11

Below we will prove that this algorithm will eventually stop and that the current matching at that moment is stable.

For further analysis of the algorithm, it will be useful to compare what happens through the eyes of the involved companies and students:

• As soon as a company becomes matched, it remains matched until the end of the algorithm, and its successive partners can only improve.


• A student, on the other hand, can become unmatched and matched many times during the process, and their successive partners can only get worse.