Asymptotic Equivalence of Immediate and Deferred Acceptance

あなたは、すべての子供に学校の席が必要であり、かつ、生徒数と座席数が正確に一致している、活気ある都市の市長であると想像してください。問題は単に「席を見つけること」ではなく、「適切な席を見つけること」です。すべての家族には、お気に入りの学校のリストがあります。「私の理想の学校」から「どうしても行かなければならない場合に行く学校」まで。都市にはルールもあります。例えば、近所に住んでいる子供や、すでに兄弟がいる子供を優先する学校があるかもしれません。そして、責任ある立場にある人々にとっての大きな疑問は、**「どのようにすれば、全員が最大限に幸せになれるように、子供たちを学校にマッチングさせられるか？」**ということです。

数十年にわたり、専門家たちはこれを行う2つの主要な方法について議論してきました。第一の方法は、**「繰延受理（Deferred Acceptance: DA）」**と呼ばれます。これは、ゆっくりとした、慎重なダンスのようなものです。生徒たちは自分たちの第一希望の学校に応募します。学校は、自分たちの好みの志願者を保持しますが、永遠に「はい」と言うわけではありません。単に「たぶん（保留）」と言うだけです。もし後でもっと優れた生徒が現れたら、学校は彼らを入れ替えることができます。このプロセスは、全員が落ち着くまで繰り返されます。これは公平で、不正が不可能なことで有名ですが、少し煩雑で非効率的になることがあります。

第二の方法は、「即時受理（Immediate Acceptance: IA）」、いわゆる「ボストン・メカニズム」として知られるものです。これは、もっと慌ただしいレースのようなものです。生徒たちは列に並び、自分の第一希望に応募します。学校は列を見て、優先順位に基づいて自分たちの好みの生徒を選び、「合格！」と即座に告げます。もし落選した場合、彼らは即座に第二希望へと駆け寄ります。問題は、もし第一希望に応募するのが遅すぎると、たとえその学校を本当に望んでいたとしても、より高い優先順位を持つ人が先に申し込んだために、その席を失ってしまう可能性があることです。そのため、IAはしばしば不公平である、あるいは操作しやすいと批判されます。しかし、IAには一つの大きな超能力があります。それは、もし全員が自分の望みを正直に話すならば、IAは「誰かを不幸にすることなしには、誰も今より幸せにできない」という結果を保証するということです。これは「パレート効率的（Pareto efficient）」と呼ばれます。

さて、ここが百万ドルの問いです。IAの超能力は、現実の世界で本当に大きな違いをもたらすのでしょうか？ IAは、DAよりも生徒たちを「ずっと良い」学校に入れるのでしょうか？それとも、その差はごくわずかで、目に見えないほど小さなものなのでしょうか？これが、ジョシュエ・オルテガ（Josué Ortega）が論文で取り組んでいるパズルです。

---

学校選びの大レース：二つのメカニズムの物語

クイーンズ大学ベルファストの研究者であるジョシュエ・オルテガは、この論争に決着をつけるために、大規模な思考実験を行いました。彼は、複雑な歴史や政治が絡み合う現実の都市を見るのではなく、「ランダムな市場」を想定しました。つまり、すべての生徒の好みの学校リストが、まるで名前を帽子から引き出す時のように、完全にランダムに選ばれる世界です。この世界には、$n$ 人の生徒と $n$ 校の学校が存在します。

オルテガは、「平均順位」を測定したいと考えました。もし、割り当てられた学校が、自分のリストの中でどれくらい上にあったかに基づいて、すべての生徒にスコアを与えられるとしたらどうなるでしょうか。もし第1希望の学校になれたら、順位は1です。もし第100希望の学校になったら、順位は100です。目標はこの数字をできるだけ低く保つことです。

長い間、私たちは（ゆっくりとした慎重なダンスである）DAについての答えを知っていました。1970年代に数学者たちは、ランダムな市場において、平均的な生徒はだいたい $\log n$ （$n$ の対数）の順位の学校に落ち着くことを突き止めました。もし1,000人の生徒がいれば、平均順位はおよそ7です。もし10万人いれば、およそ11になります。数値は増えますが、非常に緩やかです。

では、（慌ただしいレースである）IAについてはどうでしょうか？IAは仕組みが異なるため――応募の順番が重要であり、生徒は「遅れた」という理由だけで拒絶される可能性があるため――数学者たちは、より複雑になるのではないかと考えました。一部のコンピュータ科学者はこれを解こうと試みましたが、特定の順位を得る確率を計算することはできても、全員の「平均順位」を導き出すことはできませんでした。彼らは、これも対数的になるのではないかと推測していましたが、誰も証明できていませんでした。

「クーポンコレクター」の秘密

オルテガの突破口は、これら二つのメカニズムが、見た目は全く異なっていても、実は同じゲームをプレイしていることに気づいたことでした。彼は、このことを説明するために、**「クーポンコレクター問題（Coupon Collector Problem）」**という古典的なパズルを用いました。

想像してみてください。あなたは、$n$ 種類の異なるトレーディングカードの全セットを集めようとしています。シリアル食品の箱を買うたびに、ランダムなカードが1枚手に入ります。すべてのカードを少なくとも1枚ずつ集めるためには、何箱買う必要がありますか？
その答えはおよそ $n \times \log n$ です。最後の数枚のレアカードを見つけるために、膨大な数の箱を買うことになります。

オルテガは、**繰延受理（DA）**がまさにこれと同じであることを示しました。すべての学校が少なくとも1つの申し込みを受けるまで、生徒たちは申し込みを続けます。全員が行う総申し込み数は、すべてのクーポンを集めるために必要なシリアル箱の数とほぼ同じになります。したがって、平均的な生徒が行う申し込み回数は約 $\log n$ であり、彼らの最終的な学校の順位もまた約 $\log n$ となります。

次に、オルテガは**即時受理（IA）**に目を向けました。最初は、生徒がすぐに次の申し込みを続けられない（ラウンドが終わるのを待たなければならない）ため、違って見えるかもしれません。しかし、オルテガはプロセスを特定の視点から見ることで、これもまた「クーポンコレクター」であることを突き止めました。

彼は、少し「健忘症」のバージョンを想像しました。生徒が、たとえすでに試したことがある学校であっても、ランダムに学校を選び続けるとします。もし以前試した学校を選んだ場合、その試行は無視されます（これは「無駄な」試行です）。オルテガは、たとえこうした「無駄な」試行があったとしても、すべての学校を埋めるために必要な「実際の」申し込み数は、依然としてクーポンコレクター問題とほぼ同じであることを証明しました。

大いなる判明

結論はこうです。二つの手法の違いは、驚くほど小さいのです。

オルテガは、市場が巨大になるにつれて（$n$ が非常に大きくなるにつれて）、即時受理（IA）システムにおける生徒の平均順位も、またおよそ $\log n$ になることを数学的に証明しました。

これは、たとえIAが「パレート効率的」であったとしても（つまり、全員が真実を話すなら理論的に完璧であっても）、DAと比較して、生徒たちに劇的なメリットを与えるわけではないことを意味します。大きな、目に見えるほどの改善（一次的な改善）は、そこには存在しないのです。

オルテガの論文は、IAが大規模なランダム市場において、生徒の結果を劇的に改善する「魔法の弾丸」であるという考えを明確に否定しています。IAは、特定の小さなシナリオや特定の優先ルールにおいては、わずかに優れているかもしれませんが、一般的なケースにおいて、二つのメカニズムは**漸近的に等価（asymptotically equivalent）**であることを、この論文は示しています。どちらも、市場の規模に対して対数的に、生徒たちを学校に落ち着かせます。

これがなぜ重要なのか

この発見は、「即時受理」システムの支持者にとっては少し残念なニュースかもしれませんが、数学にとっては救いです。それは、「パレート効率性」というものが、平均的な幸福度という観点では、一種の蜃気楼であることを教えてくれます。不公平で操作されやすいと批判されることが多いメカニズムが、公平で騙しにくいメカニズムよりも、実際に優れた平均的な結果をもたらすわけではないのです。

オルテガの研究は、この発見を他のバリエーションにも広げています。学校が複数の座席を持っている場合（一対多のマッチング）でも、生徒が満席の学校をスキップできる場合（「スキップありのIA」と呼ばれる変種）でも、結果は変わりません。平均順位は依然として $\log n$ の周りに留まります。

ですから、次に誰かが「より効率的だから」という理由で「ボストン・メカニズム」を使うべきだと主張しているのを聞いたら、あなたは微笑んでこう言えるでしょう。「確かに効率的かもしれませんが、平均的には、もう一方の方法よりも生徒たちをより良い学校に入れるわけではないのですよ」と。学校選びという壮大なレースにおいて、両方のランナーは、ほぼ同時にゴールラインを駆け抜けているのです。