| paper | d4-conf-aaai-2018-0269 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
Theorem 1
Given peer-type masses \(\mu_t\), assignment-class masses \(\nu_s\), a feasible grading schedule with \(a_{st}\) reviewers of type \(t\) per assignment of class \(s\), diligent reliabilities \(p_t^1\), costs \(c_{ts}\), rewards \(r_{ts}\), and normalized checking budget \(\kappa\), determine the complexity of maximizing the paper’s average lower-bound accuracy over finite measures \(\rho_s\) on \([0,1]\). Each \(\rho_s\) has total mass \(\nu_s\), and \(x\) units of assignment mass receive checking probability \(x\); type \(t\) works diligently on class \(s\) exactly when \(xr_{ts}\ge c_{ts}\). The objective is \(\sum_s\int_0^1\left[1-(1-x)\exp\left(-\frac12\sum_t a_{st}(2p_t^{e_{ts}(x)}-1)^2\right)\right]d\rho_s(x)\), subject to \(\sum_s\int_0^1 x\,d\rho_s(x)\le\kappa\), where \(e_{ts}(x)=1\) when \(xr_{ts}\ge c_{ts}\) and \(0\) otherwise. In particular, determine exact and \(\epsilon\)-approximation complexity in the number of types and classes, input bit length, and precision.
A high-enrolment peer-grading society with complete reviewer types carrying mass, recurring assignment classes with compatible reviewer-panel compositions, and a mass allocation of checking probabilities. The objective remains the paper’s lower-bound accuracy, with strategic effort determined by the original incentive thresholds.
Whether real large courses have enough recurring reviewer profiles and panel patterns for the proposed regime to be common is not established; the case shows plausibility, not prevalence.
fatal: False
The mirror covers Theorem 1’s hardness result for bilevel OptSC using the paper’s lower-bound accuracy objective. It does not transfer the OptSC-PA relaxation, PASC approximation guarantees, incomplete-information result, or experimental findings.
The strongest mirror is a high-enrolment peer-grading system with a repeated grading schedule: each student authors one assignment and grades others, and students fall into a modest number of complete types. A type records diligent reliability, its cost and reward for each assignment class, and its grading role. Assignment classes record the composition of their reviewer panels. For example, a large online course could have many students but relatively few calibrated reliability-and-cost profiles and recurring rubric and panel patterns. The type counts stay small compared with the student population. Because each student authors one assignment, assignment mass is also student mass.
Call the resulting problem Continuous OptSC. Its instance has peer-type masses \(\mu_t\), assignment-class masses \(\nu_s\), a balanced grading schedule, and a normalized checking budget \(\kappa\). For each class \(s\), \(a_{st}\) is the number of its reviewers of type \(t\); type \(t\) has diligent reliability \(p_t^1\), zero-effort reliability \(1/2\), and cost and reward \(c_{ts},r_{ts}\) on that class. The schedule must be compatible with the peer and assignment masses.
A policy is a distribution \(\rho_s\) over checking probabilities \(x\in[0,1]\) across the continuum mass of assignments in class \(s\), with total mass \(\nu_s\). This lets identical assignments receive different checking rates as a mass allocation. Using the paper’s convention that checking at or above the critical probability elicits diligence, a type-\(t\) reviewer’s effort on class \(s\) is \(e_{ts}(x)=1\) when \(x r_{ts}\ge c_{ts}\), and \(0\) otherwise. The question is to choose the \(\rho_s\) maximizing the paper’s average lower-bound accuracy,
\[ \sum_s\int_0^1\left[1-(1-x)\exp\left(-\frac12\sum_t a_{st}(2p_t^{e_{ts}(x)}-1)^2\right)\right]d\rho_s(x), \]
subject to \(\sum_s\int_0^1 x\,d\rho_s(x)\le\kappa\). A solution is the collection of mass allocations \((\rho_s)_s\), or an equivalent finite list of policy rates and the mass assigned to each.
The lead anchor is Theorem 1, proved in this paper: the paper’s bilevel OptSC problem is NP-hard. That problem chooses assignment checking probabilities under a total budget to maximize the average lower-bound evaluation accuracy, accounting for peers’ strategic effort choices. The proof reduces 0–1 knapsack: it makes one peer and one assignment for each item, sets the peer’s effort cost and diligence reliability using that item’s cost and value, and uses a checking budget of one. It constructs the instance so that a target average accuracy is achievable exactly when the knapsack instance has a qualifying subset. This is a genuine hardness anchor, but its reduction uses item-specific parameters and discrete item choices.
Continuous OptSC asks the same operational question: how to spend a limited audit budget to improve grading accuracy when reviewers respond strategically. It preserves heterogeneous reliability, costs and rewards, and the assignment-to-reviewer structure through the type and panel data. It does not change the target to a fractional grading outcome or an axiomatic question. Its key difference is that the population of otherwise identical assignments can be divided across checking rates.
I expect this mirror to be Class A, tractable for the paper’s accuracy bound. For each assignment class, induced effort changes only at thresholds \(c_{ts}/r_{ts}\). Between consecutive thresholds, the accuracy expression is affine in \(x\); checking expenditure is affine too. Any mass placed at an interior rate can therefore be shifted to the two interval endpoints without changing its average expenditure or accuracy. An optimal policy exists using only \(0\), \(1\), and the threshold rates. Assigning mass to those rates gives a linear program with a number of variables polynomial in the explicit class and type descriptions. Since the exponential coefficients can be approximated from binary-rational reliabilities, this gives a polynomial-time \(\epsilon\)-optimal algorithm; the exact LP claim treats those coefficients as real inputs.
The scenario is plausible because the paper itself targets MOOCs and other large peer-grading systems, and it already models calibrated reliability and heterogeneous costs. Repeated course offerings or a very large course with standardized rubrics can have many students but comparatively few relevant peer profiles and recurring reviewer-panel patterns. The mirror retains the paper’s central incentive threshold: raising checking probability can change a reviewer’s effort discontinuously, and the instructor still trades audit mass against accuracy. In the knapsack reduction, those threshold changes combine with indivisible assignment choices. In the continuum, the mass of an assignment class can be split across policy rates, which removes that indivisibility.
This case covers Theorem 1 and the complexity of OptSC, not every result in the paper. In particular, it does not claim that the paper’s particular PASC approximation analysis transfers unchanged. A follow-up question is whether the same mass-allocation LP works with exact majority-vote error rather than the exponential upper bound. For bounded reviewer load, exact accuracy can be computed for each fixed effort profile, leaving the checking-rate dependence piecewise affine; with unbounded load, computing those coefficients may itself be costly. Another useful boundary question is how much arbitrary grading-graph structure can be retained before reviewer-panel types proliferate.
The weakest point is that the paper allows a general bipartite grading graph, while this mirror needs a balanced schedule describable by a manageable set of panel and workload types. Arbitrary named peer-assignment links could make nearly every role unique, erasing the cohort structure that makes the scenario compelling. I think the repeated-course regime is credible enough for the authors to recognize the mirror as their OptSC problem, but it is a specific instance regime, not a continuization of all instances covered by the paper.
The best case against is that OptSC’s hardness lives in a particularly individualized part of the model. Theorem 1 encodes knapsack items as assignments with item-specific costs and values. In the paper’s general input, reliability is peer-specific and costs and rewards are peer–assignment-specific; the grading graph can also give peers different workloads and panels. To preserve all of that exactly, a peer type may need to include its whole pattern of edge costs, rewards, and assignments. In such instances, the number of types can grow with the number of peers, so replacing counts by masses does not compress the hard instance.
That objection does not defeat the strongest mirror, though. In a large course with repeated assignment classes and a modest set of stable reviewer profiles, the class and panel data can be specified directly, with a feasible grading schedule. The objective is already a sum of per-assignment accuracy terms, and effort choices are separable across grading tasks. For each class, accuracy is piecewise affine in the checking rate, with breakpoints at the effort thresholds. Splitting class mass among those rates gives an LP. This is a sensible high-multiplicity version of the paper’s optimization question, and the knapsack reduction’s item identities are exactly the kind of multiplicity that such a regime relaxes.
The practical weakness is that the paper stresses heterogeneity, and real courses may have enough idiosyncratic costs, reviewer panels, or assignment roles to make exact types proliferate. But that is a limit on which instances benefit, not a reason the repeated-class regime is incoherent. Treating costs and prices as properties of types is part of high multiplicity; it cannot serve as the objection. Nor does the fact that the resulting LP may be simple make the question unworthy under the programme’s criteria.
So I cannot honestly defeat the lead anchor. Theorem 1 is a named computational result, and the proposed mirror preserves its instructor-versus-reviewer optimization question in a plausible instance regime. The negative case is weak precisely where the assignment demands it be strongest: it can question how often that regime occurs, but it cannot support the claim that no worthwhile continuous 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.