Talk:Stable marriage problem

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.

References

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. — Preceding unsigned comment added by Mircea85 (talk • contribs) 01:56, 1 August 2015 (UTC)

Uniqueness of solution

The example with the optimal/pessimal matches of the three pairs of people ABC and XYZ indicates that there is at least the possibility of a match not being unique. In this case, there were three pairs of people and three stable solutions. It is obvious that there exist cases where there is one and only one stable solution (where everybody gets their first choice). Is there a way to determine a priori how many stable solutions a given set of preference lists will yield? Iron Condor (talk) 01:54, 25 August 2010 (UTC)

Clarification request

The opening sentence seems to contradict the restatement of problem in the second paragraph:

a stable matching — a matching in which no element of the first matched set prefers an element of the second matched set that also prefers the first element...

Given n men and n women, where each person has ranked all members of the opposite sex with a unique number between 1 and n in order of preference, marry the men and women off such that there are no two people of opposite sex who would both rather have each other than their current partners. If there are no such people, all the marriages are "stable".

The first sentence says a stable matching is one where no a in E1 prefers a b in E2 such that b also prefers a. It should be "that b also prefers an a' in E1 such that a != a'.

"At the end, it is not possible for a man and a woman (call them Alice and Bob) to both prefer each other to their current partners."

What the heck does "both prefer each other to their current partners" mean? Aren't they 'currently their current partners' in the end? That doesn't seem like good english to me :[

It means that while Bob may have prefered Alice, Alice prefers her current partner to Bob. Or Alice may have preferred Bob, but Bob prefers his current partner. You can't have Bob preferring Alice to his current partner and Alice perferring Bob to her current partner.

Remember that Alice and Bob are NOT partners.

Observations

The SMP can be used to illustrate certain social phenomena, such as the effect of beauty on partner choice. When the preferences of the men and women are purely random, everyone is quite likely to get a partner that is high on their preference list. However, if the preferences tend to aim at certain beautiful individuals, a person's chances of getting a partner they really want is drastically reduced, as their top choices are massively in demand. Hence, it has been said that the SMP proves that beauty just makes everyone unhappy.

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. 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. Augurar (talk) 07:18, 14 February 2012 (UTC)

Solutions for constrained problems

Anybody know if there are computationally feasible algorithms for solving marriage problems with constraints, e.g. "Is there any stable pairing that matches Alice with Bob and Claire with Dave?" Henning Makholm 20:17, 15 October 2006 (UTC)

Your example is still just the Stable Marriage problem, using a list that excludes Alice, Bob, Claire and Dave. Tom Duff 01:56, 25 October 2006 (UTC)

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. 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). --Kraymer (talk) 14:34, 7 February 2010 (UTC)

No; see the last sentence in my 26 October comment. –Henning Makholm (talk) 02:50, 22 October 2010 (UTC)

Choices of methaphorical gender

A description of the "hospitals/residents problem" was recently added to the article. Whereas the main stable-marriage problem is symmetric in the two sexes, the "hospitals/residents problem" is not; one seeks an 1-to-n relation rather than a 1-to-1 one. I am a bit bothered that the article feels the need to explicitly assign the role of metaphorical "women" to one of the sides in the asymmetric problem (though I am pleasantly confused by the unconventional choice of women as the promiscuous sex). Can this way of stating the problem be supported by sources? And even if it can, is it really necessary to choose which is which just for explaining the problem? Henning Makholm 00:36, 26 January 2007 (UTC)

As far as I understand this, the only reason they are 'women' are because they are being proposed to. As such, they fit the role of the 'women' in the original problem. If you switched around the definitions of the roles of the men and women in the original problem, the roles would also be reversed in this problem. I think. --80.229.152.246 21:27, 12 June 2007 (UTC)

The original problem does not treat "men" and "women" differently. Only the particular solution algorithm that is described does. –Henning Makholm 22:50, 12 June 2007 (UTC)

Order of computation

What is the order of computation of this algorithm? Is it an optimal algorithm? -- Beland 14:56, 12 June 2007 (UTC)

O(n*m) --128.175.226.103 (talk) 21:25, 11 February 2008 (UTC)

The issue of optimal/pessimal choice

Frankly, this entire section is incorrect. A man will get his first choice of woman if and only if she likes him over all the other men who like her; and a woman will get her first choice of man, again, if and only if he likes her over all the other women he can choose from.

In both cases, the chance of getting a first choice depends entirely on the other person's agreement. If W X Y and Z all want A, and A likes W, then A will get W either way. If W X Y and Z are asking, A will select W from them; if W X Y and Z are being asked, A will go to W first.

Or, to put it in intuitive terms, if a woman doesn't get asked by the man she wants, then she'd have been jilted by him even if she'd been doing the asking and had got to him first.

The idea that this algorithm is somehow 'sexist' is sheer genderist nonsense. —Preceding unsigned comment added by 87.194.82.30 (talk) 14:22, 24 April 2009 (UTC)

There's clearly a different choice process with both actors, so it's not surprising there are different outcomes, but it's clear this section needs work. The definition of Pessimal at the very least needs work. It's clear that a woman can get her preferred choice (say, she's his first and he's her first). This one example renders the statement, "Thus women will always prefer another match in any stable pairing over their match in a male-optimal pairing." clearly false. It may be that the only way it could deviate from a mutual-optimality it towards male-optimality, but that's not what is said. Also, there are some at least very confusing statements such as "Also consider an arbitrary stable pairing S, where M and W are not paired. Because G is male-optimal, M prefers W to his match in S." Male-optimality would reduce the chance that M perfers someone he is not matched with, and certainly not force it. The section should be rewritten using a simple 2 or three person ranking to make these claims explicit. It should be removed in the mean time. —Preceding unsigned comment added by 98.208.58.216 (talk) 03:15, 29 July 2010 (UTC)

actually, the whole first piece on male optimality is non-sense. "Also note that, since woman W is man M's optimal partner, there exists some stable pairing S where man M is paired with woman W." No, the pairing is stable if and only if there exists no other man W would rather be paired with that would want to be paired with her, so a stable pairing of M and W might not exist. —Preceding unsigned comment added by Dalhamir (talk • contribs) 03:26, 29 July 2010 (UTC)

okay, figured out what the original poster probably meant. It can be mutual optimal, but there is an advantage to initiator. I'll write out the whole scenario and post it, loosing the needlessly inflammatory connotations to sexism. —Preceding unsigned comment added by Dalhamir (talk • contribs) 06:31, 29 July 2010 (UTC)

See also additions

I was jumping thru the See also sections at the end of the article, and i found that the article Secretary problem links to this page, but not vice-versa. Is that an addition which should be added? Could there be other articles which are also related?? Thekappen (talk) 01:14, 3 November 2009 (UTC)

The approach in the Secretary problem is quite a bit different, from what I saw at first glance. Topically related it would fit as a reference/see-also to the hospital-residents problem. --Kraymer (talk) 14:48, 7 February 2010 (UTC)

If only all math articles were so accessible!

What a spectacularly readable article this is, for a non-mathematician like myself. The algorithm is explained clearly and concisely, in English, without relying entirely on the mysterious-to-the-layman mathemagical runes that normally bedevil even the most trivial of mathematical wiki articles. I feel that encyclopaedic articles should explain a topic to the layman sufficiently well that they could then explain that topic to someone else, without needing to read a dozen other articles to effectively learn a new language first. For me at least, this article fulfils that requirement perfectly, and in my opinion sets a high bar for other articles to reach. DewiMorgan (talk) 12:06, 24 July 2010 (UTC)

The Algorithm Section Seems Incorrect to Me

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? After all, a different algorithm that produces the same result is still a different algorithm. 76.103.252.206 (talk) 16:53, 7 September 2010 (UTC)

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) — Preceding unsigned comment added by 70.70.148.137 (talk) 08:17, 30 August 2012 (UTC)

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:

• Gale-Shapley Algorithm in R package matchingMarkets

Mtching (talk) 19:40, 10 December 2014 (UTC)

Dr. Klijn's comment on this article

Dr. Klijn has reviewed this Wikipedia page, and provided us with the following comments to improve its quality:

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.

ExpertIdeasBot (talk) 12:51, 7 June 2016 (UTC)

Dr. Romero Medina's comment on this article

Dr. Romero Medina has reviewed this Wikipedia page, and provided us with the following comments to improve its quality:

<<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.

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 my edit. If you have any questions, or need the bot to ignore the links, or the page altogether, please visit 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.

This message was posted before February 2018. After February 2018, "External links modified" talk page sections are no longer generated or monitored by InternetArchiveBot. No special action is required regarding these talk page notices, other than regular verification using the archive tool instructions below. Editors have permission to delete these "External links modified" talk page sections if they want to de-clutter talk pages, but see the RfC before doing mass systematic removals. This message is updated dynamically through the template {{source check}} (last update: 5 June 2024).

• If you have discovered URLs which were erroneously considered dead by the bot, you can report them with this tool.
• If you found an error with any archives or the URLs themselves, you can fix them with this tool.

Cheers.—InternetArchiveBot (Report bug) 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. — Preceding unsigned comment added by 2603:6000:AA4D:C5B8:0:3361:EAF8:97B7 (talk) 00:48, 6 May 2022 (UTC)

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. —David Eppstein (talk) 05:19, 6 May 2022 (UTC)