Lesson 12

Let's give an example.

Student \(A\) applies to company \(H\). Since \(H\) is unmatched, it accepts \(A\)'s application, and \(A\) and \(H\) are matched. The tail of \(H\)'s preference list will be erased because it will never be needed again.

Student \(B\) applies to company \(F\), which is unmatched and accepts the application.

After that, student \(C\) applies to company \(I\), which is unmatched and accepts the application.

Student \(D\) applies to company \(F\). Company \(F\) rejects the application, since \(F\) is matched with student \(B\) and prefers \(B\).

Student \(D\) applies to company \(H\). Company \(H\) is matched with student \(A\) but prefers \(D\), so \(H\) rejects \(A\) and accepts \(D\)'s application; \(A\) becomes unmatched.

And so on. After several steps, the following perfect matching is produced. Below we will prove that it is stable.