Lesson 1

The picture below shows four men \(A\), \(B\), \(C\), \(D\) and four women \(E\), \(F\), \(G\), \(H\). Next to each of them is their preference list of people of the opposite gender. For example, man \(B\) would most like to be paired with woman \(H\), and least with woman \(E\).

We want to pair them (i.e., build a perfect matching) so that we respect all these preferences as much as possible. But what exactly do we mean by “respect all preferences as much as possible”? Of course, we can't just pair everyone with their top choice: for example, in the example above, women \(F\) and \(G\) both prefer man \(D\) the most.

We call a perfect matching unstable if there exists a man \(m\) and a woman \(w\) who are not paired together and yet \(m\) prefers \(w\) to his partner and \(w\) prefers \(m\) to her partner. If there are no such pairs, the matching is called stable.