Reducing the role of random numbers in matching algorithms for school admission

Hulsbergen, Wouter (2016): Reducing the role of random numbers in matching algorithms for school admission.

Abstract

New methods for solving the college admissions problem with indifference are presented and characterised with a Monte Carlo simulation in a variety of simple scenarios. Based on a qualifier defined as the average rank, it is found that these methods are more efficient than the Boston and Deferred Acceptance algorithms. The improvement in efficiency is directly related to the reduced role of random tie-breakers. The strategy-proofness of the new methods is assessed as well.

• Item Type: MPRA Paper
• Language: English
• Keywords: college admission problem; deferred acceptance algorithm; Boston algorithm; Zeeburg algorithm; pairwise exchange algorithm; strategic behaviour
• Subjects: I - Health, Education, and Welfare > I2 - Education and Research Institutions

References

[1] A. E. Roth, M. Sotomayor, The College Admissions Problem Revisited, Econo- metrica 57 (3) (1989) 559–570. URL http://www.jstor.org/stable/1911052

[2] A. E. Roth, Deferred Acceptance Algorithms: History, Theory, Practice, and Open Questions, Working Paper 13225, National Bureau of Economic Research (July 2007). doi:10.3386/w13225. URL http://www.nber.org/papers/w13225

[3] A. Abdulkadiro ̆glu, T. So ̈nmez, School Choice: A Mechanism Design Approach, The American Economic Review 93 (3) (2003) 729–747. URL http://www.jstor.org/stable/3132114

[4] A. Abdulkadiro ̆glu, P. A. Pathak, A. E. Roth, Strategy-proofness versus Effi- ciency in Matching with Indifferences: Redesigning the New York City High School Match, Working Paper 14864, National Bureau of Economic Research (April 2009). doi:10.3386/w14864. URL http://www.nber.org/papers/w14864

[5] A. Abdulkadiro ̆glu, Y.-K. Che, Y. Yasuda, Resolving Conflicting Preferences in School Choice: The “Boston Mechanism” Reconsidered, The American Eco- nomic Review 101 (1) (2011) 399–410. URL http://www.jstor.org/stable/41038793

[6] D. Gale, L. S. Shapley, College Admissions and the Stability of Marriage, The American Mathematical Monthly 69 (1) (1962) 9–15. URL http://www.jstor.org/stable/2312726

[7] L. E. Dubins, D. A. Freedman, Machiavelli and the Gale-Shapley Algorithm, The American Mathematical Monthly 88 (7) (1981) 485–494. URL http://www.jstor.org/stable/2321753

[8] M. de Haan, P. A. Gautier, H. Oosterbeek, B. van der Klaauw, The perfor- mance of school assignment mechanisms in practice, CESifo Area Conference on the Economics of Education, 2015. URL http://www.cesifo-group.de/dms/ifodoc/docs/Akad_Conf/CFP_ CONF/CFP_CONF_2015/ee15-Hanushek/Papers/ee15-Oosterbeek.pdf