全員が満足しなくても崩壊しない配分：ゲイル・シャプレーの安定マッチングと制度設計

1. 合格通知の裏に潜む見えない亀裂

ある志願者が第一志望の大学に不合格となり、第二志望の大学に合格したとする。表面的には入試手続きは完了したように見える。合格証書が交付され、公的な手続きはすべて終わった。

しかし、制度の外側に目を凝らすと、見えない亀裂が潜んでいる可能性がある。別の大学に配分された志願者の中には、自身の合格先よりもこの大学を望む者がいるかもしれず、大学の側も現在確保している学生よりその不合格者を高く評価しているかもしれない。もしそうであれば、双方は公式の決定を破棄し、水面下で私的な契約を結びたいという強い動機を抱くことになる。

これは単に誰かが結果に不満を漏らしているという話ではない。公式の配分から逸脱して結託したとき、双方が現在よりも有利になる脱出路が存在することを意味する。このような抜け穴が放置された制度は、参加者の自発的な離脱によって内側から崩壊していく。

大学入試や雇用、結婚のように双方が相手を選び合う二点市場（Two-Sided Matching）では、全員が同時に第一志望を得られるような魔法の配分は存在しない。では、完全な満足が不可能な世界において、制度はいかなる基準の上に築かれるべきなのだろうか。

2. すれ違う欲望：ミヌとジスの選好パラドックス

この問題の本質を直観的に捉えるために、定員がそれぞれ1名である二つの大学（A大学、B大学）と二人の学生（ミヌ、ジス）が存在する単純な市場を考えてみよう。

双方が心の中に抱く選好順位は、次のように極端にすれ違っている。

ミヌはA大学を、ジスはB大学を最も望んでいる。しかし大学側の評価は正反対である。A大学はジスを一番に欲し、B大学はミヌを一番に欲している。

定員はそれぞれ1名であるため、全員が第一志望を得ることは原理的に不可能である。誰かが必ず第二志望へと甘んじなければならない。制度はいかなる論理をもって、彼らの行き先を決定すべきなのだろうか。

확대

3. 制度を内側から崩す力：ブロッキング・ペア（Blocking Pair）

1962年、数学者のデイヴィッド・ゲイルとロイド・シャプレーは論文『大学入試と結婚の安定性』においてこの問題に挑んだ。彼らが問うたのは、全員を幸福にする方法ではなかった。当事者たちの利己的な選択によって容易に覆されない配分が常に存在するかという、極めて現実的な問いであった。

制度の存続を脅かす根本原因は、個人の不満そのものではない。重要なのは「結託の可能性」である。マッチング理論において、これをブロッキング・ペア（Blocking Pair）と呼ぶ。

flowchart LR
    subgraph Official["公式の配分結果"]
        S["学生：第二志望に配分"]
        C["大学：第二候補を選抜"]
    end

    subgraph BlockingPair["ブロッキング・ペア：相互離脱の誘因"]
        S <==>|"公式の決定を破棄して結託する誘因\n（双方が現在の相手より互いを好む）"| C
    end

    style BlockingPair fill:#fff1f0,stroke:#cf1322,stroke-width:2px
    style Official fill:#f6ffed,stroke:#52c41a,stroke-width:1px

ある学生が現在配分された大学よりも大学Xを望み、同時に大学Xも現在確保している学生よりその志願者を高く評価しているならば、両者はブロッキング・ペアとなる。彼らには中央配分システムの決定を無視して裏で手を組み、約束を破棄する明確な動機が存在する。

逆に「安定な配分（Stable Matching）」とは、市場全体においてブロッキング・ペアが一つも存在しない状態を意味する。第二志望に留まり不満を抱く者はいるかもしれない。しかし、その不満を抱く者と手を組んで共に利益を得られる相手が一人も残っていないならば、その制度は外部の強制力に頼ることなく強固に維持される。

4. 受入保留アルゴリズム：決定を留保する知恵

この安定な状態を見つけ出す手順が「受入保留（Deferred Acceptance: DA）アルゴリズム」である。学生が大学へ順次出願していくプロセスを可視化すると、次のようになる。

flowchart TD
    Start["第1段階：不合格となった学生が\n次の志望大学へ出願"] --> CollegeReview["第2段階：大学は新規出願者と\n現在の保留者を定員内で比較"]
    CollegeReview --> HoldDecision{"定員内の上位候補者のみを\n「暫定保留」として保持"}
    HoldDecision --> RejectAction["定員外の候補者へ\n不合格通知を送付"]
    RejectAction --> CheckUnmatched{"未応募の志望先が残る\n不合格者は存在するか？"}
    CheckUnmatched -- "はい" --> Start
    CheckUnmatched -- "いいえ" --> FinalMatch["第3段階：最終保留者を\n正式合格として確定（終了）"]

    style HoldDecision fill:#e6f7ff,stroke:#1890ff,stroke-width:2px
    style FinalMatch fill:#f6ffed,stroke:#52c41a,stroke-width:2px

核心は「保留（Deferred）」という概念にある。大学は好ましい志願者が現れても直ちに最終確定を与えない。より優れた人材が現れる可能性を残し、決定を暫定的に保留するに留める。学生は拒絶されるたびに、次の候補へと向かって再び扉を叩く。

大学が暫定的に確保する志願者の水準はステップが進むにつれて維持または向上し、一度不合格にした学生を後から呼び戻すことはない。したがって手続きが終了したとき、ある大学に入れなかった学生がいるとすれば、その大学はすでにその学生より優れた志願者で定員を満たしている。この原理により、結果表には私的結託を生むブロッキング・ペアが一切残らない。

확대

5. すれ違う最適性：誰に提案の権利を与えるべきか

しかしここで、制度設計者が直面する極めて重大な真実が露わになる。崩壊しない安定配分は、決して一つだけではないということだ。

先ほどのミヌとジス、A大学とB大学の例にこの手続きを適用してみよう。

ケース1：学生側から出願する場合。ミヌは第一志望のA大学へ、ジスは第一志望のB大学へ出願する。各大学に応募者が1名ずつ訪れたため、大学側は拒否することなく保留する。不合格者がいないため、手続きは第1段階で終了する。ミヌはA大学（第一志望）、ジスはB大学（第一志望）に決定する。学生は全員が最高の結果を得た。大学はそれぞれ第二候補を迎えることになり不本意であるが、学生側に転校する理由が皆無であるため結託は生じない。完璧に安定している。

ケース2：大学側からスカウトする場合。A大学は第一候補のジスへ、B大学は第一候補のミヌへオファーを出す。ジスとミヌはそれぞれオファーを保留する。拒絶された大学がないため、手続きは即座に終了する。ミヌはB大学（第二志望）、ジスはA大学（第二志望）へ配分される。大学側は最高の人材を獲得した。学生は第二志望に甘んじるが、大学側が別の学生を望まないため結託は生じない。これもまた完璧に安定している。

どちらの結果も数学的に非の打ち所がない。どちらを選んでも、密約によって制度が崩壊する恐れはない。

しかし、誰に扉を叩く権利を与えたかによって、一方は最上の果実を享受し、他方は次善の妥協を強いられる。学生提案方式は存在するすべての安定配分のうち「学生にとって最も好ましい安定配分」を保証する。逆に大学提案方式は大学にとって最も好ましい結果をもたらす。

アルゴリズムを設計する営みは、中立的な計算にとどまらない。提案権を誰に与えるかを決定した瞬間、その制度は「誰の権利と厚生を第一に守るのか」という規範的判断をすでに下しているのである。

6. 正直であることが損にならない条件：戦略的ごまかしの排除

制度の規則は配分結果だけでなく、参加者が自身の希望を表明する姿勢そのものを変容させる。

一般的な配分制度では、高度な駆け引きが発生する。真に望む場所を第一志望に書いて不合格となった場合、第二志望の学校までもがすでに定員で埋まり、完全に居場所を失う危険があるからである。その結果、人々は本心を偽り、安全な選択肢を第一志望として報告する戦略をとる。

情報に長けた者が利益を得る一方で、制度を無邪気に信じた誠実な者が不利益を被るという構造的不条理が生まれる。

受入保留アルゴリズムの力は、ここでも発揮される。学生提案方式においては、学生が自身の真の希望をそのまま正直に申告することが弱支配戦略（Weakly Dominant Strategy）となる。第一志望で不合格になっても、第二志望の学校において他の志願者と対等に比較されるためである。他者の出願動向を窺い、嘘の順位を書く動機が根底から消滅する。

2005年、米国ボストン市公立学校の配分制度改革はこれを実証した好例である。従来の制度は保護者に駆け引きと偽りの申告を強要し、情報弱者の家庭を不利な状況に追い込んでいた。教育委員会が受入保留方式を導入したのは、保護者たちに「いかなる駆け引きも必要なく、子どもが本当に行きたい順に書いてよい」という信頼を取り戻すためであった。

7. 制度の正当性を問う人々のために

誰からも破棄されない安定な配分は、直ちに公正で正義にかなった社会を意味するのだろうか。私たちはこの問いの前で立ち止まらなければならない。安定性と公平性は、まったく異なる次元の概念である。

ある大学が特定の背景や階層を持つ志願者を低く評価する偏見に満ちた選考基準を持っていたとしよう。アルゴリズムはその不当な選好順位をそのまま受け取り、微塵の狂いもなく完全な安定マッチングを算出する。そこにはブロッキング・ペアが存在しないため、システム自体は揺らぐことなく機能し続ける。

しかし、私的離脱が起こらないという事実は、その制度が正義であることを何一つ保証しない。機会は万人に均等に開かれていたか。評価基準は真の実力を反映していたか。社会的格差への配慮はなされていたか。これらは数式の外側に横たわる本質的な問いである。

安定性は、利害の不一致によって制度が自壊することを防ぐための最小限の防壁にすぎない。制度が目指すべき理想と価値までを、数式が代行して決定してくれるわけではない。

制度を設計するという営みは、全員が満足するユートピアを建設することではない。限られた資源と相容れない欲望の中で、人々が相互不信に陥り裏切り合うことのないよう、信義の堤防を築くことである。

崩れない配分を作る技術を手にした今、最後に残された問いは人間に委ねられている。この強固な仕組みを通じて、私たちは誰の尊厳と選択を守るべきなのだろうか。