News for hackers. Stuff that matters.

A comment on Ask HN: What's your favorite elegant/beautiful algorithm?.

Re:Ask HN: What's your favorite elegant/beautiful algorithm? by calciphus on Wednesday October 17, 2018 @03:15AM (#18236843)
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...

[ Parent | on HN ]
Re:Ask HN: What's your favorite elegant/beautiful algorithm? by mehrundmehr on Wednesday October 17, 2018 @07:09AM (#18237918)
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!
[ Parent | on HN ]
Re:Ask HN: What's your favorite elegant/beautiful algorithm? by j2kun on Saturday October 20, 2018 @04:57PM (#18265431)
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.

[ Parent | on HN ]
Re:Ask HN: What's your favorite elegant/beautiful algorithm? by Juminuvi on Wednesday October 17, 2018 @08:43AM (#18238383)
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.
[ Parent | on HN ]
Re:Ask HN: What's your favorite elegant/beautiful algorithm? by joker3 on Wednesday October 17, 2018 @12:47PM (#18240901)
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.
[ Parent | on HN ]
Re:Ask HN: What's your favorite elegant/beautiful algorithm? by QML on Wednesday October 17, 2018 @05:28PM (#18243985)
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?
[ Parent | on HN ]
Re:Ask HN: What's your favorite elegant/beautiful algorithm? by andreareina on Thursday October 18, 2018 @11:01PM (#18253972)
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.
[ Parent | on HN ]
Re:Ask HN: What's your favorite elegant/beautiful algorithm? by joker3 on Saturday October 20, 2018 @05:45PM (#18265662)
The issue is that couples want to be placed together. That makes everything trickier than if people just placed independently.
[ Parent | on HN ]
Re:Ask HN: What's your favorite elegant/beautiful algorithm? by zinclozenge on Wednesday October 17, 2018 @11:53AM (#18240244)
Kleinberg and Tardos start off their algorithms book with this problem, except they formulate it in terms of college juniors seeking internships and employers.
[ Parent | on HN ]
Re:Ask HN: What's your favorite elegant/beautiful algorithm? by ajay-d on Wednesday October 17, 2018 @09:21AM (#18238641)
NYC public schools use a version of this too: https://www.nytimes.com/2014/12/07/nyregion/how-game-theory-...
[ Parent | on HN ]
Re:Ask HN: What's your favorite elegant/beautiful algorithm? by alive2007 on Thursday October 18, 2018 @09:23AM (#18248076)
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.
[ Parent | on HN ]