The Secure Boston Mechanism: theory and experiments

This paper introduces a new matching mechanism that is a hybrid of the two most common mechanisms in school choice, the Boston Mechanism (BM) and the Deferred Acceptance algorithm (DA). BM is the most commonly used mechanism in the field, but it is neither strategyproof nor fair. DA is the mechanism that is typically favored by economists, but it is not Pareto efficient. The new mechanism, the Secure Boston Mechanism (sBM), is an intuitive modification of BM that secures any school a student was initially guaranteed but otherwise prioritizes a student at a school based upon how she ranks it. Relative to BM, theoretical results suggest that sBM is an improvement in terms of strategyproofness and fairness. We present experimental evidence using a novel experimental design that confirms that sBM significantly increases truth-telling and fairness. Relative to DA, theoretical results suggest that sBM can be a Pareto improvement in equilibrium but the efficiency comparison of sBM and DA is theoretically ambiguous. We present simulation evidence that suggests that sBM often does Pareto dominate DA when DA is inefficient, while sBM and DA very often overlap when DA is efficient. Overall, our results strongly support the use of sBM over BM and suggest that sBM should be considered as a viable alternative to DA.

1. Pathak and Sönmez (2008) emphasize the disadvantages of BM and state that: “It is remarkable that such a flawed mechanism is so widely used”.

2. Vaznis (2014) provides one example of a media report that focuses on the fraction of students assigned to one of their top three choices. Educational policy professionals have also advocated for maximizing the fraction of students who are assigned to one of their top choices. See the discussions in Cookson (1995) and Glenn (1991).

3. US school districts that use BM include Cambridge, MA; Charlotte-Mecklenburg, NC; Miami- Dade, FL; Minneapolis, MN; and Tampa-St. Petersburg, FL. Strikingly, the Seattle school district replaced BM with a strategyproof mechanism only to reinstitute BM in 2011 (Kojima and Ünver 2014).

4. In earlier studies, Pathak and Sönmez (2013) and Chen and Kesten (2017) compare manipulable and unfair mechanisms in terms of vulnerability to manipulation and fairness.

5. However, using data from Cambridge, MA, Agarwal and Somaini (2014) estimate that the welfare of the average student would be lower under DA than under BM.

6. Fairness is also known as elimination of justified envy.

7. This is closely related to stability in the classic two-sided matching market (Gale and Shapley 1962).

8. This way of defining BM was introduced by Ergin and Sönmez (2006).

9. One can think that this result follows from Ergin and Sönmez (2006). Although we use a similar proof technique, we present a formal proof for sBM since sBM is different than the mechanism studied by Ergin and Sönmez (2006).

10. These examples are modifications of a classic example from Abdulkadiroğlu and Sönmez (2003).

11. Note that, we do not impose any restriction on \(P'\) and \(\succ '\).

12. It is worth mentioning that we can compare two different versions of sBM defined under two different guaranteed set of students \(G'\) and \(G''\) such that for each \(a\in S\)\(G'_a\subseteq G''_a\) and \(G''_a\) is composed of the q-highest-ranked students at a where \(q\le q_a\) in terms of vulnerability to manipulation and fairness. In particular, sBM defined under \(G'\) is more manipulable than sBM defined under \(G''\). Moreover, sBM defined under \(G''\) is more fair than sBM defined under \(G'\). These results can be shown by following the steps of Theorem 2 and Proposition 3, respectively.

13. It is certainly the case that students in the field are competing against other students, not robots. However, many school choice settings involve thousands of students. This implies that a single student cannot contemplate the strategic behavior of her opponents at the individual level and instead must respond to (her perception of) their aggregate behavior. This is similar to the strategic setting in a human-robots design. In fact, several recent theoretical papers in matching have used a large-market approximation when considering the strategic behavior of an individual student, which again is similar to our human-robots design [e.g., Kojima et al. (2013)].

14. After circulating initial drafts of this manuscript, we discovered an error in the zTree code. Because we made an error in coding the rejection cycles that generate the assignment, subjects in a very small number of periods were shown the incorrect assignment (in 1% of subject-periods). The incorrect handling of rejection cycles caused subjects to be shown a more preferred school as their assignment relative to their correct assignment. In the analysis that follows, we use the subject’s correct assignment. In the Supplemental Appendix, we exclude all periods including and after the period in which a subject was shown an incorrect assignment. The relative comparison of sBM and BM in those results is very similar to the included results.

15. Again, see the Supplemental Appendix for links to the instructional videos.

16. One can deduce in Appendix Fig. 2 that schools A and C are popular in this period.

17. Specifically, if b is student i’s district school and \(aP_i b\), then it is a weakly dominated strategy for her to rank b ahead of a. Similarly, if b is i’s district school and \(b P_i c\), then it is a weakly dominated strategy for her to rank c ahead of b.

18. In one example from the Boston Public Schools, it was reported that 47.3% of students received their report top choice in 2014 (Vaznis 2014).

19. Demand at favorite averages around 51%, which implies that around half of the robotic subjects ranked the subject’s favorite school first. This is consistent with our correlated-preference environment, described earlier. Next, favorite preference intensity averages 5.7 points, where again two points are worth $1. This implies that subjects have a lot to lose by not getting their favorite school. Finally, the subject’s district school is her second favorite school around 60% of the time.

20. The rates of truth-telling we observe with BM are in line with the previous experimental literature. For example, Chen and Sönmez (2006) find a truth-telling rate of 13.9% with BM in a setting that is comparable to ours (the “designed environment”).

21. The rates of district school bias we observe with BM are in line with the previous experimental literature. For example, Chen and Kesten (2016) find a district school bias rate of 47.8% with BM.

22. See Dur et al. (2018) for evidence from the Wake County Public School System, which is one of the largest school systems in the United States.

23. Pais and Pintér (2008) present experimental evidence that district school bias is higher in a more complete information environment (similar to our finding) but they also find that truth-telling is lower with more information (where we find no effect of information).

24. Other definitions of justified envy provide similar results. The proportion of robotic subjects of whom the human subject has justified envy falls from 1.3% with BM to 0.6% with sBM. The mean number of instances of justified envy falls from 0.91 with BM to 0.47 with sBM. The effect of sBM on justified envy is similar with all three definitions and the reduction is always highly statistically significant.

25. The rates of first choice accommodation we observe with BM are in line with the previous experimental literature. For example, in Chen and Kesten (2016), around 60% of subjects were assigned to their reported first choice, while 12% of subjects were assigned to their reported true choice.

26. In the Supplemental Appendix, we present results using a normalized cardinal efficiency measure. It uses subjects’ payoffs to measure efficiency and is defined analogously with respect to normalized ordinal efficiency. The effect of sBM on normalized cardinal efficiency is 3.8%, which is very similar to the effect of 4.0% found above. See Supplemental Appendix Table 17.

27. We briefly note that Supplemental Appendix Table 4 shows the effects of demographic and other subject covariates on four separate outcomes of interest: truth-telling, district school bias, fairness, and efficiency, respectively. For risk averse subjects, economics majors, and minority subjects, we find more truth-telling and less district school bias. The fact that risk averse subjects are more truthful runs counter to the interpretation that district school bias is driven by risk avoidance. Further, subjects who have participated in past experiments report more truthfully. Other subject characteristics (including the variables from registration and enrollment records) have effects that are quantitatively small and statistically insignificant. Finally, assignments for males and American subjects had more justified envy, while assignments for American subjects and subjects with higher high school GPAs were less efficient.

28. A local polynomial regression is a nonparametric technique for flexibly modeling associations. Supplemental Appendix Figure 1 presents the period-by-period averages, overlaid with these local polynomial regression fitted curves. This figure is more visually taxing, but it conveys that the fitted curves generally represent the underlying data in an accurate way. Further, Supplemental Appendix Figure 2 alternatively uses a bandwidth of four periods. As expected, a larger bandwidth produces smoother fitted curves, but the basic conclusions continue to hold.

29. From a Cuzick nonparametric trend test, the test results are as follows: for truth-telling, z-statistic = 0.95, p value = 0.34 for BM and z-statistic = 0.37, p value = 0.71 for sBM; for district school bias, z-statistic = − 1.12, p value = 0.26 for BM and z-statistic = − 1.52, p value = 0.13 for sBM; for fairness, z-statistic = − 2.14, p value = 0.03 for BM and z-statistic = − 1.16, p value = 0.25 for sBM; and for efficiency, z-statistic = 2.28, p value = 0.02 for BM and z-statistic = 0.43, p value = 0.66 for sBM. Note that, while the above results are from a nonparametric trend test, a parametric trend test finds a statistically significant trend for sBM with less justified envy over time.

30. In addition to the experimental environment, we have explored a wide range of alternative scenarios. These robustness results are detailed in the Supplemental Appendix. An overview of the robustness results is provided at the close of this section.

31. We test for differences in the distributions in their central location, with no assumptions about the parametric form of the distributions. The use of nonparametric tests is consistent with the experimental literature.

We thank Zhiyi (Alicia) Xu for excellent research assistance; the editor, two referees, and Inacio Bo for comments, seminar participants at the 2014 INFORMS Conference, 2015 MATCH UP Conference, 2015 AMMA Conference, 2015 ESA Conference, Georgia State University, National University of Singapore, Nanyang Technological University, Davidson College, and Academia Sinica for comments; and the Faculty Research and Professional Development Grant fund for financial support.

The funding was provided by Internal research budget.

Authors and Affiliations

1. Department of Economics, North Carolina State University, Raleigh, USA

   Umut Dur, Robert G. Hammond & Thayer Morrill

Corresponding author

Correspondence to Robert G. Hammond.

Appendix

See Fig. 2 and Table 9.

Screenshot of experimental interface, ranking screen

Full size image

Reprints and permissions