Interdistrict school choice: A theory of student assignment (d4-journals-jet-2022-0032)

Given finite districts \(D\), schools \(C\), demographic types \(R\), complete repeated student types \(\Theta\), rational masses \(\mu_\theta\), per-capita capacities \(Q_c\), school-level ceilings \(U_c^r\), and a fully specified mass-valued analogue of the paper's rationed and weakly acceptant admissions rules, decide whether every bulk-SPDA outcome satisfies \(\left|y_d^r/\kappa_d-y_{d'}^r/\kappa_{d'}\right|\leq\alpha\) for every \(r\) and \(d\neq d'\). Here \(x_{\theta,c}\geq0\) is assigned mass, \(\sum_c x_{\theta,c}=\mu_\theta\), \(y_c^r=\sum_{\theta:r(\theta)=r}x_{\theta,c}\), and \(\kappa_d=\sum_{\theta:h(\theta)=d}\mu_\theta\); equivalently, compute \(\underline p_d^r\) and \(\overline q_d^r\) by min/max flow over legitimate mass assignments and test \(\overline q_d^r/\kappa_d-\underline p_{d'}^r/\kappa_{d'}\leq\alpha\) for all \(r,d\neq d'\).

Let \(D,C,R,\Theta\) be finite sets of districts, schools, demographic types, and complete student types. Each school \(c\) has district \(g(c)\); each type \(\theta\) has home district \(h(\theta)\), demographic type \(r(\theta)\), and rational mass \(\mu_\theta\). Capacities \(Q_c\), school-level ceilings \(U_c^r\), and \(\alpha\in[0,1]\) are rational; \(\kappa_d=\sum_{\theta:h(\theta)=d}\mu_\theta>0\).
A legitimate mass assignment has \(x_{\theta,c}\geq0\), \(\sum_c x_{\theta,c}=\mu_\theta\), \(\sum_\theta x_{\theta,c}\leq Q_c\), \(\sum_{\theta:r(\theta)=r}x_{\theta,c}\leq U_c^r\), and \(\sum_{c:g(c)=d,\theta}x_{\theta,c}=\kappa_d\). Write \(y_d^r=\sum_{c:g(c)=d,\theta:r(\theta)=r}x_{\theta,c}\). Assume legitimate assignments exist. Under the stipulated mass model, the bulk-SPDA outcomes relevant to this decision problem are exactly the legitimate assignments.

Is deciding whether every such outcome satisfies \(\left|y_d^r/\kappa_d-y_{d'}^r/\kappa_{d'}\right|\leq\alpha\) for all \(r\in R\) and distinct \(d,d'\in D\) in P or NP-hard?

Discrete: with rationed, weakly acceptant admissions, school-level type ceilings, and accommodation of unmatched students, the analogous diversity condition is characterized by implied floors and ceilings computable by minimum-cost flow in polynomial time. Continuum deferred acceptance has been studied for convergence from finite markets; that result does not address this district-diversity decision problem.

The decision problem is in \(\mathrm{P}\). The stipulated equivalence between relevant bulk-SPDA outcomes and legitimate assignments makes this a universal question over a rational polytope; polynomially many linear programs settle it exactly.

Let \(P\) be the set of legitimate assignments, with one variable \(x_{\theta,c}\) for each \((\theta,c)\in\Theta\times C\), and with precisely the constraints in the question. By assumption, \(P\) is nonempty. Every feasible assignment satisfies \(0\leq x_{\theta,c}\leq\mu_\theta\), because its entries are nonnegative and \(\sum_{c\in C}x_{\theta,c}=\mu_\theta\). Thus \(P\) is bounded. It is also closed, since all its constraints are linear equalities or non-strict inequalities. Consequently, every linear objective attains its maximum on \(P\).

Fix a demographic type \(r\in R\) and an ordered pair of distinct districts \((d,d')\). Define the linear objective

\(L_{r,d,d'}(x)=\kappa_{d'}\sum_{c:g(c)=d}\sum_{\theta:r(\theta)=r}x_{\theta,c}-\kappa_d\sum_{c:g(c)=d'}\sum_{\theta:r(\theta)=r}x_{\theta,c}\),

and compute its maximum \(M_{r,d,d'}=\max_{x\in P}L_{r,d,d'}(x)\) by rational linear programming.

Because \(\kappa_d\) and \(\kappa_{d'}\) are strictly positive, every \(x\in P\) satisfies the equivalence

\(\displaystyle \frac{y_d^r}{\kappa_d}-\frac{y_{d'}^r}{\kappa_{d'}}\leq\alpha\quad\Longleftrightarrow\quad L_{r,d,d'}(x)\leq\alpha\kappa_d\kappa_{d'}.\)

It follows that this directed inequality holds for every legitimate assignment if and only if \(M_{r,d,d'}\leq\alpha\kappa_d\kappa_{d'}\). Indeed, the forward implication follows by taking the maximum. For the reverse implication, every feasible objective value is at most that maximum.

The algorithm therefore returns yes exactly when \(M_{r,d,d'}\leq\alpha\kappa_d\kappa_{d'}\) for every \(r\in R\) and every ordered pair of distinct districts. This is precisely the requested condition: checking both \((d,d')\) and \((d',d)\) checks both signs of the difference, which is equivalent to bounding its absolute value. If any comparison fails, an assignment attaining that maximum is a legitimate assignment violating the requested bound. Under the stipulated mass model, it is also a relevant outcome. If there are no such demographic types or district pairs, the condition holds vacuously.

To verify polynomial running time, use the usual explicit binary encoding of the finite sets, maps, and rational data. Each linear program has \(|\Theta||C|\) variables and at most \(|\Theta||C|+|\Theta|+|C|+|C||R|+|D|\) constraints, including nonnegativity. These quantities are polynomial in the input length. Each \(\kappa_d\) is a sum of input rationals, so its binary encoding length is polynomial in the input length. The objective coefficients and comparison threshold \(\alpha\kappa_d\kappa_{d'}\) likewise have polynomial encoding length.

The polynomial-time theorem for rational linear programming states that a rational linear program can be solved, including computation of its exact optimum when feasible and bounded, in time polynomial in its binary encoding length. Its hypotheses hold here: every program has rational data, is feasible by assumption, and is bounded as proved above. Hence the comparisons can be made exactly; equality with the threshold is accepted, and no numerical tolerance or strict-feasibility assumption is needed.

There are \(|R||D|(|D|-1)\) linear programs. Thus the entire algorithm runs in polynomial time. The discrete minimum-cost-flow characterization and continuum convergence results are unnecessary for this conclusion.

⟨structured verdict parsed — rendered above⟩

The prover’s claim is correct and rigorous: the continuous decision problem is in \(\mathrm{P}\) under the stated explicit binary encoding. No mathematical gaps or false steps were found.

• Reduction to legitimate assignments. The proof uses exactly the equivalence stipulated in the task between relevant bulk-SPDA outcomes and legitimate assignments. It needs no additional claim about deferred acceptance or implementability.

• Feasibility and attainment. The feasible set \(P\) is nonempty by assumption. Nonnegativity and the type-mass equalities imply \(0\leq x_{\theta,c}\leq\mu_\theta\) for each variable, establishing boundedness. The finitely many linear equalities and non-strict inequalities establish closedness. Thus \(P\) is compact, and every linear objective attains its maximum. This reasoning also accommodates a zero-dimensional feasible set.

• Objective and denominator clearing. The defined objective is exactly

\(L_{r,d,d'}(x)=\kappa_{d'}y_d^r-\kappa_d y_{d'}^r\).
Multiplying the directed diversity inequality by the strictly positive quantity \(\kappa_d\kappa_{d'}\) preserves its direction and gives precisely the stated threshold \(\alpha\kappa_d\kappa_{d'}\). Both the coefficients and the threshold are correct.

• Universal quantification. For each fixed demographic type and ordered district pair, the directed inequality holds throughout \(P\) exactly when its maximum is at most the threshold. The proof correctly justifies both implications. If the maximum exceeds the threshold, attainment supplies an actual legitimate assignment violating that directed inequality.

• Absolute values and quantifier order. Checking both ordered pairs checks the upper bounds on a difference and its negative, which is equivalent to the required absolute-value bound. Taking these checks over all demographic types and distinct districts exactly matches the task’s universal quantifiers. Different maximizations may have different maximizers; the argument does not require a common maximizer.

• Representation size. The variable and constraint counts are correct: they account for nonnegativity, type-mass equalities, school capacities, school-demographic ceilings, and district-total equalities. Under explicit encoding, all counts are polynomial in the input length. Sums of the input rationals, and the fixed products used in the objectives and thresholds, have polynomial binary encoding length. No exponential-size formulation is concealed.

• Linear-programming theorem. The stated polynomial-time theorem for exact rational linear programming is valid in the binary bit-complexity model. Its required hypotheses are verified: the data are rational, the feasible set is nonempty, and the objective has a finite optimum. Exact optimum computation and rational comparison therefore justify accepting equality without numerical tolerances.

• Total runtime and edge cases. There are \(|R||D|(|D|-1)\) optimization problems, a polynomial number. The proof explicitly handles empty indexing collections through vacuous truth. Zero masses and the endpoint values of \(\alpha\) introduce no additional issue, because the only denominators are the stipulated strictly positive district masses.

No repair or additional clarification is needed. The discrete and convergence results are correctly identified as unnecessary for this argument.

⟨structured verdict parsed — rendered above⟩