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.