4 ms·
Flash game illustrating the Gale-Shapley algorithm
- socialist_coder 15y agoThat algorithm seems super trivial. It's the only logical way to solve the problem, is it not?
- gwern 15y agoStuff often looks trivial - in retrospect. But it's not the only logical way, just a good way. It breaks down or does odd things in some cases (this is why the whole field of 'cooperative game theory' exists, because this sort of thing is not that easy). For example, how would you divide up entropy, one of the most fundamental and scarce resources we possess? Shapley seems to work but there are some troubling parts: http://lesswrong.com/lw/12v/fair_division_of_blackhole_negentropy_an/ http://lesswrong.com/lw/12v/fair_division_of_blackhole_negen... Does it work with all division problems, such as when agents can inspect each other's source code/rules? http://lesswrong.com/lw/13y/freaky_fairness/ http://lesswrong.com/lw/13y/freaky_fairness/ and http://lesswrong.com/lw/3pv/freaky_unfairness/ http://lesswrong.com/lw/3pv/freaky_unfairness/
- eru 15y agoTrivial correction: It's neg-entropy, not entropy. And interestingly, in current computers entropy is the valued commodity, while neg-entropy doesn't cost extra.
- psykotic 15y agoThe algorithm was invented to match residents with hospitals. Before it was standardized in the 1950s, a far worse method had been widely used, so from that vantage point it cannot be entirely obvious. Often what makes a solution seem trivial in retrospect is that the problem has been whittled down to its crystalline essence and placed in its proper context. As Alan Kay likes to say, point of view is worth 80 IQ points.
- lucian1900 15y agoGenerally, when you understand something fully, it does seem trivial.
- wccrawford 15y agoThat's amazing. I can't believe the algorithm was so simple!
- john_horton 15y agoI was impressed by the simplicity as well. I think Gale & Shapley's intellectual contribution was not so much in proposing the algorithm, but in proving that a stable match is alway possible (and that this algorithm generates one such match).
- gabaix 15y agovery good tutorial - any non technical developer can follow and is still covering very well the subject. Was it a student project?
- longlistener 15y agoIts interesting, and now that I understand the game it makes sense and is cool. But it literally took me a few minutes to figure out why male 'C' liked woman 'b' better, and I kept thinking "what am I missing?". Its the order of the bubbles on the side, and as an educational game it would be useful to describe this
- pokoleo 15y agoThis algorithm is also used in a certain University in Ontario's Co-op Job Board.
- Kapelson 15y agoUgh, don't remind me. Now THAT's a student-pessimistic system if I ever saw one.
- teyc 15y agowhat happens if they realized they didn't really liked each other after marriage?
- teeray 15y agopaparazzi... and then they wind up on the next season of the bachelor/bachelorette...
- d0m 15y agoWow, that explanation is so well done.. it's a pleasure to learn like this.