解決方案
匈牙利高等教育每年透過單一的全國性制度錄取數以萬計的學生,申請者提交排序過的學程志願,並依考試分數排序。問題在於如何同時尊重申請者與學程名額。
這套制度是雙邊配對市場,但有一個特殊之處:同分。匈牙利不採抽籤(愛爾蘭)或任意因素(土耳其)來打破同分,而是採用同等對待,因此位於名額邊界的同分群體要麼全部錄取,要麼全部不錄取。
形式化而言,該制度為每個學程設定穩定的分數限制。由學生提出申請的延遲接受演算法產生最低的限制,對申請者最有利;由學院提出申請的版本則產生最高的限制。
針對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 ·