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

Optimal mechanism design of weak preference orders one-sided matching

作　　者：魏立佳[1] 

机构地区：[1]厦门大学王亚南经济研究院,厦门361005

出　　处：《系统工程理论与实践》2011年第9期1687-1695,共9页Systems Engineering-Theory & Practice

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

摘　　要：传统的匹配算法假定学生偏好序是严格的,但在现实中匹配的学生一方很可能会具有弱偏好序,这时任意一种算法的双边匹配都不能满足稳定、抗操作和帕累托最优.在中国,高等学校录取的"平行志愿"录取方式是一个典型的单边匹配.因此论文将弱偏好序的匹配算法研究拓展到单边匹配领域,设计了"挤出"匹配算法,并证明该算法满足稳定、抗操作和帕累托最优的算法,且匹配后学生总效用最高.通过计算机算法模拟的方式,全志愿模拟录取证实"挤出"算法确实能显著改进匹配效率,且主要改善优先序排名较后的学生的效用;在两批次高考志愿录取模拟中,"挤出"算法使学生总效用最高,能同时保证"高分低就"率和"高分落榜"率最低.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 efficient for one-side matching.We also use simulation method to prove that extruding mechanism promotes the efficiency of the total matching,and it mainly promotes the efficiency of students in the latter part of the priority orders;in the simulation of college admission,using extruding mechanism ensure the largest total utilities of all the students and the lowest rejection rate of high quality students.

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

分 类 号：F062.5[经济管理—政治经济学]