A First Problem: Stable Matching

The first algorithm we will cover in this course is used to solve the Stable Matching Problem. The problem has been stated as follows:

Given $n$ men and $n$ women, where each person has ranked all members of the opposite sex in order of preference, marry the men and women together such that there are no two people of opposite sex who would both rather have each other than their current partners.

When there are no such pairs of people, the set of marriages is deemed stable.

<aside> <img src="/icons/map-pin_gray.svg" alt="/icons/map-pin_gray.svg" width="40px" /> The term used, such as men, women, and marriage are all analogous, it is intended to paint the scenario of two equally sized sets of elements given an ordering of preferences.

In another context, you can think of it as $n$ students and $n$ school, where each student/school have their order of preference.

</aside>

It is bit a text-heavy, so we can look at a diagram for a better example.

Figure 1.1 Men’s and women’s preference profile.

Figure 1.1 Men’s and women’s preference profile.

As you can see, each man and woman has a list in order of preference from most to least favorite. The incentive of this problem, is that:

  1. Each man gets exactly one woman.
  2. Each woman gets exactly one man.
  3. There should be no unstable pairs.

Perfect Matching

A stable matching is a perfect matching of men to women, such that no two pairs would prefer to switch partners. Consider the following matching:

Figure 1.2 An unstable matching.

Figure 1.2 An unstable matching.

For clarity, we will use the first letter of each name to reduce redundancy. We have the pairs:

What makes it unstable, is that there exists a better match where two pairs would prefer to switch partners, denoted in blue.