Ex-Ante Welfare Superiority of the Boston Mechanism Over the Deferred Acceptance Mechanism

We compare two widely used allocation methods for assigning students to schools—the deferred acceptance (DA) mechanism and the Boston mechanism—in terms of students’ welfare under a symmetric incomplete information setting in which each student’s school preferences are privately known. We assume that each student’s type, which is the vector of cardinal values they derive from attending each school, is independently drawn, and each possible strict ranking of schools is equally likely for each student. Furthermore, all schools have an identical student priority order, which is unknown to students. When there are three schools with equal numbers of available seats, we analytically derive the probability difference between the Boston and DA mechanisms of obtaining the first, second, and third choices. Furthermore, we show that the Boston mechanism is ex-ante welfare superior to the DA mechanism under weak conditions on the distribution of valuations when each student’s value for each school is independently drawn from an identical distribution.

Data sharing is not applicable to this article as no datasets were generated or analyzed during the current study.

1. Starting with the pioneering work of Abdulkadiroğlu and Sönmez [4], most studies on school choice treat schools as “ objects” to be consumed by students. Therefore, schools do not take strategic actions. We follow the literature in this regard.

2. The Boston mechanism is named as such because it was previously used for assigning students to schools in the city of Boston. See Abdulkadiroğlu and Sönmez [4] for details.

3. Thus, the Boston mechanism may be justly called the “ immediate acceptance” mechanism, as it is sometimes referred to as in the literature.

4. To preserve the gender–neutral presentation, we use “ they/them/theirs” in reference to a student throughout the text.

5. See Dubins and Freedman [15] and Roth [28].

6. That is, students may take advantage of the mechanism by misreporting their preferences. See Abdulkadiroğlu and Sönmez [4], for example.

7. The cities of Boston (Abdulkadiroğlu et al. [3]) and New York (Abdulkadiroğlu et al. [2]) are among such districts.

8. See Ashlagi and Nikzad [9], Ehlers [16], Immorlica and Mahdian [21], Knuth [23], Pittel [26], and Ashlagi et al. [8] for examples that use similar random preferences.

9. For example, Turkey uses test scores as the sole determinant of student priorities in university placement. See Balinski and Sönmez [10] for a formal discussion.

10. In several public school systems in the USA, schools have coarse priorities over students, and a lottery system is used to assign priorities. See Abdulkadiroğlu et al. [2] for example of this in New York City.

11. We also present the relation between the probability differences in obtaining the first and third choice.

12. The ex-ante stage refers to the stage before students learn their own types. Hence, ex-ante welfare is expected welfare where expectation is over student types.

13. They also show by an example that when students have private information regarding their preferences, this result does not hold, and some types of students have higher utility under the Boston mechanism.

14. For example, school \(s_{1}\) is the first choice of every student, school \(s_{2}\) is the second choice of every student, and so on.

15. Interim stage refers to the stage in which each student knows their own type but not others’ types.

16. They also investigate students’ incentives to acquire information under the Boston and DA mechanisms and show that, unlike under the Boston mechanism, students do not have the incentive to learn their cardinal values under DA.

17. FN also provide a theoretical example (the Arts and Science example, Section 5.1 in their paper) with three students and two one-seat schools and demonstrate how the Boston mechanism can dominate the DA mechanism in terms of welfare.

18. In an object allocation problem, there are only one-sided preferences. Conversely, the school choice problem we consider here considers two-sided preferences, where students have preferences over schools and schools have priorities over students.

19. We note that we require that each school have an identical number of available seats. Conversely, ACY allow for quotas to differ across schools.

20. Throughout the text, bold letters denote vectors, capital letters denote random variables, and lowercase letters denote realizations of these random variables.

21. \(\left( s_{j},s_{k}\right) \) means \(s_{j}\) is ranked first, and \(s_{k}\) is ranked second.

22. For example, see Krishna [24] for the independent private value auctions.

23. Recall that we assume that each school has a quota of \(q\ge 1\).

24. We say student i ranks school \(s_{j}\) above school \(s_{k}\) if \( s_{j}=R_{x}^{i}\), \(s_{k}=R_{y}^{i}\) for some \(x<y\), \(x,y\in \left\{ 1,...,n\right\} \).

25. Students do not know other students’ types or school priorities when submitting their preferences. They only know the distributions of other students’ preferences and school priorities.

26. See Harsanyi [20].

27. In the rest of the paper, we write “ equilibrium” instead of “ Bayesian Nash equilibrium.”

28. A strategy is anonymous if the reported rank of a school does not depend on its name but only on its true rank. That is, if we rename the schools, reported rankings change accordingly.

29. To emphasize, we do not impose “ truth-telling.” Rather, it is an equilibrium in our setting even under the Boston mechanism.

30. This probability depends on the number of schools, the number of students, and mechanism. For notational ease, we drop these whenever there is no possible confusion.

31. In fact, this result holds even when the school rankings are not equally likely. This is simply because in the case of two schools (each with q seats) and \(r=2q\) students, it is easy to see that truthful reporting of school rankings is a weakly dominant strategy for students under the Boston mechanism as well.

32. That is, the expected value from the top-ranked school is more than \(\frac{3 }{2}\) of the expected value from the second-ranked school.

33. Note that \(E\left[ U_{1}\right] >\frac{3}{2}\) \(E\left[ U_{2}\right] \) is just sufficient, but not necessary, for the Boston mechanism to be superior to DA in this regard.

34. I thank an anonymous referee for suggesting the example.

35. Note that this is consistent with our initial assumption that the random variables \(V_{1}^{i},...,V_{n}^{i}\) are exchangeable.

36. Power distributions, which also encompass uniform distributions, are commonly used especially in the auction theory literature. For example, see Vickrey [31], Plum [27], Cheng [14] and Kaplan and Zamir [22].

37. Our simulations suggest that the difference in the interim probabilities under the Boston and DA mechanisms can be, as in the three-school case, represented in the form \({\mathbf {P}}^{B}\left( q\right) -{\mathbf {P}} ^{DA}\left( q\right) =c\left( q\right) \cdot \left( a_{1},a_{2},...,a_{n}\right) \) for some constant \(c\left( q\right) >0\), where \(\sum _{i=1}^{n}a_{i}=0\).

38. I thank an anonymous referee for recommending this exercise.

39. Note that for \(i_{1}\) to be assigned to \(s_{2}\), they must not have been assigned to \(s_{1}\) in Step 1. Therefore, t must be at least 1.

40. In the rest of Appendices, “ with probability” is often abbreviated to “ w.p.”

41. As we will be working only with the three-school case, we are suppressing n in the original notation \(P_{k}^{n}\).

42. This is because if there are q students who are tentatively accepted by each of the two schools, there are less than q students in the remaining school, say s, since there are in total 3q students. Furthermore, since there are three schools and 3q students, even if some of those student(s) are rejected by the two schools, the number of new applicants for school s together with the students who were tentatively accepted in earlier steps cannot exceed q in later steps.

43. This must be the case in fact since there are more than q students who applied to s and also to \(s^{\prime }\). Since there are 3q students, there cannot be any other school that receives more than q applicants.

44. There were \(m\le \left( q-1\right) \) students other than \(i_{1}\) who applied to \(s_{1}\) is Step 1, and l students who applied to \(s_{3}\) in Step 2 when k students applied to \(s_{3}\) in step 1.

45. (probability under Boston)-(probability under DA).

46. Under the Boston mechanism, there are q students assigned to \(s_{1}\) and q other students assigned to \(s_{3}\) is Step 1. Hence, since \(i_{1}\) will apply to \(s_{2}\) in Step 2, they are guaranteed a seat in \(s_{2}\) as there can be at most \(\left( q-j\right) \) new applicants for \(s_{2}\).

47. To see why this is the case under DA, consider the following. If \(i_{1}\) is tentatively accepted by \(s_{1}\) in step 1, this implies that students rejected by \(s_{1}\) will apply to \(s_{2}\) or \(s_{3}\) in the later step(s). Even if they eliminated some other student(s), these students cannot eliminate \(i_{1}\) since they are ranked below \(i_{1}\) as they were eliminated by student(s) ranked below \(i_{1}\).

I am deeply indebted to my Ph.D. advisor Vijay Krishna for his support and numerous comments and suggestions. I thank an anonymous associate editor and two anonymous reviewers for constructive comments and suggestions. Earlier versions were presented at the Carnegie Mellon University, Penn State University, Maastricht University, University of Technology Sydney, METU, New Economic School, TOBB ETU, Midwest Economic Theory Conference, Stony Brook Game Theory Conference, and 18th International Symposium on Dynamic Games and Applications. I thank the audience for their comments and discussions. Needless to say, any remaining errors and oversights are mine.

Authors and Affiliations

1. Department of Economics, TOBB University of Economics and Technology, Ankara, Turkey

   Ethem Akyol

Corresponding author

Correspondence to Ethem Akyol.

Code Availability

MATLAB codes that are used for simulations in Sect. 4.2 are publicly available at the author’s website (http://ethemakyol.weebly.com/matlabcodes.html) or upon request from the author.

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

This paper is based on Chapter 1 of my Ph.D. dissertation, Akyol [6], and was previously circulated as part of the unpublished manuscripts “ Welfare Comparison of School Choice mechanisms under Incomplete Information” and “ Welfare Comparison of Allocation mechanisms under Incomplete Information”

Appendix A Calculations in Example 4

Consider a student, say \(i_{1}\), and without loss of generality, let \(i_{1}\) ’s true ranking of schools be \(\left( s_{1},s_{2},s_{3}\right) \). That is, school \(s_{k}\) is student \(i_{1}\)’s \(k^{th}\) choice for any \(k\in \left\{ 1,2,3\right\} \). Note that there are two other students in this scenario.

Let t be the number of students (other than \(i_{1}\)) who rank \(s_{1}\) as a first choice, and l be the number of students who rank \(s_{2}\) as a first choice. Hence, \(2-t-l\) students rank \(s_{3}\) as a first choice.

First, consider the Boston (B) mechanism. Now,

where the term in the brackets is the probability that exactly t students rank \(s_{1}\) as their first choice, and \(\frac{1}{t+1}\) is the probability that \(i_{1}\) is ranked on top of priority order and assigned to \(s_{1}\) when there are t other students who rank \(s_{1}\) as their first choice. To calculate \(P_{2}^{B}\), first consider the case when \(t=1\).^{Footnote 39} Then, \(l\in \left\{ 0,1\right\} \). First, consider the case that \(l=0\). In this case, there is one student whose first choice is \(s_{3}\). Hence, if \(i_{1}\) is rejected in step 1, which happens with probability (w.p.)^{Footnote 40}\(\frac{1}{2}\), \(i_{1}\) will be assigned to \(s_{2}\) . Second, consider the case that \(l=1\). In that case, \(i_{1}\) cannot get into \(s_{2}\) as another student was assigned to \(s_{2}\) in step 1. Now, consider \(t=2\). If \(i_{1}\) is rejected in step 1, which happens w.p. \( \frac{2}{3}\), there is one more student other than \(i_{1}\) who is rejected. If the other student’s second choice is \(s_{3}\), \(i_{1}\) will be assigned to \(s_{2}\) in step 2. If the other student’s second choice is \(s_{2}\), \(i_{1}\) will be assigned to \(s_{2}\) w.p. \(\frac{1}{2}.\) Combining these cases, we have

and hence

Thus, we have

We next compute the desired probabilities for DA. Note that \(i_{1}\) is ranked on top of the priority order of the schools w.p. \(\frac{1}{3}\), second w.p. \(\frac{1}{3}\), and third w.p. \(\frac{1}{3}\).

If \(i_{1}\) is ranked first in the priority rankings, then \(i_{1}\) is assigned to \(s_{1}\).

If \(i_{1}\) is ranked second in the priority rankings, then they are assigned to \(s_{1}\) if the student who is ranked first in the priority ranking does not rank \(s_{1}\) as a first choice, which happens w.p. \(\frac{2}{3}\). Otherwise, \(i_{1}\) is assigned to \(s_{2}\).

If \(i_{1}\) is ranked third in the priority rankings, then they are is assigned to \(s_{1}\) only when the student who is ranked first does not rank \( s_{1}\) as a first choice, the student who is ranked second does not rank \( s_{1}\) as a first choice, and also does not rank \(s_{1}\) as a second choice if their first choice is the same as that of the student who is ranked first. This happens w.p.

Hence, the probability that \(i_{1}\) is assigned to \(s_{1}\) is

Assume that \(i_{1}\) is ranked third in the priority rankings. Then, \(i_{1}\) is assigned to \(s_{2}\) only under the following cases:

1. 1.

   The students ranked first and second in the schools’ priority list rank \(s_{1}\) as a first choice, with the student ranked second having \(s_{3}\) as a second choice;

2. 2.

   The students ranked first and second in the schools’ priority list rank \(s_{3}\) as a first choice, with the student ranked second having \(s_{1}\) as a second choice;

3. 3.

   The student ranked first in the schools’ priority list ranks \(s_{1}\) as a first choice, with the student ranked second having \(s_{3}\) as a first choice;

4. 4.

   The student ranked first in the schools’ priority list ranks \(s_{3}\) as a first choice, with the student ranked second having \(s_{1}\) as a first choice.

Thus, if \(i_{1}\) is ranked third in the priority rankings, then they are assigned to \(s_{2}\) w.p.

Hence, the probability that \(i_{1}\) is assigned to \(s_{2}\) is

and the probability that \(i_{1}\) is assigned to \(s_{3}\) is

Combining these, we obtain

Appendix B Three-School Case: Proof of Lemma 1

Before stating the proof, let us make some observations regarding the assignments under the Boston and DA mechanisms, some of which have already been presented in the text.

First, consider the Boston mechanism.

• Under the Boston mechanism, if a student i is accepted by a school s at any step, they are permanently assigned to s.

• Given that each student reports truthfully, if a student applies to school s in step k, this implies that school s is this student’s \( k^{th}\) choice. Furthermore, this student competes for a seat at the school only with students whose rank for s is identical.

• Hence, under the Boston mechanism, the probability of a student to be accepted at any step when there are z other students applying to the same school at that step is \(\frac{q^{*}}{z+1}\) if \(z\ge q^{*}\), and 1 if \(z<q^{*}\), where \(q^{*}\) is the number of seats unoccupied in earlier steps.

Conversely, recall that assignments under DA significantly differ from those under the Boston mechanism. Some observations are as follows.

• Under DA, acceptances are tentative until the final step. If student i is tentatively accepted by school s, they still face the risk of being rejected by s in a later step.

• Hence, a student who applies to a school at a certain step is competing not only with students applying to the same school at the same step but those who were tentatively accepted by that school in earlier steps.

• Because schools rank students identically, the rejection or tentative acceptance of a student when there are more applicants to the school than available seats gives us additional information regarding the rank of these students.

After these observations, we are ready to state the proof. Assume that there are three schools, each with a quota of \(q\ge 1\), and 3q students. Since students and schools are ex-ante symmetric, consider, without loss of generality, student \(i_{1}\) with a school ranking of \(\left( s_{1},s_{2},s_{3}\right) \). That is, their first three choices are \(s_{1}\), \( s_{2}\), and \(s_{3}\), respectively.

Let \(P^{B}\left( q\right) =\left( P_{k}^{B}\left( q\right) \right) _{k=1}^{3} \) denote the probability of student \(i_{1}\) getting into each school under the Boston mechanism and \(P^{DA}=\left( P_{k}^{DA}\left( q\right) \right) _{k=1}^{3}\) similarly under the DA mechanism.^{Footnote 41}

We would like to show that

Note that this will imply that

since

To perform the necessary computations, we make further observations regarding DA and introduce some notation.

• Because there are 3q total students, there can be at most two schools with at least q applicants (new applicants together with those tentatively accepted in earlier step(s)) at any step.

• If there are two schools, each with at least q applicants (new applicants together with those tentatively accepted in earlier step(s)) at any step, then applicants of a school with less than q applicants are guaranteed a seat in that school.^{Footnote 42}

• If there are at most q applicants (new applicants together with those tentatively accepted in earlier step(s)) at any step, each applicant will be tentatively accepted.

Recall that we consider student \(i_{1}\), who has a school ranking of \(\left( s_{1},s_{2},s_{3}\right) \). Assume that the DA algorithm does not stop in Step 1. That is, there is at least one student who is rejected by their first choice. Let us consider the following functions that will be useful in our computations.

• \(P\left( q,b,c,d\right) :\) Consider the situation that \(b\le \) \( \left( q-1\right) \) additional students (other than student \(i_{1}\)) apply to \(s_{1}\) in Step 1, and hence all those students (including \(i_{1}\)) are tentatively accepted by \(s_{1}\) in step 1. Assume that there is exactly one school (other than \(s_{1}\)) to which more than q students applied in step 1, denoted by \(s^{*}\). Let \(c>q\) be the number of students who applied to \(s^{*}\) in step 1, and hence \(c-q\) of them will be rejected by \(s^{*}\) in step 1. Assume that d students among those rejected by \(s^{*}\) apply to \(s_{1}\) in Step 2. Let \(P\left( q,b,c,d\right) \) denote the probability that student i will be tentatively accepted by \( s_{1}\) in step 2.

• \(P^{\prime }\left( q,b,c,d\right) :\) Consider the situation that \( b\ge q\) additional students (other than student \(i_{1}\)) apply to \(s_{1}\) in step 1, \(i_{1}\) is tentatively accepted by \(s_{1}\) in step 1, and \( b+1-q\) of the remaining students who applied to \(s_{1}\) are rejected in step 1. Assume that there is exactly one school (other than \(s_{1}\)) to which more than q students applied in step 1, denoted by \(s^{*}\).^{Footnote 43} Let \(c>q\) be the number of students who applied to \(s^{*}\) in step 1, and hence, \(c-q\) of them will be rejected by \(s^{*}\) in step 1. Assume that d students among those rejected by \(s^{*}\) apply to \(s_{1}\) in Step 2. Let \(P\left( q,b,c,d\right) \) denote the probability that student \( i_{1}\) will be tentatively accepted by \(s_{1}\) in step 2.

• \(R\left( q,b,c,d\right) :\) Consider the situation that there are \( c\ge q\) additional students (other than student \(i_{1}\)) who apply to \( s_{1} \) in step 1, and student \(i_{1}\) is rejected by \(s_{1}\). Assume that there are d additional students (among those who applied to \(s_{1}\) but were rejected in step 1) whose second choice is also \(s_{2}\) (recall that \( s_{2} \) is the second choice of student \(i_{1}\)), and hence will apply to \( s_{2}\) in step 2. Furthermore, there were \(b\le \left( q-1\right) \) students who applied to \(s_{2}\) (and hence tentatively accepted by \(s_{2}\)) in step 1. Let \(R\left( q,b,c,d\right) \) denote the probability that student \(i_{1}\) will be tentatively accepted by \(s_{2}\) in step 2.

• \(R^{\prime }\left( q,b,c,d\right) :\) Consider the situation that there are \(c\ge q\) additional students (other than \(i_{1}\)) who apply to \(s_{1}\), and student \(i_{1}\) is rejected by \(s_{1}\). Assume that there are d additional students (among those who applied to \(s_{1}\) but were rejected in step 1) whose second choice is \(s_{2}\), and hence will apply to \(s_{2}\) in step 2. Furthermore, there are \(b\ge q\) students who apply to \(s_{2}\) in step 1, and hence q of them are tentatively accepted by \(s_{2}\) in step 1. Let \(R^{\prime }\left( q,b,c,d\right) \) denote the probability that student \(i_{1}\) will be tentatively accepted by \(s_{2}\) in step 2.

Note that P and \(P^{\prime }\) are identical except that one is defined for \(b\le \left( q-1\right) \) and the other is defined for \(b\ge q\). Theoretically, they could have been combined in one function, which would be acceptable, but conceptually there is a difference. When \(b\le \left( q-1\right) \), no one is rejected by school \(s_{1}\) in step 1 of DA and we gain no information about student \(i_{1}\)’s priority ranking. Conversely, when \(b>q\), we have additional information because q students will be accepted and the remaining \(b-q\) students will be rejected. Therefore, we can conclude that rejected students are ranked below accepted students in the priority list of schools. Therefore, we keep these functions separate to keep track of these facts. Similarly, R and \(R^{\prime }\) differ only in that R is defined for the case when \(b\le \left( q-1\right) \) and \( R^{\prime }\) is defined for the case when \(b\ge q\). Similarly, combining the two functions would be theoretically acceptable, but conceptually there is a difference between R and \(R^{\prime }\).

Recall that we consider student \(i_{1}\) with the school ranking of \(\left( s_{1},s_{2},s_{3}\right) \).

To conserve space, let \(f\left( q,m,j\right) \) denote the probability that there are exactly m students (other than student \(i_{1}\)) who rank \(s_{1}\) as the first choice, j students who rank \(s_{2}\) as the first choice and \( k\equiv 3q-m-j-1\) students who rank \(s_{3}\) as the first choice. That is,

Notation 1

\(f\left( q,m,j\right) =\left( {\begin{array}{c}3q-1\\ m\end{array}}\right) \left( {\begin{array}{c}3q-1-m\\ j\end{array}}\right) \left( \frac{1}{3} \right) ^{3q-1}\)

We work case by case depending on m, j, and k to determine the probabilities of obtaining \(s_{1}\), \(s_{2}\), and \(s_{3}\) for \(i_{1}\) under the Boston and DA mechanisms. Note that there are m students that apply to \(s_{1}\), j students that apply to \(s_{2}\) and k students that apply to \(s_{3}\) in step 1 under both the Boston mechanism and DA.

1.1 Case 1 \(m\le \left( q-1\right) \)

In this case, under the Boston mechanism, student \(i_{1}\) will be assigned to \(s_{1}\). Therefore, the probability that \(i_{1}\) gets their first choice, school \(s_{1}\), is 1, and the probability that they are assigned to \(s_{2}\) or \(s_{3}\) is 0.

To be able to compute these probabilities under DA, we consider the following subcases:

1.1.1 Case 1.i \(j\le q-1\)

In this case, all students who apply to \(s_{1}\) and \(s_{2}\) will be tentatively accepted by those schools in step 1. However, since \(k\ge \left( q+1\right) ;\) q students will be tentatively accepted by \(s_{3}\) and remaining \(\left( k-q\right) =2q-m-j-1\) students will be rejected by \( s_{3}\) in the first step. Therefore, those \(\left( k-q\right) \) students will apply to their second choice in step 2.

The probability that l students among those \(k-q=2q-j-m-1\) apply to \(s_{1}\) in the next step (step 2) is the probability that l students out of \( 2q-j-m-1\) rank \(s_{1}\) over \(s_{2}\) and hence, will apply to \(s_{1}\) in step 2, which is given by

If \(l\le q-1-m\), and hence, \(m+l\le \left( q-1\right) \), no student is rejected by \(s_{1}\) in the second step. There are at least q students applying to \(s_{2}\), and q of those are tentatively accepted by \(s_{2}\) in step 2. Because q other students were also tentatively accepted by \(s_{3} \) in step 1, there can be at most q applicants in total (together with those who were tentatively accepted by \(s_{1}\) in earlier step(s)), and student \(i_{1}\) will therefore be assigned to \(s_{1}\).

When \(l\ge \left( q-m\right) ,\) the probability that student \(i_{1}\) will be tentatively accepted by \(s_{1}\) in step 2 is \(P\left( q,m,k,l\right) \), where \(k=3q-m-j-1\).^{Footnote 44} Note again that if student \(i_{1}\) is tentatively accepted in Step 2, then they will be assigned to \(s_{1}\) for sure. Note also that if student \(i_{1}\) is rejected by \(s_{1}\) in step 1, which happens w.p. \(1-P\left( q,m,k,l\right) \), \( i_{1}\) will be assigned to \(s_{2}\) under DA.

Therefore, when \(m,j\le \left( q-1\right) ,\) the difference in probability of getting into \(s_{1}\) between the Boston mechanism and DA^{Footnote 45} for \(i_{1}\) is

where \(k=3q-m-j-1\). Note also that under both DA and the Boston mechanism, \( i_{1}\) cannot be assigned to \(s_{3}\) in this case.

1.1.2 Case 1.ii \(q\le j\le \left( 2q-m-1\right) \)

In this case \(j,k\ge q\) and student \(i_{1}\) is assigned to \(s_{1}\) for sure under DA. This is because there can be at most q students applying to \( s_{1}\) (together with those who were already tentatively accepted by \(s_{1}\) in earlier step(s)) even in later steps. Therefore, there is no difference in the outcome of the Boston mechanism and DA in this case.

1.1.3 Case 1.iii \(\left( 2q-m\right) \le j\le \left( 3q-m-1\right) \)

We have \(j\ge \left( q+1\right) \) and \(k\le \left( q-1\right) \). Hence, all students who apply to \(s_{1}\) and \(s_{3}\) in step 1 will be tentatively accepted, and \(\left( j-q\right) \ge 1\) students will be rejected by \(s_{2}\) in step 1. Assume that l of those \(\left( j-q\right) \) students apply to \(s_{1}\) in the second step, which happens w.p. \(\left( {\begin{array}{c} j-q\\ l\end{array}}\right) \left( \frac{1}{2}\right) ^{l}\left( \frac{1}{2}\right) ^{j-q-l}= \left( {\begin{array}{c}j-q\\ l\end{array}}\right) \left( \frac{1}{2}\right) ^{j-q}\).

If \(l\le q-1-m\), and hence \(l+m\le \left( q-1\right) \), student \(i_{1}\) will be tentatively accepted by \(s_{1}\) in step 2, and thus, assigned for sure to \(s_{1}\).

If \(l\ge \left( q-m\right) \), the probability that student \(i_{1}\) is tentatively accepted by, and thus, assigned for sure to \(s_{1}\) is \(P\left( q,m,j,l\right) \). Hence, the difference in the probability that \(i_{1}\) is assigned to \(s_{1}\) between the Boston mechanism and DA in these cases is

Note that (1) =(2) by symmetry.

Student \(i_{1}\) will be assigned to \(s_{3}\) if they are rejected in step 2 under DA, which happens w.p. \(\left( 1-P\left( q,m,j,l\right) \right) \). Recall that under the Boston mechanism, \(i_{1}\) will be assigned to \(s_{1}\) for sure, and hence, the difference in probability of getting into \(s_{3}\) between the Boston mechanism and DA in these cases is

1.2 Case 2 \(q\le m\le \left( 2q-1\right) \)

In this case, under both the Boston mechanism and DA, student \(i_{1}\) will be accepted in step 1 w.p. \(\frac{q}{m+1}\). Under the Boston mechanism, student \(i_{1}\) will be assigned to \(s_{1}\) for sure if they are accepted in step 1. If \(i_{1}\) is rejected, we need to consider the subcases whether \( i_{1}\) will be assigned to \(s_{2}\) or \(s_{3}\).

1.2.1 Case 2.i \(0\le j\le 2q-m-1\)

In this case, \(j\le \left( q-1\right) \) and \(k\ge q\).

Assume that student \(i_{1}\) is accepted in step 1,  which happens w.p. \( \frac{q}{m+1}\). Then, \(i_{1}\) will be assigned to \(s_{1}\) under the Boston mechanism.

Consider DA. Now, \(k-q\) students will be rejected by \(s_{3}\) in step 1, and assume that l students among these \(\left( k-q\right) =2q-j-m-1\) students apply to \(s_{1}\) in step 2, which happens w.p. \(\left( {\begin{array}{c}2q-j-m-1\\ l \end{array}}\right) \left( \frac{1}{2}\right) ^{2q-j-m-1}\).

The probability that student \(i_{1}\) is tentatively accepted by \(s_{1}\) is step 2 in this case is \(P^{\prime }\left( q,m,k,l\right) \) under DA. In that case, \(i_{1}\) will be permanently assigned to \(s_{1}\). Note that if student \(i_{1}\) is rejected by \(s_{1}\) in step 2, they will be assigned to \(s_{2}\) under DA.

Second, assume that student \(i_{1}\) is rejected in step 1, which happens w.p. \(\frac{m+1-q}{m+1}\). Then, student \(i_{1}\) will be assigned to \(s_{2}\) under both the Boston mechanism and DA.^{Footnote 46}

Therefore, the difference in the probability that \(i_{1}\) gets into \(s_{1}\) between B and DA is

As shown earlier, there is no difference in the probability that \(i_{1}\) gets into \(s_{3}\) between the Boston mechanism and DA in this case.

1.2.2 Case 2.ii \(\left( 2q-m\right) \le j\le q\)

In this case \(k\le \left( q-1\right) \).

If student \(i_{1}\) is accepted in step 1, which happens w.p. \(\frac{q}{m+1} \), student \(i_{1}\) will be assigned to \(s_{1}\) under both the Boston mechanism and DA.^{Footnote 47} Therefore, there is no difference in the probability that \(i_{1}\) will be assigned to \(s_{1}\) between the Boston mechanism and DA in this case.

Assume that student \(i_{1}\) is rejected in step 1, which happens w.p. \( \frac{m+1-q}{m+1}\). There are \(\left( m-q\right) \) additional students rejected by \(s_{1}\) in the first step. Assume that \(m^{\prime }\) of them rank \(s_{2}\) as second choice, and hence apply to \(s_{2}\) in the second step.

If \(m^{\prime }+j\le \left( q-1\right) \), student \(i_{1}\) will be assigned to \(s_{2}\) under both the Boston mechanism and DA.

If \(m^{\prime }+j\ge q\), under the Boston mechanism, student \(i_{1}\) will be assigned to \(s_{2}\) w.p. \(\frac{q-j}{m^{\prime }+1}\), and to \(s_{3}\) w.p. \(\left( 1-\frac{q-j}{m^{\prime }+1}\right) \).

Under DA, student \(i_{1}\) will be tentatively accepted by \(s_{2}\) w.p. \( R\left( q,j,m,m^{\prime }\right) \) since there were \(j\le q\) students that applied to \(s_{2}\) in step 1, and \(i_{1}\) was rejected by \(s_{1}\) with \( m^{\prime }\) other students in step 1 when there were m other applicants in step 1. Note that if \(i_{1}\) is accepted by \(s_{2}\) in step 2, they will be permanently assigned to \(s_{2}\).

If \(i_{1}\) is rejected by \(s_{2}\), which happens w.p. \(\left( 1-R\left( q,j,m,m^{\prime }\right) \right) \), they will be assigned to \(s_{3}\) under DA.

Therefore, in this case, the difference in probability of getting into \(s_{1} \) between the Boston mechanism and DA is 0, and the difference in probability of getting into \(s_{3}\) between the Boston mechanism and DA is

1.2.3 Case 2.iii \(\left( q+1\right) \le j\le \left( 3q-m-1\right) \)

In this case \(k\le \left( q-2\right) \) and \(j\ge \left( q+1\right) \).

Assume that student \(i_{1}\) is accepted in step 1, which happens w.p. \( \frac{q}{m+1}\). Then, \(i_{1}\) will be assigned to \(s_{1}\) under the Boston mechanism.

Under DA,  \(j-q\) students will be rejected by \(s_{2}\) in step 1, and assume that l among \(j-q\) students rejected apply to \(s_{1}\) in step 2. Now, \(P^{\prime }\left( q,m,j,l\right) \) is the probability of student \( i_{1} \) being tentatively accepted by \(s_{1}\) in step 2 under DA. Hence, the difference in probability that \(i_{1}\) is assigned to \(s_{1}\) between the Boston mechanism and DA is

Again, by symmetry (3) = (5).

In this case, if student \(i_{1}\) is rejected by \(s_{1}\) in the second step, which happens w.p. \(\left( 1-P^{\prime }\left( q,m,j,l\right) \right) \), \( i_{1}\) will be assigned to \(s_{3}\) under DA. Hence, the difference in probability that \(i_{1}\) is assigned to \(s_{1}\) between the Boston mechanism and DA is

Second, assume that student \(i_{1}\) is rejected in the first step, which happens w.p. \(\frac{m+1-q}{m+1}\). Then, since there are more than q applicant to \(s_{2}\) in step 1, student \(i_{1}\) will be assigned to \(s_{3}\) under the Boston mechanism. Under DA, \(i_{1}\) will be assigned to \(s_{2}\) w.p. \(R^{\prime }\left( q,j,m,m^{\prime }\right) ,\) and to \(s_{3}\) w.p. \( \left( 1-R^{\prime }\left( q,j,m,m^{\prime }\right) \right) \), where \( m^{\prime }\) is the number of students (other than student \(i_{1}\)) who are rejected by \(s_{1}\) in the first step and apply to \(s_{2}\) in the second step. Therefore, the difference in probability that \(i_{1}\) is assigned to \( s_{3}\) between the Boston mechanism and DA is

1.3 Case 3 \(2q\le m\le \left( 3q-1\right) \)

Then, we have \(j,k<q\). If student \(i_{1}\) is accepted in the first step, they will be assigned to \(s_{1}\) under both the Boston mechanism and DA.

Assume that student \(i_{1}\) is rejected in the first step, which happens w.p. \(\frac{m+1-q}{m+1}\). Note that there are no students rejected by \(s_{2}\) or \(s_{3}\) in Step 1. Let \(m^{\prime }\) be the number of students (other than \(i_{1}\)) who are rejected by \(s_{1}\) in the first step and will apply to \(s_{2}\) in the second step.

If \(m^{\prime }+j\le \left( q-1\right) \), student \(i_{1}\) will be assigned to \(s_{2}\) under both the Boston mechanism and DA.

If \(m^{\prime }+j\ge q\), under the Boston mechanism, student \(i_{1}\) will be assigned to \(s_{2}\) w.p. \(\frac{q-j}{m^{\prime }+1}\), and to \(s_{3}\) w.p. \(\left( 1-\frac{q-j}{m^{\prime }+1}\right) \). Under DA, student \(i_{1}\) will be assigned to \(s_{2}\) w.p. \(R\left( q,m,j,m^{\prime }\right) \), and to \( s_{3}\) w.p. \(\left( 1-R\left( q,m,j,m^{\prime }\right) \right) \).

Therefore, in this case, the difference in probability that \(i_{1}\) is assigned to \(s_{1}\) between the Boston mechanism and DA is 0, and the difference in probability that \(i_{1}\) is assigned to \(s_{3}\) between the Boston mechanism and DA is

Thus, we covered all possible cases. Combining all the cases, we have the following:

where \(k=3q-m-j-1\) and \(\gamma \left( q,m,k,l\right) =1-P^{\prime }\left( q,m,k,l\right) \) and

Note first that \(P_{1}^{B}\left( q\right) -P_{1}^{DA}\left( q\right) >0\).

We present two more observations on probability functions defined.

Lemma 2

When \(m\ge m^{\prime }\), \(m\ge q\), \(j\le q\) and \(m^{\prime }+j\ge \left( q-1\right) \),

Proof

Consider student i whose first and second choices are schools s and \( s^{\prime }\), respectively. Assume that there are \(m\ge q\) other students whose first choice is s, \(j\le q\) students whose first choice is \( s^{\prime }\), and who hence apply to school \(s^{\prime }\) is step 1. Let student \(i^{\prime }\) be one of those j students. Consider the situation that student i together with \(m^{\prime }\) other students is rejected by s in step 1. Note that the probability that student \(i^{\prime }\) (and any of the j students) is accepted by \(s^{\prime }\) in step 2 is \(P\left( q,j-1,m+1,m^{\prime }+1\right) \). Furthermore, the probability that student i (and any of the other \(m^{\prime }\) students) is accepted by \(s^{\prime }\) in step 2 is \(R\left( q,j,m,m^{\prime }\right) \).

Note that there are at least q applicants for \(s^{\prime }\) in step 2. Hence, it must be that \(\left( m^{\prime }+1\right) R\left( q,j,m,m^{\prime }\right) +j\times \left( P\left( q,j-1,m+1,m^{\prime }+1\right) \right) =q\), which implies the desired result. \(\square \)

Lemma 3

When \(j\ge \left( q+1\right) ,\) \(m\ge q,\)

Proof

Similar to the aforementioned lemma, we must have that \(\left( m^{\prime }+1\right) R^{\prime }\left( q,j,m,m^{\prime }\right) +q\times \left( P^{\prime }\left( q,j-1,m+1,m^{\prime }+1\right) \right) =q\). \(\square \)

Therefore, \(P_{3}^{B}\left( q\right) -P_{3}^{DA}\left( q\right) \) becomes

where \(g\left( m,q\right) =\frac{m+1-q}{m+1}\), \(h\left( m,q\right) =\frac{q}{ m+1},\) \(z\left( m,j,m^{\prime },q\right) =\left( \frac{q-\left( j\times P\left( q,j-1,m+1,m^{\prime }+1\right) \right) }{m^{\prime }+1}\right. \left. -\frac{q-j}{ m^{\prime }+1}\right) \).

Noting that

where \(k=3q-m-j-1\) and

it suffices to prove the following equality to show that \(P_{1}^{B}\left( q\right) -P_{1}^{DA}\left( q\right) =2\left( P_{3}^{B}\left( q\right) -P_{3}^{DA}\right. \left. \left( q\right) \right) \):

where again \(g\left( m,q\right) =\frac{m+1-q}{m+1}\) and \(z\left( m,j,m^{\prime },q\right) =\left( \frac{q-\left( j\times P\left( q,j-1,m+1,m^{\prime }+1\right) \right) }{m^{\prime }+1}-\frac{q-j}{m^{\prime }+1}\right) \).

Denoting the first sum as \(S_{1}\) and the second as \(S_{2}\), and using the notation \(\alpha \left( j,q,m^{\prime }\right) =\left( j\times \left( 1-P\left( q,j-1,m+1,m^{\prime }+1\right) \right) \right) \) and \(\beta \left( j,q,m^{\prime }\right) =\left( 1-P^{\prime }\left( q,j-1,m+\right. \right. \left. \left. 1,m^{\prime }+1\right) \right) ,\) \(S_{2}\) becomes

which is equal to

Claim 1

Let \(k=3q-m-j-1\).

Proof

We want to show

Note that \(P^{\prime }\left( q,m,k,0\right) =1\) and if \(m=2q-1\), then \(j=0\) and \(2q-m-j-1=0\). Furthermore, if \(j=2q-m-1\), then \(2q-m-j-1=0\). Note also that \(3q-m-1=q<\left( q+1\right) \) when \(m=2q-1\). Hence, in effect, we want to show the following:

Take some \(\left( m,j\right) \) such that \(m\in \{q,...,2q-2\}\) and \(j\in \left\{ 0,...,2q-m-2\right\} \). Now, consider \(m^{*}=3q-m-j-2\) and \( j^{*}=m+1\). Note that \(m^{*}\in \left\{ q,...,2q-2\right\} \) and \( j^{*}\in \left\{ q+1,...,3q-m^{*}-1\right\} \).

Recall that \(f\left( q,m,j\right) =\left( {\begin{array}{c}3q-1\\ m\end{array}}\right) \left( {\begin{array}{c}3q-1-m\\ j\end{array}}\right) \left( \frac{1}{3}\right) ^{3q-1}\). We claim that

where \(h\left( q,j^{*},m^{*},m^{\prime }\right) =\left( 1-P^{\prime }\left( q,j^{*}-1,m^{*}+1,m^{\prime }+1\right) \right) \). It is easy to see that

We also claim that

Now,

and

Hence, we have proven the claim.

Note that there is a one-to-one correspondence between \(\left( m,j\right) \) and \(\left( m^{*},j^{*}\right) \), and hence, we have the desired result. \(\square \)

Claim 2

where again \(\alpha \left( j,q,m^{\prime }\right) =j\times \left( 1-P\left( q,j-1,m+1,m^{\prime }+1\right) \right) \).

Proof

Consider some m, \(j\in \left\{ 0,...,q-1\right\} \). Now, consider \(m^{*}=3q-m-j-2\) and \(j^{*}=m+1\). Then, by identical arguments as above, we have the result. \(\square \)

Hence, we showed that \(S_{1}=S_{2}\) which was the desired result.

Appendix C Proof of Proposition 2

Proof

We simply show that \(w_{F^{i}}=2E\left[ U_{1}\right] -3E\left[ U_{2}\right] +E\left[ U_{3}\right] >0\) when \(\left( i\right) ,\left( ii\right) \),\(\left( iii\right) \) or \(\left( iv\right) \) holds. \(\left( i\right) \), \(\left( ii\right) \) and \(\left( iii\right) \) follow from Theorem 1.A.19, Theorem 1.C.43 and Theorem 1.A.22 of Shanthikumar [29], respectively, which show that, under the stated assumptions, \(\left( U_{1}-U_{2}\right) \) first order stochastically dominates \(\left( U_{2}-U_{3}\right) \). Hence,

Thus, we have

implying that

The proof of (iv) is by direct calculation. For ease of notation, we suppress agent name i from the CDF \(F^{i}\) and corresponding density function \(f^{i}\). Assume that \(F\left( x\right) =\left( \frac{x}{a}\right) ^{\beta }\), \(\beta >0\). Now, \(U_{k}\) is the \(k^{th}\) highest order statistic of three random variables IID from F. Hence, the CDF of \(U_{k}\), denoted as \(H_{k}\left( .\right) \), can simply be calculated as follows: For any \( x\in \left[ 0,a\right] \),

and

Thus, since

we obtain

Hence,

When \(F\left( x\right) =\left( \frac{x}{a}\right) ^{\beta }\) over \(0\le x\le a\), and hence \(f\left( x\right) =\frac{\beta }{a}\left( \frac{x}{a} \right) ^{\beta -1}=\beta \frac{1}{x}\left( \frac{x}{a}\right) ^{\beta }\), we have

\(\square \)

Reprints and permissions