Content deleted Content added
→Solution: no reason for cap |
same change as in main |
||
Line 58:
== Strategic considerations ==
The GS algorithm 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>{{
| 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}}</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}}</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.
| |||