ノーベル経済学賞 ロイド・シャプレー教授が
発見した驚きのアルゴリズム
共同受賞のロス教授との見事な「マッチング」
∗安田 洋祐
†初出： 2012 年 10 月
先週月曜日に発表された今年のノーベル経済学賞は「（マッチング問題における） 安定配分の理論とマーケットデザインの実践に関する功績」を讃えて，米ハーバー ド大学のアルビン・ロス教授とカルフォルニア大学バークレー校のロイド・シャプ レー名誉教授に授与された．
ただし，2 人同時受賞とは言っても，両氏がそれぞれ打ち立てた業績は，かな り違う特徴を持つ．ロス教授の愛弟子で筆者の親友でもある小島武仁・米スタン フォード大学助教授が，2012 年 10 月 18 日付本サイトでロス教授の業績について 心のこもった解説を書いていた．小島氏と同じく「マーケットデザイン」を専門 とする筆者は，もう 1 人の受賞者・シャプレー教授の理論に迫り，解説したいと 思う．
マッチング現象を初めて数学の問題として定式化し，誰もが一番ふさわしい相 手とマッチできる「安定配分の理論」を生み出したのがシャプレー教授（および故 デヴィッド・ゲール）だ．それに対し，その理論を発展させて現実の制度設計（＝ マーケットデザイン）にまで応用したのがロス教授である．この意味で，実は受 賞者 2 人の業績自体がお互いを補い合う形で見事にマッチングしているのである！
では，マッチング問題における安定配分の理論を中心に，「理論家シャプレー」の 貢献を振り返ってみよう．
∗本稿は『日経ビジネスオンライン』(2012 年 10 月 25 日)「気鋭の論点」に掲載された記事を転 載したものです．
†やすだ・ようすけ — 政策研究大学院大学助教授．2002 年東京大学経済学部卒．2007 年，米プ リンストン大学経済学部博士課程修了 (Ph.D.)，同年から現職．専門はゲーム理論とマーケットデ ザイン．編著書に『学校選択制のデザイン ゲーム理論アプローチ』(NTT 出版) がある．Twitter アカウントは@yagena．
わずか 7 ページの論文で全てが始まった
安定配分の理論が生まれたのは今からちょうど半世紀前のことである．1962 年 に数学誌に掲載された「大学入学と結婚の安定性（College Admissions and the Stability of Marriage）」と題するわずか 7 ページの論文によって，シャプレー教授 は共著者であった故デヴィット・ゲールと共にマッチングに関する数理分析の分野 を切り開いた．
彼らが考察したマッチング問題は，人と人，人と組織など，2 つのグループのメ ンバー同士をパートナーとしてマッチさせる問題を幅広く扱うものだ．論文タイ トルにも含まれる「大学入学」（学生と学校のマッチング）や「結婚」（男性と女 性のマッチング）をはじめとして，労働市場（労働者と企業のマッチング）やビ ジネス上の取引（卸売店と小売店のマッチング）など，経済活動と結びつきが深 い応用例を数多く含んでいる．
ゲールとシャプレーは，社会に溢れるこうしたマッチング現象をまとめて分析 するためのフレームワークを確立し，その代表的な解として「安定性」という概 念を提唱したのである．
安定性とはざっくり言うと，たとえマッチング結果から個人やペアが逸脱した としても，決してその逸脱者たちが当初の結果と比べて得をすることがない，と いう性質を指す．彼らはこの短い論文（繰り返すが 7 ページしかない）の中で，安 定性を満たすマッチング結果（これを「安定マッチング」と呼ぶ）がどんなマッ チング問題にも必ず存在することを示した．さらにそれを見つけるアルゴリズム
（機械的な作業手順）まで明らかにしたのである．
安定マッチングのもとでは，すべての参加者にとって「自分がマッチできる（手 の届く）可能性のある相手の中でベストなパートナーとマッチしている」という 状況が成立する．これは同時に，マッチング結果が安定マッチングから他の結果 へと変わると少なくとも一人は現状よりも損をする，ということを意味する．経 済学では，誰も損することなく誰かが得できるような改善の余地が残されていな い状況を「パレート効率的」（パレート最適とも呼ばれる）と言う．安定マッチン グはこの効率性の条件も満たしているのだ．
つまりまとめると，安定マッチングとは「お互いの好みを反映し尽くした効率 的なマッチング結果」なのだ．ゲールとシャプレーは，このような理想的なマッチ ングを簡単に見つけることができる仕組みを生み出したわけである．
安定マッチングを導く「GS アルゴリズム」とは
では，彼らが見つけ出した，安定マッチングを導くアルゴリズムとはどのよう なものだろうか．これは考案者にちなんでゲール＝シャプレー（GS）アルゴリズ ムと呼ばれたり，後述するように，その作業の中身から受け入れ保留アルゴリズ
ムと呼ばれたりしている．
以下では，男性グループと女性グループとの間の 1 対 1 のマッチング（合コンを イメージして欲しい）という状況を挙げて，アルゴリズムを解説していく．男性， 女性はそれぞれ何人でも構わない．また，説明の単純化のため，各人とも「誰と もマッチせずに 1 人でいるのは最悪だ」と思っていることにしよう．
GSアルゴリズムでは，まず参加者たち全員から相手グループのメンバーに対す る好みをランキングしてもらう必要がある．そして，提出された好みに基づいて マッチメイカーである第三者が機械的に以下の作業をする．厳密に言うと，GS ア ルゴリズムはどちらのグループから提案（プロポーズ）するかによって 2 通りの 方法があるのだが，以下では元の論文に沿って，男性側提案バージョンを紹介す る（女性側提案バージョンは，男女の役割を入れ替えればよい）．
GSアルゴリズムの手順
1. 各男性が第一希望の女性に一斉にプロポーズ
2. 複数の男性からプロポーズされた女性は，その中でベストの男性を「キープ」
（仮マッチ）して後はリジェクト
3. リジェクトされた男性が第二希望の女性にプロポーズ 4. 女性は毎回ベストな男性をキープ，残りをリジェクト
5. 男性はリジェクトされるたびに残りの中でベストの女性にプロポーズ
リジェクトされる男性がいなくなるまで以上の作業を続け，この作業がストッ プした段階でマッチング結果が確定する．各ラウンドで決まるパートナーと直ち にペアが確定するのではなく，あくまで暫定的な仮マッチとなっているのがポイ ントだ．
安定マッチングを導くためには，すぐに結果を求めずに，あえて「受け入れを 保留する」のが肝心なのである．ここでは男女が 1 対 1 でパートナーとなる状況 を想定しているが，女性が複数の男性を受け入れるような 1 対多数の形にも簡単 にアルゴリズムを拡張することができる．
以上，ノーベル賞受賞の決め手となったシャプレー教授の主要功績がお分かり いただけただろうか．この例の男女を，労働者と企業，学生とゼミ（研究室），研 修医と病院，と置き換えることで，様々な現実のマッチング問題に GS アルゴリズ ムが応用できることが分かるだろう．日本でも，2003 年度から，臨床研修医を病 院へ配属するためのマッチングの仕組みとして GS アルゴリズムが実際に使われて いる．
偉大な理論家シャプレーの受賞は確実視されていた
さて，上で議論したマッチング問題や GS アルゴリズムでは，マッチングに伴う 金銭の授受が考慮されていなかった．実はシャプレー教授は，1971 年に出版され たマーティン・シュービック（米イェール大学名誉教授）との共同研究でこの問題 にも取り組んでいる．
彼らは，売買契約のように金銭授受が可能な場合のマッチング問題について初め て考察し，その理論的に重要な性質を明らかにした．他にも，74 年にはハーバー ト・スカーフ（米イェール大学名誉教授）との共同研究で，参加者がそれぞれ保 有するお互いのモノとモノとを交換する「交換問題」を考察した．
そして，交換問題における安定配分の自然な定義である「コア」（正確には「強 コア配分」）が常に一つだけ存在することを示すと共に，それを導くための具体的 なアルゴリズムを生み出している．コアとは，たとえ交換結果から個人やグルー プが逸脱したとしても，決してその逸脱者たちが（当初の結果と比べて）得をす ることがない，という配分を指す．
ちなみに，コアを導くために提案された「トップ・トレーディング・サイクル」
（TTC）と呼ばれるアルゴリズムを思いついたのは著者たちではなく，彼らに研究 のアドバイスをしたゲールだったことが論文内で言及されている．これは，マッチ ング分野におけるゲール氏の貢献がいかに大きいかを物語るエピソードと言える．
もしも彼が存命していたなら，今回のノーベル賞を共同受賞したに違いない．4 年前に他界したのが悔やまれる．TTC アルゴリズムはその後より一般的な形に拡 張され，ロス教授らが学校選択制や腎臓移植の交換メカニズムとして採用を提言 している．
シャプレー教授による理論的貢献はマッチング問題だけに留まらない．おそら く彼の名前をもっとも有名にしたのは「シャプレー値」と呼ばれる，「協力ゲーム 理論」で欠かすことのできない主要な解概念の発見を通じてだろう．今回は詳細 には触れないが，協力ゲーム理論は，参加者たちが拘束力のある合意（あるいは 契約）を結べることを前提に，グループ内での望ましい配分を分析・提案するア プローチである．今まで様々な解が提案されてきたが，シャプレー値はこの中で 最も頻繁に用いられている．
ゲーム理論には，この協力ゲーム理論の他に，拘束力のある合意を前提とせず 個々人のインセンティブに基づいてゲームの結果を予測・解釈する「非協力ゲーム 理論」と呼ばれるアプローチがある．シャプレー教授はゲーム理論創成期の 1950 年代から，協力ゲーム理論，非協力ゲームの両分野で数多くの重要な業績を残し ている．余談ではあるが，シャプレー教授の共同研究者の一人であり，2005 年に ノーベル経済学賞を受賞したゲーム理論学会の重鎮ロバート・オーマン（イスラ エルのヘブライ大学教授）は，筆者も参加した数年前の国際学会で「ここにいる どのノーベル賞学者よりも，シャプレー氏はノーベル賞に値する」旨の発言をし
ていた．
それくらいシャプレー教授の存在はゲーム理論の発展にとって大きく，遅きに 失することなく無事に今回の受賞に至ったことで，ほっと胸を撫で下ろしている 関係者も多いに違いない．
ゲーム理論の聖地プリンストン
個人的な話で恐縮だが，筆者とシャプレー教授との間には，大学院生活を米プ リンストン大学で過ごしたという共通点がある．シャプレーが数学科に在籍してい た 1950 年代初頭は，まさにプリンストンがゲーム理論研究の世界的な中心地だっ た（現在でも，米スタンフォード大学や米ノースウェスタン大学などと並んで研 究の一大拠点である）．
44年に出版された大著『ゲームの理論と経済行動』によってゲーム理論を生み 出した大天才ジョン・フォンノイマンはキャンパスからほど近い高等研究所に，共 著者オスカー・モルゲンシュテルンは経済学部に在籍していた．
非協力ゲーム理論における最も重要な解である「ナッシュ均衡」を発見して 1994 年にノーベル経済学賞を受賞したジョン・ナッシュ氏や，本稿で何度も言及した キー・パーソンのゲール氏はシャプレー教授の数年上の先輩にあたる．共同研究 者のシュービック教授とスカーフ教授はいずれも同時期の学友だ．
こうした恵まれた環境の中で，世界屈指のゲーム理論家集団が基礎研究を量産 し，その成果がロス教授をはじめとする後続の研究者たちとの時空を超えたマッ チングによって現実の世界に役立てられているのだ．
半世紀遅れではあるが，彼らと同じ聖地でゲーム理論を学ぶことができた幸運と 感慨に改めて浸ると共に，大先輩であるシャプレー氏の受賞を心より祝福したい．
