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

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

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

この記事では「インセンティブの作法」付録編として、
「週刊東洋経済」(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ラウンド以降のダイナミックな展開!
関連記事
Topic Board トピックボード
人気連載
Trend Library トレンドライブラリー
  • コメント
  • facebook
0/400

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

Access Ranking
  • 1時間
  • 24時間
  • 週間
  • 月間
  • いいね!

※過去48時間以内の記事が対象

※過去1ヵ月以内の記事が対象

※過去1ヵ月以内の記事が対象

※過去1ヵ月以内の記事が対象

※週間いいね数のランキングです。

トレンドウォッチ
JR九州“脱鉄道”の成算

今年、上場を果たしたJR九州。豪華寝台列車「ななつ星in九州」は話題になった。しかし、人口減少などもあって鉄道事業の先行きは暗い。成長は非鉄道事業の成否に懸かっている。