3 ms·

The Gale-Shapley Algorithm to solve the "Stable Marriage" problem. 2012 Nobel Prize in Economic Sciences for its wide-ranging use in medicine, education, and re

The Gale-Shapley Algorithm to solve the "Stable Marriage" problem. 2012 Nobel Prize in Economic Sciences for its wide-ranging use in medicine, education, and resource allocation. It's fairly easy to implement a basic version of it, feels intuitively obvious once explained, and has been applied to everything from organ transplants to student placement in elementary schools. Really, any place you have two groups where individual members have a preferential ranking of the other. https://en.wikipedia.org/wiki/Stable_marriage_problem#Solution https://en.wikipedia.org/wiki/Stable_marriage_problem#Soluti...

mehrundmehr 8y ago
I remember when this "Nobel Prize" was announced I immediately started reading the paper and trying to figure out how it could work in code. It seems like it could have amazing economic potential if put to a good use, but until your comment I hand't known of any real-world uses outside of organ transplantation. Very excited to see it being appreciated by more computer scientists! I need to look into it again for sure!
- j2kun 8y ago
  The organ transplant algorithm is not really that similar to the stable marriage algorithm. It's a different mechanism based on the housing allocation problem. See https://www.nber.org/papers/w10002 https://www.nber.org/papers/w10002 I think they are lumped together because they are both "mechanism design" problems that were studied by Roth and part of his prize.
Juminuvi 8y ago
Interesting! I knew that med school applicants were accepted on some sort of ranking and matching process but didn't realize there was a real algorithm behind it. This, or one similar, seems to be what's behind it.
- joker3 8y ago
  There's no matching process at the beginning of medical school, but there is for assigning med school graduates to residencies. This variant of the problem is NP-hard, so there's no exact solution, but matching still works pretty well. https://web.stanford.edu/~alroth/papers/rothperansonaer.PDF https://web.stanford.edu/~alroth/papers/rothperansonaer.PDF has all the details.
  - QML 8y ago
    When you are referring to this "variant", are you referring to maximal matching, or bipartite matching when the number of people and schools don't equal?
    - andreareina 8y ago
      Not the parent, but I think they refer to the fact that with admissions, matches are permanent (once a student accepts a school's offer, said offer can't be rescinded), while Gale-Shapely requires provisional pairings until all the rounds have been gone through and a final result is available.
    - joker3 8y ago
      The issue is that couples want to be placed together. That makes everything trickier than if people just placed independently.
ajay-d 8y ago
NYC public schools use a version of this too: https://www.nytimes.com/2014/12/07/nyregion/how-game-theory-helped-improve-new-york-city-high-school-application-process.html https://www.nytimes.com/2014/12/07/nyregion/how-game-theory-...
zinclozenge 8y ago
Kleinberg and Tardos start off their algorithms book with this problem, except they formulate it in terms of college juniors seeking internships and employers.
alive2007 8y ago
The real shocker is that it took until 2012 for this pivotal algorithm to win a Nobel Prize. David Gale had passed by then! The Nobel committee must be backlogged to Hell and back.

mehrundmehr 8y ago

I remember when this "Nobel Prize" was announced I immediately started reading the paper and trying to figure out how it could work in code. It seems like it could have amazing economic potential if put to a good use, but until your comment I hand't known of any real-world uses outside of organ transplantation. Very excited to see it being appreciated by more computer scientists! I need to look into it again for sure!

j2kun 8y ago
The organ transplant algorithm is not really that similar to the stable marriage algorithm. It's a different mechanism based on the housing allocation problem. See https://www.nber.org/papers/w10002 https://www.nber.org/papers/w10002 I think they are lumped together because they are both "mechanism design" problems that were studied by Roth and part of his prize.

Juminuvi 8y ago

Interesting! I knew that med school applicants were accepted on some sort of ranking and matching process but didn't realize there was a real algorithm behind it. This, or one similar, seems to be what's behind it.

joker3 8y ago
There's no matching process at the beginning of medical school, but there is for assigning med school graduates to residencies. This variant of the problem is NP-hard, so there's no exact solution, but matching still works pretty well. https://web.stanford.edu/~alroth/papers/rothperansonaer.PDF https://web.stanford.edu/~alroth/papers/rothperansonaer.PDF has all the details.
- QML 8y ago
  When you are referring to this "variant", are you referring to maximal matching, or bipartite matching when the number of people and schools don't equal?
  - andreareina 8y ago
    Not the parent, but I think they refer to the fact that with admissions, matches are permanent (once a student accepts a school's offer, said offer can't be rescinded), while Gale-Shapely requires provisional pairings until all the rounds have been gone through and a final result is available.
  - joker3 8y ago
    The issue is that couples want to be placed together. That makes everything trickier than if people just placed independently.

ajay-d 8y ago

NYC public schools use a version of this too: https://www.nytimes.com/2014/12/07/nyregion/how-game-theory-helped-improve-new-york-city-high-school-application-process.html https://www.nytimes.com/2014/12/07/nyregion/how-game-theory-...

zinclozenge 8y ago

Kleinberg and Tardos start off their algorithms book with this problem, except they formulate it in terms of college juniors seeking internships and employers.

alive2007 8y ago

The real shocker is that it took until 2012 for this pivotal algorithm to win a Nobel Prize. David Gale had passed by then! The Nobel committee must be backlogged to Hell and back.