The Gale-Shapley Algorithm

The Gale-Shapley algorithm is designed to solve what’s called the stable marriage problem. The algorithm is named after two eminent mathematicians, David Gale and Lloyd Shapley, who solved the stable marriage problem in 1962. It’s interesting to know that Shapley was also a corecipient of a Nobel prize for his work in game theory on stable allocations.

We make use of a fictional universe to help contextualize the stable marriage problem but give examples of how the algorithm is applied at the end of this lesson.

Stable marriage problem

In an alternate universe, a group of individuals called the Harmonites is known throughout their universe for their long-lasting partnerships. Some of these individuals refer to themselves as men and others as women.

The custom is that every year, $n$ men are paired with $n$ women. Such a pairing where each man is matched with exactly one woman is called a perfect matching. Each of the men and women submits a list of their rankings for their choices of partners. Given these ranking lists, the problem is to find a perfect matching between the men and the women, which is stable.

What’s a stable matching?

Suppose there’s a perfect matching between a set of $n$ men $\{ m_0, m_1, \ldots , m_n\}$ and a set of $n$ women $\{w_0, w_1, \ldots , w_n\}$. Two individuals who prefer each other over their matched partners have cause to leave their partners. If there is no such pair in a perfect matching, it is said to be a stable matching. The first slide in the following deck is an illustration of a stable matching.

A perfect matching is unstable ...