Monday, October 15, 2012

Matching Nobel Prizes

This week Bill and I have traveled to Germany for the Dagstuhl Seminar on Algebraic and Combinatorial Methods in Computational Complexity. Plenty of newly minted Nobel laureates here, winners of the Peace Prize last Friday. But this post celebrates today's winners of the Economics Prize, Al Roth and Lloyd Shapley for their work in matching theory that has made a difference in the real world.

In 1962, Shapley and David Gale created the first algorithm that finds stable marriages. David Gale would surely have shared this award had he not passed away in 2008. Nicole Immorlica's guest obit of Gale nicely describes this work and its applications including matching medical students with residencies.

Al Roth uses matching algorithms for a variety of projects, most notably creating large scale kidney exchanges, saving lives with algorithmic mechanism design. Doesn't get cooler than that.


  1. There are Nobel laureates at your Dagstuhl seminar?

  2. Anon #1: Yes. Everyone in the EU (and hence EU citizens at Dagstuhl) is a Nobel prize winner, thanks to last Friday's award of the Peace prize.

  3. This is dumb as "you" as the Time "Person of the Year" a while back.

  4. Don't be stupid. The post might make a small joke, but in reality the Nobel was awarded to EU as an organization, not the Europeans themselves. Remember that EU states are independent, with many differences, unlike the US model where different states are autonomous but are united under one country.

    The UN got awarded a Peace Prize (the one awarded on 2001 illustrates my point best, I guess) does this mean that every country participating in the UN got the prize? Then I guess we awarded some dictators with peace prizes, which I guess is really really bad.

    I guess it is easy to forget now, but try to remember the state of Europe in the 50's . The EU (and its precedessors that it evolved from) played a fundamental part in uniting Europe and make it more or less a conflict-free zone.

  5. Can you please elaborate in Algorithmic Mechanism Design in solving a series of Kidney transplants?