| paper | d4-journals-jair-2023-0041 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Proposition 19
Given a fixed set of schools \(O\), a finite support \(T\) of strict school rankings, rational masses \(\mu_t\) with \(\sum_{t\in T}\mu_t=1\), and rational per-capita seat supplies \(q_o\) with \(\sum_{o\in O}q_o=1\), take cohort sizes \(N\) for which every \(N\mu_t\) and \(Nq_o\) is integral. Represent each school’s \(Nq_o\) seats as ordered copies, ranked consistently within each school by all types, and run Eager Boston with uniform lotteries among applicants for each available seat. Compute the exact limit, in probability as \(N\to\infty\), of \(X_{t,o}^{(N)}/N\), where \(X_{t,o}^{(N)}\) is the number of type-\(t\) students assigned to school \(o\).
The population is a mass distribution \(\mu\) over complete school-ranking types \(T\), and each school \(o\) has per-capita seat supply \(q_o\). The output is the aggregate allocation \(x_{t,o}\), with \(\sum_o x_{t,o}=\mu_t\) and \(\sum_t x_{t,o}=q_o\), generated by the fluid limit of Eager Boston’s sequential seat lotteries. There is no objective to optimize; the task is to compute this limiting allocation.
The proposed output is a deterministic aggregate limit rather than Proposition 19’s labelled lottery outcome, and a convergence result is needed to connect the repeated lotteries to that limit; it also does not compute the finite expected assignment.
fatal: False
The mirror covers Proposition 19’s polynomial-time computation of a realized Eager Boston assignment in a population-scaled school-choice regime. It leaves the finite expected outcome and the paper’s fairness, strategyproofness, characterization, and impossibility results outside the mirror.
The best positive case is narrow: this paper has no named NP-hardness result to anchor a hardness-dissolution question. Its named impossibilities concern combinations of fairness, efficiency and strategyproofness, not computational complexity. The lead anchor is Proposition 19, proved in the paper: given a preference profile \(R\), the deterministic assignment \(\mathrm{EBM}(R)\) can be computed in polynomial time in the number of agents, provided the lottery winner generator \(G\) runs in polynomial time. That is a result about computing one realized Eager Boston assignment, not its expected assignment. [The published paper, Proposition 19](https://par.nsf.gov/servlets/purl/10466783)
A plausible mirror is Fluid Eager Boston Evaluation. The instance consists of a fixed set \(O\) of schools, a finite support \(\mathcal T\) of strict school rankings, rational type masses \(\mu_t\) summing to \(1\), and rational per-capita seat supplies \(q_o\) summing to \(1\). Take a large cohort of students whose school rankings fall into those types, with \(N\mu_t\) students of type \(t\) and \(Nq_o\) seats at school \(o\). Represent each school’s seats as individual items, ordered by the same fixed tie-break for everyone; then each type specifies a complete strict ranking over the seats. The regime is many students but relatively few ranking types, with school capacity growing with the cohort.
The question is: compute the limiting aggregate assignment as \(N\) grows. A solution is a matrix \(x_{t,o}\), where \(x_{t,o}\) is the mass of type \(t\) assigned a seat at school \(o\), and \(\sum_o x_{t,o}=\mu_t\), \(\sum_t x_{t,o}=q_o\). These fractional entries describe fractions of a type’s population; each individual still receives one indivisible seat. There is no welfare objective to optimize: the required output is the aggregate assignment generated by the EBM process.
One precise way to define that output is as EBM’s fluid limit. Let \(z_t\) be the unassigned mass of type \(t\), \(b_o\) the remaining supply at school \(o\), and \(A_o\) the active mass currently applying to \(o\). In normalized rounds, each school with applicants and remaining seats awards seats at unit rate; its selected mass is split among applicant types in proportion to their current masses. Thus, while \(t\) applies to \(o\), \(\dot{x}_{t,o}=z_t/A_o\) and \(\dot{z}_t=-z_t/A_o\), while \(\dot{b}_o=-1\). When a school’s supply runs out, it leaves the remaining rankings and affected types apply to their next available school. When its applicant pool runs out first, those applicants are assigned and the school can serve later applicants. The normalized clock describes the limit of repeated seat-level lotteries; the continuous object is the population.
I expect this problem to be tractable. An event-driven algorithm can advance to the next school-supply or applicant-pool exhaustion, update the type masses and continue. Each event exhausts a school or assigns the remaining mass of at least one type, so there are at most \(O(|O|+|\mathcal T|)\) such events. With rational input, the updates are rational arithmetic. The formal discrete-to-continuous convergence and its running-time details are further results to prove, not claims already established by Proposition 19.
The mirror is credible because the paper itself motivates assignment with school choice, where seats are naturally repeated copies of a school option and capacity scales with the student cohort. Authors could recognize this as their assignment process in a high-multiplicity regime: types are shared rankings, mass is the proportion of students of each ranking, and the computed object is the aggregate EBM allocation.
The weak point is that Proposition 19 computes a random realized assignment in polynomial time, whereas this mirror computes a deterministic fluid aggregate. The paper explicitly gives no polynomial-time guarantee for computing EBM’s expected outcome and conjectures that task is \(\#\mathrm{P}\)-complete. The mirror therefore needs a limit theorem showing that seat-level lottery fluctuations vanish at the aggregate scale; it does not answer the finite-instance expectation problem. It also leaves open whether the paper’s fairness and strategyproofness properties have meaningful population versions—individual manipulation by a zero-mass agent may be vacuous.
Proposition 19 is the only serious computational anchor, but its output is a *labelled* assignment: it tells us which named agent receives each named item in one lottery realization. The proposed table \(x_{t,o}\) forgets those identities and instead gives the limiting mass assigned to each school. That is a sensible question, but it is not the continuous version of Proposition 19’s computation. Nor does it compute the expected finite assignment: the paper explicitly separates that problem and conjectures it is \(\#\mathrm{P}\)-complete. A fluid limit would wash out the individual lottery outcomes rather than resolve their expected distribution.
The strongest version of the mirror is still worth examining: fixed schools, per-capita capacities, and a fixed support of ranking types, with the target being the exact aggregate output of the limiting EBM process. But that model appears to have a direct event simulation. While the active applicant groups stay fixed, each school’s remaining capacity and applicant mass fall at unit rate; advance to the first exhaustion, update the affected groups, and repeat. There are at most \(O(m+\tau)\) such events, with rational updates. This is a clean mean-field description, but it offers no evident complexity landscape or optimization problem for ChoCo’s continuous-optimization tools to expose. The finite expectation problem that might have supplied a harder target requires retaining the discrete lotteries the limit removes.
So the negative case is that this would make a neat asymptotic analysis of EBM, not a compelling computational mirror of the paper’s result. I would not call that case decisive: the fluid aggregate is well-posed, the school-capacity regime is plausible, and a formal convergence theorem could be useful. The honest weakness is that I cannot show such a result would be unworthy of the programme; I can only argue that Proposition 19 gives it a thinner computational motivation than the proponent’s framing suggests.
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.