Content deleted Content added
m Add assessment for importance |
|||
| (36 intermediate revisions by 21 users not shown) | |||
Line 1:
{{WikiProject banner shell|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 ==
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-->
== Uniqueness of solution ==
Line 28 ⟶ 38:
I removed this section. I doubt that it is even true that it is quite likely you will get someone high on your preference list (what are the chances that you were high on their preference list?), let alone the stuff about beauty and happiness. [[User:192.75.48.150|192.75.48.150]] 19:17, 21 September 2006 (UTC)
If someone could supply useful references for this it would be helpful, something along the lines of how the algo fails or does little when everybody ranks the choices the same. In public school assignments (a variation of H/R), parents tend to adhere to a rigid pecking order, but I haven't seen a metric that describes this aspect of the input.
:The algorithm never "fails", in that it always terminates in finite time and the result is always stable. Using the algorithm, the members of the "suitor" group all get their best possible choice for any stable pairing, and the "suitees" get their worst possible choice for any stable pairing. If all the members of group A have the same preferences, then there is only one stable pairing, which can be produced by the following process: each member of group B, in order of highest to lowest rank (according to group A preferences), chooses the best possible partner from the members of group A not yet chosen. So in the high school example, the highest ranked school would get to choose the students it wanted most, then the next-highest ranked would choose its preferred students from those not chosen by the highest ranked, and so on. [[User:Augurar|Augurar]] ([[User talk:Augurar|talk]]) 07:18, 14 February 2012 (UTC)
== Solutions for constrained problems ==
Line 35 ⟶ 49:
:: Not quite. Alice and Bob might not be each other's first choice, but their marriage needs to remain stable given the pairings we find for the rest of the people. In particular, each man that Alice likes better than Bob needs to be paired with a woman he likes better than Alice, ''and'' each woman that Bobs likes better than alice must be paired with a man she likes better than Bob. One can construct examples where this combined condition holds neither for the male-optimal nor for the female-optimal pairing of for the rest ignoring Alice and Bob, but still is possible for some ''third'' stable pairing. [[User:Henning Makholm|Henning Makholm]] 14:05, 26 October 2006 (UTC)
::: So couldn't you just exclude the four persons, do the GS algorithm and then check if the pairings are still stable? Computationally, that would still be in O(m*n). --[[User:Kraymer|Kraymer]] ([[User talk:Kraymer|talk]]) 14:34, 7 February 2010 (UTC)
:::: No; see the last sentence in my 26 October comment. –[[User:Henning Makholm|Henning Makholm]] ([[User talk:Henning Makholm|talk]]) 02:50, 22 October 2010 (UTC)
== Choices of methaphorical gender ==
Line 78 ⟶ 93:
Even though it produces the same result, the pseudo-code algorithm is not written the same way as it is described in words. It does not handle "rounds" properly as they were described, as it does not contain the part of the process where "Each woman then considers all her suitors and tells the one she most prefers Maybe and all the rest of them No." According to the algorithm as specified, the woman says yes to every man who proposes, only to dump him if she gets a better offer, and a man receives a "no" answer only by being engaged and subsequently dumped.
I do realize that the pseudo-code algorithm produces the same result as the one described in words, but aren't algorithms supposed to be written as described
== Related Problems ==
Hey I was wondering if anyone knows the name of the related problem where Women have preferences and Men do not (i.e. a sharing problem with 1-1 matchings and no divisibility). Does this just fall under matching? http://en.wikipedia.org/wiki/Matching_(graph_theory) <span style="font-size: smaller;" class="autosigned">— Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/70.70.148.137|70.70.148.137]] ([[User talk:70.70.148.137|talk]]) 08:17, 30 August 2012 (UTC)</span><!-- Template:Unsigned IP --> <!--Autosigned by SineBot-->
== Software implementation ==
I think it useful to add links to open source software that implements the Gale Shapely algorithm described in the article. To this end I suggest to add the following in the External links section:
*[http://cran.r-project.org/web/packages/matchingMarkets/ Gale-Shapley Algorithm in R package matchingMarkets]
[[User:Mtching|Mtching]] ([[User talk:Mtching|talk]]) 19:40, 10 December 2014 (UTC)
== Dr. Klijn's comment on this article ==
Dr. Klijn has reviewed [https://en.wikipedia.org/w/index.php?title=Stable_marriage_problem&oldid=720801008 this Wikipedia page], and provided us with the following comments to improve its quality:
{{quote|text=The largest (!) part of the article is about the case of stable marriage with indifference(S?). Even though the case of indifferences is studied in the literature, the three notions of stability and their algorithms receive too much attention. Probably it is more interesting to say more about the lattice structure of the set of stable matchings (i.e., extend the section "optimality of the solution") and discuss incentives / strategic aspects of the gale-shapley algorithm (also known as the deferred acceptance algorithm!). I think it would also of interest to mention that variants of the gale-shapley algorithm are actually used in real-life applications. For instance, medical interns in the US, or school choice in Boston and New York.}}
We hope Wikipedians on this talk page can take advantage of these comments and improve the quality of the article accordingly.
Dr. Klijn has published scholarly research which seems to be relevant to this Wikipedia article:
*'''Reference ''': Peter Biro & Flip Klijn, 2011. "Matching with Couples: a Multidisciplinary Survey," IEHAS Discussion Papers 1139, Institute of Economics, Centre for Economic and Regional Studies, Hungarian Academy of Sciences.
[[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">— 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)
| |||