Content deleted Content added
m Signing comment by 2603:6000:AA4D:C5B8:0:3361:EAF8:97B7 - "" |
r |
||
Line 10:
In this sections it is claimed "The traditional form of the algorithm is optimal for the initiator of the proposals and the stable, suitor-optimal solution may or may not be optimal for the reviewer of the proposals.".
I am not sure this is sufficiently clear. In fact it seems quite misleading. If the initiators (suitors) do not collude, in some cases they end up strictly worse off if the follow the letter of the algorithm. So it is in their interest to agree to lie about their preferences so that they all get better outcomes. <small><span class="autosigned">— Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[User:Mircea85|Mircea85]] ([[User talk:Mircea85|talk]] • [[Special:Contributions/Mircea85|contribs]]) 01:56, 1 August 2015 (UTC)</span></small><!-- Template:Unsigned --> <!--Autosigned by SineBot-->
== Other Algorithms? ==▼
The Gale-Shapley method seems pretty lopsided. Aren't there other algorithms known, particularly ones that treat both groups symmetrically? It doesn't seem too difficult to think of one. For instance, one method would be: (a) sort all pairs of uncommitted individuals in decreasing order of mutual preference (e.g. one if A has a #m on their list, and a has A as #n on their list, then the total preference might be m + n or some other monotonic symmetric function of m and n); and set up a tie-breaking convention to handle ties (or select amongst ties randomly); (b) find the first stable pair on the list and commit the individuals to each other; (c) repeat (a) for the remaining uncommitted individuals. By construction, the result is stable; and the method is symmetric, subject to the symmetry of the tie-breaking convention. <!-- Template:Unsigned IP --><small class="autosigned">— Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/2603:6000:AA4D:C5B8:0:3361:EAF8:97B7|2603:6000:AA4D:C5B8:0:3361:EAF8:97B7]] ([[User talk:2603:6000:AA4D:C5B8:0:3361:EAF8:97B7#top|talk]]) 00:48, 6 May 2022 (UTC)</small> <!--Autosigned by SineBot-->▼
== Uniqueness of solution ==
Line 166 ⟶ 163:
Cheers.—[[User:InternetArchiveBot|'''<span style="color:darkgrey;font-family:monospace">InternetArchiveBot</span>''']] <span style="color:green;font-family:Rockwell">([[User talk:InternetArchiveBot|Report bug]])</span> 06:23, 15 December 2017 (UTC)
▲== Other Algorithms? ==
▲The Gale-Shapley method seems pretty lopsided. Aren't there other algorithms known, particularly ones that treat both groups symmetrically? It doesn't seem too difficult to think of one. For instance, one method would be: (a) sort all pairs of uncommitted individuals in decreasing order of mutual preference (e.g. one if A has a #m on their list, and a has A as #n on their list, then the total preference might be m + n or some other monotonic symmetric function of m and n); and set up a tie-breaking convention to handle ties (or select amongst ties randomly); (b) find the first stable pair on the list and commit the individuals to each other; (c) repeat (a) for the remaining uncommitted individuals. By construction, the result is stable; and the method is symmetric, subject to the symmetry of the tie-breaking convention. <!-- Template:Unsigned IP --><small class="autosigned">— Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/2603:6000:AA4D:C5B8:0:3361:EAF8:97B7|2603:6000:AA4D:C5B8:0:3361:EAF8:97B7]] ([[User talk:2603:6000:AA4D:C5B8:0:3361:EAF8:97B7#top|talk]]) 00:48, 6 May 2022 (UTC)</small> <!--Autosigned by SineBot-->
:Whatever do you mean by a stable pair? A specific matching can have an UNstable pair, but being stable is a property of a whole matching, not a pair. In any case, this talk page is for improvements to our article based on published sources (and since there are so many publications on this topic, the bar to inclusion is pretty high). It is not for speculation on what directions research on this problem should take. —[[User:David Eppstein|David Eppstein]] ([[User talk:David Eppstein|talk]]) 05:19, 6 May 2022 (UTC)
| |||