Interdistrict school choice: A theory of student assignment

The strongest honest positive case is narrow but real. This paper has no named NP-hardness, membership-in-\(\mathrm{P}\), FPT, or approximation theorem. Its closest computational anchor is Theorem 3, proved in the paper: it reduces a universal SPDA diversity guarantee to min/max linear programs, which the paper observes are minimum-cost flow problems. If the anchor rule requires an explicitly numbered complexity classification, this paper has no qualifying anchor; the following is therefore a formulation-based case.

Theorem 3 says the following in full. Suppose every district admissions rule has school-level type-specific ceilings, is rationed and weakly acceptant, and the profile of admissions rules accommodates unmatched students. Let \(\hat p_d^t\) and \(\hat q_d^t\) be, respectively, the minimum and maximum number of type-\(t\) students that can be assigned to district \(d\) in any legitimate matching. Then SPDA satisfies the \(\alpha\)-diversity policy for every preference profile if and only if, for every type \(t\) and every distinct pair of districts \(d,d'\), \(\hat q_d^t/k_d-\hat p_{d'}^t/k_{d'}\leq\alpha\). The theorem is proved here; the polynomial min-cost-flow machinery used to calculate the bounds is cited from the network-flow literature.

My lead mirror would be Continuous \(\alpha\)-Diversity Verification for Interdistrict SPDA.

An instance contains finite districts \(D\), schools \(C\), demographic types \(R\), and full student types \(\Theta\). A full type \(\theta\) includes home district, demographic type \(r(\theta)\), initial school, preference ranking, and every priority or admissions attribute used by the mechanism. The society is given by rational masses \(\mu_\theta\geq 0\) with \(\sum_{\theta\in\Theta}\mu_\theta=1\). Thus \(\mu_\theta\) is the fraction of students of type \(\theta\), not a fractional school assignment for an individual.

Let \(\kappa_d=\sum_{\theta:h(\theta)=d}\mu_\theta\) be the mass originating in district \(d\), and let \(M_r=\sum_{\theta:r(\theta)=r}\mu_\theta\). Schools have per-capita capacities \(q_c\), and school-level type ceilings \(u_c^r\). Districts use the mass-scaled analogue of the paper’s rationed, weakly acceptant admissions rules with reserves.

A feasible population assignment is a family \(x_{\theta,c}\geq 0\) satisfying \(\sum_c x_{\theta,c}=\mu_\theta\). Each unit of mass is still assigned one integral school; \(x_{\theta,c}\) records only how much of a large homogeneous cohort goes to each school. Write \(y_c^r=\sum_{\theta:r(\theta)=r}x_{\theta,c}\). A legitimate assignment satisfies

\(\sum_{c:d(c)=d}\sum_\theta x_{\theta,c}=\kappa_d\) for every district \(d\), \(\sum_\theta x_{\theta,c}\leq q_c\) for every school \(c\), and \(y_c^r\leq u_c^r\) for every school and demographic type.

Define the implied continuous floor and ceiling by

\(\underline p_d^r=\min\{\sum_{c:d(c)=d}y_c^r:x\text{ is legitimate}\}\)

and

\(\overline q_d^r=\max\{\sum_{c:d(c)=d}y_c^r:x\text{ is legitimate}\}\).

The question is:

Given this instance and \(\alpha\), does every outcome of the bulk, type-level SPDA satisfy

\(\left|\frac{y_d^r}{\kappa_d}-\frac{y_{d'}^r}{\kappa_{d'}}\right|\leq\alpha\)

for every demographic type \(r\) and every pair of districts \(d,d'\)?

The continuous problem has a direct solution: compute the \(2|D||R|\) extrema above by network-flow optimization and answer yes exactly when

\(\frac{\overline q_d^r}{\kappa_d}-\frac{\underline p_{d'}^r}{\kappa_{d'}}\leq\alpha \] for every r\) and every \(d\neq d'\). Thus I would expect this mirror to be Class A, with running time polynomial in the number of schools, districts, types, and the rational input length, assuming the admissions rule is given explicitly through the paper’s finite reserve/priority representation.

The regime is plausible for a large regional transfer programme: tens of thousands of students, but relatively few recurring cohorts sharing home district, demographic category, initial school, priority class, and preference template. The relevant comparison is \(N\gg|\Theta|\), not merely “school choice is large.” If a school uses a fully individualized priority lottery, those lottery ranks must be included in the type, and the advantage may disappear. That is a limitation of the scenario, not of the continuous formulation.

This is recognizably the authors’ problem. Their own central objects are distributions \(\xi_c^t\), school-level type ceilings, implied district floors and ceilings, and SPDA outcomes. The mirror changes the population from integer counts to rational mass and scales capacities and ceilings per capita; it does not fractionalize schools, candidates, or student outcomes. Conversely, any rational continuous instance can be multiplied by a common denominator and realized as a finite high-multiplicity instance, with each unit of mass receiving one school.

The mirror covers Theorem 3 only. I would not claim that it automatically continuizes the paper’s impossibility results for district-level ceilings or all of its TTC incentive results.

The weakest point is that Theorem 3 is fundamentally a structural characterization, not an explicitly numbered theorem saying “this problem is in \(\mathrm{P}\).” The polynomial conclusion comes from the paper’s surrounding min-cost-flow computation. A strict reader may therefore reject it as a ChoCo anchor. Substantively, however, it is a good population mirror: it turns the paper’s integer distributional analysis into an exact high-multiplicity mass problem, with a concrete algorithmic question and a clear tractable answer. Further work would study minimum achievable \(\alpha\), optimal design of school ceilings, finite-\(N\) rounding error, and what happens when the number of full types grows with the population.