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

✎ 1 ✎ 2 ✎ 3 ✎ 4 ✎ 最新
著者フォロー
ブックマーク

記事をマイページに保存
できます。
無料会員登録はこちら
はこちら

印刷ページの表示はログインが必要です。

無料会員登録はこちら

はこちら

縮小



【第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アルゴリズムを応用できる場面は、日常や職場の中にもあるだろう。経済学の知見を、ぜひ色々なかたちで活用してほしい。 

 

 

 

 

 

図表作成:安田洋祐

 

(担当者通信欄)

ゲール=シャプレーアルゴリズムの細かな手順を理解できました!「週刊東洋経済」を読んで、この記事を探してくださったみなさま、ありがとうございました。

ちなみに、自分がキープされたり、リジェクトされたりすることを考えると、ぞっとしない話ですが、実際にはそんな心配はありません。

その理由なども解説されている連載第2回。未読の方は、今年のノーベル経済学賞について、GSアルゴリズムにおける重要な概念「安定性」や細かな性質について、さらに雄弁に語る、本誌「週刊東洋経済」(2012/11/12発売号)「インセンティブの作法」第2回【理想のパートナーはマッチング理論で……】も、ぜひ合わせてご覧ください。

11/12発売号の特集は、「解雇・リストラ新時代」です。

 

 

 

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

 

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

 

 

 

安田 洋祐 大阪大学大学院経済学研究科教授

著者をフォローすると、最新記事をメールでお知らせします。右上のボタンからフォローください。

やすだ ようすけ / Yosuke Yasuda

1980年東京都生まれ。2002年東京大学経済学部卒業。最優秀卒業論文に与えられる大内兵衛賞を受賞し、経済学部卒業生総代となる。2007年米プリンストン大学よりPh.D.取得(経済学)。政策研究大学院大学助教授を経て、2014年4月から現職。専門は戦略的な状況を分析するゲーム理論。主な研究テーマは、現実の市場や制度を設計するマーケットデザイン。【Webサイト】【ブログ「ECONO斬り!!」】【Twitter(@yagena)

 

 

この著者の記事一覧はこちら
ブックマーク

記事をマイページに保存
できます。
無料会員登録はこちら
はこちら

印刷ページの表示はログインが必要です。

無料会員登録はこちら

はこちら

関連記事
トピックボードAD
キャリア・教育の人気記事