Hacker News Reader

Comment by calciphus | Hacker News Reader

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#Soluti...

View on HN

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!

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

I think they are lumped together because they are both "mechanism design" problems that were studied by Roth and part of his prize.

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.

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 has all the details.

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?

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.

The issue is that couples want to be placed together. That makes everything trickier than if people just placed independently.

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

NYC public schools use a version of this too: https://www.nytimes.com/2014/12/07/nyregion/how-game-theory-...

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.

Reply on news.ycombinator.com