弱偏好序下的最优单边匹配算法设计

传统的匹配算法假定学生偏好序是严格的, 但在现实中匹配的学生一方很可能会具有弱偏好序, 这时任意一种算法的双边匹配都不能满足稳定、抗操作和帕累托最优. 在中国, 高等学校录取的“平行志愿”录取方式是一个典型的单边匹配. 因此论文将弱偏好序的匹配算法研究拓展到单边匹配领域, 设计了“挤出”匹配算法, 并证明该算法满足稳定、抗操作和帕累托最优的算法, 且匹配后学生总效用最高. 通过计算机算法模拟的方式, 全志愿模拟录取证实“挤出”算法确实能显著改进匹配效率, 且主要改善优先序排名较后的学生的效用; 在两批次高考志愿录取模拟中, “挤出”算法使学生总效用最高, 能同时保证“高分低就”率和“高分落榜”率最低.

Optimal mechanism design of weak preference orders one-sided matching

The DA algorithm requires that both the preference orders and priority orders should be strict. However,there are often weak preference orders in matching.In this situation,any algorithm can't be stable,strategy-proof and Pareto efficient at the same time in two-side matching.This paper studies the matching mechanism with weak preference orders in one-side matching based on the applications of matching theory in China.Extruding mechanism is not only stable,strategy-proof and Pareto efficient, but also most ...