I came across these terms recently. No, it is not about "real" stable marriages...Thats a generalisation that I wouldnt venture into. This is called the bi-partite matching problem. What the hell is that?
To simplify things, let us assume that you have 5 men and 5 women. Assume that each woman have a ranked list of preferences in marrying from among the 5 men. There are some interesting conditions to ponder. The first condition is about pairing. How do we pair the men and women in the best way possible so that the ranked list of each women is honored and everyone is treated fairly. The other condition is a little twist to the situation. At any time, one could assume that only a subset of men really propose a woman and the woman is given the choice of selecting only among the proposed set of individuals. The other condition ( a more realistic assumption..;) which contradicts the previous assumption, but added to make the problem simpler) is that each man proposes to the set of all women available (in this case 5 women) hoping that he will gain acceptance from atleast one. The final condition is that more than one woman has the same preferred man in their ranked list, or rather, the same ranked list for all men.
The solution to this problem is only mathematically interesting and I dont want to delve into that. But, I was thinking about the reality of the situation. Comprehending solutions for mathematical fairness is the ideality that a society would want to strive for. While, in reality, fairness is a very subjective term and preferences are a subjective term too. Quantifying subjective terms to derive mathematical solutions might only make a scheduler problem get solved. In the global scheme of things, I could only hope that each scheduler cycle depicts a life cycle and over many cycles, fairness is achieved for all the contentious resources in the society...
Saturday, June 03, 2006
Stable Marriage Problem
Posted by Suresh Sankaralingam at 9:44 AM
Subscribe to:
Post Comments (Atom)
Posts
8 comments:
I could understand about men and women pairing....After that...Hmmmm..I guess I would have to say..
Yes...Yes....Thankyou...( As Rajinikanth says)..:-)
Anyway,I think quantifying subjective terms is tough and achieving stability and fairness in our society over life cycles...interesting...
I see that Mindframes is back to form! As for pairing, maybe that is what the jaadhagams tried to do, and in the process started involving the celestial bodies to make things a little more interesting, and you have what we have today in India!
I couldn't decide whether this is mathematical model or life example.
I could blame my impatience while reading this article.
Yet, I am still in that CONFUSION stage :)
hehehe...dude u pose some interesting problemsss...hmm well i missed the fun here...
okie lets think about this problem a bit more deeper...we have a group of 5 men and 5 women..we do not know who wants to propose to whom and also that not everybody among them wants to propose...the question is natural preferences...
okie now the problem is of common knowledge...lets say we bring in a neutral party...the women can tell their preferences to the third party and the men can also give the same...for instance consider the case of a marriage bureau..all parties can give their preferences and if a unique match for each and every person is available then the problem is solved and everybody is happy..
notice that under this situation there is no loss of efficiency because there is distortion for any of the parties involved...
what happens when there is not unique pairing..what happens if one women wants to have rights to more than one man...then the suggested alternative of each man proposing to the other will not be a good idea...because every player in the game has incentive to deviate and as long as such incentives remain, we can never achieve an efficient solution..
one way to solve this problem is how to assign property rights to each of the parties...hold a tournament and the pairings will be decided based on who wins...therefore if two women like the same man..then a tournament between the two women ensures that the winnes take the guy..then there is no strict incentive for the other to deviate...we can of course do this recursively and arrive at efficient solutions...however it should be noted that this would still be a second best approach...
Anup,
u r in the right direction with the solution. In theory, this is a scheduler's problem (scheduler being the third party and men and women being input and output ports that like to be connected). The scheduler tries to be establish fairness. "Fairness" can be achieved through several ways. One way is to just round-robin. Another way is to do random selection. Another way is to do a weighted-round robin and so on. But, all these measures of fairness works only if a statistical mean of many such proposals and acceptances are measured.
However, in the case of marriage, that is obviously not the case...:)
@ Mindframes: good point...but let me clarify here...what we need to do is a mechanism that is not really based on chance...when we talk about fairness here we need not take it from a statistical perspective...in fact if we go in that direction then other issues pop up...for instance if the tie break was a toss of the coin, it is quite possible that the coin can be biased...this gives the player an incentive to deviate...therefore it is imperative that mixed strategies (randomizing) is not allowed...only pure strategies can be played which means we need a mechanism that tests some innate characteristics or something like that...
the designers problem here is to align the incentives of the two parties...therefore why not a game of skill or some other which establishes fairness but not in the random sense...for instance just for the sake of clarification lets assume that all the players are neutral and no one is particularly skilled at something...lets say this one girl likes all the guys but decides that this being unfair she will marry the person who can can beat the others in an arm wrestling contest (this is just one illustration..we can come up with any kind of mechanism far more realistic but at the same time not based on pure chance)...here innate characteristics of the players come into the picture...think of the swayamvara system that was held ages ago...thats a fair game tooo..skill was tested and winner takes home the princess..
I dont understand how a skill or a game will establish fairness. To me, it just broadens or rather narrows the spectrum of preference by adding more preferences.
If no one is particularly skilled in a chosen game/skill, then, I dont see how different will it be from a random selection..;)
oops..i guess i was not being clear...okie what i intended was people have their own skills, but the skills are public information...if only one person's skill is known to the designer of the game then designing a game in favour of or against that person will not be considered fair...however if the skills are common knowledge, then when choosing to accept the game, the player knowing that he might not be as skilled as the other still decides to play...now when i meant particularly skilled, think of a player like tiger woods...if ur up against tiger woods in a golf tournament, there is no way the other players will agree that it is fair..that was what i intended to convey...sorry for the confusion..but this discussion is real fun..
Post a Comment