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

プリンストン大学がゲイルとシャープレーの邂逅の場となった。ただ、2人がプリンストンで一緒に過ごしたのは1年間だけだった。

ゲイルは1949年にプリンストン大学で博士号を取得したが、1950年からアメリカの北東部に位置するロードアイランド州のブラウン大学へ赴き、1965年まで数学を教えた。

一方、シャープレーは1949年にプリンストン大学大学院に入学した。1953年に博士号を取得した後、翌年からアメリカ南西部カリフォルニア州にあるランド研究所に勤め始めた。つまり、ゲイルとシャープレーは約5000km隔てた地でそれぞれ研究をしていたことになる。

そのような状況で、1960年にゲイルがシャープレーに送った1通の手紙が2人の転機になる。その手紙にはこう書かれていた。

男女がお互いの選好順位に基づいて安定した結婚ペアを作れるか？

のちに「安定結婚問題」と呼ばれる問いを正午に受け取ったシャープレーは、午後4時までに返信を送ったといわれている。

（イラスト：芦刈将、『教養としての数学史』より）

これをきっかけに、アメリカ東西を結ぶ文通が始まったゲイルとシャープレー。

2年後の1962年には、共著論文で「ゲイル・シャープレーアルゴリズム」を発表した。そのアルゴリズムが「安定結婚問題」の解として脚光を浴びたのである。

カギは「駆け落ち可能な相手がいない」こと

ここで、彼らが研究した「安定結婚問題」について解説しよう。

現在の結婚活動（婚活）は多様化しているが、今回は男性4人と女性4人だけが登録している架空の結婚相談所を舞台とする。あくまで数学的に単純化されたモデルとして次の問題を考えてほしい。

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

この問題の前提として知っておきたいのは、8人全員が満足できるようなマッチングなど存在しないということだ。選好順を見てわかる通り、全員が第1希望の異性とペアになれるわけではない。

安定結婚問題のゴールは「今の相手よりももっと好きな相手がいて、その相手も自分のことを今の相手より好き」という男女がいない状態である。そのような「駆け落ちペア」がいた場合、マッチングは不安定となる。