Talk:Stable marriage problem

From Wikipedia, the free encyclopedia

You have new messages (last change).

[edit] Clarification request

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

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

[edit] 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)
Retrieved from "http://en.wikipedia.org../../../s/t/a/Talk%7EStable_marriage_problem_73b5.html"