Monday, February 05, 2007
No Single-hood allowed!
I finally started studying this semester and the 1st lecture in my algorithms class was on Matching algorithms. So here's the 1st problem that we discussed in class for which an algorithmic solution is required -
There are n men and n women each of who has a clear ranking of who they wish to be paired with. We need to match the men and women such that there are no singles remaining and there is no polygamy. Also it should be such that no man prefers another woman who also prefers him over her current partner. In mathematical terms, the pairing should be perfect and stable.
We start with each man "proposing" to the woman on the top of his list. The woman at this point is not quite sure if she wants to marry this man but since she is also not sure which other men have her on the top of their preference list she may run the risk of "being too choosy and ending up alone" or "compromising and getting engaged".
The solution as taught to us in class? The optimal solution suggested that the women compromise and get engaged but they would be free to break this engagement and get engaged to another man who proposes and is higher on her list. The solution went on to prove that though it seems like the men are getting a rough deal with the women dumping them for any man she prefers, they are actually more likely to get a better deal than the women. If the women had done the proposing they would have been better off.
Ah! now you see what got me started on this blog!
There are n men and n women each of who has a clear ranking of who they wish to be paired with. We need to match the men and women such that there are no singles remaining and there is no polygamy. Also it should be such that no man prefers another woman who also prefers him over her current partner. In mathematical terms, the pairing should be perfect and stable.
We start with each man "proposing" to the woman on the top of his list. The woman at this point is not quite sure if she wants to marry this man but since she is also not sure which other men have her on the top of their preference list she may run the risk of "being too choosy and ending up alone" or "compromising and getting engaged".
The solution as taught to us in class? The optimal solution suggested that the women compromise and get engaged but they would be free to break this engagement and get engaged to another man who proposes and is higher on her list. The solution went on to prove that though it seems like the men are getting a rough deal with the women dumping them for any man she prefers, they are actually more likely to get a better deal than the women. If the women had done the proposing they would have been better off.
Ah! now you see what got me started on this blog!
I know a lot of my friends are getting married nowadays. And a lot of times I wonder if its to the man on the top of their list or just the best man who proposed. And if in reality that is the recommended solution. I mean - say yes to the first guy who asks coz you never know if you can do better. And it scares me. I grew up believing in the fairy tale, the perfect guy with eyes only for me and of course we lived happily ever after! But I'm older now, and I've seen that the perfect guy was not quite so perfect and we didn't live happily ever after. I've also been "proposed to" and by some amazing guys but I didn't say yes because I still wanted to believe in the fairy tale and they were not my "perfect guy", my top of the preference list.
Its also a little pathetic that an Algorithms Design class can make start thinking about this! Of course, the solution in class claims that everyone is happy because they get the best match possible. But we all know reality is a little different. I'm not quite sure why but over the last few months it has been worrying me that my fairy tale has still not come true. Yet I'm not at all convinced that ranking the possibilities and settling for the best match possible is the way to go either.
I guess life's solutions aren't as perfect or stable as the solutions for algorithmic problems. And maybe I need to re-iterate to myself the conclusion I reached in my last write-up.
"I know I need something, someone, somewhere. But I also know I’m not going to find it any time soon so I have to be patient and wait. And make the best of today. I know I will be OK."
PS: I also need a new roommate! My current one keeps pushing me to write and hence I end up with pointless posts like this one on my blog :P
by nutty at 5:39 PM |
1 Comments:
u actually went ahead n bitched abt me on ur blog!!! Now its official---The WAR is on!!! N for starters i am not makin fish for u---ever!!!
Post a Comment
<< Home