传统的匹配算法假定学生偏好序是严格的, 但在现实中匹配的学生一方很可能会具有弱偏好序, 这时任意一种算法的双边匹配都不能满足稳定、抗操作和帕累托最优. 在中国, 高等学校录取的“平行志愿”录取方式是一个典型的单边匹配. 因此论文将弱偏好序的匹配算法研究拓展到单边匹配领域, 设计了“挤出”匹配算法, 并证明该算法满足稳定、抗操作和帕累托最优的算法, 且匹配后学生总效用最高. 通过计算机算法模拟的方式, 全志愿模拟录取证实“挤出”算法确实能显著改进匹配效率, 且主要改善优先序排名较后的学生的效用; 在两批次高考志愿录取模拟中, “挤出”算法使学生总效用最高, 能同时保证“高分低就”率和“高分落榜”率最低.
Abstract
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.
关键词
弱优先序 /
单边匹配 /
算法设计 /
高考录取
{{custom_keyword}} /
Key words
weak preference orders /
one-side matching /
mechanism design /
college admission
{{custom_keyword}} /
中图分类号：
F062.5
{{custom_clc.code}}
({{custom_clc.text}})
{{custom_sec.title}}
{{custom_sec.title}}
{{custom_sec.content}}
参考文献
[1] Gale D, Shapley L. College admissions and the stability of marriage[J]. American Mathematical Monthly, 1962, 69(1): 9-15.
[2] Abdulkadiroglu A, Pathak P, Roth A. The New York city high school match[J]. American Economic Review, 2005a, 95(2): 364-367.
[3] Abdulkadiroglu A, Pathak P, Roth A, et al. The Boston public school match[J]. American Economic Review, 2005b, 95(2): 368-371.
[4] Dubins L, Freedman D. Machiavelli and the Gale-Shapley algorithm[J]. American Mathematical Monthly, 1981, 88(7): 485-494.
[5] Roth A. The economics of matching: Stability and incentives[J]. Mathematics of Operations Research, 1982, 7(4): 617-628.
[6] Balinski M, Sonmez T. A tale of two mechanisms: Student placement[J]. Journal of Economic Theory, 1999, 84(1): 73-94.
[7] Abdulkadiroglu A, Sonmez T. School choice: A mechanism design approach[J]. American Economic Review, 2003: 93(3): 729-747.
[8] Roth A. Deferred acceptance algorithms: History, theory, practice and open questions[J]. International Journal of Game Theory, 2008, 36: 537-569.
[9] Kesten O. Student placement to public schools in US: Two new solutions[R]. Working Paper, Carnegie Mellon University, 2004.
[10] Erdil A, Ergin H. Two-sided matching with indifferences[R]. 2006, Working Paper.
[11] Erdil A, Ergin H. What’s the matter with tie-breaking? Improving efficiency in school choice[J]. American Economics Review, 2007, 98(3): 669-689.
[12] Abdulkadiroglu A, Pathak P, Roth A. Strategy-proofness versus efficiency in matching with indifference: Redesigning the NYC high school match[R]. 2006, Working Paper.
[13] Ergin H, Sonmez T. Games of school choice under the Boston mechanism[J]. Journal of Public Economics, 2006, 90(1/2): 215-237.
[14] Zhou L. On a conjecture by Gale about one-sided matching problem[J]. Journal of Economic Theory, 1990, 52(1): 123-135.
[15] 聂海峰. 高考录取机制的博弈分析[J]. 经济学(季刊), 2007, 6(3): 899-916. Nie H F. A game-theoretical analysis of China’s college admission mechanism[J]. China Economic Quarterly, 2007, 6(3): 899-916.
[16] 魏立佳. 中国高考录取与博士生录取的机制设计[J]. 经济学(季刊), 2009, 9(1): 349-362. Wei L J. A mechanism design of China’s college and graduate school admissions problem[J]. China Economic Quarterly, 2009, 9(1): 349-362.
{{custom_fnGroup.title_cn}}
脚注
{{custom_fn.content}}
基金
2010年度教育部博士研究生学术新人奖(1231-ZX11B1);中央高校基本科研业务费专项基金(201122G011)
{{custom_fund}}
PDF(588 KB)
