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

摘要：

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

关键词：弱优先序、单边匹配、算法设计、高考录取

所属期刊栏目：31

分类号：F062.5(经济学分支科学)

资助基金：2010年度教育部博士研究生学术新人奖1231-ZX11B1;中央高校基本科研业务费专项基金201122G011

在线出版日期：2012-02-21（万方平台首次上网日期，不代表论文的发表时间）

页数：共9页

页码：1687-1695