The cost of strategy-proofness in school choice. (English) Zbl 1521.91251
Summary: We compare the outcomes of the most prominent strategy-proof and stable algorithm (deferred acceptance, DA) and the most prominent strategy-proof and Pareto optimal algorithm (top trading cycles, TTC) to the allocation generated by the rank-minimizing mechanism (RM). While one would expect that RM improves upon both DA and TTC in terms of rank efficiency, the size of the improvement is nonetheless surprising. Moreover, while it is not explicitly designed to do so, RM also significantly improves the placement of the worst-off student. Furthermore, RM generates less justified envy than TTC. We corroborate our findings using data on school admissions in Budapest.
MSC:
| 91B68 | Matching models |
References:
| [1] | Abdulkadiroglu, A.; Andersson, T., School choice (2022), National Bureau of Economic Research |
| [2] | Abdulkadiroglu, A.; Dur, U. M.; Grigoryan, A., School assignment by match quality (2021), National Bureau of Economic Research, Tech. rep |
| [3] | Abdulkadiroğlu, A.; Pathak, P. A.; Roth, A. E., Strategy-proofness versus efficiency in matching with indifferences: redesigning the NYC high school match, Am. Econ. Rev., 99, 1954-1978 (2009) |
| [4] | Abdulkadiroğlu, A.; Sönmez, T., School choice: a mechanism design approach, Am. Econ. Rev., 93, 729-747 (2003) |
| [5] | Abdulkadiroğlu, A.; Che, Y.-K.; Pathak, P. A.; Roth, A. E.; Tercieux, O., Efficiency, justified envy, and incentives in priority-based matching, Am. Econ. Rev. Insights, 2, 425-442 (2020) |
| [6] | Abdulkadiroğlu, A.; Sönmez, T., Random serial dictatorship and the core from random endowments in house allocation problems, Econometrica, 66, 689-701 (1998) · Zbl 1019.91016 |
| [7] | Aldous, D. J., The ζ (2) limit in the random assignment problem, Random Struct. Algorithms, 18, 381-418 (2001) · Zbl 0993.60018 |
| [8] | Allen, R.; Burgess, S.; McKenna, L., The short-run impact of using lotteries for school admissions: early results from Brighton and Hove’s reforms, Trans. Inst. Br. Geogr., 38, 149-166 (2013) |
| [9] | Ashlagi, I.; Kanoria, Y.; Leshno, J., Unbalanced random matching markets: the stark effect of competition, J. Polit. Econ., 125, 69-98 (2017) |
| [10] | Aue, R.; Klein, T.; Ortega, J., What happens when separate and unequal school districts merge? (2022), ZEW - Centre for European Economic Research Discussion Paper 20-032 |
| [11] | Basteck, C.; Klaus, B.; Kübler, D., How lotteries in school choice help to level the playing field, Games Econ. Behav., 129, 198-237 (2021) · Zbl 1470.91190 |
| [12] | Biró, P., Student admissions in Hungary as Gale and Shapley envisaged (2008), University of Glasgow Technical Report TR-2008-291 |
| [13] | Bodoh-Creed, A., Optimizing for distributional goals in school choice problems, Manag. Sci., 66, 3657-3676 (2020) |
| [14] | Brown, M.; Donnelly, C.; Shevlin, P.; Skerritt, C.; McNamara, G.; O’Hara, J., The rise and fall and rise of academic selection: the case of Northern Ireland, Ir. Stud. Int. Aff., 32, 477-498 (2021) |
| [15] | Cerrone, C.; Hermstrüwer, Y.; Kesten, O., School choice with consent: an experiment (2022), MPI Collective Goods Discussion Paper |
| [16] | Che, Y.-K., Tercieux, O., 2017. Top trading cycles in prioritized matching: an irrelevance of priorities in large markets. Columbia University. Unpublished Manuscript. |
| [17] | Che, Y.-K.; Tercieux, O., Payoff equivalence of efficient mechanisms in large matching markets, Theor. Econ., 13, 239-271 (2018) · Zbl 1396.91563 |
| [18] | Coldron, J.; Tanner, E.; Finch, S.; Shipton, L.; Wolstenholme, C.; Willis, B.; Demack, S.; Stiell, B., Secondary school admissions (2008), Department for Children, Schools and Families, Tech. rep |
| [19] | Featherstone, C., 2020. Rank efficiency: Modeling a common policymaker objective. University of Pennsylvania. Unpublished paper. |
| [20] | Frieze, A.; Pittel, B. G., Probabilistic analysis of an algorithm in the theory of markets in indivisible goods, Ann. Appl. Probab., 768-808 (1995) · Zbl 0843.90031 |
| [21] | Frieze, A.; Sorkin, G. B., The probabilistic relationship between the assignment and asymmetric traveling salesman problems, SIAM J. Comput., 36, 1435-1452 (2007) · Zbl 1161.90468 |
| [22] | Gale, D.; Shapley, L. S., College admissions and the stability of marriage, Am. Math. Mon., 69, 9-15 (1962) · Zbl 0109.24403 |
| [23] | Galichon, A.; Ghelfi, O.; Henry, M., Stable and extremely unequal, Econ. Lett., 226, Article 111101 pp. (2023) · Zbl 1521.91246 |
| [24] | Kesten, O., School choice with consent, Q. J. Econ., 125, 1297-1348 (2010) · Zbl 1197.91153 |
| [25] | Knoblauch, V., Marriage matching and gender satisfaction, Soc. Choice Welf., 32, 15-27 (2009) · Zbl 1183.91113 |
| [26] | Knuth, D., An exact analysis of stable allocation, J. Algorithms, 20, 431-442 (1996) · Zbl 0852.68034 |
| [27] | Kosinar, P., 2021. Probability of getting into my favorite PhD. Mathematics Stack Exchange. |
| [28] | Krokhmal, P. A.; Pardalos, P. M., Random assignment problems, Eur. J. Oper. Res., 194, 1-17 (2009) · Zbl 1179.90212 |
| [29] | Liu, Q., Pycia, M., 2016. Ordinal efficiency, fairness, and incentives in large markets. SSRN preprint. |
| [30] | Manea, M., Asymptotic ordinal inefficiency of random serial dictatorship, Theor. Econ., 4, 165-197 (2009) |
| [31] | Nikzad, A., Rank-optimal assignments in uniform markets, Theor. Econ., 17, 25-55 (2022) · Zbl 1489.91181 |
| [32] | Noden, P.; West, A.; Hind, A., Banding and ballots: secondary school admissions in England: admissions in 2012/13 and the impact of growth of academies (2014), The Sutton Trust, Tech. rep |
| [33] | Olin, B., Asymptotic properties of random assignment problems (1992), Stockholm Royal Institute of Technology, PhD Thesis |
| [34] | Oosterbeek, H., Ruijs, N., De Wolf, I., 2020. Using admission lotteries to estimate heterogeneous effects of elite schools. Unpublished paper, SSRN. |
| [35] | Ortega, J., Social integration in two-sided matching markets, J. Math. Econ., 78, 119-126 (2018) · Zbl 1416.91305 |
| [36] | Ortega, J., The losses from integration in matching markets can be large, Econ. Lett., 174, 48-51 (2019) · Zbl 1422.91557 |
| [37] | Ortega, J., Ziegler, G., 2023. The limits of school choice with consent. Unpublished. |
| [38] | Parviainen, R., Random assignment with integer costs, Comb. Probab. Comput., 13, 103-113 (2004) · Zbl 1048.60010 |
| [39] | Pathak, P. A.; Sönmez, T., School admissions reform in Chicago and England: comparing mechanisms by their vulnerability to manipulation, Am. Econ. Rev., 103, 80-106 (2013) |
| [40] | Pittel, B., The average number of stable matchings, SIAM J. Discrete Math., 2, 530-549 (1989) · Zbl 0729.05004 |
| [41] | Pittel, B., On likely solutions of a stable marriage problem, Ann. Appl. Probab., 358-401 (1992) · Zbl 0753.60016 |
| [42] | Pycia, M., 2019. Evaluating with statistics: Which outcome measures differentiate among matching mechanisms? University of Zurich. Unpublished paper. |
| [43] | Pycia, M., Troyan, P., 2021. A theory of simplicity in games and mechanism design. University of Zurich. Unpublished paper. |
| [44] | Roth, A. E., The college admissions problem is not equivalent to the marriage problem, J. Econ. Theory, 36, 277-288 (1985) · Zbl 0594.90002 |
| [45] | Roth, A. E.; Sotomayor, M., Two-sided matching, Handbook of game theory with economic applications, vol. 1, 485-541 (1992) · Zbl 0968.91516 |
| [46] | Schilling, M. F., The surprising predictability of long runs, Math. Mag., 85, 141-149 (2012) · Zbl 1246.60018 |
| [47] | Sethuraman, J., 2022. A note on the average rank of rank-optimal assignments. Unpublished. |
| [48] | Söderström, M.; Uusitalo, R., School choice and segregation: evidence from an admission reform, Scand. J. Econ., 112, 55-76 (2010) |
| [49] | Tang, Q.; Yu, J., A new perspective on Kesten’s school choice with consent idea, J. Econ. Theory, 154, 543-561 (2014) · Zbl 1309.91103 |
| [50] | Troyan, P., Non-obvious manipulability of the rank-minimizing mechanism (2022), arXiv preprint |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
