2014-05-01

How did GS algorithm come out?

Roth, A. (2008), Deferred acceptance algorithms: history, theory, practice, and open questions, International Journal of Game Theory, 36: 537-569.

In this survey article on the Gale-Shapley's deferred acceptance algorithm, Al Roth mentions (in footnote 3) an amazing story about how GS discovered the algorithm (which of course established the theory of two-sided matchings):

At his birthday celebration in Stony Brook on 12 July 2007, David Gale related the story of his collaboration with Shapley to produce GS by saying that he (Gale) had proposed the model and definition of stability, and had sent to a number of colleagues the conjecture that a stable matching always existed. By return mail, Shapley proposed the deferred acceptance algorithm and the corresponding proof

No comments: