How Did GS Algorithm Come Out? | どうやってGSアルゴリズムは生まれたか？

英文ブログ[2014/5/1]より転載

コメント　マッチング理論のパイオニアである、超偉大なGale-Shapley論文の誕生秘話です。まさに２人の共同作業であったことが分かりますね。
あっ、今後も英文ブログの過去記事からちょいちょい転載予定です。どうぞよろしくお願いします^^

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