Stable marriage problem - Wikipedia, the free encyclopedia

http://en.wikipedia.org/wiki/Stable_marriage_problem

In 1962, David Gale and Lloyd Shapley proved that, for any equal number of men and women, it is always possible to solve the SMP and make all marriages stable. They presented an algorithm to do so.^[2][3]

The game is V-Bi or Y-Ro, it is high on time and low on energy so the players are cooperating honestly. This is because the women have more time to change her mind and can say maybe, they are then like Bi consumers in the I-O market. The offerers here then would be Iv and might try to use deception to counter her ability to choose from all of them.

For example each man wants to bluff and cheat to get the best wife, or make the best deal in the I-O market. Each Bi consumer can say maybe then go to other stores to see if there are better deals. The men can then disguise their defects so the women often make the wrong decision. This is like Iv agents in the market ripping off Bi consumers and hoping they won't renege. 

Car yards often have this problem where a Bi customer wants to walk into each yard one by one and say maybe, the defect is they usually buy from the last yard who undercuts or otherwise trashes the reputation of the others.  

To balance this game the offerers might not give the women an option either, they say maybe as well unless both agree to a deal immediately. Often a car yard will not make an offer at all for this reason. Iv agents in the I-O market then can make implicit offers by having their wares on show with prices allowing the Bi women to say maybe and shop around. However this only works on the posted prices and not if the Iv offerers will make further concealed discounts.

Also Iv competitors can cause chaos in this game, for example with 5 men and 5 women the most handsome man proposes to the ugliest women who accepts and then dismisses the others. Now he has prevented his competitor from getting the woman he wants, if he profits from this more than he loses by not getting the optimum woman then he wins in a relative way on the margin. 

This also happens in markets, for example a car yard might deliberately make a high offer to a Bi consumer on their lot because he knows they will buy from the last yard and so he makes the Bi consumer pay more. Each yard unless they can make Bi agree to buy with them will then make a non optimum offer so Bi has not beaten everyone down as much in price.

The outcome would be unstable with booms and busts if the husbands are deceptive to make profits against each other, people who are not suited end up married to stop other marriages and then crash in divorce. Also the women can be deceptive making it an Iv-B or Oy-R game, they might deceptively look better as happens in real life to get better offers. 

Also the game can be nontransitive, for example Bob wants Alice the most and proposes but Alice wants Charlie and so accepts Bob first and the  dumps him later if Charlie offers. Charlie wants Debbie who accepts him but wants Eddie, she accepts him and dumps Charlie later if Eddie offers. Eddie wants Fiona who wants Bob, she takes Eddie and will dump him if Bob comes available.

So even though each woman had all the options in front of her before deciding they each end up with a sub optimal mate. the women might all decide to dump their men but the nontransitivity means the men would offer the same again of they could. it might however come out well for the women if the right ones were the second choice, however this just means the women get their first choice and the men their second instead of vice versa. In the real world this often happens in relationships as in real games, for example in tennis A can beat B, B can beat C, and C can beat A.


 So the game can develop vicious circles including because only half of it is random, also women might hold onto a bad choice just because the others end up with worse ones so over time she will win out. For example she might be the last one to get divorced.  


There can also be a divorce game where one man wants to get a divorce and the woman holds them up with maybe until she arranges a better marriage. The one who is unhappy ends up worse off because they can't divorce until the woman gets a better deal. 







The Gale-Shapley algorithm involves a number of "rounds" (or "iterations"). In the first round, first a) each unengaged man proposes to the woman he prefers most, and then b) each woman replies "maybe" to her suitor she most prefers and "no" to all other suitors. She is then provisionally "engaged" to the suitor she most prefers so far, and that suitor is likewise provisionally engaged to her. In each subsequent round, first a) each unengaged man proposes to the most-preferred woman to whom he has not yet proposed (regardless of whether the woman is already engaged), and then b) each woman replies "maybe" to her suitor she most prefers (whether her existing provisional partner or someone else) and rejects the rest (again, perhaps including her current provisional partner). The provisional nature of engagements preserves the right of an already-engaged woman to "trade up" (and, in the process, to "jilt" her until-then partner).

This algorithm guarantees that:

Everyone gets married 

Once a woman becomes engaged, she is always engaged to someone. So, at the end, there cannot be a man and a woman both unengaged, as he must have proposed to her at some point (since a man will eventually propose to everyone, if necessary) and, being unengaged, she would have had to have said yes.

The marriages are stable 

Let Alice be a woman and Bob be a man who are both engaged, but not to each other. Upon completion of the algorithm, it is not possible for both Alice and Bob to prefer each other over their current partners. If Bob prefers Alice to his current partner, he must have proposed to Alice before he proposed to his current partner. If Alice accepted his proposal, yet is not married to him at the end, she must have dumped him for someone she likes more, and therefore doesn't like Bob more than her current partner. If Alice rejected his proposal, she was already with someone she liked more than Bob.