Lesson 1

The picture below shows four students \(A\), \(B\), \(C\), \(D\) and four companies \(E\), \(F\), \(G\), \(H\). Next to each student and company is a preference list for the other side. For example, student \(B\) would most like to be paired with company \(H\), and least with company \(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, companies \(F\) and \(G\) both rank student \(D\) first.

We call a perfect matching unstable if some student \(s\) and company \(c\) are not paired together, yet each prefers the other to their current match. If there are no such pairs, the matching is called stable.

Can you construct a stable matching? Try it!