Talk:Stable matching problem

	This article is part of WikiProject Game theory, an attempt to improve, grow, and standardize Wikipedia's articles related to Game theory. We need your help! Join in \| Fix a red link \| Add content \| Weigh inGame theoryWikipedia:WikiProject Game theoryTemplate:WikiProject Game theorygame theory
C	This article has been rated as C-class on Wikipedia's content assessment scale.
???	This article has not yet received a rating on the importance scale.

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)[reply]

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)[reply]

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)[reply]

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)[reply]

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)[reply]

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)[reply]

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)[reply]

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

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)[reply]

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)[reply]

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)[reply]

Order of computation

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

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

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)[reply]

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)[reply]

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)[reply]

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)[reply]

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)[reply]

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)[reply]

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 — Preceding unsigned comment added by Mtching (talk • contribs) 19:24, 10 December 2014 (UTC)[reply]