| paper | d4-conf-atal-2016-0330 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
P→P discrete result → its continuous mirror
Answer: Exact computation is polynomial-time in \(m,\tau,L\). Every integral replication scale \(K\) has normalized aggregate TTCR-SS outcome \(x\). · discrete side: polynomial · adjudication: proved
full proof & adversarial review →
Theorem 4
statement extracted from the paper’s text layer
Input schools \(C\), types \(T\) with binary-rational masses \(\mu_t\), strict rankings \(\succ_t\), initial schools \(\omega(t)\), and ordered priority blocks with each type contiguous in the induced individual master list, plus rational quotas \(p_c,q_c\) satisfying initial feasibility. Can the paper’s representative, dummy-student, school-state, and cycle rules be batched to compute the exact allocation matrix \(x_{t,c}\) in time polynomial in \(m,\tau,L\), and does that allocation equal the aggregate TTCR-SS outcome on every integral replication of the instance?
A unit population mass over complete types \(t=(\succ_t,\omega(t),r_t)\), where \(r_t\) is the priority block. The assignment variable \(x_{t,c}\) records the mass of type \(t\) assigned to school \(c\), with row totals \(\mu_t\) and school totals between \(p_c\) and \(q_c\). The allocation is selected by a mass-batched TTCR-SS process using the paper’s school states, representatives, dummy representatives, and trading cycles.
The paper assumes a strict master list of individuals, while the proposed priority blocks and batching may not reproduce its representatives or exact outcomes; the proponent flags this assumption but supplies no equivalence proof.
fatal: False
The mirror covers Theorem 4’s implementation question for TTCR-SS. Continuous analogues of Theorems 1–3 and the simulation results remain outside this anchor.
The strongest case is for a high-multiplicity version of the paper’s school-reallocation problem: a large district redistributing students after a trial period, as the paper itself proposes. Students have current schools they can fall back on, schools must meet hard lower quotas, and seats have upper limits. In a large annual cohort, many students can share the same strict ranking, current school, and priority class. A type is that complete tuple; its mass is the fraction of students with that tuple. With \(n\) students and \(\tau\) such types, the intended regime has \(\tau\) far smaller than \(n\). Each student still receives one school; the mass assigned from type \(t\) to school \(c\) records what fraction of that type receives \(c\).
My lead anchor is Theorem 4, proved in this paper: “The time complexity of TTCR-SS is \(O(|S|\cdot|C|)\).” The authors’ argument is that each round fixes at least one student’s assignment, so there are at most \(|S|\) rounds; each round has at most \(|C|\) representative contracts, and finding cycles takes \(O(|C|)\). This is the paper’s named computational result. It is an algorithmic anchor; the paper offers no named hardness result to prefer.
A concrete mirror is Type-Batched TTCR-SS Mass Allocation. Its input is a finite set \(C\) of schools and a finite support \(T\), where each type \(t\) has binary-rational mass \(\mu_t>0\), a strict ranking \(\succ_t\) over \(C\), an initial school \(\omega(t)\), and a position in a common priority order over types. The quota bounds \(p_c,q_c\) are rational population shares, with
\[
\sum_t\mu_t=1,\qquad
p_c\leq \sum_{\omega(t)=c}\mu_t\leq q_c,\qquad
\sum_c p_c\leq 1\leq\sum_c q_c.
\]
The question is to compute the mass allocation prescribed by the type-batched version of TTCR-SS. A solution is the exact rational matrix \(x_{t,c}\): \(x_{t,c}\) is the mass of type \(t\) assigned to \(c\), each row sums to \(\mu_t\), only schools acceptable relative to \(\omega(t)\) receive mass, and each school’s column sum lies between its quotas.
The batching rule follows the paper’s procedure. Keep track of remaining initial-endowment mass by type and already assigned mass by school. Classify schools using the same minimum, decrementable, maximum, and incrementable states as the paper, now with rational masses. Select the highest-priority remaining type at each school that still has initial-endowment mass; add dummy representatives at incrementable schools when decrementable schools remain. Representatives point to their most-preferred available schools, and dummy representatives point to the highest-priority remaining representative at a decrementable school. For each cycle, move a common mass \(\delta\) of its real types to their pointed-to schools. Choose the largest \(\delta\) that does not exhaust a participating type or cross a school’s quota boundary; then update the representatives and repeat. Cycle transfers may batch many identical students at once, while every unit of mass continues to stand for an individual receiving an integral school.
I expect this problem to be Class A, though that is a conjecture for the mirror, not a result of Theorem 4. The paper already represents TTCR-SS as repeated cycle finding on a small graph. In the batched version, a step exhausts a type or reaches a quota boundary, so there is reason to expect an event-driven algorithm polynomial in \(m,\tau,L\), where \(L\) is the input bit length. Proving termination, bounding the number of events, and accounting for exact rational arithmetic are part of the question. The mechanism has no scalar welfare objective to optimize; the task is to compute its rule-selected allocation.
This is a plausible object for the authors because the application remains their problem: allocate a large cohort subject to the same initial-endowment and hard-quota constraints, using a TTCR-style trading rule. The priority order over types is a natural institutional batching convention for a high-multiplicity population. This mirror covers Theorem 4’s implementation result. The paper’s Theorems 1–3—feasibility, strategy-proofness, and Pareto efficiency—are relevant follow-up properties, but this anchor does not claim their continuous analogues.
The weakest point is the priority convention. The paper assumes a strict master list of named students. If that list gives every student an effective, distinct priority position, including it in the type would make \(\tau\) approach \(n\) and defeat the compression. The proposed regime instead has students grouped into priority blocks, with identical students within a block interchangeable for the aggregate outcome. That is a real modeling choice. The case survives if the authors accept block priority as a plausible high-multiplicity version of their common master list; otherwise the anchor’s runtime theorem does not by itself yield this mirror.
The resulting questions are whether the batching rule is well-defined and polynomial in \(m,\tau,L\); whether its output is the limit or exact aggregate of TTCR-SS on replicated, block-ordered cohorts; and whether feasibility, strategy-proofness, and Pareto efficiency survive the batching. These keep the proposed mirror centered on continuous population mass while testing the properties that make the paper’s mechanism worth studying.
The only serious anchor is Theorem 4: TTCR-SS runs in \(O(|S|\cdot|C|)\). The paper does have a named computational result, so the negative case cannot lead by saying there is nothing to mirror. Its best argument is that the proposed batching has not yet shown it preserves the input that makes this particular runtime theorem meaningful.
TTCR-SS uses a strict master list of individual students. At each school, the highest-ranked remaining initial-endowment student becomes its representative. A complete type must therefore include the student’s position in that list. Since each position is unique, this makes \(\tau=|S|\), eliminating the proposed compression. If position is omitted, masses over rankings and initial schools no longer determine the mechanism’s output: the master list can change the representatives and the cycles. The paper itself reports that changing the list can change how many students are assigned to particular schools (§6.2).
The proposed repair—give each type a priority position and let its whole mass act together—therefore adds a type-priority rule in place of the paper’s strict individual list. Its \(\delta\)-transfers may define a sensible new mechanism, but the paper’s \(O(|S|\cdot|C|)\) proof does not establish its running time or show that its allocation is the aggregate outcome of TTCR-SS. A continuous priority coordinate offers another formulation, but then a school’s highest-priority remaining person may have zero mass and no representative is attained. Defining the resulting limit requires more than replacing student counts with rational masses.
This is a real fidelity problem, but it does not finish the negative case. A high-multiplicity regime with priority tiers—or repeated types contiguous in a strict master list—could plausibly yield an exact batched simulation. The authors might recognize that co-modification as their problem, and an event bound in \(m,\tau,L\) would be a legitimate computational question. If that route works, Theorem 4 has a continuous-population mirror, even if its algorithm turns out to be straightforward.
So the strongest case against is that the proponent’s proposed mirror has not yet established that it computes the paper’s mechanism: individual priority is both essential to TTCR-SS and hostile to compression. But I cannot honestly turn that into the universal claim that no worthwhile mirror exists. A priority-tier model remains plausible, and this paper has a computational anchor. The negative case is therefore weak against the best version of the mirror.
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.