Lesson 11

Below we will prove that this algorithm will eventually stop and that the engaged pairs at that moment form a stable matching.

For further analysis of the algorithm, it will be useful to look at what happens through the eyes of the involved women and men:

• As soon as a woman becomes engaged to someone, she remains engaged until the end of the algorithm, and her partners can only get better.


• A man, on the other hand, can become free and engaged many times during the process. And the women he ends up engaged to during the process become only worse.