DAアルゴリズムとは？

受け入れ保留アルゴリズム（Deferred Acceptance Algorithm）の仕組みと公立高校入試への応用について

DAアルゴリズムの基本概念

DAアルゴリズム（受け入れ保留アルゴリズム）は、1962年にデビッド・ゲール氏とロイド・シャプレー氏によって考案されたマッチング理論のアルゴリズムです。このアルゴリズムは2012年にノーベル経済学賞を受賞し、世界中の様々な割り当て問題（学校選択、研修医の病院配属など）に応用されています。

DAアルゴリズムの最大の特徴は、以下の3つです：

公平性：全ての学生が志望と成績に基づいて適切に割り振られることです。どの学生も、他の学生のマッチング結果に対して「自分ならもっと良い（優先順位が高い）はず」と主張できるケースが存在しません。
安定性：マッチング後に、任意の学生と学校の組み合わせが、現行の割り当てに対して両者ともより良いと感じる（ブロッキングペアとなる）状態が存在しないことです。
戦略的操作不可能性：学生が本当の志望順位を正直に申告することが最適な戦略となることです。

準備段階: 各生徒は志望校を順位付けしたリストを提出します。各学校は定員と合格最低点（または選抜基準）を設定します。
第1ラウンド: 各生徒は自分の第1志望校に出願します。各学校は出願してきた生徒を成績順に並べ、定員内であれば全員を「仮合格」とします。定員を超える場合は、成績上位から定員分だけを「仮合格」とし、残りは「待機」とします。
第2ラウンド以降: 「待機」となった生徒は、次の志望校に出願します。各学校は前ラウンドで「仮合格」とした生徒と新たに出願してきた生徒を合わせて成績順に並べ、定員内であれば全員を「仮合格」とします。定員を超える場合は、成績上位から定員分だけを「仮合格」とし、残りは「待機」とします。
終了条件: 全ての生徒が「仮合格」を得るか、志望校リストを使い果たすまで、上記のプロセスを繰り返します。最終的に「仮合格」となっている組み合わせが、最終的な割り当て結果となります。

初期状態:

DAアルゴリズムの実行後、各生徒がどの高校に最終的に合格したかを視覚的に表現したものです。この結果は、各生徒の志望順位と各学校の定員を考慮した最適なマッチングとなっています。

※生徒Bは東高校（第1志望）の定員の関係で待機となり、第2志望の南高校に進みました

東高校（定員1名）

西高校（定員1名）

南高校（定員2名）

経済状況に関わらず、全ての生徒が自分の実力に合った最良の高校に入学できる機会を得られます。私立高校を滑り止めにできない経済的に困窮している家庭の生徒でも、安心して難関校に挑戦することができます。

生徒は「受かりそうな学校」ではなく「行きたい学校」を正直に順位付けするのが最適な戦略となります。複雑な受験戦略を考える必要がなくなり、本来の志望校に挑戦する機会が増えます。

複数合格による空席や繰り上げ合格の混乱がなくなり、最適なマッチングが実現します。学校側も定員を効率的に埋めることができ、行政コストの削減にもつながります。

「落ちたらどうしよう」という不安を減らし、生徒と保護者の心理的負担を軽減します。志望校の合格最低点に達していれば、必ずその学校に入れることが保証されるため、安心して受験に臨むことができます。

A: はい、DAアルゴリズムは数学的に証明された公平性を持っています。全ての生徒が自分の真の志望順位を申告することが最適な戦略となり、また全ての生徒が自分より低い順位の学校に入学することはありません。

A: 主なコストはシステム開発費用です。既存の入試システムをDAアルゴリズムに対応させるためのシステム改修が必要になりますが、長期的には繰り上げ合格などの手続きが不要になるため、行政コストの削減につながります。

A: 海外ではニューヨーク市やボストン市の公立高校入試、全米の研修医マッチングシステムなどで導入されています。日本国内では一部の私立大学のAO入試などで類似のシステムが採用されていますが、公立高校入試での本格的な導入はまだ進んでいません。

A: 理論上は無制限ですが、実際の運用では行政側が上限を設定することが多いです。例えばニューヨーク市では最大12校まで志望校を書くことができます。日本での導入を考える場合、各都道府県内の公立高校数や行政コストを考慮して適切な上限を設定することになるでしょう。