Content deleted Content added
m Dating maintenance tags: {{Cn}} |
|||
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.{{cn|date=May 2024}}
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
| |||