The Stable Marriage Problem
The stable marriage problem can be stated as follows:
Given (a) two sets that have the same number of elements and (b) a set of preferences for each element, find a stable matching between the two sets.
That is a very general formulation of the problem. The reason that the problem is called "the stable marriage problem" is that the problem is usually formulated like this:
Consider a population of people. Half of them are men, and half of them are women. Each man has a list of all of the women ranked according to his preferences, and each woman has a list of all of the men ranked according to her preferences. Find a stable matching that marries everybody off.
In this context, a matching is an assignment of men and women to each other. A matching is unstable if there is a man and a woman who both prefer each other to their spouses. So, for example, if Arthur and Barbara both prefer each other to their spouses, then their marriages are at risk.
A matching is stable if it is not unstable. In a stable matching, nobody has an incentive to seek a different spouse, because no two people prefer each other to their spouses. So, if Alan prefers Betsy to his wife, he can't marry her, because she prefers her husband to him.
Everybody is not guaranteed to get their most preferred match. For instance, multiple men might all have the same woman as their highest preference, but only one man can marry her. So, the problem is simply to find a matching that is stable. And, in 1962, David Gale and Lloyd Shapley provided a way to do that.
The Gale-Shapley algorithm consists of a series of rounds. At each round, each unengaged man proposes to the woman that he prefers the most out of all of the women that haven't rejected him yet. Each woman accepts the proposal of the man that she prefers the most, and she rejects every other proposal. If she had already accepted another proposal, then she rejects that proposal, too, and that man becomes unengaged. Then this process continues, until no man is unengaged.
The process is guaranteed to end. If we have N men and N women, then each of the N men can propose to only N women. So, only N ^ 2 proposals can occur. And at least one man proposes at each round. So, the process terminates after O(N ^ 2) rounds.
The resultant matching is guaranteed to be stable. To see this, suppose that it is unstable. Then there is a man (call him "Arthur") and a woman (call her "Barbara") who both prefer each other to their spouses (call them "Cate" and "Dave"). So, Arthur prefers Barbara to his wife Cate, and Barbara prefers Arthur to her husband Dave. But if Arthur prefers Barbara to Cate, then Arthur proposed to Barbara before he proposed to Cate, since men propose to women in order of preference. Barbara may have accepted Arthur's proposal at first, but, because Barbara is married to Dave, Barbara must have rejected Arthur and accepted Dave's proposal, which means that Barbara prefers Dave to Arthur. So, Barbara and Arthur do not both prefer each other to their spouses, because Barbara does not prefer Arthur to her spouse. So, we have a contradiction. Therefore, there is not a man and a woman who both prefer each other to their spouses, and the matching is stable.
As the general formulation of the problem suggests, the stable marriage problem applies to more than just pairing off men and women. It appears in many guises in many places. For example, in 2004, New York City began using a version of the Gale-Shapley algorithm to match eighth graders and NYC public high schools, and the U.S. medical establishment has long used a version of the Gale-Shapley algorithm to match medical students and residency programs.
My implementation of the Gale-Shapley algorithm is up at my GitHub.
Sources:
http://www.ams.org/samplings/feature-column/fc-2015-03