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.
Key words
weak preference orders /
one-side matching /
mechanism design /
college admission
{{custom_keyword}} /
{{custom_sec.title}}
{{custom_sec.title}}
{{custom_sec.content}}
References
[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_en}}
Footnotes
{{custom_fn.content}}
PDF(588 KB)
