経済学で理想のパートナーを探そう!

ゲール=シャプレーアルゴリズムを合コンのマッチング問題から考える

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

この記事では「インセンティブの作法」付録編として、
「週刊東洋経済」(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
関連記事
  • Amazon週間ビジネス・経済書ランキング
  • 令和を生きる若者のための問題解決法講座
  • 精神医療を問う
  • 読んでナットク経済学「キホンのき」
トレンドライブラリーAD
  • コメント
  • facebook
-

コメント投稿に関する規則(ガイドライン)を遵守し、内容に責任をもってご投稿ください。

ログインしてコメントを書く(400文字以内)
アクセスランキング
  • 1時間
  • 24時間
  • 週間
  • 月間
  • シェア
トレンドウォッチAD
衝撃!住めない街<br>自然災害・人口減を甘く見るな

東京・江東5区や川崎など、首都近郊でひっそりと「住めないエリア」が広がっています。近年の大規模災害で補修が追いつかないところに、人口減少、インフラ老朽化などが重なり、苦悩する街。その現実と、日本人の「住まい方」を考えます。

  • 新刊
  • ランキング