The stable marriage problem
There are men and women, and each person ranks all members of the other group. A perfect matching is unstable if some man and woman both prefer each other to their assigned partners. Prove that a stable matching always exists, and give an algorithm that finds one in time.
History and references
Solved in 1962 by David Gale and Lloyd Shapley.
Gale and Shapley posed and solved the problem in 1962, in the context of college admissions and marriage. In their deferred acceptance algorithm each unmatched man proposes to the best woman he has not yet asked, and each woman keeps the best proposal she has received so far and rejects the others. Each man proposes to each woman at most once, so the process stops after at most proposals. The result is stable, because any woman a man prefers to his final partner has already rejected him for someone she likes better. Among all stable matchings it gives every proposer the best partner possible. Variants are used to place medical residents in hospitals, and Shapley shared the 2012 Nobel Memorial Prize in Economic Sciences with Alvin Roth for this line of work.
References
Solutions 0
Sign in or create an account to publish a solution