実践ノーベル経済学賞！ゲール＝シャプレーアルゴリズム
この記事では「インセンティブの作法」付録編として、
「週刊東洋経済」（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ラウンドは終了。
無料会員登録はこちら
ログインはこちら