Skip to main content
Top
Published in:

21-04-2021 | Original Paper

A modification aimed at reducing the manipulability and inefficiency of the Boston school choice mechanism

Author: Benoit Decerf

Published in: Social Choice and Welfare | Issue 1-2/2023

Log in

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

search-config
loading …

Abstract

The Boston mechanism (BOS) is widely used for the assignment of students to schools. Yet, BOS is highly manipulable and, therefore, may lead to Pareto inferior assignments. We propose a new indirect matching mechanism (\({{ NBOS }}\)) that is a slight variant of BOS. \({{ NBOS }}\) is less manipulable than BOS in two important ways: (i) students always have a best reply featuring truthful reported preference, (ii) rational students avoid particular re-rankings that are typical in BOS. Most importantly, the lower manipulability of \({{ NBOS }}\) helps reaching more efficient assignments than those reached by BOS. We show that each equilibrium of BOS is associated to a set of equilibria of \({{ NBOS }}\), all of which are Pareto superior. \({{ NBOS }}\) generalizes to a class of mechanisms whose members are even less manipulable than \({{ NBOS }}\).

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
Officials in charge of the assignment of students to schools try to avoid mechanisms that are too manipulable. For instance, Pathak and Sönmez (2013) document that several US districts decided to shift to less manipulable mechanisms. Manipulable mechanisms such as BOS may hurt students who have more difficulties at strategizing (Pathak and Sonmez 2008). If socially disadvantaged students use less sophisticated strategies, manipulable mechanisms hurt this group more.
 
2
The earliest proposal is to let the algorithm skip exhausted schools. Several aspects of this modified algorithm (SKIPBOS) have been studied by Miralles (2008), Dur et al. (2018b), Mennle and Seuken (2015) or yet Harless (2017). Another variant (SECBOS) secures any school at which a student has top-priority (Dur et al. 2015). Then, the Parallel mechanisms, a class of hybrid mechanisms between BOS and DA, constitute a third alternative, which is used for college admission in China (Chen and Kesten 2017). The Parallel mechanisms let students rank schools within choice bands, each containing several schools. The priority of a student at a school is affected by the choice band in which she reports the school, but not by its exact rank inside the choice band. Finally, another class of hybrid mechanisms between BOS and DA is used in Taiwan (Dur et al. 2018a), where priorities are based on the students’ scores at an admissions exam. In the Taiwan mechanisms, points are deducted from an applicant’s score with larger penalties for lower ranked choices.
 
3
Not all reported schools are assignable. For instance, if \(t_i\) has top-priority at her neutralized school \(x_i\), any school reported in \(Q_i\) below \(x_i\) is not assignable.
 
4
A student should not neutralize a school that she deems worse than her preferred top-priority school. In contrast, a student reporting a preference ranking first a school she deems worse than her preferred top-priority school can be an undominated strategy of BOS. See Proposition 4 in Decerf and Van der Linden (2017), which characterizes undominated strategies in BOS: if a student does not have top-priority at her favorite school, then almost all strategies are undominated.
 
5
Theorem 1 in Dur et al. (2015) shows that, if the most efficient stable assignment is inefficient, then there exists a “larger assignment problem” in which efficient assignments can be supported by a NE in undominated strategies.
 
6
Proposition 5 in Chen and Kesten (2017) also shows that the Parallel mechanisms satisfy some insurance property. Assume that all students anticipate a particular NE-outcome \(\mu \) of BOS. Parallel mechanisms allow students to secure their assignment \(\mu _i\) while at the same time have a chance to obtain a better school. The same holds true for \({{ NBOS }}\). If all students neutralize their \(\mu _i\) and report above it only schools that they prefer to it, then all students obtain a school they deem as good as \(\mu _i\).
 
7
This implies that an interrupter student does not neutralize the school at the origin of her rejection cycle, and thus her pre-existing priority may sometimes be bypassed at that school.
 
8
For instance, consider the alternative preference \(R_3': s_2~s_1~s_3\) for the problem presented in (2). When all students \(t_i \in \{t_1,t_2,t_3\}\) neutralize \(\mu ^0_i\) and report truthfully their ordinal preferences, the assignment under \({{ NBOS }}\) is \(\mu ^0\) rather than \(\mu ^1\), because \(t_3\) has higher implicit priority at \(s_2\) than \(t_1\).
 
9
This is implied by Proposition 1 and the proof of Statement 1 of Theorem 1.
 
10
This means that there is a probability 60% of being of type \(\tau _1\), 25% of being of type \(\tau _2\) and 15% of being of type \(\tau _3\).
 
11
Even if \(\sigma _i=(Q_i,s_1)\) with \(Q_i:~s_1~s_2\) for all other \(t_i\), neutralizing \(s_1\) yields for a student of type \(\tau _1\) an expected utility above 33 while neutralizing \(s_2\) yields her an expected utility smaller than 10.
 
12
Given the BNE in \({{ NBOS }}\), a student drawing type \(\tau _2\) who deviates to play \((Q_{\tau _2}^{N},s_1)\) gets an EU of 62.8 instead of 64.33. In turn, given the BNE in BOS, a student drawing type \(\tau _2\) who deviates to play \(Q^{BOS}_{\tau _1}: ~s_1~s_2\) gets an EU of 62.8 instead of 64.13.
 
13
To be more precise, these priority profiles are the same if the ordinal rankings \(Q_i^{g}\) and \(Q_i^{g'}\) are “completed” by reporting the remaining schools as unacceptable in the appropriate order.
 
14
Students \(t_l\) who are unassigned in \(\mu ^0\) do not neutralize any school (\(x_l=t_l\)).
 
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 Abdulkadiroglu A, Pathak P, Roth A (2009) Strategy-proofness versus efficiency in matching with indifferences: redesigning the New York City high school match. Am Econ Rev 99(5):1954–1978CrossRef Abdulkadiroglu A, Pathak P, Roth A (2009) Strategy-proofness versus efficiency in matching with indifferences: redesigning the New York City high school match. Am Econ Rev 99(5):1954–1978CrossRef
go back to reference Abdulkadiroğlu A, Che Y, Yasuda Y (2011) Resolving conflicting preferences in school choice: the “Boston mechanism’’ reconsidered. Am Econ Rev 101(1):399–410CrossRef Abdulkadiroğlu A, Che Y, Yasuda Y (2011) Resolving conflicting preferences in school choice: the “Boston mechanism’’ reconsidered. Am Econ Rev 101(1):399–410CrossRef
go back to reference Abdulkadiroğlu A, Che Y-K, Yasuda Y (2015) Expanding “choice’’ in school choice. Am Econ J Microecon 7(1):1–42CrossRef Abdulkadiroğlu A, Che Y-K, Yasuda Y (2015) Expanding “choice’’ in school choice. Am Econ J Microecon 7(1):1–42CrossRef
go back to reference Basteck C, Mantovani M (2018) Cognitive ability and games of school choice. Games Econ Behav 109:156–183CrossRef Basteck C, Mantovani M (2018) Cognitive ability and games of school choice. Games Econ Behav 109:156–183CrossRef
go back to reference Calsamiglia C, Haeringer G, Klijn F (2010) Constrained school choice: an experimental study. Am Econ Rev 100(4):1860–1874CrossRef Calsamiglia C, Haeringer G, Klijn F (2010) Constrained school choice: an experimental study. Am Econ Rev 100(4):1860–1874CrossRef
go back to reference Calsamiglia C, Güell M (2014) The illusion of school choice: empirical evidence from Barcelona Calsamiglia C, Güell M (2014) The illusion of school choice: empirical evidence from Barcelona
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 Decerf B, Van der Linden M (2017) In search of advice for participants in constrained school choice. SSRN Working Paper Decerf B, Van der Linden M (2017) In search of advice for participants in constrained school choice. SSRN Working Paper
go back to reference Dubins LE, Freedman DA (1981) Machiavelli and the Gale–Shapley algorithm. Am Math Mon 88(7):485–494CrossRef Dubins LE, Freedman DA (1981) Machiavelli and the Gale–Shapley algorithm. Am Math Mon 88(7):485–494CrossRef
go back to reference Dur UM (2018) The modified Boston mechanism. Math Soc Sci Dur UM (2018) The modified Boston mechanism. Math Soc Sci
go back to reference Dur U, Hammond RG, Morrill T (2015) The secure Boston mechanism: theory and experiments. Working Paper Dur U, Hammond RG, Morrill T (2015) The secure Boston mechanism: theory and experiments. Working Paper
go back to reference Dur U, Pathak PA, Song F, Sonmez T (2018) Deduction dilemmas: the Taiwan assignment mechanism. NBER Working Paper 25024 Dur U, Pathak PA, Song F, Sonmez T (2018) Deduction dilemmas: the Taiwan assignment mechanism. NBER Working Paper 25024
go back to reference Erdil A, Ergin H (2008) What’s the matter with tie-breaking? Improving efficiency in school choice. Am Econ Rev 98(3):669–689CrossRef Erdil A, Ergin H (2008) What’s the matter with tie-breaking? Improving efficiency in school choice. Am Econ Rev 98(3):669–689CrossRef
go back to reference Ergin H, Sönmez T (2006) Games of school choice under the Boston mechanism. J Public Econ 90(1–2):215–237CrossRef Ergin H, Sönmez T (2006) Games of school choice under the Boston mechanism. J Public Econ 90(1–2):215–237CrossRef
go back to reference Featherstone CR, Niederle M (2016) Boston versus deferred acceptance in an interim setting: an experimental investigation. Games Econ Behav 100:353–375CrossRef Featherstone CR, Niederle M (2016) Boston versus deferred acceptance in an interim setting: an experimental investigation. Games Econ Behav 100:353–375CrossRef
go back to reference Featherstone C, Niederle M (2014) Improving on strategy-proof school choice mechanisms: an experimental investigation. Working Paper Featherstone C, Niederle M (2014) Improving on strategy-proof school choice mechanisms: an experimental investigation. Working Paper
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 (2017) Immediate acceptance with or without skips? Comparing school assignment procedures. University of Glasgow (Unpublished manuscript) Harless P (2017) Immediate acceptance with or without skips? Comparing school assignment procedures. University of Glasgow (Unpublished manuscript)
go back to reference Hassidim A, Romm A, Shorrer RI (2016) “Strategic” behavior in a strategy-proof environment. In: Proceedings of the 2016 ACM conference on economics and computation, pp 763–764 Hassidim A, Romm A, Shorrer RI (2016) “Strategic” behavior in a strategy-proof environment. In: Proceedings of the 2016 ACM conference on economics and computation, pp 763–764
go back to reference He Y (2015) Gaming the Boston school choice mechanism in Beijing He Y (2015) Gaming the Boston school choice mechanism in Beijing
go back to reference Kojima F, Manea M (2010) Axioms for deferred acceptance. Econometrica 78(2):633–653CrossRef Kojima F, Manea M (2010) Axioms for deferred acceptance. Econometrica 78(2):633–653CrossRef
go back to reference Mennle T, Seuken S (2015) Trafe-offs in school choice: comparing deferred acceptance, the Naive and the adaptive Boston mechanism. Working Paper Mennle T, Seuken S (2015) Trafe-offs in school choice: comparing deferred acceptance, the Naive and the adaptive Boston mechanism. Working Paper
go back to reference Miralles A (2008) School choice: the case for the Boston method. Working Paper Miralles A (2008) School choice: the case for the Boston method. Working Paper
go back to reference Pathak PA, Sonmez T (2008) Leveling the playing field: sincere and strategic players in the Boston mechanism. Am Econ Rev 98(4):1636–1652CrossRef Pathak PA, Sonmez T (2008) Leveling the playing field: sincere and strategic players in the Boston mechanism. Am Econ Rev 98(4):1636–1652CrossRef
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 Sönmez T, Ünver MU (2010) Course bidding at business schools. Int Econ Rev 51(1):99–123CrossRef Sönmez T, Ünver MU (2010) Course bidding at business schools. Int Econ Rev 51(1):99–123CrossRef
go back to reference Troyan P (2012) Comparing school choice mechanisms by interim and ex-ante welfare. Games Econ Behav 75(2):936–947CrossRef Troyan P (2012) Comparing school choice mechanisms by interim and ex-ante welfare. Games Econ Behav 75(2):936–947CrossRef
Metadata
Title
A modification aimed at reducing the manipulability and inefficiency of the Boston school choice mechanism
Author
Benoit Decerf
Publication date
21-04-2021
Publisher
Springer Berlin Heidelberg
Published in
Social Choice and Welfare / Issue 1-2/2023
Print ISSN: 0176-1714
Electronic ISSN: 1432-217X
DOI
https://doi.org/10.1007/s00355-021-01331-0

Other articles of this Issue 1-2/2023

Social Choice and Welfare 1-2/2023 Go to the issue

Original Paper

Ordinal allocation

Premium Partner