Stable matching problem: Difference between revisions

Content deleted Content added
Pairing where no unchosen pair prefers each other over their choice
GreenC bot (talk | contribs)
Rescued 1 archive link. Wayback Medic 2.5
Line 83:
{{main|Gale–Shapley algorithm}}
[[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 name=gs62>{{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 |archive-url=https://web.archive.org/web/20170925172517/http://www.dtic.mil/get-tr-doc/pdf?AD=AD0251958 |url-status=dead |archive-date=September 25, 2017 }}</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>
 
The [[Gale–Shapley algorithm]] (also known as the deferred acceptance algorithm) involves a number of "rounds" (or "[[iteration]]s"):