Sequential school choice with public and private schools

For an early account of the system in New York City, see Abdulkadiroğlu et al. (2009). That paper also hints at the problems studied in the current paper. The system in Boston has recently undergone a series of reforms. For a detailed description of the current system, see www.​bostonpublicscho​ols.​org/​Page/​7080 or www.​bostonpublicscho​ols.​org/​Page/​6594 (Last accessed: 7/29/2022).

Problems associated with such admissions has been heavily debated in Sweden in the last few years, see, e.g., the following op-ed in one of the leading Swedish newspapers (Dagens Nyheter): https://​www.​dn.​se/​debatt/​tre-reformer-som-behovs-for-ett-mer-likvardigt-skolval/​

Very few papers exclusively model decentralized college admissions. See, for example, Chade et al. (2014) and Che and Koh (2016).

In particular, seats of schools available in the second stage are not wasted. Moreover, any other sequential assignment system that guarantees the existence of a straightforward SPNE respects priorities and does not waste the seats available in the second stage needs to use a wasteful mechanism in the first stage.

In an earlier working paper (Andersson et al. 2020), we quantify these theoretical results using the 2015 admission data from the Swedish municipality Botkyrka. The main finding is that the waste of school seats can be dramatically reduced by organizing the two-stage admission system in such a fashion that students in the first stage are allowed to apply only to either private or public schools depending on which of the two sets of schools that is expected to have the fewest number of applicants. The empirical analysis also confirms the theoretical trade-off between incentives and wastefulness.

We are indebted to an insightful anonymous referee for suggesting this result.

An overall five supplementary rounds took place that year in which 13,398, 15,694, 39,037, 13,130, and 18,014 students were assigned and reassigned, respectively. See TEDMEM Report (2014).

Görmez and Coşkun (2015) conducted interviews with students, parents, and school administrators about their opinion on the admission system. For example, one administrator commented: “The system may become overwhelmed and unable to accommodate the registration process if students who plan to attend private schools are included. This often results in parents spending a considerable amount of time trying to enroll their children. Additionally, placing students who have opted for private schools and those who have not, in the same enrollment pool may create obstacles. Since students who intend to attend private schools are not making a choice from the pool anyway, it raises questions as to why the National Education is attempting to place these students.”

A letter from a parent to the President of the Republic of Türkiye echoes this concern: “The current system forces us to make a decision between public and private schools in the beginning... Hence, many parents are forming a line before private schools fearing that they would not be admitted to any public school.” (Haberturk newspaper, July 2015).

This problem was, for example, discussed in a proposal submitted to the Swedish Parliament in 2015 (Motion 16:2156 2015).

In recent works, Doğan and Yenmez (2018, 2019) analyze developments in the Chicago school system in which there are unified and divided enrollment systems for different types of schools. In the former paper, they particularly focus on the inefficiency of the divided enrollment system. Under substitutable choice rules, they show that students are weakly better off in the unified enrollment than the divided one. In the latter paper, they consider the welfare effects of an additional stage of assignment. By allowing students to be strategic in a two-stage game where the same set of schools are available in both stages, they compare equilibrium outcomes of one-stage and two-stage enrollment systems. Under an acylicity condition, they show that either there exists no pure strategy SPNE of two-stage system or students are weakly better off under truthful equilibrium of one-stage system. On the other hand, some students may benefit from two-stage system when acyclicity is not met.

As for many-to-many matching markets, Echenique and Oviedo (2006), Romero-Medina and Triossi (2014) and Sotomayor (2004), provide similar characterizations.

In real-life, priority classes may be thick (see the extended discussion in Abdulkadiroğlu and Andersson 2023). If so, ties are often broken in order to obtain strict preferences, for example, by assigning each student a distinct number and break ties in accordance to those numbers (see, e.g., Abdulkadiroğlu et al. 2009). This may even by required by law for transparency reasons. In Sweden, for example, private schools rank students strictly according to rules set by the Swedish Schools Inspectorate (by Law Proposition 2009/10:165 2009).

With slight abuse of notation, we denote the priority order of school \(s\in S\) over the subsets of students with \(\succ _s\).

Since \(q_{s_\emptyset }=|I|\), capacity constraint for the null-school never binds.

Notice that, the grand problem itself can also be defined as a subproblem. As a result, matching for the grand problem is defined in the same way.

The serial dictatorship and the DA mechanisms select the same outcome whenever schools have the same priority order over the acceptable students. Since schools may have different priority orders under acyclic priority-capacity structure, such an equivalence does not immediately hold here.\(\square \)

This property is satisfied by most well-known mechanisms in school choice, including, e.g., the deferred acceptance algorithm and the top-trading cycles mechanism.

Note that it is easy to extend the correspondence \(\psi \) to also include the intermediate cases in which some of the assigned students in Round 1 can participate in Round 2 and some of the unassigned students in Round 1 cannot participate in Round 2. All results presented in this paper still hold for these intermediate cases.

Note that this does not have to be a proper subgame.

We would like to emphasize that in the proofs of Propositions 1 and 2 we use examples in which priority orders satisfy our acyclicity condition.

In other words, if she is assigned to some school in Round 2, then only that school will be available in Round 3.

Since any other individually rational, non-wasteful and fair mechanism is not strategy-proof, one can find a problem such that there does not exist a straightforward SPNE in the associated game with rules \(\psi ^{*}\) and \( \gamma ^{*}\), and stable mechanisms other than DA. In fact, this observation can be generalized to any mechanism that is not strategy-proof.

However, it is still possible to use a limited (Pareto inferior) version of DA that preserves strategy-proofness in Round 1. For example, a version of DA where some seats are first removed before applying the mechanism to the remaining problem would work. Our proof for Theorem 1 can be adapted also for this version.

In the proof of Proposition 3, the relationship between acyclicity and Ergin-acyclicity implies that Ergin-acyclicity does not guarantee the existence of a straightforward SPNE when the rules of the game are given by \( (\phi ^{1*},\phi ^{2*},\psi ^*,\gamma ^*)\).

These reforms, that were part of a series of changes in the Turkish high school entrance examination system, mark a significant shift in educational policy. The 2013–2014 reform, known as TEOG (Transition from Basic Education to Secondary Education), introduced two key modifications: the introduction of two centralized exams and the inclusion of GPA in placement scores. This change aimed to align the high school entrance process more closely with the academic curriculum and reduce disparities in student preparation. For a detailed overview of these reforms and their historical context, see Görmez and Coşkun (2015).

Decentralized admissions are analyzed by Chade et al. (2014) and Che and Koh (2016). In Appendix D, it is demonstrated that the decentralized game for private schools has a unique SPNE. It can be shown that this unique equilibrium is identical to the straightforward strategy profile. Furthermore, this strategy profile aligns with the outcome produced by the (constrained) serial dictatorship mechanism under true preferences and true cut-off scores. In this decentralized context, straightforwardness implies the following strategy for students: At each stage, students should apply to all schools they rank above their currently assigned school which did not reject them yet and they should hold the best offer at each stage. Consequently, the concept involves agents choosing their optimal action based on the current set of available actions, without attempting to strategize about potential future rounds.

Most private schools also form their priorities via SFPs. There are only a few private schools (mostly international schools) that use different weights (Görmez and Coşkun 2015).

Although in the old Turkish system, schools have the same ranking over the students, this result is also true under acyclic priority and quota profiles.

Since all schools rank the acceptable students in the same order, there is a unique stable matching.

As in Proposition 4, this result is also true under acyclic priority-capacity structures.

See Andersson (2017) for a detailed description of the Swedish school choice system, and Kessel and Olme (2018) for a more detailed description of the Botkyrka system.

Because the waiting lists are based on a first-come-first-served basis and students in practice only can apply to at most one private school, the fact that the admissions to private schools are decentralized plays no role since the outcome would be identical even if the admissions to private schools would be centralized, i.e., if the private schools instead would simultaneously submit their waiting lists (priorities) to a centralized clearing house.

If we focus on the simultaneous preference revelation game in which students submit a single preference list, any Nash equilibrium outcome is non-wasteful, individually rational, and fair for private schools.

We thank an insightful referee for raising this important question whose suggestion motivated this section.

This follows from the fact that DA respects priorities when it is applied in Steps 1 and 2, and no student applies to an unacceptable school.

Recall that, in Theorem 1 and Proposition 3, we show that an acyclic priority-capacity structure is needed to guarantee existence of straightforward SPNE when the rules of the game are given by \((\phi ^{1*},\phi ^{2*},\psi ^*,\gamma ^*)\).

We prove this result in Proposition 7 in Appendix C.

We use a similar notation as Romero-Medina and Triossi (2014).

Note that the analysis allows for the possibility that \(M_{i}^{h}=s_ \emptyset \) for some \(i\in I\) and for some \(h\in H\). In particular, \( M_{i}^{h}=s_\emptyset \) means that player \(i\in I\) is not active at node h.

Note that one can easily modify these examples by adding schools to these sets.

Note that this strategy does not violate straightforwardness. Straightforwardness requires ranking schools better than first round assignment truthfully, but it does not bring any restrictions on the rankings of worse schools.

One can show that this result holds whenever \((\succ ,q)\) is acyclic by considering the sequential deferred acceptance mechanism in which student i applies last.

One can show that this result holds whenever \((\succ ,q)\) is acyclic by considering the sequential deferred acceptance mechanism in which student i applies last.

One can show that this result holds whenever \((\succ ,q)\) is acyclic by considering the sequential deferred acceptance mechanism in which student i applies last.

One can show that this result holds whenever \((\succ ,q)\) is acyclic by considering the sequential deferred acceptance mechanism in which student i applies last.

Recall that when all schools have the same relative priorities over acceptable students, SD and DA are outcome equivalent.

When there is no restriction on the priorities over acceptable students, Ekmekci and Yenmez (2019) provide a negative result.

In practice, any ties in test scores are broken via date of birth.