Lesson 10

The Gale — Shapley algorithm works as follows. Initially, all \(n\) men and \(n\) women are free. While there is an unengaged man with a non-empty preference list, the following occurs:

• an unengaged man \(m\), whose preference list is not empty, chooses from his list the woman \(w\) he likes the most and proposes to her; to remember that he already proposed to woman \(w\), he immediately crosses her off his list;


• if woman \(w\) is not engaged, she accepts;


• if woman \(w\) is already engaged to a man \(m'\) whom she prefers more, she rejects the current man;


• finally, if woman \(w\) is already engaged, but to a man \(m'\) whom she prefers less than \(m\), she breaks the engagement with \(m'\) (man \(m'\) becomes free) and accepts the proposal from \(m\).