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

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

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

この記事では「インセンティブの作法」付録編として、
「週刊東洋経済」(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
人気の動画
保険営業 ノルマ未達なら「雇用契約打ち切り」の無惨
保険営業 ノルマ未達なら「雇用契約打ち切り」の無惨
ラーメン店の倒産ラッシュが必然でしかない事情
ラーメン店の倒産ラッシュが必然でしかない事情
攻撃的な人の態度を軟化させる絶妙なワザ
攻撃的な人の態度を軟化させる絶妙なワザ
都心vs. 郊外 家を購入するならどっち?
都心vs. 郊外 家を購入するならどっち?
アクセスランキング
  • 1時間
  • 24時間
  • 週間
  • 月間
  • シェア
トレンドウォッチAD
人材戦略から儲けのからくり<br>まで コンサル全解明

人材の争奪戦が過熱し、年収水準もうなぎ登りに。デジタル化を背景にコンサルティング業界は空前の活況を呈しています。本特集ではコンサル業界の動向やビジネスモデルを徹底解説。コンサル会社を賢く選び、上手に活用していくノウハウを紹介します。

東洋経済education×ICT