解決策
ハンガリーの高等教育は、毎年数万人の学生を単一の全国的制度を通じて受け入れており、志願者はランク付けされたプログラム選択肢を提出し、試験スコアによって順序付けられる。課題は、志願者とプログラムの定員の両方をいかに尊重するかである。
この制度は、ひねりのある両面マッチング市場である。すなわち同点である。くじ引き(アイルランド)や恣意的な要素(トルコ)で同点を解消するのではなく、ハンガリーは平等な扱いを採用しているため、定員の境界にある同点グループは全員が合格するか全員が不合格となるかのいずれかである。
形式化すると、この制度は各プログラムに対して安定したスコア上限を設定する。学生提案型の遅延受諾アルゴリズムは最も低い上限をもたらし、志願者にとって最適である。大学提案型は最も高い上限をもたらす。
実際の2008年および2009年の入学データと共通定員構造(プログラム定員の上に階層化された学部定員)に関する研究は、問題が困難になることを示しているが、整数計画法の定式化によって実際に解くことができる。
達成したこと
同点に対する単一のルールを伴うスコア順位付けされた遅延受諾
うまくいった理由
スコア順位付けされた安定マッチングは公平であり、大規模に再現可能である。
同点スコアの平等な扱いは、恣意的なくじ引きによる不合格を避ける。
安定した上限とは、交換を双方が望むような志願者とプログラムの組み合わせが存在しないことを意味する。
数万人が一度に応募する場合、委員会ではなくアルゴリズムが機能する。
応用できること
大規模な中央集権的マッチングでは、委員会ではなくアルゴリズムが決定すべきである。明確な同点ルールを伴う安定したスコア順位付けマッチングは公平かつ予測可能である。
その後
ハンガリーは中央集権的なスコア上限入学制度を大学への標準的な経路として維持し、学術研究(Biróら)は同点や重複する定員に対処するための改良を続け、計算上困難なマッチング問題を解く手法を発表した。
出典をたどる
出典
- College admissions with stable score-limits Central European Journal of Operations Research / MTA Repository · real.mtak.hu
- College admissions with ties and common quotas: Integer programming approach European Journal of Operational Research / Corvinus Research Archive · unipub.lib.uni-corvinus.hu ·