math algorithm matching See / WVU

This year Alvin Roth and Lloyd Shapley are splitting the Nobel Prize for Economics, and it's about time.

Each has made a huge impact on both the theory and the real world practice of economics, and have saved thousands of lives in doing so. 

Shapley is the more senior of the pair, and scores the prize for his work on — of all things — dating and marriage. 

Shapley is favored for something called the Stable Marriage Problem, which goes like this:

Say that you have a population of an equal number of men and women, all of whom are dating someone in the set at the moment but want to get married to an ideal partner down the line.

Each person has ranked every member of the opposite sex in order of preference. The goal is to make a stable marriage for every single person in the group. 

A solution occurs when everyone in the set is married to someone, and no two people of the opposite sex prefer one another to their current partner. For instance, let's say Fred is with Wilma and Barney is with Betty. If both Barney and Wilma would prefer to be married to one another rather than their current spouses, the marriages aren't "stable." 

Shapley designed an algorithm with David Gale to solve this problem in 1962. It's iterative, which means that the algorithm runs several times before a stable situation is found. The algorithm guarantees that everyone gets married and all marriages are stable. 

Here's the process: 

  • First, the algorithm matches each man to the highest ranked woman whom he hasn't yet proposed to. 
  • If that woman is free, then they become engaged. If not, the algorithm checks to see whether she prefers her current fiance or the new suitor. 
  • If she prefers the suitor, her current fiance becomes single and the new pair becomes engaged. 
  • If she prefers her fiance, they remain engaged and the suitor moves down to the next on the list. 
  • This process is repeated for each man. By the end, everyone is engaged and every pairing is stable.

The goal here is stability, not perfection.

While this wife-swapping may sound callous, the solution Shapley found was later expanded by Roth to make kidney donor matching, New York City High School matching, and the program that matches first year residents to hospitals that want them. 

That's why these men got the prize.

Shapley's work on matching problem theory and Roth's work on implementing them in the real world is an excellent example of practical economics at its best.

You can't sell a kidney, so a typical market can't work with the kidney donor allocation system. Roth's upgrade to the kidney exchange system — the same one that resulted in a simultaneous six-way kidney transplant in 2008 — saves lives every day.