[[File:Gale-Shapley.gif|thumb|right|Animation showing an example of the Gale–Shapley algorithm]]
In 1962, [[David Gale]] and [[Lloyd 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.<ref>{{cite journal |first1=D. |last1=Gale |first2=L. S. |last2=Shapley |title=College Admissions and the Stability of Marriage |journal=[[American Mathematical Monthly]] |volume=69 |issue=1 |pages=9–14 |year=1962 |jstor=2312726 |doi=10.2307/2312726 |url=http://www.dtic.mil/get-tr-doc/pdf?AD=AD0251958 |access-date=2019-11-20 |archive-date=2017-09-25 |archive-url=https://web.archive.org/web/20170925172517/http://www.dtic.mil/get-tr-doc/pdf?AD=AD0251958 |url-status=dead }}</ref><ref>[[Harry Mairson]]: "The Stable Marriage Problem", ''The Brandeis Review'' 12, 1992 ([http://www1.cs.columbia.edu/~evs/intro/stable/writeup.html online]).</ref> In 1984, [[Alvin E. Roth]] observed that essentially the same algorithm had already been in practical use since the early 1950s, in the [[National Resident Matching Program]].<ref>{{cite journal|last=Bergstrom|first=Theodore C.|date=June 1992|issue=2|journal=[[Journal of Economic Literature]]|jstor=2727713|pages=896–898|title=Review of ''Two-Sided Matching: A Study in Game-Theoretic Modeling and Analysis'' by A. E. Roth and M. A. O. Sotomayor|volume=30}}</ref>
The '''Gale–Shapley algorithm''' involves a number of "rounds" (or "[[iteration]]s"):
