The Algorithm

In 1962, David Gale and Lloyd Shapley presented the stable marriage problem in a paper titled “College Admissions and the Stability of Marriage.”[GD1] They posed and answered the question of whether it is possible to find a stable marriage for instance of the stable marriage problem involving n men and n women. In their affirmative answer, they present the following algorithm to find a stable marriage.

Gale-Shapley Algorithm: Let every man propose to the first woman on her list. Any woman with exactly one proposal accepts her suitor provisionally. A woman with more than one proposal chooses the suitor highest on her list. Any rejected man proposes to the next woman on his list. Again, any woman with more than one suitor accepts the highest on her list. The algorithm continues until every man has been accepted or has been rejected by the every woman on his list, at which point each courting couple is declared married.
An example of the execution of the Gale-Shapley algorithm is shown on the next page.

Proposition: The algorithm described above terminates.

Proof: There are n men and n women involved in the algorithm. So a man must propose to at most n women before being accepted or being rejected by the final one. So at most n2 proposals may occur, after which the algorithm terminates.

Proposition: At the termination of the algorithm described above, every man is married.

Proof: Assume towards contradiction that m is an unmarried man at the termination of the G-S algorithm. Then there is some unmarried woman w, since there are the same number of men and women and no one can be married to more than one person. So if a woman gets even one proposal, she is married when the algorithm terminates. So w received no proposals. But, in order for the algorithm to terminate man m must be married, which he is not, or have been rejected by every woman, including w. So m must have proposed to w, which is a contradiction. So m must be married at the termination of the algorithm.

It follows immediately that every woman must be married at the termination of the G-S algorithm.

Theorem: The G-S algorithm produces a stable marriage.

Proof: Assume towards contradiction that the Gale-Shapley algorithm produces an unstable matching for an instance of the stable marriage problem. Then there exists a pair, m, w', who are not matched by the algorithm, such that m prefers w' to w, his assigned partner, and w' prefers m to m', her assigned partner. Then m proposed to w' before he proposed to w, since w' is before w on his list. But a woman can only reject a man if she receives a proposal from a man she prefers. So if a woman rejects a man, she prefers her final marriage partner to the rejected man. So w' prefers m' to m, which is a contradiction. So the G-S algorithm produces a stable matching.

Since the Gale-Shapley algorithm always terminates and its result is a stable matching, there is a stable marriage for every instance of the stable marriage problem.

It is worth noting that the result of the Gale-Shapley algorithm does not depend on the order in which the men propose.