Stable matching problem

In mathematics, the Stable Marriage Problem (hereafter: SMP) is as follows:

Given n men and n women, where each person has ranked all members of the opposite sex with a unique number between 1 and n in order of preference, marry the men and women off such that there are no two people of opposite sex who would both rather have each other than their current partners. If there are no such people, all the marriages are "stable".

Solving the problem

In 1962, Gale and Shapley proved that, for any equal number of men and women, it is always possible to solve the SMP and make all marriages stable. They presented an algorithm to do so.

The Gale-Shapley algorithm involves a number of "rounds" (or "iterations") where each unengaged man "proposes" to the most-preferred woman that he has not yet proposed to, and she accepts or rejects him based on whether she is already engaged to someone she prefers. If she is unengaged, or engaged to a man lower down her preference list than her new suitor, she accepts the proposal (and in the latter case, the other man becomes unengaged again).

This algorithm guarantees that:

Everyone gets married: Once a woman becomes engaged, she is always engaged to someone. So, at the end, there cannot be a man and a woman both unengaged, as he must have proposed to her at some point (since a man will eventually propose to everyone, if necessary) and, being unengaged, she would have to have said yes.

The marriages are stable: At the end, it is not possible for a man and a woman (call them Alice and Bob) to both prefer each other to their current partners. This is easy to show. If Bob prefers Alice to his current partner, he must have proposed to Alice before he proposed to his current partner. If Alice accepted his proposal, yet is not married to him at the end, she must have dumped him for someone she likes more (since women only switch partners to increase their happiness). If Alice rejected his proposal, she was already with someone she liked more than Bob.

Real world applications

There are a number of real world applications for the Gale-Shapley solution. For example, their algorithm has been used to pair graduating medical students with hospital jobs.

Other observations

The SMP can be used to illustrate certain social phenomena, such as the effect of beauty on partner choice. When the preferences of the men and women are purely random, everyone is quite likely to get a partner that is high on their preference list. However, if the preferences tend to aim at certain beautiful individuals, a person's chances of getting a partner they really want is drastically reduced, as their top choices are massively in demand. Hence, it has been said that the SMP proves that beauty just makes everyone unhappy.

Solving the problem

Real world applications

Other observations

Further reading