DAアルゴリズム（受入保留方式）の実装と理解：安定マッチングの理論的基礎
本記事は、GaleとShapleyが1962年に提案した「DAアルゴリズム」（Deferred Acceptance Algorithm / 受入保留方式）をPythonコードで実装し、その動作原理と背後にあるマッチング理論の概念的な理解を深めることを目的としています。このアルゴリズムは、学生（提案者）と大学（受入者）といった二つのグループ間の「安定マッチング」を求めるための手法です。
記事ではまず、望ましいマッチング結果が持つべき3つの性質について解説しています。一つ目は「個人合理性」（Individual Rationality）であり、参加者が誰ともマッチしない状態よりはマシな結果であること（ブロックされないこと）を指します。二つ目は「耐戦略性」（Strategy-Proofness）であり、参加者が自分の希望を偽って有利な結果を得ることができない性質です。三つ目が最も重要な「安定性」（Stability）であり、どの学生も現在のマッチングに対して不満を持たず、かつ大学側も受け入れている誰かよりその学生を好むといった「ブロッキングペア」が存在しない状態を指します。
DAアルゴリズムは、これらの性質（個人合理性、耐戦略性、安定性）を満たすことが理論的に証明されています。具体的なプロセスとして、提案者（例：学生）が志望順位の高い大学から順番に「仮出願」を行い、受入者（大学）はその定員に基づき好ましい候補者を一時的に受け入れます。この過程をステップ2以降も繰り返すことで、最終的な安定マッチングが決定されます。
記事の後半では、実際に学生と大学のマッチングや、研修医と病院のマッチングといった具体的な例を用いてPythonコードによる実行トレース（例1, 例2）を示し、アルゴリズムの動作を詳細に解説しています。また、定員合計が提案者数を下回る場合や、特定のグループからの出願がない場合の未マッチな状況も具体的に示されています。
背景
本記事は、経済学やコンピュータサイエンスにおける「マッチング市場」の理論的枠組みを扱っています。特にDAアルゴリズムは、学生と大学のマッチング（例：日本の医学部入試）など、二者間の選好に基づく配属決定プロセスにおいて、公平で安定した結果を得るための基礎的なモデルとして知られています。
重要用語解説
- DAアルゴリズム: GaleとShapleyが1962年に提案した受入保留方式。学生（提案者）から大学（受入者）へ順番に出願させ、定員制に基づき安定なマッチングを決定する手法。
- 個人合理性: 参加者が現在のマッチング結果を受け入れるインセンティブがある状態。誰ともマッチしないよりはマシであるという最低限の条件を満たすこと。
- 耐戦略性: 参加者が自分の真の希望（選好）を正直に表明することが、常に最善の結果をもたらす性質。制度設計において公平性を保証する重要な要素。
今後の影響
このアルゴリズムは、配属やマッチングが必要なあらゆる分野（医療研修医、大学進学など）における公正なシステム設計の基礎となります。理論的な理解を深めることで、より複雑な市場構造や制約条件に対応した応用モデル開発に繋がります。