数学的に解説！お見合いパーティーで「1番好きな人」とマッチングできない理由　なぜアルゴリズムは「第2希望が最適解」と導くのか

実はこのアルゴリズムを用いると安定マッチングができる。そのためには次のような手順を踏む。

ゲイル・シャープレーアルゴリズムは最大でも16（＝4×4）回の試行で安定したマッチングを行うことができる効率的なアルゴリズムだ。

これまでに示したのは男性視点のマッチングだが、もちろん女性視点でも同様に行うことができる。その場合の安定マッチングは次のようになる。

（画像：『教養としての数学史』より）

男性と女性のどちらの視点に立つかによって結果は変わってくることに注意したい。

ゲイル・シャープレーアルゴリズムは、この安定結婚問題の解として提案されたものの、1980年代以降に驚くべき広がりを見せることになる。

「安定結婚問題」がノーベル経済学賞に結びつく

アメリカの経済学者のアルヴィン・ロスが、このアルゴリズムを「医学生と病院のマッチング」「生徒と学校のマッチング」「腎不全患者と腎臓のドナーのマッチング」に応用し始めた。

『教養としての数学史』（かんき出版）。書影をクリックするとAmazonのサイトにジャンプします

ゲイルがシャープレーに手紙で送った男女のマッチングの問題が、実社会のさまざまな問題を解決する鍵となったのである。

最後に提唱者である2人のその後について見てみよう。

ゲイルとシャープレーは1962年に画期的な論文を共著で出した後、それぞれの道を歩んでいる。

ゲイルは数学教育の分野で貢献を続け、シャープレーはマッチング理論をさらに発展させるべく研究を行った。

ロスによってゲイル・シャープレーアルゴリズムの可能性が世界に知られるようになり、2012年にシャープレーとロスはノーベル経済学賞を受賞した。

残念ながら2008年にゲイルが亡くなっていたため、シャープレーとロスのみの受賞となったが、式典にはゲイルの遺族も招待された。 

そして、シャープレーは次のように友を悼む。

この栄誉をデイヴィッド（ゲイル）と分かち合えなかったことが唯一の悔いだ。

プリンストンで奇跡的なマッチングを果たし、手紙が紡いだ2人の美しき友情がその言葉に表れている。

著者フォローすると、Fukusukeさんの最新記事をメールでお知らせします。