Flash game illustrating the Gale-Shapley algorithm

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

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

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/

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.

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