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