Top

Social Choice and Welfare

Published in:

07-01-2024 | Original Paper

Robustness to manipulations in school choice

Authors: Alexander Nesterov, Olga Rospuskova, Sofia Rubtcova

Published in: Social Choice and Welfare | Issue 3/2024

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

We study the school choice problem and propose a new criterion for comparing non-strategy-proof mechanisms: robustness to manipulations. Mechanism A is more robust than mechanism B if each student (given any preferences of this student and any profile of schools’ priorities) can potentially access a smaller set of schools via a profitable manipulation under mechanism A than under mechanism B. This criterion strengthens the two independent criteria proposed by Bonkoungou and Nesterov (Theor Econ 16(3):881–909, 2021) and Decerf and Van der Linden (J Econ Theory 197:105313, 2021). We then show that all results obtained with these two criteria, as well as with the original criterion proposed by Pathak and Sönmez (Am Econ Rev 103(1):80–106, 2013), can also be obtained using robustness. Our results provide a stronger rationalization for a wide range of reforms in school choice and college admissions system.

previous article The Quintilian School in the history of Social Choice: an early tentative step from plurality rule to pairwise comparisons

next article Consistent social ranking solutions

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Available only for authorised users

The definitions of the mechanisms are given in “Mechanisms” section.

Pathak and Sönmez (2013) provide three logically related criteria but only the weakest can be used to compare school choice mechanisms.

This inspired the term robustness similar to the hypothetical worst-case scenario in the robust mechanism design literature (Bergemann and Morris 2005; Andreyanov and Sadzik 2021; Suzdaltsev 2022).

The results on the constrained Boston and \( DA \) have been strengthened using a stronger criterion of counting the number of students with an incentive to manipulate (Bonkoungou and Nesterov 2023; Imamura and Tomoeda 2022). Chen et al. (2016) compare stable mechanisms using a stronger criterion.

There have been other attempts to improve upon the Boston mechanism in terms of incentive properties that can be evaluated using PS-manipulability and that we do not consider in the paper: the Boston-with-skips mechanism (Alcalde 1996; Miralles 2009; Harless 2019; Dur 2019; Mennle and Seuken 2021), also known as Modified Boston Mechanism or Adaptive Boston Mechanism, and the Secure Boston mechanism (Dur et al. 2019). The recent modification called the Neutralized Boston mechanism (Decerf 2023) is compared to the Boston mechanism using a criterion specific to this mechanism.

For a formal statement of AM-manipulability, see Definition 3.

For a formal statement of BN-manipulability, see Definition 4.

The converse is not true. Indeed, see Table 1: \(\beta ^{k+1}\) is at least as AM-manipulable as \(\beta ^k\), but the same is not true by robustness.

Note: if two mechanisms are comparable by robustness, this does not imply the strict comparison by AM-manipulability.

Indeed, since for each student at fixed preference relation the set of strategically accessible schools via mechanism \(\psi \) is weakly included in the set of strategically accessible schools via mechanism \(\varphi \), the union of the strategically accessible schools over all preference relations via \(\psi \) is also included in the union of the strategically accessible schools over all preference relations via \(\varphi \).

Note that the parameter k in Chinese Parallel mechanism has a different meaning than in the rest of the mechanisms. For this reason, we write this parameter in parentheses.

By \(P^{k+1}\) we denote a preference profile that consists of the first \(k+1\) rows of the preference profile P.

Lemma 1, Bonkoungou and Nesterov (2021).

Abdulkadiroğlu A, Sönmez T (2003) School choice: a mechanism design approach. Am Econ Rev 93(3):729–747CrossRef

Alcalde J (1996) Implementation of stable solutions to marriage problems. J Econ Theory 69(1):240–254CrossRef

Andreyanov P, Sadzik T (2021) Robust mechanism design of exchange. Rev Econ Stud 88(2):521–573CrossRef

Arribillaga RP, Massó J (2016) Comparing generalized median voter schemes according to their manipulability. Theor Econ 11(2):547–586CrossRef

Arribillaga RP, Massó J (2017) Comparing voting by committees according to their manipulability. Am Econ J Microecon 9(4):74–107CrossRef

Balinski M, Sönmez T (1999) A tale of two mechanisms: student placement. J Econ Theory 84(1):73–94CrossRef

Bergemann D, Morris S (2005) Robust mechanism design. Econometrica 73(6):1771–1813CrossRef

Bonkoungou S, Nesterov A (2021) Comparing school choice and college admissions mechanisms by their strategic accessibility. Theor Econ 16(3):881–909CrossRef

Bonkoungou S, Nesterov A (2023) Incentives in matching markets: counting and comparing manipulating agents. Theoretical Economics (forthcoming)

Chen Y, Kesten O (2017) Chinese college admissions and school choice reforms: a theoretical analysis. J Polit Econ 125(1):99–139CrossRef

Chen P, Egesdal M, Pycia M, Yenmez MB (2016) Manipulability of stable mechanisms. Am Econ J Microecon 8(2):202–214CrossRef

Decerf B (2023) A modification aimed at reducing the manipulability and inefficiency of the Boston school choice mechanism. Soc Choice Welf 60(1–2):75–101CrossRef

Decerf B, Van der Linden M (2021) Manipulability in school choice. J Econ Theory 197:105313CrossRef

Dur UM (2019) The modified Boston mechanism. Math Soc Sci 101:31–40CrossRef

Dur U, Hammond RG, Morrill T (2019) The secure Boston mechanism: theory and experiments. Exp Econ 22(4):918–953CrossRef

Gale D, Shapley LS (1962) College admissions and the stability of marriage. Am Math Mon 69(1):9–15CrossRef

Haeringer G, Klijn F (2009) Constrained school choice. J Econ Theory 144(5):1921–1947CrossRef

Harless P (2019) Immediate acceptance with or without skips? Comparing school assignment procedures. Working paper

Imamura K, Tomoeda K (2022) Measuring manipulability of matching mechanisms. Available at SSRN 4000419

Mennle T, Seuken S (2021) Partial strategyproofness: relaxing strategyproofness for the random assignment problem. J Econ Theory 191:105144CrossRef

Miralles A (2009) School choice: the case for the Boston mechanism. In: International conference on auctions, market mechanisms and their applications. Springer, pp 58–60

Pathak PA, Sönmez T (2011) School admissions reform in Chicago and England: Comparing mechanisms by their vulnerability to manipulation. NBER working paper no. 16783. National Bureau of Economic Research

Pathak PA, Sönmez T (2013) School admissions reform in Chicago and England: comparing mechanisms by their vulnerability to manipulation. Am Econ Rev 103(1):80–106CrossRef

Pathak PA, Sönmez T (2020) Corrigendum for proposition 3 in pathak and sönmez (2013)

Suzdaltsev A (2022) Distributionally robust pricing in independent private value auctions. J Econ Theory 206:105555CrossRef

Title: Robustness to manipulations in school choice
Authors: Alexander Nesterov
Olga Rospuskova
Sofia Rubtcova
Publication date: 07-01-2024
Publisher: Springer Berlin Heidelberg
Published in: Social Choice and Welfare / Issue 3/2024
Print ISSN: 0176-1714
Electronic ISSN: 1432-217X
DOI: https://doi.org/10.1007/s00355-023-01504-z

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Other articles of this Issue 3/2024

The Quintilian School in the history of Social Choice: an early tentative step from plurality rule to pairwise comparisons

Animals and social welfare

Relative measures of economic insecurity

Dorm augmented college assignments

Consistent social ranking solutions

Redistributive politics under ambiguity