Talk:Stable matching problem: Difference between revisions

Revision as of 12:51, 7 June 2016

Latest revision as of 12:47, 27 June 2025

(16 intermediate revisions by 12 users not shown)

Line 1:

{{WikiProject Gamebanner theoryshell|class=C}}|vital=yes|1=

{{WikiProject Economics|importance=mid}}

{{WikiProject Game theory}}

}}

==Applications==

The first application given is not an application of the stable marriage problem, since a hospital may hire more than one graduate at a time. For this the college admissions algorithm of Gale and Shapley is required. An important application of the stable marriage algorithm is matching organ donors to organ recipients. Many lives have been saved by using this algorithm, also devised by Gale and Shapley.<ref>''Mariages Stable'', Donald E Knuth.</ref><ref>Gale, D.; Shapley, L. S. (1962). "College Admissions and the Stability of Marriage". American Mathematical Monthly 69: 9–14. doi:10.2307/2312726. JSTOR 2312726.</ref>

{{reflist-talk}}

== Optimality of the solution ==

Line 119 ⟶ 123:

[[User:ExpertIdeasBot|ExpertIdeasBot]] ([[User talk:ExpertIdeasBot|talk]]) 12:51, 7 June 2016 (UTC)

== Dr. Romero Medina's comment on this article ==

Dr. Romero Medina has reviewed [https://en.wikipedia.org/w/index.php?title=Stable_marriage_problem&oldid=733328992 this Wikipedia page], and provided us with the following comments to improve its quality:

{{quote|text=<<The stable marriage problem has been stated as follows:>>

Reference Gale, D.; Shapley, L. S. (1962).

Consider the possibility of n=/m.

<<Algorithms for finding solutions to the stable marriage problem have applications in a variety of real-world situations, perhaps the best known of these being in the assignment of graduating medical students to their first hospital appointments>>

Is a case of many to one matching problem different from the one to one case of the marriage problem.

<<This algorithm guarantees that:

Everyone gets married

At the end, there cannot be a man and a woman both unengaged>>

This is under the assumption the every one is admissible to all the agents on the other side of the market.

}}

We hope Wikipedians on this talk page can take advantage of these comments and improve the quality of the article accordingly.

We believe Dr. Romero Medina has expertise on the topic of this article, since he has published relevant scholarly research:

*'''Reference ''': Antonio Romero-Medina & Matteo Triossi, 2011. "Games with capacity manipulation : incentives and Nash equilibria," Economics Working Papers we1125, Universidad Carlos III, Departamento de Economia.

[[User:ExpertIdeasBot|ExpertIdeasBot]] ([[User talk:ExpertIdeasBot|talk]]) 15:46, 24 August 2016 (UTC)

== External links modified ==

Hello fellow Wikipedians,

I have just modified one external link on [[Stable marriage problem]]. Please take a moment to review [[special:diff/815504287|my edit]]. If you have any questions, or need the bot to ignore the links, or the page altogether, please visit [[User:Cyberpower678/FaQs#InternetArchiveBot|this simple FaQ]] for additional information. I made the following changes:

*Added archive https://web.archive.org/web/20080512150525/http://kuznets.fas.harvard.edu/~aroth/alroth.html to http://kuznets.fas.harvard.edu/~aroth/alroth.html

When you have finished reviewing my changes, you may follow the instructions on the template below to fix any issues with the URLs.

{{sourcecheck|checked=false|needhelp=}}

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">—&nbsp;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)