Skip to main content
Top

07-01-2024 | Original Paper

Robustness to manipulations in school choice

Authors: Alexander Nesterov, Olga Rospuskova, Sofia Rubtcova

Published in: Social Choice and Welfare

Log in

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

search-config
loading …

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.

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!

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!

Appendix
Available only for authorised users
Footnotes
1
The definitions of the mechanisms are given in “Mechanisms” section.
 
2
Pathak and Sönmez (2013) provide three logically related criteria but only the weakest can be used to compare school choice mechanisms.
 
3
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).
 
4
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.
 
5
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.
 
6
For a formal statement of AM-manipulability, see Definition 3.
 
7
For a formal statement of BN-manipulability, see Definition 4.
 
8
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.
 
9
Note: if two mechanisms are comparable by robustness, this does not imply the strict comparison by AM-manipulability.
 
10
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 \).
 
11
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.
 
12
By \(P^{k+1}\) we denote a preference profile that consists of the first \(k+1\) rows of the preference profile P.
 
13
Lemma 1, Bonkoungou and Nesterov (2021).
 
Literature
go back to reference Abdulkadiroğlu A, Sönmez T (2003) School choice: a mechanism design approach. Am Econ Rev 93(3):729–747CrossRef Abdulkadiroğlu A, Sönmez T (2003) School choice: a mechanism design approach. Am Econ Rev 93(3):729–747CrossRef
go back to reference Alcalde J (1996) Implementation of stable solutions to marriage problems. J Econ Theory 69(1):240–254CrossRef Alcalde J (1996) Implementation of stable solutions to marriage problems. J Econ Theory 69(1):240–254CrossRef
go back to reference Andreyanov P, Sadzik T (2021) Robust mechanism design of exchange. Rev Econ Stud 88(2):521–573CrossRef Andreyanov P, Sadzik T (2021) Robust mechanism design of exchange. Rev Econ Stud 88(2):521–573CrossRef
go back to reference Arribillaga RP, Massó J (2016) Comparing generalized median voter schemes according to their manipulability. Theor Econ 11(2):547–586CrossRef Arribillaga RP, Massó J (2016) Comparing generalized median voter schemes according to their manipulability. Theor Econ 11(2):547–586CrossRef
go back to reference Arribillaga RP, Massó J (2017) Comparing voting by committees according to their manipulability. Am Econ J Microecon 9(4):74–107CrossRef Arribillaga RP, Massó J (2017) Comparing voting by committees according to their manipulability. Am Econ J Microecon 9(4):74–107CrossRef
go back to reference Balinski M, Sönmez T (1999) A tale of two mechanisms: student placement. J Econ Theory 84(1):73–94CrossRef Balinski M, Sönmez T (1999) A tale of two mechanisms: student placement. J Econ Theory 84(1):73–94CrossRef
go back to reference Bergemann D, Morris S (2005) Robust mechanism design. Econometrica 73(6):1771–1813CrossRef Bergemann D, Morris S (2005) Robust mechanism design. Econometrica 73(6):1771–1813CrossRef
go back to reference 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 (2021) Comparing school choice and college admissions mechanisms by their strategic accessibility. Theor Econ 16(3):881–909CrossRef
go back to reference Bonkoungou S, Nesterov A (2023) Incentives in matching markets: counting and comparing manipulating agents. Theoretical Economics (forthcoming) Bonkoungou S, Nesterov A (2023) Incentives in matching markets: counting and comparing manipulating agents. Theoretical Economics (forthcoming)
go back to reference Chen Y, Kesten O (2017) Chinese college admissions and school choice reforms: a theoretical analysis. J Polit Econ 125(1):99–139CrossRef Chen Y, Kesten O (2017) Chinese college admissions and school choice reforms: a theoretical analysis. J Polit Econ 125(1):99–139CrossRef
go back to reference Chen P, Egesdal M, Pycia M, Yenmez MB (2016) Manipulability of stable mechanisms. Am Econ J Microecon 8(2):202–214CrossRef Chen P, Egesdal M, Pycia M, Yenmez MB (2016) Manipulability of stable mechanisms. Am Econ J Microecon 8(2):202–214CrossRef
go back to reference 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 (2023) A modification aimed at reducing the manipulability and inefficiency of the Boston school choice mechanism. Soc Choice Welf 60(1–2):75–101CrossRef
go back to reference Decerf B, Van der Linden M (2021) Manipulability in school choice. J Econ Theory 197:105313CrossRef Decerf B, Van der Linden M (2021) Manipulability in school choice. J Econ Theory 197:105313CrossRef
go back to reference Dur U, Hammond RG, Morrill T (2019) The secure Boston mechanism: theory and experiments. Exp Econ 22(4):918–953CrossRef Dur U, Hammond RG, Morrill T (2019) The secure Boston mechanism: theory and experiments. Exp Econ 22(4):918–953CrossRef
go back to reference Gale D, Shapley LS (1962) College admissions and the stability of marriage. Am Math Mon 69(1):9–15CrossRef Gale D, Shapley LS (1962) College admissions and the stability of marriage. Am Math Mon 69(1):9–15CrossRef
go back to reference Haeringer G, Klijn F (2009) Constrained school choice. J Econ Theory 144(5):1921–1947CrossRef Haeringer G, Klijn F (2009) Constrained school choice. J Econ Theory 144(5):1921–1947CrossRef
go back to reference Harless P (2019) Immediate acceptance with or without skips? Comparing school assignment procedures. Working paper Harless P (2019) Immediate acceptance with or without skips? Comparing school assignment procedures. Working paper
go back to reference Imamura K, Tomoeda K (2022) Measuring manipulability of matching mechanisms. Available at SSRN 4000419 Imamura K, Tomoeda K (2022) Measuring manipulability of matching mechanisms. Available at SSRN 4000419
go back to reference Mennle T, Seuken S (2021) Partial strategyproofness: relaxing strategyproofness for the random assignment problem. J Econ Theory 191:105144CrossRef Mennle T, Seuken S (2021) Partial strategyproofness: relaxing strategyproofness for the random assignment problem. J Econ Theory 191:105144CrossRef
go back to reference 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 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
go back to reference 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 (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
go back to reference 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 (2013) School admissions reform in Chicago and England: comparing mechanisms by their vulnerability to manipulation. Am Econ Rev 103(1):80–106CrossRef
go back to reference Pathak PA, Sönmez T (2020) Corrigendum for proposition 3 in pathak and sönmez (2013) Pathak PA, Sönmez T (2020) Corrigendum for proposition 3 in pathak and sönmez (2013)
go back to reference Suzdaltsev A (2022) Distributionally robust pricing in independent private value auctions. J Econ Theory 206:105555CrossRef Suzdaltsev A (2022) Distributionally robust pricing in independent private value auctions. J Econ Theory 206:105555CrossRef
Metadata
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
Print ISSN: 0176-1714
Electronic ISSN: 1432-217X
DOI
https://doi.org/10.1007/s00355-023-01504-z