eliminated: '''stable marriage problem''' as lead id. as the identifier - with: Stable_marriage_problem#Algorithmic_solution "In 1962 - stable marriage problem and make all marriages stable" G & S: "college admissions" is first title and paper begins with discussion of college not mar. - Talk:List_of_algorithms#G.-S._a.
{{Short description|Pairing where no unchosen pair prefers each other over their choice}}
In [[mathematics]], [[economics]], and [[computer science]], the '''stable marriagematching problem''' (also<ref>{{cite '''stableweb matching|author=Tesler, problem''')G.|url=https://mathweb.ucsd.edu/~gptesler/154/slides/154_galeshapley_20-handout.pdf|website=mathweb.ucsd.edu|title=Ch. 5.9: Gale-Shapley Algorithm|date= 2020|publisher=[[University of California San Diego]]|access-date=26 April 2025|url-status=|archive-url=|archive-date=}}</ref><ref>{{cite web|last1=Kleinberg|first1=Jon |last2=Tardos|first2=Éva |url=https://www.cs.princeton.edu/~wayne/kleinberg-tardos/pdf/01StableMatching.pdf|website=www.cs.princeton.edu|title=Algorithmn Design: 1. Stable Matching|date= 2005|publisher=[[Pearson PLC|Pearson]]-[[Addison Wesley]]: [[Princeton University]]|access-date=26 April 2025|url-status=|archive-url=|archive-date=}}</ref><ref>{{cite web |last1=Goel|first1=Ashish |editor1-last=Ramseyer|editor1-first=Geo |url=https://web.stanford.edu/~ashishg/cs261/win21/notes/l5_note.pdf|website=web.stanford.edu|title=CS261 Winter 2018- 2019 Lecture 5: Gale-Shapley Algorith|date= 21 January 2019|publisher=[[Stanford University]]|access-date=26 April 2025|url-status=|archive-url=|archive-date=}}</ref> is the problem of finding a stable matching between two equally sized sets of elements given an ordering of preferences for each element. A matching is a [[bijection]] from the elements of one set to the elements of the other set. A matching is ''not'' stable if:
{{Ordered list|list-style-type=numeric
Line 85:
{{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 in different groups, in the context of mencollege admissions and women,individuals wanting marriage it is always possible to solve theas stablematched marriagecouples problemandto make all marriagesresultant pairings / matched factors 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"):
