Preference profiles for efficiency, fairness, and consistency in school choice problems

We study the school choice problem in which a school district assigns school seats to students. There has been a long debate over the three best-known rules for this problem: the deferred acceptance rule (DA), the top-trading cycles rule (TTC), and the immediate acceptance rule (IA). We evaluate these rules by investigating how often they satisfy three central requirements, efficiency, fairness, and consistency. We compare the restricted domains of students’ preferences on which each rule satisfies these requirements. From the containment relations between them, we show that DA performs better than IA, which itself performs better than TTC in terms of efficiency and fairness. If we consider consistency instead, IA performs better than DA, which itself performs better than TTC.

1. This rule is also called the “Boston” mechanism. We adopt the terminology of Thomson (2013).

2. We present the formal definition in Sect. 2.2. For an exhaustive survey on consistency, see Thomson (2015).

3. Precisely, such priority profiles exist only if there are at most two students, or there is only one school, or the sum of capacities of each pair of distinct schools is no smaller than the total number of students. There are other restrictions on priority profiles under which rules satisfy various properties: see Kojima (2011), Haeringer and Klijn (2009), Ehlers and Erdil (2010), Hatfield et al. (2016), Hsu (2013), and Han (2018).

4. The structures of these priority profiles are derived from conditions on priority-capacity pairs. Here we simply assume that the capacity constraints are fixed and keep them implicit.

5. This explanation is borrowed from Che and Tercieux (2017) who also make an “quantitative” analysis on the conflict between efficiency and fairness in a large matching problem. While we analyze the frequency of inefficient/unstable incidences in terms of preference profiles, they analyze it in terms of the fraction of students (or student-school pairs) involved in those incidences. As the size of the problem grows, they keep track of the change of this fraction and study “asymptotic” notions of efficiency and fairness. In their analysis, the number of school types increases as the matching market grows, while we keep it fixed.

6. It is very common to investigate preference restrictions, given an underlying impossibility result. A best-known example is the single-peaked preference domain in the social choice model. A list of papers on “maximal domain” also study preference restrictions (Barbera et al. 1991). Most of these papers focus on restrictions on individual preferences to achieve some relational properties, such as “strategy-proofness”. They also require that a minimally plausible subdomain be included in the resulting domain. In this paper, however, we do not consider such a minimal subdomain and we consider non-relational properties of rules. For a maximal domain approach in the matching context, see Kojima (2007).

7. In case \(n>\sum _{a\in A}q_a\), we can introduce an outside option \(\emptyset \) of “home-schooling” and set its capacity n.

8. This terminology is adopted from Thomson (2013).

9. The definition above is the “TTC algorithm with inheritance” that Kesten (2006) introduces. It is equivalent to the original TTC algorithm proposed by Abdulkadiroǧlu and Sönmez (2003).

10. In defining consistency, we fix an original economy and then check the selections that a rule makes only for its subeconomies. This notion of consistency is introduced by Thomson and Zhou (1993).

11. Note that there are two ways of formulating reduced economies of e. The difference comes from the fact that there can be schools with no available seats at \(x^S\). We keep A as the set of schools, even if some schools have no seats at \(x^S\). This is an adaptation of consistency in Bu (2015) and Kojima and Ünver (2014) to the variable-population setting, which is also referred to as “pre-assignment invariance” in Harless (2017). On the other hand, it is also possible to update students’ preferences to be defined only over the schools with available seats in the reduced economy. Kumano (2013) and Jaramillo (2017) consider this notion of consistency.

12. Here are some examples.

    Example 1 Preference profiles in \(\varvec{\mathcal {P}^N_{max\text {-}min}}\)

    Let \(N\equiv \{1,2,3,4,5\}\), \(A\equiv \{a,b,c,d,e\}\), and \(q=(1,1,1,2,2)\).

    $$\begin{aligned}&\begin{array}{ccccc}P_1&{} P_2&{} P_3&{}P_4&{}P_5\\ \hline a &{} b&{} c&{} d&{}d\\ \vdots &{}\vdots &{}\vdots &{}\vdots &{}\vdots \\ &{}&{}&{}&{}\end{array}\qquad \begin{array}{ccccc}P_1&{} P_2&{} P_3&{}P_4&{}P_5\\ \hline a &{} a&{} a&{} a&{}a\\ b&{}c&{}d&{}d&{}e\\ \vdots &{}\vdots &{}\vdots &{}\vdots &{}\vdots \end{array}\\&\begin{array}{ccccc}P_1&{} P_2&{} P_3&{}P_4&{}P_5\\ \hline a &{} a&{} a&{} a&{}a\\ b&{}b&{}b&{}b&{}b\\ c&{}d&{}d&{}d&{}e\\ \vdots &{}\vdots &{}\vdots &{}\vdots &{}\vdots \\ \end{array}\qquad \begin{array}{ccccc}P_1&{} P_2&{} P_3&{}P_4&{}P_5\\ \hline a &{} a&{} a&{} a&{}a\\ d&{}d&{}d&{}d&{}d\\ b&{}b&{}c&{}c&{}c\\ \vdots &{}\vdots &{}\vdots &{}\vdots &{}\vdots \\ \end{array}\qquad \begin{array}{ccccc}P_1&{} P_2&{} P_3&{}P_4&{}P_5\\ \hline a &{} a&{} a&{} a&{}a\\ b&{}b&{} b&{}b&{}b\\ c&{}c&{} c&{}c&{}c\\ d&{}d&{} d&{}d&{}d\\ e&{}e&{} e&{}e&{}e\\ \end{array} \end{aligned}$$

    The first profile exhibits no conflict, since all students can be simultaneously assigned their favorite schools. The second profile exhibits maximal conflict over a, but there is no conflict over the second most preferred schools. The third profile exhibits maximal conflict over a and b. Additionally, there is some conflict over d, because three students rank d in the third position but \(q_d=2\). There are two cases: (1) All students are assigned to their third most preferred schools or better (almost no conflict). This is when a or b is assigned to one of students 2, 3, and 4. (2) Not all students are assigned their third most preferred schools or better. This is when a and b are assigned to students 1 and 5. The remaining students compete for d and one of them is eventually assigned a school worse than d. A similar argument applies to the fourth profile. There is some conflict over b and c in addition to the maximal conflicts over the top two. Again, there are two cases: (1) All students are assigned to their third most preferred schools or better (almost no conflict). This is when a and d are assigned to one of students 1 and 2 and two of students 3, 4, and 5. (2) Not all students are assigned to their third most preferred schools or better. This is when a and d are assigned either to students 3, 4, and  5 or to students 1, 2, and one of students 3, 4, and 5. The two remaining students compete for the same school and one of them is eventually assigned to a school worse than this school. The last profile exhibits maximal conflict over all schools. \(\square \)

13. If \(k=|A|\), all students have the same preferences and \(P\in \mathcal {P}^N_{max\text {-}min}\).

14. That is, if \(\prec \notin \Sigma ^A_{da}\), there is a preference profile \(P\in \mathcal {P}^N\) such that \({{\mathrm{DA}}}(\prec ,P)\) is not efficient at P. The other two domains are defined similarly.

15. That is, \(a_1\) is assigned to the students with at least \(x^S_{a_1}\)th priority according to \(\prec _{a_1}|_S\); \(a_2\) is assigned to the students with at least \(x^S_{a_2}\)th priority among the remaining students according to \(\prec _{a_2}|_S\); and so on.

16. We assume that \(i^*\) is rejected by \(a^*\). If \(q_{a^*}< n-q_{A^k_0(P)}-1\), then, since \(P\in \mathcal {P}^N_{ttc}\), the number of applicants to \(a^*\) at this step does not exceed \(q_{a^*}\). Then, all of them are accepted, contradicting the assumption. If \(q_a^{*}> n-q_{A^k_0(P)}-1\), then school \(a^*\) can accommodate all applicants at this step, because the number of all students present at this step is \(n-q_{A^k_0(P)}\). This again contradicts the assumption. Therefore, \(q_{a^*}=n-q_{A^k_0(P)}-1\). On the other hand, suppose that any student present at this step applies to a school other than \(a^*\). Then, the number of applicants of \(a^*\) is at most \((n-q_{A^k_0(P)}-1)\), which is exactly \(q_{a^*}\). Therefore, \(a^*\) can accommodate all applicants at this step, contradicting the assumption.

17. Since it is well-known that \({{\mathrm{\overline{DA}}}}\) is “non-wasteful” (Kojima and Manea 2010), it is not possible at y to assign some seats that were not assigned to anyone at x. Therefore, \(\{x_i:i\in S\}=\{y_i:i\in S\}\).

18. Let \(i_0\equiv i_s\).

19. Recall that the statement is modulo s.

20. Since DA is not efficient, \(\mathcal {P}^N_{da}\subsetneq \mathcal {P}^N\).

21. Suppose that for some \(\prec \), a student, say i, is rejected by a school at a step, but the school already accepted another student, say j, in an earlier step. Modify the priority of this school such that all students who are accepted to the school, except for j, are placed above j and student i is now placed just above j. It is easy to see that the IA assignment resulting from this new priority profile and the initial preference profile is not fair.

22. Student i forms a rejection chain if he applies to school a in the DA algorithm and school a accepts i temporarily but rejects another student j. Suppose that the rejected student j forms another rejection chain, and so on, until student i forms a rejection chain again. If all students, other than i, are assigned the schools that they apply in these rejection chains, these students can make a Pareto improvement from their final allocations.

23. We can also compare \(\mathcal {P}^N_{ia}\) and the domain of preference profiles at which no student can benefit from misrepresenting his preferences. If we denote the latter domain by \(\hat{\mathcal {P}}^N_{ia}\), it is easy to check that \(\hat{\mathcal {P}}^N_{ia}\subsetneq \mathcal {P}^N_{ia}\) (the proper inclusion can be shown with identical preferences). The similar comparisons can be made on monotonicity requirements for TTC.

Authors and Affiliations

1. Department of Economics, Vanderbilt University, Nashville, TN, 37235, USA

   Eun Jeong Heo

Corresponding author

Correspondence to Eun Jeong Heo.

This paper was previously circulated under the title “Efficiency and Fairness in School Choice Problem: the Maximal Domain of Preference Profiles”. Most of all, I thank William Thomson for his support and guidance. I also appreciate the associate editor and the two anonymous referees giving me constructive comments and suggestions. I benefited from discussions with Anna Bogomolnaia, Bettina Klaus, Youngwoo Koh, Fuhito Kojima, Patrick Harless, Vikram Manjunath, Hervé Moulin, Kyoungwon Seo, Shigehiro Serizawa, Utku Ünver, and Özgür Yılmaz. I am also grateful to seminar audiences at the University of Rochester in 2012, Rice University in 2012, the University of Montreal in 2012, the Catholic University of Louvain in 2013, and the 12th meeting of the society for social choice and welfare at Boston College in 2014 for helpful comments. All remaining errors are my own responsibility.

Reprints and permissions