Romancing in Mathland

So, you thought the only things mathematicians and computer scientists romanced was complicated graphs and even more complicated algorithms.

Now well, even though I may not doubt the verity of the above statement, there are perhaps more facets to a mathematicians life and to his imagination. And I would like a describe one, which will perhaps convince you that romance has not left the mathematicians.

So, one day long long ago there lived a mathematician. Surely, like all of his ilk, he was immersed in creating Game Trees, but he never found a "game" for himself. All his artificial and real intelligence combined could not get him an acquaintance with the Eighth Queen, despite an exhaustive search through and through the chessboard. His Rubik cube didn't seem to have any solution, all the generations of mathematicians before him Newton et al, seemed to have deserted him in this crucial juncture of life. Even though he sometimes dreamt of conjugal bliss, the problem of finding a stable member of the opposite sex seemed to be not just NP-complete, but he could not find any solutions in P-space.

Undaunted, he set about to find an algorithm by which he could find a "stable" match with the woman who would complete his graph. It was a difficult task to do it alone, so took resort to distributed search. Given n men and n women he tried to find the most "stable" match for them. Mathematicians usually try to disambiguate everything before they start looking for answers, and he decided to do the same:

• If a man x and a woman y like each other more than their existing partners, they might switch in favour of each other, and leave their current partners.
• In that case, we say that the pair (x,y) is an unstable pair.
• A perfect matching is a stable matching if it yields no unstable pair.

Try as he might, he could not understand how to find the most stable girl for himself, who would not leave him despite his wierd mathematical ideas and wierder computer scientific actions.

At that time, there lived two great mathematical saints Gale and Shapley, whose fame spread far and wide, and mathematics students from the seven continents came to seek their blessings and their algorithms. Our dearest mathematician decided that matters were now out of his hands, and it required "divine" algorithms. St. Gale and St. Shapley heard his problem and they had just the right decision procedure to suit his needs. They proposed the "Gale-Shapley Proposal Algorithm":

Input: Preference rankings by each of n men and n women.
Iteration:

1. Each man proposes to the woman highest on his preference list, who has not previously not rejected him
2. If each woman receives exactly one proposal, say "yes", go straight to the two great Saints and request them to sanctify their love.
3. Otherwise, every woman receiving more than one proposal rejects all of them except the one highest on her preference list.
4. Every woman receiving a proposal says "maybe" to the most attractive proposal received.

The iteration is repeated and the Saints were able to use all the formal logic at their disposal to prove that their scheme of mass marriage would be able to produce a lasting marriages with cute kids.

And they differentiated and integrated happily ever after ... would be a nice ending to the mathematicians story, but alas! it wasn't to be! A lady mathematicians soon discovered that the schema was biased towards the men, because if all of them had distinct crushes, every woman would get just one proposal which she would be bound to accept. She decided to revolt against the "Man's World", gather all her allies, statistically find out the probability of winning, optimise her troops to achieve the lowest cost function and the largest victory (it was a multi-objective optimisation). She built an inverted index to ensure that the troops were posted in the correct location always, she created genetic algorithms to design the best weapons ever, she took the help of artificial neural networks to make sure the enemy's location always was known to the tenth of a millimeter in her specially designed infrared hypercube radar (outsourced for design to India), she arranged her soldiers in Ant colonies and left them to create the best of the breed attack strategies ... (okay okay I know its getting just a little too ludicrous with every clause!)

Anyway, the men were also obviously preparing hard for it. With St. Gale and St. Shapley in charge, and our very own beloved mathematician at the helm of the attacking troops, they worked out the best strategies to build a huuuuuge fortress, with a fuzzy moat all around it, and an even fuzzier mist surrounding it.

And ever since, the students of IIT Kharagpur have been sitting in this castle of theirs, with all the girls all around the world, and none in Kharagpur [the few that are are quick to ensnare a few chaps into getting out of their halls in the nights]. And ever since, your beloved little mathematician has been blogging so that one day, just one day, the seige will get over, and some girl would be kind enough to overlook the war of the worlds and say "yes".