Al Roth: An economist who saves lives

The BBC ran a story on the work of Al Roth and Lloyd Shapley on an algorithm to solve the "stable marriage problem".  Given a group of men and women, is there a way of pairing them up such everyone has a "stable match", such that no pairings exist where both parties prefer each other rather than their current relationship.  UC Berkley has created an interactive website where you can walk through the steps and explore the process in depth.

There is no evidence that the work of Roth and Shapley was inspired by biology.  However, I see this as an example of how simple algorithms can lead to optimal solutions that would normally be considered hard to solve.  The algorithm is not necessarily efficient - rather, it should be judged on whether it is effective.  When I first tried the UC Berkely demo, I was able to find a solution on the second attempt by 'eyeballing' the board.   We are not dealing with an 'all-knowing' matchmaker.  Although each person can rate/rank their prospective spouses, they have no knowledge of anyone else's preferences.  A comparable scenario is speeding dating followed by pairing off - a recipe for a rather fluid environment that may remain unstable for a considerable period of time.

The article describes three cases whether the algorithm has been used: matching kidney donors, matching students to schools and also medical students to hospitals.  Unfortunately, the article does not explain the 'before' and 'after' scenarios.  The last two examples are a 'many to few' matching situation, quite different from the 'stable marriage' or kidney matching situations.  If anyone has more information, I would be very interested in hearing about it. 

If you are at all interested, I recommend exploring the UC Berkeley interactive website.  Try to recreate the situation where you have only a narrow view of the 'board'. 

Your rating: None
Login or register to tag items