Content deleted Content added
m Dating maintenance tags: {{Cn}} |
→Algorithmic solution: any source on this topic will include this, but might as well reuse the same footnote used for this in Gale–Shapley algorithm |
||
Line 94:
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>{{
| 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
| |||