Lesson 10

The Gale — Shapley algorithm works as follows. Students apply to companies. Initially, all students and companies are unmatched. While there is an unmatched student with a non-empty preference list, the following occurs:

• an unmatched student \(s\), whose preference list is not empty, chooses the highest-ranked company \(c\) remaining on the list and applies to \(c\); to record this application, \(s\) immediately crosses \(c\) off the list;


• if company \(c\) is unmatched, it accepts the application, and \(s\) and \(c\) are matched;


• if \(c\) is matched with a student \(s'\) whom it prefers to \(s\), then \(c\) rejects \(s\);


• finally, if \(c\) is matched with a student \(s'\) whom it prefers less than \(s\), then \(c\) rejects \(s'\) (who becomes unmatched) and accepts the application from \(s\).