| paper | d4-conf-atal-2018-0108 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Theorem 5.7
statement extracted from the paper’s text layer
Given schools \(C\), a finite supported distribution \(\mu\) over types \(t=(\omega_t,\succ_t)\), and a rational per-capita quota polytope \(P\), suppose \(F_N=\{v\in\mathbb{Z}_{\ge 0}^{|C|}:\sum_{c\in C}v_c=N,\ v/N\in P\}\) is M-convex and the replicated endowment load is feasible for each admissible \(N\). Replicate each type \(t\) into \(N\mu_t\) students, draw a uniform common priority order, and run TTC-M. For \(a_N(t,c)\), the expected number of type-\(t\) students assigned to \(c\), divided by \(N\), determine whether \(a_N\) converges along admissible replication sizes and, if it does, compute its limiting matrix within additive error \(\epsilon\) in time polynomial in \(m,\tau,L,\log(1/\epsilon)\).
Types are complete student descriptions \((\omega_t,\succ_t)\) with mass \(\mu_t\); the district’s scaled quotas are encoded by \(P\) and the M-convex families \(F_N\). The decision output is the limiting expected assignment matrix \(x_{t,c}=\lim_N a_N(t,c)\), where \(\sum_c x_{t,c}=\mu_t\) and assignments below a type’s endowment have zero mass. There is no optimization objective: the task is to compute the aggregate TTC-M outcome under the common-priority lottery.
Theorem 5.7 analyzes one explicitly listed run and gives no support-sensitive compression bound; the mirror adds convergence and integration over random priority orders.
fatal: False
The mirror builds on Theorem 5.7’s algorithmic TTC-M result. It leaves the feasibility, strategy-proofness, and Pareto-efficiency theorems, as well as Theorem 3.2’s incompatibility result, unmirrored.
My strongest honest case is narrow: Lead mirror — Limit TTC-M evaluation. The paper has one clean complexity anchor. Theorem 5.7, proved here, says TTC-M runs in \(O(|S|\cdot|C|)\) time, assuming it takes \(O(1)\) time to test whether a school-load vector \(\nu\) belongs to the M-convex feasible set \(F\). The paper has no named NP-hardness or other hardness result. Its other main theorems establish feasibility, strategy-proofness, and Pareto efficiency, or show an incompatibility; they are not complexity classifications.
A plausible high-multiplicity setting is a large school district where students choose from a bounded menu of preference rankings and their initial school is determined by a catchment area. A type is the pair \((\omega_t,\succ_t)\): the student’s initial school and complete ranking. Its mass \(\mu_t\) is the fraction of students with that type. With many thousands of students and a fixed menu of rankings and catchments, the population size \(N\) can be much larger than the support size \(\tau\). The paper itself allows a lottery to choose the common priority order, so I would treat that order as fresh mechanism randomization, not as an individual attribute that destroys type aggregation.
Here is the continuous problem. The input is a school set \(C\), a finite supported type distribution \(\mu\) with rational masses, and a rational per-capita feasible-load polytope \(P\). \(P\) encodes the district’s scaled quotas; require that for every allowed replication size \(N\), \(F_N=\{v\in\mathbb Z_{\ge0}^{|C|}: \sum_c v_c=N,\ v/N\in P\}\) is M-convex and the replicated initial-endowment load is feasible. Replicate each type \(t\) into \(N\mu_t\) students, draw a uniform common priority order, and run TTC-M. Let \(a_N(t,c)\) be \(1/N\) times the expected number of type-\(t\) students assigned to \(c\), where the expectation is over the priority lottery.
Limit TTC-M evaluation asks: along replication sizes for which all type counts are integral, does \(a_N\) converge, and, when it does, compute a matrix \(x_{t,c}\) within additive error \(\epsilon\) of its limit. The matrix records the mass of type \(t\) assigned to school \(c\), so \(\sum_c x_{t,c}=\mu_t\); individual rationality requires \(x_{t,c}=0\) when \(c\) is below that type’s endowment. Each finite run remains feasible, individually rational, and Pareto efficient, and truthful reporting remains optimal under each priority order. The output is the aggregate outcome of the mechanism, not an optimized welfare score. A compressed algorithm should run in time polynomial in \(m,\tau,L,\log(1/\epsilon)\), where \(L\) describes the rational input.
I would provisionally expect this mirror to be Class A: the finite-support population suggests a finite-dimensional flow or event description that could approximate the limiting outcome without processing every student. That is a research conjecture, not a consequence of Theorem 5.7. The result establishes \(O(Nm)\) time on an explicitly listed market; it does not establish support-sensitive running time. The first questions are whether the limit always exists, whether its value is computable from \((\mu,P)\), and whether the lottery over priority orders can be integrated efficiently. If those order interactions remain hard after aggregation, the mirror could instead be continuum-specifically hard.
This case covers Theorem 5.7’s computational question and uses the paper’s mechanism as the object being evaluated. It does not claim a continuous proof of the paper’s full axiomatic results. Its weakest point is also clear: TTC-M works through cycles among individual students, and the common serial order can affect those cycles. Taking expected assignments under random priorities is a plausible population analogue—the paper explicitly permits lottery-based priorities—but convergence and compact computation are new questions, not results supplied by the paper.
The strongest objection is to the bridge from Theorem 5.7 to the proposed mirror. The theorem bounds the time to produce one matching, given an explicit strict priority order and an \(O(1)\) feasibility test. That order affects which students schools choose. If it is fixed, grouping students only by endowment and preference loses information the algorithm uses; including priority position in each type can make the support as large as the population. The faithful deterministic version therefore offers no evident high-multiplicity compression.
The proposed repair—take a uniform lottery over priority orders and compute the limiting expected type-by-school assignment—is sensible, especially because the paper itself mentions lottery priorities. But it changes the computational question. Theorem 5.7 analyzes one run; the mirror asks for a limit of randomized outcomes and an efficient way to integrate over priority orders. A direct continuum version has a related problem: each school’s highest-priority eligible student has zero mass, so finite TTC cycles remove zero mass. To get a nontrivial process, one would need a time-scaled limit of the sequential removals. That looks like a new stochastic limit problem, not a continuous runtime analysis of the theorem.
This does not defeat the stronger mirror outright. A large district with a bounded set of endowment-and-preference types is plausible, and expected assignments under the paper’s own priority lottery are a meaningful aggregate. Computing them from type masses could be a worthwhile algorithmic question. The negative case is therefore weak: it can argue that the proposed mirror is a new problem whose connection to Theorem 5.7 is indirect, but it cannot honestly rule out that the authors would recognize it as their problem.
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.