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
???	This article has not yet received a rating on Wikipedia's content assessment scale.
???	This article has not yet received a rating on the importance scale.

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]

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]

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, so a stable pairing of M and W might not exist.

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]