Stable Marriage Algorithm

March is the month that many families waited, anxiously, the result from NRMP, National Resident Matching Program. This centralized “exchange” determined the fate for almost every medical doctors in the US. Residency is the last stop of the long journey to become a real doctor. The program is pivotal to the career of the young graduates. “So, how do they (NRMP) do it?”, many asked this alleged computer software expert.

It is based on the, invented in 1962, Gale-Shapley algorithm. In 2012, Al Roth and Lloyd Shapley (namesake for the algorithm, picture from Economist.com) received Nobel prize for researches based on the this algorithm. It computes the stable matching: that the pairings are as good as they can possibly be.

The algorithm works quite simply: members from one side “propose” according to their preference. The other side will say “maybe” if the current proposal the best, otherwise reject. The subsequent rounds ensue with those yet to be “engaged.” Some of those “maybes” in the previous rounds can be broken when the proposed get a better choice in a later round. The algorithm ends when all proposers received an “engagement.” Supposedly, all pairs will then proceed to get married.

After NRMP, Al Roth and Lloyd Shapley moved on to solve kidney donation matching problem and saved many lives.

There are some well known “cheats” for this algorithm. One side can lock down a partner before the “settle date,” as in “early commitment” in college applications. Theoretically, both sides may lose: the student may miss out a better college and the college may not get the best students. The other cheat is to disguise the preference: rank the person differently than the true desirability. Or one can also reject certain candidates, forcing a no match even one should be possible. The kid ended up going stag because he/she will only go with her/him.

As long as people do not cheat, this algorithm gives the mathematically the best pairings. Sigh… How computers fail to solve the real life problems!?

This entry was posted in Management Thoughts, Peek into my mind. Bookmark the permalink.

Leave a Reply

Your email address will not be published.