先週月曜日に発表された今年のノーベル経済学賞は「（マッチング問題における）安定配分の理論とマーケットデザインの実践に関する功績」を讃えて、米ハーバード大学のアルビン・ロス教授とカルフォルニア大学ロサンゼルス校のロイド・シャプレー名誉教授に授与された。

　ただし、2人同時受賞とは言っても、両氏がそれぞれ打ち立てた業績は、かなり違う特徴を持つ。ロス教授の愛弟子で筆者の親友でもある小島武仁・米スタンフォード大学助教授が、2012年10月18日付本サイトでロス教授の業績について心のこもった解説を書いていた。小島氏と同じく「マーケットデザイン」を専門とする筆者は、もう1人の受賞者・シャプレー教授の理論に迫り、解説したいと思う。

　マッチング現象を初めて数学の問題として定式化し、誰もが一番ふさわしい相手とマッチできる「安定配分の理論」を生み出したのがシャプレー教授（および故デヴィッド・ゲール）だ。それに対し、その理論を発展させて現実の制度設計（＝マーケットデザイン）にまで応用したのがロス教授である。この意味で、実は受賞者2人の業績自体がお互いを補い合う形で見事にマッチングしているのである！

　では、マッチング問題における安定配分の理論を中心に、「理論家シャプレー」の貢献を振り返ってみよう。

わずか7ページの論文で全てが始まった

　安定配分の理論が生まれたのは今からちょうど半世紀前のことである。1962年に数学誌に掲載された「大学入学と結婚の安定性（College Admissions and the Stability of Marriage）」と題するわずか7ページの論文によって、シャプレー教授は共著者であった故デビッド・ゲールと共にマッチングに関する数理分析の分野を切り開いた。

　彼らが考察したマッチング問題は、人と人、人と組織など、2つのグループのメンバー同士をパートナーとしてマッチさせる問題を幅広く扱うものだ。論文タイトルにも含まれる「大学入学」（学生と学校のマッチング）や「結婚」（男性と女性のマッチング）をはじめとして、労働市場（労働者と企業のマッチング）やビジネス上の取引（卸売店と小売店のマッチング）など、経済活動と結びつきが深い応用例を数多く含んでいる。

　ゲールとシャプレーは、社会に溢れるこうしたマッチング現象をまとめて分析するためのフレームワークを確立し、その代表的な解として「安定性」という概念を提唱したのである。

　安定性とはざっくり言うと、たとえマッチング結果から個人やペアが逸脱したとしても、決してその逸脱者たちが当初の結果と比べて得をすることがない、という性質を指す。彼らはこの短い論文（繰り返すが7ページしかない）の中で、安定性を満たすマッチング結果（これを「安定マッチング」と呼ぶ）がどんなマッチング問題にも必ず存在することを示した。さらにそれを見つけるアルゴリズム（機械的な作業手順）まで明らかにしたのである。

　安定マッチングのもとでは、すべての参加者にとって「自分がマッチできる（手の届く）可能性のある相手の中でベストなパートナーとマッチしている」という状況が成立する。これは同時に、マッチング結果が安定マッチングから他の結果へと変わると少なくとも一人は現状よりも損をする、ということを意味する。経済学では、誰も損することなく誰かが得できるような改善の余地が残されていない状況を「パレート効率的」（パレート最適とも呼ばれる）と言う。安定マッチングはこの効率性の条件も満たしているのだ。

　つまりまとめると、安定マッチングとは「お互いの好みを反映し尽くした効率的なマッチング結果」なのだ。ゲールとシャプレーは、このような理想的なマッチングを簡単に見つけることができる仕組みを生み出したわけである。

安定マッチングを導く「GSアルゴリズム」とは

　では、彼らが見つけ出した、安定マッチングを導くアルゴリズムとはどのようなものだろうか。これは考案者にちなんでゲール＝シャプレー（GS）アルゴリズムと呼ばれたり、後述するように、その作業の中身から受け入れ保留アルゴリズムと呼ばれたりしている。