indicates that there are i schools, each with a capacity of j. The numbers shown refer to the number of 5,000 runs of ea
Supplemental Appendix to “The Secure Boston Mechanism: Theory and Experiments” Umut Dur∗
1
Robert G. Hammond†
Thayer Morrill‡
Robustness of Simulation Evidence In Dur, Hammond, and Morrill (2015), we presented simulation evidence that the assignment
of the Secure Boston Mechanism (sBM) often Pareto dominates the assignment of the Deferred Acceptance algorithm (DA). We used a simulation environment that was designed to be consistent with the experimental design. In this appendix, we present results from a wide range of alternative scenarios to demonstrate that the environment detailed in the paper is representative of the general pattern of results comparing sBM to DA. We run simulations under different cases in which the number of schools and students vary. Specifically, we consider 32 additional simulation environments, where the number of schools ranges from 3 to 16 and capacities range from 2 to 12. The number of students ranges from 8 to 48 and, in all cases, the number of students and the number of total available seats are the same.1 Each student has a unique secure school and her secure school is either second or third in her true preference order. The relative order of the other schools is selected randomly. Each school has a priority order in which the school’s secure students have the highest priority, while the non-secure students are randomly ordered in the remaining priority slots. For each case, we first calculate the outcome of DA and sBM using the constructed priorities ∗
Department of Economics, North Carolina State University. Contact:
[email protected] Department of Economics, North Carolina State University. Contact: robert
[email protected]. ‡ Department of Economics, North Carolina State University. Contact: thayer
[email protected] 1 Considering a larger number of students substantially increases the processing time required for the simulation. The results discussed here show that the relative efficiency advantage of sBM over DA increases as the number of students increases. As a result, including environments with larger number of students will only make our comparison to DA more favorable for sBM. †
1
and preferences. Given that DA is strategyproof, the DA assignment is determined assuming truth-telling. For sBM, we need to find an equilibrium profile for each run. To do so, we start from the constructed preferences and find the best response strategy of each student fixing the other students. Then, we update the preference profile and find the best response of another student. We continue updating this procedure to get a preference profile in which each student’s best response is equal to the preference order of the student in that preference profile. If this procedure terminates, we calculate the outcome of sBM using the final preference profile, which is an equilibrium. Otherwise, we stop after 500 steps, construct a new preference and priority profile, and follow the same procedure using these new profiles. The simulation is complete once we have 5,000 different preference and priority profiles in which we can reach an equilibrium profile. The results across 32 simulation environments are shown in Table 1. For each case, SiCj indicates that there are i schools, each with a capacity of j. The numbers shown refer to the number of 5,000 runs of each outcome. The left panel shows the total number of runs in which DA is efficient, as well as the breakdown of these runs into several outcomes, as described below. The right panel shows the total number of runs in which DA is inefficient, as well as the breakdown of these runs into several outcomes. “Same” refers to cases in which DA and sBM produce the same assignment. “Unranked” refers to cases in which DA and sBM produce different assignments but the two assignments cannot be Pareto ranked (i.e., one student prefers her DA assignment and another student prefers her sBM assignment). “DA” refers to cases in which the DA assignment Pareto dominates the sBM assignment. Finally, “sBM” refers to cases in which the sBM assignment Pareto dominates the DA assignment. To more easily interpret the results in Table 1, Figures 1, 2, and 3 express several interesting outcomes as a percentage of the 5,000 simulation runs. Figure 1 shows the fraction of the time that DA is inefficient, where the y-axis ranges from 0% to 100%. Figure 2 shows how often sBM Pareto dominates DA, while Figure 3 shows how often DA Pareto dominates sBM. Note that the scale of the y-axis remains the same across these three figures and thus the interpretation of Figure 3 is in outcomes that occur in less than one percent of runs. The results show that sBM Pareto dominates DA in between 4.7% and 58.9% of runs, with an average sBM Pareto domination rate of 26.3%. This suggests that the results reported in the paper (where sBM Pareto dominated DA 13.5% of the time) are conservative. Moreover, we find that DA 2
Pareto dominates sBM in between 0.0% and 0.3% of runs, with an average DA Pareto domination rate less than 0.1%. In words, DA Pareto dominates sBM less than one-tenth of one percent of the time, while sBM Pareto dominates DA around one fourth of the time. Also note that we can compare sBM to DA in terms of stochastic ordering, where we say that a mechanism first-order stochastically dominates another mechanism if it assigns more students to their first choice, more students to either their first or second choice, and so on. In the simulation environment in Dur, Hammond, and Morrill (2015), sBM first-order stochastically dominated DA. The results are consistent with those in the paper: sBM first-order stochastically dominates DA in all 32 simulation environments. Consistent with the analysis discussed above, sBM often improves efficiency relative to DA. This appendix shows that the simulation environment in Dur, Hammond, and Morrill (2015) provides results that are representative of the general pattern of simulation results comparing sBM to DA and, in some senses, is conservative. These additional results support our conclusion that sBM should be considered as a viable alternative to DA.
3
References Dur, U., R. G. Hammond, and T. Morrill (2015): “The Secure Boston Mechanism: Theory and Experiments,” mimeo.
4
100 80 % DA Inefficient 60 40 S3C4 S3C8 S3C12 S4C2 S4C3 S4C4 S4C5 S4C6 S4C7 S4C8 S4C9 S4C10 S4C12 S5C4 S5C8 S6C2 S6C4 S6C6 S6C8 S7C4 S8C2 S8C3 S8C4 S8C6 S9C4 S10C2 S10C4 S11C4 S12C2 S12C3 S12C4 S16C3
20
Figure 1: DA Inefficient, Percent of Simulation Runs Notes: On average, DA is inefficient in 70.6% of 5,000 simulation runs across these 32 simulation environments. For each case, SiCj indicates that there are i schools, each with a capacity of j.
5
60 % sBM Dominates 20 40 S3C4 S3C8 S3C12 S4C2 S4C3 S4C4 S4C5 S4C6 S4C7 S4C8 S4C9 S4C10 S4C12 S5C4 S5C8 S6C2 S6C4 S6C6 S6C8 S7C4 S8C2 S8C3 S8C4 S8C6 S9C4 S10C2 S10C4 S11C4 S12C2 S12C3 S12C4 S16C3
0
Figure 2: sBM Pareto Dominates DA, Percent of Simulation Runs Notes: On average, sBM Pareto dominates DA in 26.3% of 5,000 simulation runs across these 32 simulation environments. For each case, SiCj indicates that there are i schools, each with a capacity of j.
6
.5 .4 % DA Dominates .2 .3 .1 S3C4 S3C8 S3C12 S4C2 S4C3 S4C4 S4C5 S4C6 S4C7 S4C8 S4C9 S4C10 S4C12 S5C4 S5C8 S6C2 S6C4 S6C6 S6C8 S7C4 S8C2 S8C3 S8C4 S8C6 S9C4 S10C2 S10C4 S11C4 S12C2 S12C3 S12C4 S16C3
0
Figure 3: DA Pareto Dominates sBM, Percent of Simulation Runs Notes: On average, DA Pareto dominates sBM in 0.1% of 5,000 simulation runs across these 32 simulation environments. For each case, SiCj indicates that there are i schools, each with a capacity of j.
7
Table 1: Simulation Results DA Efficient Case S3C4 S3C8 S3C12 S4C2 S4C3 S4C4 S4C5 S4C6 S4C7 S4C8 S4C9 S4C10 S4C12 S5C4 S5C8 S6C2 S6C4 S6C6 S6C8 S7C4 S8C2 S8C3 S8C4 S8C6 S9C4 S10C2 S10C4 S11C4 S12C2 S12C3 S12C4 S16C3
DA Inefficient
All
Same
Unranked
DA
All
Same
Unranked
DA
sBM
3946 3535 3205 3111 2813 2624 2425 2195 2176 1989 1917 1903 1774 1741 421 1614 1164 837 673 753 924 687 2176 344 383 583 264 157 358 187 110 45
3946 3535 3205 3110 2812 2619 2423 2190 2172 1980 1915 1901 1769 1736 412 1607 1156 830 671 747 917 677 2172 337 374 579 259 154 356 182 108 44
0 0 0 1 1 5 2 3 3 7 2 2 5 4 5 6 7 4 0 5 4 8 3 6 4 4 3 0 1 3 1 0
0 0 0 0 0 0 0 2 1 2 0 0 0 1 4 1 1 3 2 1 3 2 1 1 5 0 2 3 1 2 1 1
1054 1465 1795 1889 2187 2376 2575 2805 2824 3011 3083 3097 3226 3259 4579 3386 3836 4163 4327 4247 4076 4313 2824 4656 4617 4417 4736 4843 4642 4813 4890 4955
819 1216 1529 1296 1507 1739 1903 2056 2128 2282 2394 2391 2499 2262 2624 2145 2434 2714 2839 2599 2390 2510 2128 2778 2559 2437 2457 2395 2306 2292 2286 1924
0 0 0 1 3 10 14 7 11 9 13 16 10 17 68 12 29 42 50 35 12 22 11 89 63 19 60 88 19 56 90 75
0 0 0 0 0 0 0 0 0 0 1 4 1 1 9 0 5 5 6 4 1 3 0 12 10 3 13 12 1 6 15 11
235 249 266 592 677 627 658 742 685 720 675 686 716 979 1878 1229 1368 1402 1432 1609 1673 1778 685 1777 1985 1958 2206 2348 2316 2459 2499 2945
Notes: Shown are the number out of 5,000 simulation runs of each outcome. “Same” refers to cases in which DA and sBM produce the same assignment. “Unranked” refers to cases in which DA and sBM produce different assignments but the two assignments cannot be Pareto ranked. “DA” refers to cases in which the DA assignment Pareto dominates the sBM assignment. “sBM” refers to cases in which the sBM assignment Pareto dominates the DA assignment. For each case, SiCj indicates that there are i schools, each with a capacity of j.
8
