The cost of strategy-proofness in school choice

The numbered propositions are asymptotic probabilistic performance statements, not computational results under the programme's gate. The RM high-multiplicity transport problem is a legitimate, author-recognizable continuous extension, but it is not a computational result stated by this paper. Therefore bit (a) fails.

The objection that survived

The mass-transport model does not preserve the paper's iid market with \(n\) individually distinct schools: finite type sets remove the \(\log n\) and \(\log^2 n\) scales, whereas growing type sets can destroy high multiplicity.

What the mirror covers

It covers only the RM sum-of-ranks assignment objective. It leaves the paper's iid random-market asymptotics, maximum-rank and justified-envy results, DA/TTC/EADA comparisons, strategic-applicant simulations, and Budapest evidence outside the mirror.

Open questions for a prover

The case FOR (proponent)

The strict answer is that this paper has no qualifying computational anchor. Its numbered results are asymptotic performance statements, not claims that a problem is in \(P\), NP-hard, FPT, or given by an explicit computational formulation. In particular, Propositions 1–3 concern expected ranks and justified envy. Their proofs largely invoke external results by Parviainen, Knuth, Pittel, Aldous, and Che–Tercieux. The paper’s remarks that computing RM allocations is “computationally intensive” and that EADA is challenging do not constitute named complexity results.

The strongest positive case, under a relaxed anchor rule, is the RM component of Proposition 1. The proposition states, for iid one-to-one markets with \(n\) students and schools, that

\[ \lim_{n\to\infty}\mathbb{E}[x_{\mathrm{RM}}]\le 2,\qquad \lim_{n\to\infty}\frac{\mathbb{E}[x_{\mathrm{TTC}}]}{\log n}=1,\qquad \lim_{n\to\infty}\frac{\mathbb{E}[x_{\mathrm{DA}}]}{\log n}=1, \]

where \(x\) is average assigned rank. The paper does not prove these three statements from scratch: it attributes them respectively to Parviainen (2004), Knuth (1996), and Pittel (1989). I would use only the first entry, the RM bound, as the relaxed lead anchor.

A precise mirror is Continuous Rank-Minimizing Assignment. An instance consists of finitely many student types \(A\), finitely many school-seat types \(B\), rational student masses \(\mu_a\) with \(\sum_a\mu_a=1\), rational seat-capacity masses \(\nu_b\) with \(\sum_b\nu_b=1\), and, for every \(a\in A\), a complete ranking of the school types, represented by \(r_a(b)\in\{1,\ldots,|B|\}\). A type is a complete preference ranking; two students of one type are interchangeable for the rank objective. School priorities are omitted because RM itself ignores them.

The decision variable is a mass transport \(x_{ab}\ge0\), where \(x_{ab}\) is the mass of type \(a\) assigned to school type \(b\), subject to

\[ \sum_{b\in B}x_{ab}=\mu_a \quad\text{and}\quad \sum_{a\in A}x_{ab}=\nu_b. \]

The problem is to output a feasible \(x\) minimizing

\[ R(x)=\sum_{a\in A}\sum_{b\in B}r_a(b)x_{ab}. \]

This does not give an individual fractional school: every unit of population mass receives one school type. Fractionality occurs only because a positive-mass type may be split across different schools in aggregate.

The natural regime is a large school district with \(N\gg |A|+|B|\): many students share complete preference profiles, while school campuses or seat pools occur in repeated types. Rational masses give the exact high-multiplicity bridge. After clearing denominators, \(x\) is an ordinary finite assignment of repeated student and school types; conversely, every replicated finite market aggregates to such an \(x\).

This mirror is plausibly recognizable to the authors because the paper explicitly defines RM as minimizing total rank and connects it to the minimum-cost assignment problem. It is also computationally clean: the continuous problem is a transportation LP, equivalently a min-cost flow problem, solvable in time polynomial in \(|A|+|B|\) and the input bit length, independently of the population denominator. I would classify it as Class A.

The weakest point is substantial: this does not preserve Proposition 1’s particular iid random-market asymptotics. It mirrors the underlying rank-minimization problem in a high-multiplicity admissions regime, not the claim that the expected rank is bounded by \(2\) when every student ranks \(n\) individually distinct schools. Moreover, discrete RM is already polynomial-time solvable, so there is no discrete hardness whose dissolution the mirror demonstrates. The paper’s Proposition 2 could motivate a second question about minimizing the worst rank among rank-minimizing mass assignments, and Proposition 3 could motivate a priority-sensitive justified-envy problem, but neither is a named computational result and both require additional choices about type-level priorities and tie-breaking.

So the honest positive conclusion is modest: there is a sensible and natural Class A population-continuation of the paper’s RM assignment problem, but the paper fails the programme’s strict computational-anchor requirement.

The case AGAINST (opponent, writing after the proponent)

The strongest negative case is procedural but decisive under ChoCo’s stated gate: this paper contains no computational result to mirror. Propositions 1–3 are asymptotic, average-case statements about the outcomes of RM, TTC, and DA. They do not assert membership in \(P\), hardness, approximation guarantees, or even formulate an input-output computational problem. “Computationally intensive” for finding RM allocations and “challenging open question” for EADA are not complexity results.

The proponent’s proposed mirror therefore changes the object. Their mass-transport problem,

\[ \min_x \sum_{a,b} r_a(b)x_{ab}, \]

is a perfectly sensible high-multiplicity assignment model, but it is not a continuous version of Proposition 1’s random-market claim. That claim depends on \(n\) individually named schools, independently random complete rankings, and the limit \(n\to\infty\). With finitely many school types, the model becomes a transportation problem and the paper’s \(\log n\), \(\log^2 n\), and bounded-rank asymptotics disappear. If the number of distinct schools grows with \(n\), the complete-ranking type space grows correspondingly—typically factorially—and almost no students share a type under the paper’s random model. The high-multiplicity compression then vanishes.

One could formulate a better continuous question: retain finitely many preference and school types, study rank-minimizing mass assignments, and perhaps compare continuum analogues of DA and TTC. But that is a new school-choice model, not a computational theorem or problem from this paper. The authors’ actual contribution is comparative probabilistic analysis of mechanisms, not the computation of an allocation from a compressed population. The transport formulation is already polynomial in the ordinary finite assignment problem, so it does not expose a computational phenomenon latent in the paper’s results.

This does not show that the proposed mass-assignment model is illegitimate. On the contrary, it is recognizable, mathematically clean, and arguably worth studying in ChoCo’s broader programme. Nor can one honestly defeat it by saying that its answer is easy: a well-posed Class A mirror may still matter. The negative conclusion is narrower: it cannot serve as a mirror of this paper’s named results under the programme’s strict computational-anchor requirement.

So the paper should fail the strict gate, but the universal claim that it has no worthwhile continuous mirror in any scenario is too strong. The RM transport model survives as a legitimate relaxed mirror; what fails is its connection to the paper’s actual asymptotic computational content.

The adversarial triple: the proponent anchors on up to three named results; the opponent sees that case and must defeat every anchor; the judge decides which case convinced it. These are the pipeline’s own outputs, generated by tools/triple_run.py — no human edited them. The paper’s own text is not reproduced here beyond the quoted statement above.