マッチング理論：安定結婚問題からノーベル賞までの数学の旅

毎年9月、数十万人の高校卒業生が統一入試制度を通じて大学に入学する。毎年3月、数万人の医学部卒業生がNRMP（全米研修医マッチングプログラム）を通じて教育病院に配属される。アメリカでは毎年、数千人の腎不全患者が腎臓交換プログラムを通じて新たな命を得る。これら一見無関係なシステムには、共通の数学的基盤がある。安定マッチング理論である。1962年に初めて提起されたこの数学的問題は、最終的に2012年のノーベル経済学賞で認められ、数学が社会制度を改善しうる最も優美な例の一つとなった。

I. 安定結婚問題：「裏切り」が脅威となるとき

1962年、アメリカの数学者デイヴィッド・ゲールとロイド・シャプレーは、わずか9ページの論文を『アメリカン・マスマティカル・マンスリー』に発表した。「大学入試と結婚の安定性」と題されたこの一見控えめな論文は、マッチング理論という分野全体を確立することとなった。^[1]

彼らが提起した問題は驚くほど簡潔であった。n人の男性とn人の女性がいて、各人が異性全員に対する選好順位（最も好む相手から最も好まない相手まで）を持っていると仮定する。全員をn組のカップルに組み合わせ、そのマッチングが「安定」であるようにするのが課題である。では「安定」とは何を意味するのか？

定義：マッチングが不安定であるとは、マッチされていない男女のペア（例えばジョンとメアリー）が存在し、双方とも現在のパートナーを離れて互いに一緒になることを望む場合を言う。このようなペアを「ブロッキングペア」と呼ぶ。安定マッチングとは、ブロッキングペアが存在しないマッチングである。

平たく言えば、安定マッチングとは「誰もより良いパートナーへ『逃げる』ことができない」状態である。なぜなら、そのより良い相手が受け入れてくれないからだ。これは一種の「適材適所」の社会秩序のように聞こえる――各人が第一希望の相手を得るとは限らないが、少なくとも「駆け落ち」するペアがシステム全体を乱すことはない。

ゲールとシャプレーは決定的な問いを提起した。安定マッチングは常に存在するのか？ 彼らは答えが「はい」であることを証明しただけでなく、その一つを見つけるための優美なアルゴリズムも提供した。

II. 受入保留アルゴリズム：数学的優美さ

ゲール＝シャプレーのアルゴリズム（「受入保留アルゴリズム」とも呼ばれる）は、マッチング理論の基礎である。以下がその仕組みだ。

男性提案バージョン

1. 第1ラウンド：各男性が自分の選好リストで最上位の女性にプロポーズする。
2. 各女性は受け取ったすべてのプロポーズを審査し、最も好む求婚者を仮に「保留」する（ただしまだ正式には受諾しない）。残りは拒否する。
3. 以降のラウンド：拒否された男性は、自分の選好リストの次の女性にプロポーズする。女性は「乗り換え」が可能で、新たな求婚者が現在保留中の相手より好ましければ、現在の保留者を解放して新たな求婚者を保留する。
4. 終了：すべての男性がマッチされるか、すべての女性に拒否された時点でアルゴリズムは終了し、各女性は保留中の男性を正式に受諾する。

このアルゴリズムが「受入保留」と呼ばれるのは、女性がプロポーズを即座に受諾せず、より良い求婚者の可能性に備えて選択肢を開いておくからである。この「比較検討」戦略こそが、アルゴリズムが安定マッチングを達成することを可能にしている。

存在証明

なぜこのアルゴリズムは常に安定マッチングを生み出すのか？ 証明は背理法に基づく。

最終的なマッチングにブロッキングペア（ジョン、メアリー）が含まれると仮定する。つまり、ジョンもメアリーも互いに一緒になることを好む。これは以下を意味する：

• ジョンはメアリーを最終的なマッチ相手より好む。
• メアリーはジョンを最終的なマッチ相手より好む。

しかし、アルゴリズムの手順によれば、ジョンはプロセスのどこかの時点でメアリーにプロポーズしたはずである（選好順にプロポーズするため、メアリーの方を好むならば）。ジョンがメアリーにプロポーズしたにもかかわらず、なぜメアリーは最終的にジョンと組まなかったのか？ 可能性は二つしかない：

1. メアリーがその時点でジョンを拒否した。すでにジョンより好む相手を保留していたため。
2. メアリーが後に「乗り換えた」。ジョンより良い求婚者のためにジョンを解放したため。

いずれの場合も、メアリーの最終的なマッチ相手はジョンより好む相手でなければならない（女性は乗り換える際、常にランクアップするため）。これは「メアリーがジョンを好む」という仮定に矛盾する。したがって、ブロッキングペアは存在し得ず、マッチングは必然的に安定である。^[2]

男性最適 vs. 女性最適

ここに重要な非対称性がある。男性がプロポーズする場合、アルゴリズムは男性最適な安定マッチングを生成する。つまり、すべての男性が、あらゆる安定マッチングの中で最良のパートナーを得る。同時に、このマッチングは女性最悪でもある。すべての安定マッチングの中で、すべての女性にとって最悪の結果となる。

逆に、女性がプロポーズし男性が保留する場合、結果は女性最適かつ男性最悪となる。この発見は深い真理を明らかにする。アルゴリズムの設計上の選択は、暗黙のうちに権力の分配を決定するのだ。誰がプロポーズし誰が待つかが、誰が有利になるかを決める。これは単なる数学的定理ではなく、マーケットデザインの政治経済学――あらゆる意思決定フレームワークにおける根本的な選択である。^[3]

III. 二人の数学者の物語

デイヴィッド・ゲール（1921～2008年）はカリフォルニア大学バークレー校の数学者で、ゲーム理論と線形計画法の分野で著名であった。ロイド・シャプレー（1923～2016年）はカリフォルニア大学ロサンゼルス校の数学者・経済学者で、ゲーム理論の創始者の一人として広く認められている。

彼らの協力は、シンプルな問いから始まった。大学入試制度をもっと公平に設計できないか？ 当時のアメリカの大学入試は混沌としていた。各大学が異なるタイミングで合格通知を出し、学生は不完全な情報の下で決断を迫られ、その結果、「入学辞退」や「約束の破棄」が横行していた。ゲールとシャプレーは、これが本質的にマッチング問題であることに気づいた。

興味深いことに、論文のタイトルには「大学入試」とあるにもかかわらず、テキストのほぼ全体が「結婚の安定性」について論じている。これはシャプレーのスタイルであった。彼は深い数学的構造を照らし出すためにシンプルな比喩を好んだ。「安定結婚」の名前は、以来この分野のトレードマークとなった。^[4]

シャプレーのもう一つの主要な貢献は「シャプレー値」であった。これは協力ゲームから得られる利益を公平に分配する方法である。安定マッチングが「どうマッチするか」の問題を解決し、シャプレー値が「どう分配するか」の問題を解決する。この二つの業績が合わさって、現代のマーケットデザインの数学的基盤を築いた。

IV. アルヴィン・ロス：理論と実践の架け橋

ゲールとシャプレーが理論を創り出したとすれば、それを現実世界に持ち込んだのはアルヴィン・ロスであった。ハーバード大学（現在はスタンフォード大学）の経済学者であるロスは、多くの一見無関係な現実の制度が実はマッチング問題であり、ゲール＝シャプレーのフレームワークを用いて分析・改善できることを発見したことで名声を得た。

米国研修医マッチングシステム（NRMP）

ロスの最も有名な発見の一つは、アメリカの研修医マッチングシステムに関するものであった。1950年代、アメリカの医学教育は深刻な問題を抱えていた。医学生は卒業前のかなり早い時期に病院に引き抜かれ、中には2年生の段階でオファーを受ける者もいた。この「早期採用の軍拡競争」は双方に十分な情報がないまま意思決定を迫り、広範な不満を生んでいた。

1952年、NRMP（全米研修医マッチングプログラム）が設立され、集中マッチングメカニズムが採用された。驚くべきことに、ロスは1984年に、NRMPが使用しているアルゴリズムが本質的にゲール＝シャプレーのアルゴリズムの変形であることを証明した――NRMPの設計者はゲールとシャプレーの論文を知らなかったにもかかわらずだ。これは独立発見の印象的な事例である。^[5]

しかしロスは、NRMPの問題点も指摘した。元のデザインは「病院提案」バージョンであり、結果は病院にとって最適で学生にとって最悪であった。1990年代、ロスはNRMPを「学生提案」バージョンに再設計し、学生にとってより有利な結果を生むようにした。この改革は現在も運用されており、毎年4万人以上の研修医のマッチングを行っている。^[6]

ニューヨーク市の高校入学選抜システム

2003年、ロスはニューヨーク市の高校入学選抜システムの再設計に招かれた。既存のシステムは「混沌とした市場」であった。生徒は5校までしか志願できず、各校は自校を第一志望に挙げた受験生を戦略的に優先できた。結果として、毎年3万人以上の生徒が志願していない学校に配属されていた。

ロスのチームは受入保留アルゴリズムを導入し、生徒は最大12校（後に無制限に拡大）の志望校を順位付けでき、学校側は生徒の志望順位リスト上の自校の順位を知ることができないようにした。この設計には二つの重要な利点があった：

1. 耐戦略性：生徒は真の選好を戦略的に隠す必要がない。正直な申告が最適戦略である。
2. 安定性：双方がともに現在の配属先から「逃げたい」と望む生徒-学校ペアが存在しない。

改革後、志望校のいずれにもマッチングされなかった生徒の数は3万人から約3,000人に減少した。これは、マーケットデザインが公共政策を改善した古典的事例である。^[7]

腎臓交換マッチング

ロスの最も人道的な貢献は、腎臓交換プログラムかもしれない。アリスが夫のボブに腎臓を提供したいが、血液型が不適合であるとする。一方、キャロルが兄のダンに腎臓を提供したいが、これも不適合である。もしアリスの腎臓がダンと適合し、キャロルの腎臓がボブと適合すれば、「交換」が可能になる――アリスがダンに提供し、キャロルがボブに提供する。四者全員が利益を得る。

ロスと共同研究者は、このような「交換チェーン」を全国規模で見つけることができるアルゴリズムを設計した。これは標準的な安定マッチング問題ではない（腎臓交換には「同時性」制約があるためだ。すべての手術は同時に行われなければならず、さもなければ誰かが翻意する可能性がある）。しかしロスは理論的フレームワークを創造的に応用してこれを解決した。

これまでに、このシステムは数千人の命を救ってきた。数学が人命を救う最も直接的な例の一つかもしれない。^[8]

V. 2012年ノーベル経済学賞

2012年、スウェーデン王立科学アカデミーはロイド・シャプレーとアルヴィン・ロスに「安定配分の理論とマーケットデザインの実践」に対してノーベル経済学賞を授与した。これはマッチング理論にとって最高の栄誉であり、「マーケットデザイン」が認知された分野として正式に確立されたことを意味した。^[9]

授賞理由では、この研究の独自性が特に強調された。それは伝統的な価格ベースの市場に関するものではなく、「価格のない市場」に関するものだった。大学入試、研修医マッチング、臓器提供において、ポジションや臓器を金銭で売買することはできない（道徳的にも法的にも許されない）。しかしマッチングの問題は存在し、それらにも効果的なメカニズムが必要である。ゲール＝シャプレーのフレームワークはまさにそのような手段を提供した。

なお、デイヴィッド・ゲールは2008年に亡くなり、この栄誉を目にすることはなかった。ノーベル賞は故人には授与されないが、誰もが彼の先駆的貢献を認めている。

VI. 数学的深掘り：三つの定理

マッチング理論をより深いレベルで理解したい読者のために、三つの中核的定理を紹介する。

定理1：安定マッチングの存在

定理：有限の二面マッチング問題に対して、安定マッチングは常に存在する。

証明：ゲール＝シャプレーのアルゴリズムは有限ステップで終了し、安定マッチングを生成する（上で示した通り）。アルゴリズムが構成的であるため、これは同時に存在を証明する。

定理2：提案者最適性

定理：受入保留アルゴリズム（男性が提案者の場合）は、すべての安定マッチングの中で、すべての男性にとって最適なマッチングを生成する。同時に、すべての安定マッチングの中で、すべての女性にとって最悪のマッチングとなる。

この定理の含意は、安定マッチングは一般に一意ではなく（通常は複数存在する）、受入保留アルゴリズムは提案側にとって最も有利なものを選ぶということだ。^[10]

定理3：耐戦略性

定理：受入保留アルゴリズムにおいて、提案側にとって真の選好を申告することが支配戦略である。すなわち、他者が何を申告しようとも、提案者は自分の選好を偽るインセンティブを持たない。

これはマーケットデザインの黄金基準である。良いメカニズムは、参加者が「ゲーミング」なしに成功できるようにすべきだ――正直であることが最善の戦略である。ただし、この定理には重要な但し書きがある。受入側は耐戦略性を享受しない。女性は選好リストを戦略的に変更することで、より良い結果を得られる場合がある。これが、現実のマッチングシステム設計において慎重な取り扱いが必要とされる理由である。^[11]

VII. 拡張：一対一マッチングを超えて

現実のマッチング問題は、「安定結婚」の設定よりも複雑であることが多い。いくつかの重要な拡張を紹介する。

多対一マッチング：学校入試

大学入試では、一つの学校が複数の学生を受け入れられるが、各学生は一つの学校にしか通えない。これは「多対一マッチング」問題である。ゲール＝シャプレーのアルゴリズムは直接一般化できる。各学校に「定員」を設け、アルゴリズム中にその人数まで受験生を保留できるようにすればよい。安定性の定義もそれに応じて調整される。

カップルのマッチング

研修医マッチングにおける特殊な課題が「カップルマッチング」である。結婚している二人の医学生が同じ都市の病院に配属されることを望む場合だ。これにより問題の複雑性は大幅に増加し、安定マッチングが存在しなくなる可能性すらある。ロスと共同研究者はこのケースに対処する専門的なアルゴリズムを開発したが、完全な安定性ではなく「近似的安定性」を受け入れる必要がある。^[12]

腎臓交換の特殊性

腎臓交換は標準的な二面マッチングではなく、「交換サイクル」を含む。3者間交換とは、三つのドナー・レシピエントペアが同時に交換することを意味する。より長いチェーンはより多くの人を助けられるが、すべての手術を同時に行うという要件はますます充足が困難になる。ロスのイノベーションの一つは「非指定ドナー」――見知らぬ人で無償で腎臓を提供する意思のある人――を交換チェーンの起点として導入することで、可能なマッチ数を劇的に増加させたことだ。

VIII. 台湾への応用と教訓

台湾の統一大学入試制度は、本質的にマッチング問題である。現行のシステムは「受験生優先」の選好に基づく配分（受入保留アルゴリズムの学生提案バージョンに類似）を使用しており、受験生にとって比較的有利である。ただし、台湾のシステムにはその独自性がある：

• 試験成績を唯一の基準とする：アメリカの総合的審査とは異なり、台湾は伝統的に試験の点数のみで入学を決定してきた。これは学校の「選好」を単純化するが、他の考慮事項を犠牲にしている。
• 繁星計画と個人申請：これらのチャネルは「双方向の選択」の要素をより多く導入し、システムをゲール＝シャプレーのフレームワークに近づけている。
• 戦略的行動：受験生は志望校記入の際に依然として戦略的考慮を行う（例：「合格ライン分析」）。これはシステムがまだ完全な耐戦略性を達成していないことを示している。

マッチング理論の観点から、台湾の高等教育入試制度にはまだ改善の余地がある。特に、受験生がより正直に選好を表明できるようにし、「志望校の賭け」による不安を軽減することにおいてである。

IX. 結論：数学はいかに社会制度を改善しうるか

マッチング理論の物語は、数学と社会科学の完璧な融合の模範例である。1962年の純粋数学の問題が、数十年の発展を経て、最終的に数百万人の人生の軌跡を変えた――夢の学校への入学から命を救う臓器の移植まで。

この物語はいくつかの深い教訓を提供する：

1. 良い制度設計は「消耗戦」を減らす：ルールが明確で正直な申告が最適戦略である時、参加者はシステムのゲーミングにエネルギーを費やす必要がなくなり、本当に重要なことに集中できる。
2. 数学は計算だけでなく設計のツールである：ゲール＝シャプレーのアルゴリズムは問題を解くだけでなく、どの問題が解決可能か、解がどのような性質を持つか、設計の選択がどのような結果をもたらすかを明らかにする。
3. 理論と実践の橋渡しには架け橋を築く人が必要：シャプレーが理論を創り、ロスがそれを現実に持ち込んだ。学術研究の価値は、しばしばこうした「翻訳者」によって実現される。

この歴史を振り返ると、おそらく最も心を打つ洞察はこうだ。制度を思慮深く設計すれば、数学は公正の道具となりうる。価格のない市場において、安定マッチングは一つの公平性を提供する――すべての人がシステムが提供しうる最善の結果を得て、誰も不公平に取り残されないのである。

これが「マーケットデザイン」という分野の核心的信念である。既存の制度を受動的に受け入れる必要はない。数学と経済学のツールを用いて、より良いゲームのルールを設計できるのだ。