Editing Stable matching problem (section)

==Algorithmic solution==
{{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 college admissions and individuals wanting marriage it is always possible to solve as matched couples  to make all resultant 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"):
* In the first round, first ''a'') each unengaged man proposes to the woman he prefers most, and then ''b'') each woman replies "maybe" to her suitor she most prefers and "no" to all other suitors. She is then provisionally "engaged" to the suitor she most prefers so far, and that suitor is likewise provisionally engaged to her. 
* In each subsequent round, first ''a'') each unengaged man proposes to the most-preferred woman to whom he has not yet proposed (regardless of whether the woman is already engaged), and then ''b'') each woman replies "maybe" if she is currently not engaged or if she prefers this man over her current provisional partner (in this case, she rejects her current provisional partner who becomes unengaged).  The provisional nature of engagements preserves the right of an already-engaged woman to "trade up" (and, in the process, to "jilt" her until-then partner).
* This process is repeated until everyone is engaged.

This algorithm is guaranteed to produce a stable marriage for all participants in [[Big O notation|time]] <math>O(n^2)</math> where <math>n</math> is the number of men or women.<ref name="IwamaMiyazaki2008">{{cite conference|last1=Iwama|first1=Kazuo|author1-link=Kazuo Iwama (computer scientist)|last2=Miyazaki|first2=Shuichi|contribution=A Survey of the Stable Marriage Problem and Its Variants|year=2008|pages=131–136|doi=10.1109/ICKS.2008.7|title=International Conference on Informatics Education and Research for Knowledge-Circulating Society (ICKS 2008)|publisher=IEEE|isbn=978-0-7695-3128-1|hdl=2433/226940|hdl-access=free}}</ref>

Among all possible different stable matchings, it always yields the one that is best for all men among all stable matchings, and worst for all women.<ref>{{cite book
 | last = Erickson | first = Jeff
 | contribution = 4.5 Stable matching
 | contribution-url = https://jeffe.cs.illinois.edu/teaching/algorithms/book/04-greedy.pdf
 | access-date = 2023-12-19
 | date = June 2019
 | pages = 170–176
 | publisher = University of Illinois
 | title = Algorithms}}</ref>

It is a [[truthful mechanism]] from the point of view of men (the proposing side), i.e., no man can get a better matching for himself by misrepresenting his preferences. Moreover, the GS algorithm is even ''group-strategy proof'' for men, i.e., no coalition of men can coordinate a misrepresentation of their preferences such that all men in the coalition are strictly better-off.<ref>{{cite journal
 | last1 = Dubins | first1 = L. E. | author1-link = Lester Dubins
 | last2 = Freedman | first2 = D. A. | author2-link = David A. Freedman
 | doi = 10.2307/2321753
 | issue = 7
 | journal = [[American Mathematical Monthly]]
 | mr = 628016
 | pages = 485–494
 | title = Machiavelli and the Gale–Shapley algorithm
 | volume = 88
 | year = 1981| jstor = 2321753 }}</ref> However, it is possible for some coalition to misrepresent their preferences such that some men are better-off and the other men retain the same partner.<ref>{{cite conference
 | last = Huang | first = Chien-Chung
 | editor1-last = Azar | editor1-first = Yossi
 | editor2-last = Erlebach | editor2-first = Thomas
 | contribution = Cheating by men in the Gale–Shapley stable matching algorithm
 | doi = 10.1007/11841036_39
 | mr = 2347162
 | pages = 418–431
 | publisher = Springer
 | series = Lecture Notes in Computer Science
 | title = Algorithms – ESA 2006, 14th Annual European Symposium, Zurich, Switzerland, September 11–13, 2006, Proceedings
 | volume = 4168
 | year = 2006| isbn = 978-3-540-38875-3
 }}</ref>
The GS algorithm is non-truthful for the women (the reviewing side): each woman may be able to misrepresent her preferences and get a better match.