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

✎ 1 ✎ 2 ✎ 3 ✎ 4 ✎ 最新
拡大
縮小

実践ノーベル経済学賞!ゲール=シャプレーアルゴリズム

この記事では「インセンティブの作法」付録編として、
「週刊東洋経済」(2012/11/12発売号)に掲載の
「インセンティブの作法」
第2回【理想のパートナーはマッチング理論で……】

に例示したマッチング問題における、ゲール=シャプレーアルゴリズム(以下GSアルゴリズム)の手順を個別具体的に解説する。

……と、その前に、本誌を読んでいない方に向けて、GSアルゴリズムについて簡単に触れておこう。

まず、GSアルゴリズムの「ゲール=シャプレー」は、米カリフォルニア大学ロサンゼルス校のロイド・シャプレー名誉教授とその共同研究者の故デビッド・ゲール氏、考案者2人の名前からきている。

今年のノーベル経済学賞は「(マッチング問題における)安定配分の理論とマーケットデザインの実践に関する功績」により、2人の経済学者が受賞することになったのだが、シャプレー氏はその1人だ。

シャプレー、ゲール両氏によってマッチングに関する数理分析の分野が切り開かれ、誰もがいちばんふさわしい相手とパートナーになれる、「安定配分の理論」が生み出された。

2人が「大学入学と結婚の安定性」と題するたった7ページの論文の中で明らかにした、理想的なマッチングを実現する方法、GSアルゴリズムと呼ばれるそれは、理解しやすく、身近に活用しやすいマッチングの仕組みだ。知っておいて損はない、そんな気持ちで、お付き合いいただきたい。

それでは、今回考えるマッチング問題の状況とGSアルゴリズムの手順を、以下簡単に示す。

■状況
男性3人のグループ(こうきだいきともき
女性3人のグループ(るいひとみあい)  ……の合コンをイメージ

・異性グループの誰かが自分のパートナーとなるなら、その望ましさの序列はどのようになるか? 1~3位の確たるランキングを、参加者全員が心に抱いていることを前提とする。
・誰ともマッチできなかったら最悪だ、と各参加者が考えていることにする。
・ここでは、プロポーズ(提案)可能なのは男性参加者のみとする。(女性参加者がプロポーズする場合には、以下の手順で男性と女性の役割を交換すればよい)


■この状況におけるGSアルゴリズムの手順
1. 男性が第1希望の女性に一斉にプロポーズ(提案)
2. 女性は自分の好みにいちばん近い人を選んでキープ(保留)、残りの男性をリジェクト(拒否)
3. 男性はリジェクトされるたびに次に好みの女性にプロポーズ
4. 女性はより好みの男性が来るたびにキープ相手を変更、残りをリジェクト
※この作業をリジェクトされる男性がいなくなるまで続ける。
 

いま、各参加者の好みは左の表で与えられているとする。この例で、男性側がプロポーズ(提案)するGSアルゴリズムがどのように機能するのか、丁寧に見ていこう。

 


 



【第1ラウンド】


 

まず第1ラウンドでは、男性陣がそれぞれ自分の第1希望の女性にプロポーズする。

つまり、こうきだいきるいに、ともきあいにプロポーズするのだ。
ここでは、こうきだいきが同じ女性るいにプロポーズしているので、るいはどちらか一人を選ばなければならない。

るいのランキングを確認すると、こうきの方がだいきより上にいる。ということは、こうきをキープ(=仮マッチ)してだいきにはさようならだ。
 あいに関してはともきからのプロポーズしか来なかったので、そのままともきをキープ。

ここまでで第1ラウンドは終了。

次ページ第2ラウンド以降のダイナミックな展開!
関連記事
トピックボードAD
キャリア・教育の人気記事
トレンドライブラリーAD
連載一覧
連載一覧はこちら
人気の動画
パチンコ、「倒産」と「リストラ」ドミノの深刻背景
パチンコ、「倒産」と「リストラ」ドミノの深刻背景
パチンコ業界で「キャッシュレス」進まぬ複雑背景
パチンコ業界で「キャッシュレス」進まぬ複雑背景
イオン、PB価格据え置きの「やせ我慢」に募る憂鬱
イオン、PB価格据え置きの「やせ我慢」に募る憂鬱
「イトーヨーカドー幕張店」激戦区の大改装に差した光明
「イトーヨーカドー幕張店」激戦区の大改装に差した光明
アクセスランキング
  • 1時間
  • 24時間
  • 週間
  • 月間
  • シェア
会員記事アクセスランキング
  • 1時間
  • 24時間
  • 週間
  • 月間
トレンドウォッチAD
東洋経済education×ICT