経済学で理想のパートナーを探そう！ ゲール＝シャプレーアルゴリズムを合コンのマッチング問題から考える

【第2ラウンド】

次に第2ラウンド。
第2ラウンドでは、第1ラウンドでリジェクトされてしまっただいきが、今度は第2希望の女性あいにプロポーズする。  

そうすると、第1ラウンドで既にともきと仮マッチしているあいのところに、新たにだいきがやってくることになる。
ここであいのリストを見ると、だいきはともきよりも優先順位が高い。
よって、あいは仮マッチしていたともきをリジェクト、キープする相手を新たにプロポーズしてきただいきに切り替えるのだ。

ここまでが第2ラウンド。

 さて、第1ラウンドではあいと仮マッチ状態にあったともきだが、第2ラウンドの結果リジェクトされてしまった。このともきが次のプロポーズを行うのが第3ラウンドだ。

【第3ラウンド】

第3ラウンドでは、まずともきの好みのランキングを確認する。
 ともきは第2ラウンドで、第1希望のあいにリジェクトされてしまっているので、この第3ラウンドでは第2希望のるいにプロポーズすることになる。

もともとこうきをキープしていたるいだが、そこにともきがやってくる。
 るいのランキング順位は 、仮マッチしていたこうきよりも、後からやってきたともきのほうが高い。るいは第2希望のこうきと別れて、第1希望のともきに相手を切り替える。

これで第3ラウンドは終了だ。

【第4ラウンド】

第4ラウンドでは、第1ラウンドで仮マッチしたものの、第3ラウンドで第1希望のるいにリジェクトされてしまったこうきが、第2希望のひとみにプロポーズすることになる。

すると、まだどの男性とも仮マッチしていなかったひとみが、ここにきてプロポーズしてきたこうきをキープする。
 こうきがひとみと仮マッチすると、これ以上は誰もリジェクトされなくなる。

ここでステップは終了、GSアルゴリズムは止まるのだ。

【最終結果】

第4ラウンド時点での仮マッチ、

こうきとひとみ
だいきとあい
ともきとるい

というペアが、最終的なマッチング結果となる。

 

以上が本誌で紹介しきれなかった、このケースにおけるGSアルゴリズムの細かな手順だ。

ここでは、合コンを例にGSアルゴリズムを紹介したが、人と人、人と組織など、二つの異なるグループのメンバー同士をマッチングさせるような例は枚挙に暇がない。GSアルゴリズムを応用できる場面は、日常や職場の中にもあるだろう。経済学の知見を、ぜひ色々なかたちで活用してほしい。 

図表作成：安田洋祐

制度設計を鋭く分析、経済学初心者にも理解しやすい丁寧な解説でマーケットデザインに触れられる『学校選択制のデザイン ゲーム理論アプローチ』（安田洋祐編著、NTT出版、2010年）

ソロモン王のジレンマや企業が直面する問題への経済学的解決のヒントが提示される『日本の難題をかたづけよう 経済、政治、教育、社会保障、エネルギー』（光文社、2012年）他のパートも豪華な執筆陣。現実問題に挑みながらも知的好奇心を刺激します！