Hacker Newsnew | past | comments | ask | show | jobs | submitlogin
Flash game illustrating the Gale-Shapley algorithm (math.berkeley.edu)
57 points by john_horton on July 13, 2011 | hide | past | favorite | 14 comments


Wow, that explanation is so well done.. it's a pleasure to learn like this.


Its 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


That's amazing. I can't believe the algorithm was so simple!


I 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).


This algorithm is also used in a certain University in Ontario's Co-op Job Board.


Ugh, don't remind me. Now THAT's a student-pessimistic system if I ever saw one.


very good tutorial - any non technical developer can follow and is still covering very well the subject. Was it a student project?


That algorithm seems super trivial. It's the only logical way to solve the problem, is it not?


Stuff 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_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/ and http://lesswrong.com/lw/3pv/freaky_unfairness/


Trivial correction: It's neg-entropy, not entropy.

And interestingly, in current computers entropy is the valued commodity, while neg-entropy doesn't cost extra.


The 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.


Generally, when you understand something fully, it does seem trivial.


what happens if they realized they didn't really liked each other after marriage?


paparazzi... and then they wind up on the next season of the bachelor/bachelorette...




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: