Content deleted Content added
→Optimality of the solution: Fixed grammar Tags: Mobile edit Mobile app edit Android app edit |
→Solution: in practical use 10 years before its discovery |
||
Line 16:
==Solution==
[[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 |first=D. |last=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 }}</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"):
| |||