The Stable Marriage Problem

Discussion in 'Relationships, Discrimination, and Jealousy' started by Principessa, Mar 2, 2008.

  1. Principessa

    Gold Member

    Joined:
    Nov 22, 2006
    Messages:
    19,494
    Likes Received:
    28
    Gender:
    Female

    Computer scientists and economists will perhaps disregard this post as pretentious. But I think that the Stable Matching problem is really cool and easily formulated, so I am going to go ahead with it anyway.

    Assume, for whatever reason, that you are holding a grand ball-dancing event in which you invite 'n' men and 'n' women. Each man has a strict preference ordering over the women and analogously, every woman has a strict preference ordering over the men. Your objective is to match men with women such that the pairing has a certain 'stability' quality. For the sake of this problem, assume that you have been sent back about twenty years in time and the main pairing mechanism is still heterosexual). A given pairing is said to be unstable if there exist two pairs (Amit, Puja) and (John, Alice) say, such that Amit prefers Alice to Puja and Alice prefers Amit to John (so that both Amit and Alice have incentive to cheaton their partners). Given the fickle and uncompromising nature of men, clearly instability is an undesirable property and you would like to avoid the anguish it ensues at all cost. So your task as a match maker is to pair up men and women, one on one such that the resulting pairing is stable in the sense that there are no unstable pairs. It is interesting to note that it is not sufficient for Amit to prefer Alice to Puja to make the pairing unstable. In other words, Alice must reciprocate this bias for instability.

    The first question that you might be interested in is, do stable matchings always exist?
    Answer: Yes (was shown by Gale and Shapley in 1962).
    Caveat: The proof breaks down for mixed (homosexual + heterosexual) preferences.

    The next question that you would like to resolve, given that you are organizing this ball is whether there is some easy (efficient) way in which you can determine this matching. In other words, you are interested in an efficient algorithm that computes a stable matching. The solution (also given by Gale and Shapley in 1962) is a simple and elegant one.

    Here is the algorithm. Imagine that the men and women are standing at either end of the room. The algorithm is the Men Propose, Women Reject algorithm (much like the real world).

    It proceeds in rounds. In the first round, every man proposes to his most desired woman. Among the proposals that a woman receives in this round (she might receive none), she (temporarily) accepts her most desired man, and rejects everyone else. In subsequent rounds, each unpaired man (and hence one who was rejected in the previous round) proposes to the most desired woman who has not yet rejected him. In case a woman, currently matched with John receives a proposal from a man she prefers to John, she rejects John (after having led him on initially by saying yes to him in an earlier round!) and accepts this other man. The algorithm terminates when all men are paired. And this works and produces a stable matching! How much it resembles real world dynamics in a modern day society - I leave to your imagination!

    PS (thanks to Vivek for pointing this out): It turns out that the Men Propose, Women Reject algorithm is optimal for men in the following sense: the algorithm produces a matching in which every man lands up with the best possible woman he could have been with in any stable matching.

    Moral of the story: Always hit on the best girl even if you don't have the confidence, get ditched a few times, until you settle with the best possible woman you could possibly get.

    Gale-Shapley algorithm
    Stable Marriage Problem
     
  2. Charles Finn

    Gold Member

    Joined:
    Feb 20, 2006
    Messages:
    2,538
    Albums:
    3
    Likes Received:
    29
    Gender:
    Male
    Location:
    Toledo Ohio
    so yet again the gays and the bi's get left out
    thanks alot
     
  3. Ed69

    Gold Member

    Joined:
    Jul 26, 2006
    Messages:
    2,617
    Likes Received:
    211
    Gender:
    Male
    Location:
    Talent (OR, US)
    Sheesh!Lets complicate it why don't we?All I had to do was buy a motorcycle helmet to meet the right girl!
     
  4. Jovial

    Gold Member

    Joined:
    Apr 11, 2006
    Messages:
    2,404
    Albums:
    1
    Likes Received:
    5
    Gender:
    Male
    Location:
    CA
    What's left out of the original post, but explained on the wikipedia entry for Stable Marriage Problem, is that the algorithm of men proposing and women accepting/rejecting results in a male-optimal, female-pessimal stable pairing.

    So of all ways to pair the men and women up in a stable way, the men end up paired with their best choice, but the women end up with their worst choice.

    A simple example is two men (Adam, Brian) and two women (Nancy, Mary).
    Say Adam prefers Nancy over Mary, and Brain prefer Mary over Nancy.
    Say Nancy prefers Brian over Adam, and Mary prefers Adam over Brian.
    Their prefer orders are then:
    Adam {Nancy, Mary}
    Brian {Mary, Nancy}
    Nancy {Brian, Adam}
    Mary {Adam, Brian}

    In the men proposing algorithm the pairing ends up being:
    Adam with Nancy, and Brian with Mary.

    The men both end up with their first choice, but the women end up with their second choice.

    The other pairing (Adam with Mary, Brian with Nancy) is also stable, and here the women get their first choice and the men get their second choice. But this doesn't happen in the men ask, women accept/reject algorithm.


    If we relate this to the real world, it would appear that the etiquette of men doing the asking out/proposing and women accepting/rejecting is more favorable for men than women.
     
  5. Principessa

    Gold Member

    Joined:
    Nov 22, 2006
    Messages:
    19,494
    Likes Received:
    28
    Gender:
    Female
    I disagree; because as in life, women always have the right to reject one man when a better one comes along. :biggrin1: It's ridiculous to assume on the basis of one algorithm that every women ends up wit her third and not best choice. There are too many variables at play.
     
  6. Jovial

    Gold Member

    Joined:
    Apr 11, 2006
    Messages:
    2,404
    Albums:
    1
    Likes Received:
    5
    Gender:
    Male
    Location:
    CA
    Once a stable pairing of men and women occurs there are no more men coming along. The better man won't come along because he is already paired with someone higher on his preference list. It, of course, assumes he starts at the top of his list and works his way down until a girl accepts him.

    This obviously is a much simpler model than the real world, but it still illustrates that in general the people doing the asking end up better off than the people just accepting/rejecting.
     
  7. Ed69

    Gold Member

    Joined:
    Jul 26, 2006
    Messages:
    2,617
    Likes Received:
    211
    Gender:
    Male
    Location:
    Talent (OR, US)
    Lord have mercy this is complicating life. WHY ASK WHY and just accept that finding your soul mate is by chance. My hubby bought a helmet at the shop I worked at, My grandfather met my gradmother once at a church social and decided she was the one. Married her without even really courting her. They were married for 62 years.

    It is simple stop looking for love and enjoy life. The one you should be with will come along when you least expect it.

    And What about he gay and bi part of this problem. OR do the same rules apply.

    ed69 girls, Bad me I forgot to sign ED out and sign me in.
     
  8. D_Ed69s girl

    D_Ed69s girl <img border="0" src="/images/badges/member.gif" wi

    Joined:
    Oct 7, 2007
    Messages:
    272
    Likes Received:
    0
    :rolleyes:Sorry Ed69, Didn't mean to use your name but I just forgot to log you out before I logged in. Promise it won't happen again. BY the way love your new AVATAR.:biggrin1:
     
  9. Jovial

    Gold Member

    Joined:
    Apr 11, 2006
    Messages:
    2,404
    Albums:
    1
    Likes Received:
    5
    Gender:
    Male
    Location:
    CA
    WHY ASK WHY? The unexamined life is not worth living. - Socrates
    Some people enjoy life by thinking about such things.
    It is different for homosexual couples. A stable pairing may not exist!

    In the heterosexual case, we can always pair men with women in a stable way. There is no man and woman in different marriages that would prefer to be with each other over their current spouses. Plenty of people would want to cheat with someone they prefer more than their current spouse, but the feeling is not mutual. Therefore, the pairings are stable.

    In the homosexual case, it turns out that there is no guarantee that a stable pairing of people exists. This depends on the prefer order of all the people. What this means is that no matter how you pair the men up, there may be 2 men in different marriages that are willing to cheat with each other because they both prefer each other over their current spouse.

    Here is an example that illustrates this fact. Four men numbered 1-4, with their preference order:
    1 {3, 2, 4}
    2 {1, 3, 4}
    3 {2, 1, 4}
    4 {1, 2, 3}
    You can not pair them in a stable way:
    1/2 and 3/4 means 1 and 3 may cheat with each other.
    1/3 and 2/4 means 2 and 3 may cheat with each other.
    1/4 and 2/3 means 1 and 2 may cheat with each other.
     
  10. B_quietguy

    B_quietguy New Member

    Joined:
    Sep 17, 2005
    Messages:
    1,286
    Likes Received:
    5
    Gender:
    Male
    Location:
    Bay Area, California
    I find this post pretentious. It certainly does not go about describing how I choose partners.

    The simple solution is polyamory. Each person can choose the partner(s) that support and nurture him or herself - regardless of whether they choose just 1, 2, 3 or 7. If any relationship becomes unhealthy, or the participants change and become incompatible, then they return to being friends. The end result is that each person's stable relationships endure - whether they have 1 or 4 or 5, and the unstable ones break up.

    Enforced monogamy just leads to less than ideal situation for everyone.

    Generalize much about the nature of all men? Make put-downs of all men much? This may describe some men some of the time, and some women some of the time, but I would never say this about all men.
     
  11. Principessa

    Gold Member

    Joined:
    Nov 22, 2006
    Messages:
    19,494
    Likes Received:
    28
    Gender:
    Female
     
  12. D_Ed69s girl

    D_Ed69s girl <img border="0" src="/images/badges/member.gif" wi

    Joined:
    Oct 7, 2007
    Messages:
    272
    Likes Received:
    0
    :confused::confused:What do we have a bunch of statistician, cause really I find this stuff extremely one sided. Really were on earth did you people get your numbers from. I have met several gay couples you have a more stable relationship than most hetrosexual couples. I mean really no one can predict human nature. I watch pleanty of shows on animal planet and Discovery that have shown me that. I also feel like it is totally not fair to exclude all sexual preferences just to make it easier for your stats.
     
  13. Jovial

    Gold Member

    Joined:
    Apr 11, 2006
    Messages:
    2,404
    Albums:
    1
    Likes Received:
    5
    Gender:
    Male
    Location:
    CA
    I was, of course, referring to the simplified problem of pairing like people together where each person has a simple preference order. This is nowhere near accurate to real life. But it is still a starting point to trying to understand the situation. From here one can develop a more accurate way to model human interactions.

    These problems don't have to be about human sexual relationships. For example, pairing college students as roommates in 2-person dorm rooms is similar to the "homosexual" pairing problem. The "heterosexual" pairing problem could also apply to a situation of pairing people at a company with interns or something like that.
     
  14. SandraSmithCarver

    SandraSmithCarver New Member

    Joined:
    Dec 28, 2007
    Messages:
    527
    Albums:
    1
    Likes Received:
    18
    Gender:
    Female
    Location:
    St Louis Mo
    Oh i don't know,, if your gay? the same rules can apply to men, can't it?
    Bi? same thing
     
  15. Jovial

    Gold Member

    Joined:
    Apr 11, 2006
    Messages:
    2,404
    Albums:
    1
    Likes Received:
    5
    Gender:
    Male
    Location:
    CA
    I think you are taking this too seriously. I think they just call it the Stable Marriage Problem so that it's easy to remember, not because it accurately reflects human sexual relationships. From wikipedia:
    In mathematics, the stable marriage problem (SMP) is the problem of finding 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.
    The heterosexual and homosexual couples you know have nothing to do with this simple mathematical problem or the results that have been proved about it. And this type of problem can be applied to many other areas.

    I found at least two books devoted to the Stable Marriage Problem, so this type of problem must be fairly important:
    Stable Marriage and Its Relation to Other Combinatorial Problems: An Introduction to the Mathematical Analysis of Algorithms (Crm Proceedings & Lecture Notes, V. 10): Donald E. Knuth

    The Stable Marriage Problem: Structure and Algorithms (Foundations of Computing): Dan Gusfield,Robert W. Irving
     
Draft saved Draft deleted