On the Gale-Shapley Algorithm for Stable Matching
Abstract
Given a community with the same number of men and women,
is it possible to pair them up so that no one will have an
affair? In 1962, David Gale and Lloyd Shapley showed that
the answer is yes. We must only make a few simple assumptions,
and a matching can be created using a relatively simple algorithm.
The goal of these pages is to present the Gale-Shapley algorithm
for stable matching and to introduce some extensions of the
algorithm such as its use in real world and modifications to
handle non-bipartite sets.
Table of Contents
Complete List of References
- [BM1]
Balinski, Michel and Guillaume Ratier.
Graphs and Marriages.
The American Mathematical Monthly, Vol. 105. 430-445. 1989.
- [DL1]
Dubins, L. E. and D. A. Freedman.
Machiavelli and the Gale-Shapley Algorithm.
The American Mathematical Monthly, vol 88. 485-469. 1981.
- [GD1]
Gale, David and Marilda Sotomayor.
Ms. Machiavelli and the Stable Matching Problem.
The American Mathematical Monthly, vol 92. 216-268. 1985.
- [GD2]
Gusfield, Dan and Robert W. Irving.
The Stable Marriage Problem: Structure and Algorithms.
Cambridge: MIT Press. 1989.
- [IS1]
Itoga, Stephen Y.
The Upper Bound for the Stable Marriage Problem.
The Journal of the Operational Research Society, vol. 29. 811-814. 1978.
