Content deleted Content added
Undid revision 941144552 by BernardoSulzbach (talk). Took out all caps tho I think they help since this it may not be at once obvious that this is so (as evidenced by incorrect original entry and bernardo's 'maybe' instead of 'correct') |
Citation bot (talk | contribs) m Alter: journal. Add: jstor. | You can use this bot yourself. Report bugs here. | Activated by User:AManWithNoPlan | All pages linked from User:AManWithNoPlan/sandbox2 | via #UCB_webform_linked |
||
Line 88:
* This process is repeated until everyone is engaged.
This algorithm is guaranteed to produce a stable marriage for all participants in time <math>O(n^2)</math> where <math>n</math> is the number of men or women.<ref name="IwamaMiyazaki2008">{{cite journal|last1=Iwama|first1=Kazuo|author1-link=Kazuo Iwama (computer scientist)|last2=Miyazaki|first2=Shuichi|title=A Survey of the Stable Marriage Problem and Its Variants|year=2008|pages=131–136|doi=10.1109/ICKS.2008.7|journal=International Conference on Informatics Education and Research for Knowledge-Circulating Society (
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.
Line 101:
| 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
| |||