| paper | d4-journals-jair-2024-0016 |
| 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: Polynomial-time computable in \(m,\tau,K,L\) with the prescribed exact arithmetic-circuit output. · discrete side: polynomial · adjudication: proved_with_minor_gaps
full proof & adversarial review →
Theorem 3
statement extracted from the paper’s text layer
Given a rational distribution \(\mu\) over complete student types, where each type fixes its own paper type, its \(K\)-paper grading bundle and reports, and the incoming reviewer profiles for its papers, compute the probe estimates, PEQA paper scores, and per-capita bonuses from the leave-one-reviewer-out accuracy calculation. Require the repeated incidence pattern to be realizable by the paper’s \(\texttt{computeG}\) rule; return type-wise and mass-weighted outputs using binary-rational inputs and the paper’s squared-error reward.
A continuum of students with type masses \(\mu_t\), represented by PEQA’s grader-paper incidence graph on exact repeated local records. Reports, verified probe scores, and integral \(K\)-paper bundles are type attributes; the task computes fixed mechanism outputs, with no optimization variable.
The opponent’s strongest point is that grader and paper marginals may lose realized neighborhood correlations, and the case does not establish that its balanced incidence tables arise from PEQA’s specific \(\texttt{computeG}\) rule.
fatal: False
Covers Theorem 3’s \(O(nK)\) computation of probe estimates, assigned scores, and performance bonuses; it leaves the incentive properties in Theorems 1–2, the equilibrium result in Theorem 4, and the experiments untouched.
The strongest anchor is Theorem 3, proved in this paper (Appendix B.4): “The worst-case complexity of computing PEQA is \(O(nK)\).” Here \(n\) is the number of students, each of whom grades \(K\) papers. The computation includes the probe-based bias and reliability estimates, the assigned paper scores, and the graders’ performance scores. This is the paper’s only named result that gives a computational running-time bound; Theorems 1, 2, and 4 establish incentive, uniqueness, and equilibrium properties, not complexity classifications.
A plausible high-multiplicity setting is a large MOOC using repeated, standardized assignments. Millions of students may grade a small catalogue of question types under a fixed rubric, with a bounded number \(K\) of reviews per student. For a particular course run, types would be cohorts sharing the complete PEQA-relevant record: their own paper category, the categories and probe status of the papers they grade, and the scores they report. With quantized scores and balanced, anonymous assignments, the number \(\tau\) of distinct records could be much smaller than \(n\). A paper type records its probe or regrading status and any verified score. This scenario depends on repeated local profiles; an arbitrary reviewer graph need not compress well.
My lead is Type-Compressed PEQA Evaluation. An instance gives a finite support \(\mathcal T\) of grader types with binary-rational masses \(\mu_t>0\), summing to \(1\), and paper types \(\mathcal P\) with masses \(\nu_p>0\), also summing to \(1\). Each grader type has the same \(K\)-slot review bundle for every member, including the reported scores \(z_{tp}\); each paper type has the same incoming reviewer profile. Let \(b_{tp}\) be the number of type-\(t\) papers graded by each member of type \(t\), and \(a_{tp}\) the number of type-\(t\) graders assigned to each paper of type \(p\). The assignment table is PEQA-valid, with \(\mu_t b_{tp}=\nu_p a_{tp}\), \(K\) slots per grader, and the probe and reviewer counts required by the mechanism. Probe papers and regraded papers have verified scores; unresolved papers follow PEQA’s stated convention.
The question is to compute the PEQA assigned score \(\rho_p\) for each paper type and the per-capita performance score \(\pi_t\) for each grader type. For example, the probe estimates are \(\hat b_t=(2/K)\sum_{p\text{ probe}}b_{tp}(z_{tp}-y_p)\) and \(\hat\tau_t=(K/2-1)/\sum_{p\text{ probe}}b_{tp}(z_{tp}-y_p-\hat b_t)^2\), assuming positive sample variance. For a non-probe paper type, the assigned score is \(\rho_p=(\sqrt{\gamma}\mu_0+\sum_t a_{tp}\sqrt{\hat\tau_t}(z_{tp}-\hat b_t))/(\sqrt{\gamma}+\sum_t a_{tp}\sqrt{\hat\tau_t})\); probes receive their verified scores. The bonus is \(\pi_t=\alpha\sum_{p\text{ non-probe}}b_{tp}(W_p-W_{p,-t})\), using the paper’s accuracy function and the leave-one-reviewer-out calculation. A solution is the resulting score and bonus vectors, including each type’s mass-weighted aggregate. Graders’ reports are observed inputs here; the computed scores and bonuses are the mechanism’s outputs.
This is a computation problem, not an optimization problem: Theorem 3 specifies no maximizing decision variable or welfare objective. The continuous question asks for exact evaluation of the same mechanism on a distribution of complete types. Every individual still has an integral bundle of \(K\) papers; the mass of each cohort and its aggregate bonus can be fractional. Clearing denominators maps rational type masses to a finite replicated population, while a discrete instance with repeated local profiles maps to the corresponding type distribution. The match to the authors’ problem is direct: PEQA is their mechanism, and the paper explicitly motivates its use at MOOC scale.
I expect this question to be Class A. The type-level assignment table has \(O(\tau K)\) entries, so the same calculations give \(O(\tau K)\) arithmetic operations. That is an arithmetic-operation claim in the spirit of Theorem 3; a bit-complexity statement would need a specified output precision for the square roots. The result would support the feasibility of type-compressed PEQA, not show that a hard discrete problem becomes tractable.
A natural follow-up is the continuous welfare-design question suggested by Section 6: with type-specific reliability costs \(c_t\), choose a reliability level for each type to maximize expected grading accuracy minus aggregate cost, and ask whether a type-level PEQA bonus implements a welfare-maximizing choice at equilibrium. Theorem 4 motivates that question, but I would not count it as another complexity anchor: it establishes an equilibrium property, not a runtime or hardness classification.
The soft spot is substantial: Theorem 3 already gives a linear-time algorithm for the finite mechanism, so this mirror mainly replaces \(n\) repeated records with \(\tau\) types. Its value depends on a real regime with many repeated complete grading profiles; if assignment patterns or report vectors make \(\tau\) approach \(n\), the compression contributes little. This is a credible, narrow mirror of a named computational result, but not a case where continuization dissolves hardness.
Theorem 3 is a genuine computational anchor, so I cannot dismiss this paper on the ground that it lacks a named complexity result. Theorem 4 does not add another one: its welfare and equilibrium claim motivates a possible new design problem, but does not establish a computational bound.
The difficulty is that PEQA computes scores from a realized assignment graph and realized reports. A grader’s probe estimates depend on that grader’s particular probe reports; a paper’s score depends on its particular reviewers; and each reviewer’s bonus depends on leave-one-out scores for the papers they graded. The paper’s model allows real-valued reports with continuous noise. In a generic large course, grouping agents by their complete PEQA-relevant records—including these local assignment and report patterns—will therefore produce nearly as many types as students. The proposed count tables do not by themselves retain those local correlations. Refining the types to retain them is the correct repair, but can erase the compression.
The strongest version of the mirror would assume a finite score alphabet and a deliberately regular assignment schedule, then represent repeated local neighborhoods by types. That is coherent, and can yield a computation in terms of the number of repeated profiles. But it is a narrow symmetry regime: every grader still has only \(K\) reviews and \(K/2\) probe observations, and each paper still has only a bounded reviewer group. Increasing the population does not make those individual calculations more representative or let the mechanism replace them with aggregate statistics. If the aim is to handle ordinary stochastic grading at MOOC scale, the input must preserve the distribution of local neighborhoods and reports; that is a different, richer object than the proposed type and paper marginals.
There is also a gap between the proposed assignment table and Theorem 3’s input. The theorem computes PEQA using the paper’s specified assignment procedure. Balanced type counts are necessary for a block representation, but do not establish that its incidence pattern is realizable by that procedure. A stronger mirror could encode the procedure’s full repeated local pattern, but that only reinforces the restriction to schedules and reports with substantial exact symmetry.
So the negative case is about scope: the mirror that preserves the theorem’s outputs appears to apply only when the finite computation already has repeated local records, while the mirror broad enough for generic MOOC data has to retain the individualized realized neighborhoods. The paper’s explicit MOOC motivation makes that a meaningful objection, but it does not establish that no worthwhile mirror exists. A regular, quantized high-multiplicity regime remains plausible, and the proponents’ proposed \(O(\tau K)\) evaluation is credible there. My case against this anchor is therefore weak on the universal claim: it narrows the mirror to a special regime rather than defeating every scenario.
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.