| paper | Controlled School Choice with Soft Bounds and Overlapping Types |
| authors | Ryoji Kurata, Masahiro Goto, Atsushi Iwasaki, M. Yokoo |
| venue | AAAI 2015 |
| filed under | coalition · matching |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
P→P discrete result → its continuous mirror
Answer: polynomial-time solvable · discrete side: polynomial · adjudication: proved
full proof & adversarial review →
Theorem 3
statement extracted from the paper’s text layer
Given finite schools \(C\), overlapping labels \(T\), complete applicant types \(\Theta\) containing membership sets, strict preferences, and priority blocks at every school, rational masses \(\mu_\theta\), and per-capita bounds \(\bar q_c\) and \(\bar p_{c,t}\), compute the mass assignment \(x_{\theta,c,t}\) produced by DA-OT: schools first accept highest-priority proposal mass up to each \(\bar p_{c,t}\), then fill capacity up to \(\bar q_c\), splitting mass when a quota cuts through a type block. Determine whether this stable, student-optimal assignment is computable in time polynomial in the compressed input size and rational bit length.
A high-multiplicity controlled-school-choice model with finite complete types \(\Theta\), population mass \(\mu\), assignment variables \(x_{\theta,c,t}\), block priorities, and the DA-OT reserved-seat choice rule; the objective is the stable assignment that is student-optimal under each type's preferences.
The paper's strict priority order is over named contracts, so the mass construction needs an explicit block-priority and quota-boundary convention plus a new compressed bit-complexity proof; Theorem 3 itself supplies none of these.
fatal: False
The mirror covers DA-OT's basic computational and stable-outcome guarantees, but not the exact atom-level strategy-proofness claim, the extended DA-OT* model, or the simulation comparisons.
The strongest honest positive case is a narrow Class A mirror. The paper has no named NP-hardness result, so this cannot be a hardness-dissolution case. Its defensible computational anchor is the polynomial-time algorithmic result Theorem 3, with Theorem 1 supplying the semantic correctness of the algorithm.
The natural high-multiplicity regime is a large school-choice clearinghouse with many applicants but relatively few complete applicant profiles. A type \(\theta\) must include everything relevant to the problem: its overlapping status set \(A_\theta\subseteq T\), its complete strict preference order over school-seat contracts, and its priority position at every school. For example, \(\theta\) could encode a preference template, socioeconomic and language categories, sibling status, catchment band, and a finite priority band. A district may have millions of students but only hundreds or thousands of such repeated profiles. This is not true of every school market; if every student has an idiosyncratic preference order or random priority position, the number of types approaches the number of students and the mirror loses its point.
The population is a rational distribution \(\mu\) over \(\Theta\), with \(\sum_{\theta\in\Theta}\mu_\theta=1\). Capacities and soft bounds are normalized per capita: \(\bar q_c\) is the capacity of school \(c\), and \(\bar p_{c,t}\) is its type-\(t\) soft target. This scaling is part of the population mirror, not an illicit continuization of the outcome. Each unit of mass still receives one integral contract \((c,t)\); only the aggregate assignment is fractional.
My lead problem is Continuous DA-OT Computation, denoted \(\mathrm{DA\text{-}OT}_\infty\).
An instance consists of finite sets of schools \(C\), status labels \(T\), and complete student types \(\Theta\); rational masses \(\mu_\theta\); overlapping memberships \(A_\theta\); a strict preference order \(\succ_\theta\) over
\[ K_\theta=\{(c,t):c\in C,\ t\in A_\theta\}; \]
a strict priority order at each school over the relevant \((\theta,t)\) contracts; rational capacities \(\bar q_c\); and rational soft lower bounds \(\bar p_{c,t}\), with \(\sum_c\bar q_c\ge1\).
The decision variable is a mass assignment \(x_{\theta,c,t}\ge0\), satisfying
\[ \sum_{c,t\in A_\theta}x_{\theta,c,t}=\mu_\theta \]
for every \(\theta\), and
\[ \sum_{\theta:t\in A_\theta}x_{\theta,c,t}\le \bar q_c \]
for every school \(c\). The quantity assigned to a type-\(t\) reserved seat is \(\sum_\theta x_{\theta,c,t}\); overlapping membership does not count a student twice, because each unit of mass receives only one seat contract.
The continuous DA-OT choice rule is the exact mass analogue of Definition 5. Given proposal masses at school \(c\), the school first accepts, for every \(t\), the highest-priority proposed mass up to \(\bar p_{c,t}\). It then fills the remaining capacity up to \(\bar q_c\) with the highest-priority remaining proposals. Rejected mass moves to its next preferred contract. If a type is cut at a quota boundary, its mass is split there; no individual receives a fractional seat.
The requested solution is the final mass assignment produced by this rejection process. Equivalently, it is a feasible assignment with no positive-mass Hatfield–Milgrom blocking move: no positive amount of a type can move to a more-preferred contract and be accepted by the relevant school’s mass choice rule after that move. To retain the paper’s “student-optimal” language, compare assignments by first-order stochastic dominance in each type’s preference order: for every \(\theta\) and every preference prefix \(P\),
\[ \sum_{(c,t)\in P}x_{\theta,c,t} \]
should be at least as large as under any other stable mass assignment.
This mirrors Theorem 3, proved in the paper: DA-OT has time complexity \(O(|X|^3)\), where \(X\) is the set of contracts. The proof uses the fact that the rejected-contract set grows monotonically, so the proposal step is repeated at most \(|X|\) times, while each choice computation takes \(O(|X'|^2)\). The paper also notes that, under its assumptions, \(|X|\) is at most linear in the type-space size.
The continuous analogue should therefore ask whether the same rejection argument can be carried out over
\[ \widehat X=\{(\theta,c,t):\theta\in\Theta,\ c\in C,\ t\in A_\theta\}, \]
with running time polynomial in \(|\Theta|\), \(|C|\), \(|T|\), and the rational input length \(L\), rather than in the expanded population size. I expect this problem to be tractable, hence Class A. Each type-contract edge can be permanently rejected at most once, and quota-boundary operations are rational additions, comparisons, and subtractions. The missing theorem is an exact bit-complexity and termination proof for this compressed mass implementation; Theorem 3 itself does not supply that proof.
The semantic companion is Theorem 1, proved in the paper using Lemmas 1 and 2 together with the general matching-with-contracts theorem of Hatfield and Milgrom. It states that a stable matching always exists, DA-OT is strategy-proof, and DA-OT returns a stable matching that is student-optimal among all stable matchings. In the continuous problem, the existence and student-optimality portions have a direct mass interpretation. Strategy-proofness needs more care: a single atomless student has zero mass, so an individual deviation cannot change the aggregate outcome. A meaningful extension would ask whether a positive-mass cohort can profitably misreport, but that is a new coalition notion rather than a literal transfer of individual strategy-proofness.
The high-multiplicity bridge is exact for rational instances. Clearing denominators turns \(\mu_\theta\) into \(N\mu_\theta\) cloned students and turns \(\bar q_c,\bar p_{c,t}\) into integer capacities and targets. Conversely, any large finite market whose students fall into these complete profiles compresses to the mass instance. Ties among clones in a finite priority list can be broken arbitrarily without changing the aggregate assignment. Thus the model is recognizably the paper’s overlapping-type school-choice problem, not merely a fractional assignment problem.
The paper’s extended model suggests a further question, but I would not use it as a second anchor. One could add per-capita soft ceilings \(\bar u_{c,t}\), introduce first-, second-, and third-class seat contracts, and define \(\mathrm{DA\text{-}OT}^{\star}_\infty\) by the mass version of Definition 10. The expected result is again polynomial-time computability and a stable, student-optimal mass assignment. But the strategy-proofness issue becomes even more visibly vacuous in an atomless population, so the basic DA-OT mirror is cleaner.
The weakest point is that the paper’s explicit runtime theorem is already polynomial in the named-contract representation, and it does not itself prove a compressed algorithm polynomial in \(|\Theta|\). The positive case therefore rests on a plausible new high-multiplicity theorem, not on a result already contained in the paper. Moreover, the paper has no hardness anchor, so this mirror cannot answer where continuization stops helping. Its value is narrower: it turns a large repeated-profile school-choice market into a genuine population-mass computation while preserving overlapping types, reserved seats, priorities, soft bounds, and the DA rejection structure.
The best negative case is that the paper’s computational content is tied to named students and a strict priority order, not to population mass. In the paper, \(\tau(s)\) records only overlapping status labels. Students with the same labels may have different preference orders, and every school ranks named contracts strictly. Aggregating by those labels therefore destroys exactly the information that drives DA-OT.
The proponent repairs this by making a type include a complete preference profile and “priority band.” But a band is not a complete type under the paper’s model: strict tie-breaking positions are still individual data. If those positions are included, repeated types largely disappear. If they are suppressed, one has changed the model to block priorities or weak priorities. That is a legitimate research direction, but not a direct high-multiplicity version of the paper: one must newly specify how mass is selected at a priority boundary, how ties enter justified envy, and what stability means. Different tie resolutions can produce different aggregate assignments.
This problem affects Theorem 3 most directly. Its \(O(|X|^3)\) bound is a bound for deferred acceptance over an explicit finite contract set. A mass implementation with block priorities would be a batch-processing representation of that same procedure. It might be useful engineering, but the paper supplies no population-level optimization problem, separation problem, or nontrivial complexity barrier for it. The proposed mirror therefore risks reducing to “run DA on each distinct profile and split the last block,” rather than exposing a new continuous-computational phenomenon.
Theorem 1 is an even weaker anchor. Individual strategy-proofness becomes vacuous for atomless mass: one student’s report has measure zero and cannot affect the outcome. Replacing it with positive-mass coalition strategy-proofness is not the theorem in the paper and has no canonical definition. Existence and student-optimality can plausibly be obtained for rational masses by cloning and taking an aggregate of the finite DA outcome, but that is a transfer argument, not a meaningful continuous incentive result.
Still, this does not establish the requested universal negative. A sensible district could genuinely have large cohorts with identical preferences, overlapping attributes, and school priorities that are constant on profile blocks. Under that restricted regime, the mass DA-OT problem is well-defined, and the compressed algorithm is a legitimate high-multiplicity result. Thus the strongest honest conclusion is that the proposed mirror is narrower and less theoretically rich than claimed—not that no worthwhile mirror exists.
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.