| paper | Aggregating Partial Rankings with Applications to Peer Grading in Massive Online Open Courses |
| authors | I. Caragiannis, George A. Krimpas, A. Voudouris |
| venue | ATAL 2015 |
| filed under | voting · theory |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
other→other discrete result → its continuous mirror
Answer: Both guarantees hold. One may take \(C=C_6=4\sqrt{3\pi}\). · discrete side: other · adjudication: proved
full proof & adversarial review →
Theorem 2
statement extracted from the paper’s text layer
Given a finite type set \(T\), rational masses \(\mu\), a finitely represented measure-preserving \(k\)-regular bundle graphing \(K\) retaining the relevant overlap structure, and a hidden strict type order ≽★, place types exchangeably on \(K\), form type-averaged Borda scores from integral \(k\)-item local rankings, and decide whether ℼ[\uoperatorname{Acc}μ] ≥ \(1-ε\), where \(\uoperatorname{Acc}μ is weighted agreement on distinct type pairs.
A high-multiplicity peer-grading model in which μ gives masses of exchangeable assignment and grader profiles, \(K\) supplies integral \(k\)-regular bundle incidence and overlap data, Borda produces type-level scores, and the objective is expected weighted recovery between distinct types.
The proponent's ρ records bundle compositions but not the common-neighbourhood quantities λ, θ, or girth on which Theorem 2 depends, so the proposed mass kernel alone cannot support the theorem's claimed guarantee.
fatal: False
The mirror covers the perfect-grading Borda guarantee in Theorem 2. It leaves aside the order-revealing construction, RSD and MC4, noisy experiments, conjectures, and the proposed future analyses.
The strongest honest case is a narrow Class A mirror of the paper’s main result, Theorem 2. The paper contains no named NP-hardness, polynomial-time, FPT, or parameterized-complexity theorem, so this cannot honestly be presented as a hardness-dissolution result. Theorem 2 is instead an algorithmic recovery guarantee, proved in this paper.
The natural regime is a very large MOOC, or many repeated runs of the same course, with \(N\) students and submissions, \(N\gg \tau\), and only \(\tau\) materially distinct types. A type records everything relevant to this problem: rubric-level assignment quality, grading ability, course track, and any assignment constraints. Thus agents of the same type are interchangeable. The population is represented by masses \(\mu_t\), where \(\mu_t\) is the fraction of students and submissions of type \(t\), with \(\sum_t\mu_t=1\). The bundle size \(k\) remains small and individual: every student still receives an integral bundle of exactly \(k\) submissions.
The continuous bundle system is a mass-level version of the paper’s \(k\)-regular bundle graph. Let \(\rho_{g,b}\) be the mass of graders of type \(g\) who receive a bundle with type composition \(b\), where \(b\) contains \(k\) submission slots. The regularity constraints are \(\sum_b\rho_{g,b}=\mu_g\) and \(\sum_{g,b}\rho_{g,b}N_t(b)=k\mu_t\), where \(N_t(b)\) is the number of type-\(t\) submissions in \(b\). Thus every unit of submission mass is graded \(k\) times. The variables \(\rho_{g,b}\) are fractional only at the aggregate level; a rational solution can be expanded into a sufficiently large finite population in which every individual receives an integral bundle.
Here is the lead problem.
Continuous Borda Peer-Grading Recovery. An instance consists of \(T\), rational masses \(\mu\), a \(k\)-regular bundle kernel \(\rho\), and the type-level partial rankings observed on the bundles. The rankings are promised to be consistent with some hidden strict ground-truth order \(\succ^\star\) on the assignment types. For a bundle whose \(j\)-th position contains type \(t\), award \(k-j+1\) points. The per-unit Borda score of type \(t\) is \(B_t=\frac{1}{\mu_t}\sum_{g,b}\rho_{g,b}\sum_{j:\,b_j=t}(k-j+1)\). The required solution is the complete order \(\widehat{\succ}\) obtained by sorting the \(B_t\)'s, with a specified tie rule.
The objective is weighted pairwise recovery,
\(\operatorname{Acc}_\mu(\widehat{\succ},\succ^\star)=\frac{1}{1-\sum_t\mu_t^2}\sum_{t\ne u}\mu_t\mu_u\,\one{\widehat{\succ}\text{ agrees with }\succ^\star\text{ on }t,u}.\)
The associated decision question is whether the expected accuracy, over the random mass-preserving assignment of submission units to bundle slots, is at least \(1-\varepsilon\). A design version may make \(\rho\) the decision variable and ask for a feasible \(k\)-regular bundle kernel maximizing this expected accuracy. The recovery version is the closest mirror of the theorem; the design version directly mirrors the paper’s motivating question of how assignments should be distributed.
The paper’s anchor is:
Theorem 2, proved here. Under the preceding assumptions \(k\ge3\) and \(n\ge3k(k-1)+2\), when Borda is applied to partial rankings consistent with the ground truth, the expected fraction of correctly recovered pairwise relations is at least \(1-\bigO(1/k)\) when the \(k\)-regular bundle graph has girth at least \(6\), and at least \(1-\bigO(1/\sqrt{k})\) for an arbitrary \(k\)-regular bipartite bundle graph. The expectation is with respect to the random assignment of elements to graph nodes used in the paper’s analysis. The proof is the paper’s martingale and Azuma–Hoeffding argument, not an external citation.
The continuous question is recognisably the same problem. It retains the two-sided population of students and submissions, local partial rankings of \(k\) submissions, \(k\)-regular exposure, Borda aggregation, a hidden ground-truth ranking, and weighted pairwise accuracy. It does not replace the population by a probability model while leaving the original problem intact: the population itself is the mass distribution \(\mu\), and the regular bundle graph becomes the mass-preserving kernel \(\rho\).
I would expect the supplied-kernel recovery problem to be Class A. Given explicit finite support, all Borda scores are computable by summation and the output order by sorting. The substantive theorem to establish is the continuous analogue of Theorem 2: for kernels arising as limits of \(k\)-regular girth-\(6\) graphs, expected recovery should remain \(1-\bigO(1/k)\), while unrestricted kernels should retain the weaker \(1-\bigO(1/\sqrt{k})\) guarantee. This is not automatic—the finite proof uses dependencies in a random permutation, and an atomless limit may require a new exchangeability or concentration argument—but it is a precise, nontrivial continuation of the paper’s result.
The bridge to the finite problem is especially clean. If \(\mu\) and \(\rho\) are rational, choose a common denominator \(N\), replicate each type \(N\mu_t\) times, and realize \(N\rho_{g,b}\) as integer bundle assignments. The normalized finite Borda scores converge exactly to the mass-level scores above. Conversely, a finite peer-grading instance with repeated type profiles produces such a rational \((\mu,\rho)\). This is genuine high multiplicity, not fractional grading: each realized student still ranks an integral bundle, while only the aggregate number of students assigned to each bundle pattern is fractional.
The paper is not already continuous. Its \(n\) is the number of individually labelled assignments and bundles, and its random permutation is a random finite placement, not a distribution over high-multiplicity voter or assignment types. The large-\(n\), fixed-\(k\) asymptotics make the proposed regime particularly natural, but they do not themselves supply a continuous-population formulation.
The weakest point is that the paper insists on a strict ranking of individually distinct assignments, whereas a genuine high-multiplicity model has repeated types and therefore ties or exchangeable individuals. The proposed mirror handles this by evaluating cross-type pairwise accuracy and treating within-type comparisons as random tie-breaks. If the authors regard ranking every individual submission as essential, they may reject the type-level target as too coarse. The best response is that the type includes the complete information used by the model: when repeated submissions are genuinely indistinguishable to the grading process, demanding an individual ranking among them is artificial. Nevertheless, this limitation should be conceded.
Further questions include whether the \(1-\bigO(1/k)\) bound survives for atomless bundle kernels, whether noisy type-dependent Mallows grading admits an analogous guarantee, how to optimize \(\rho\) under locality or no-self-grading constraints, and whether bundle-design optimization becomes continuum-specifically hard.
The proponent’s only anchor, Theorem 2, does not meet the programme’s computational-anchor requirement. It is a probabilistic accuracy guarantee for a fixed Borda aggregation rule and a fixed \(k\)-regular bundle graph. The paper proves no complexity classification, exact or approximation algorithm, parameterized result, or computational decision theorem. Given the graph and profile, Borda aggregation is simply score accumulation followed by sorting. The proposed threshold problem and the design problem over \(\rho\) are new problems invented by the mirror, not continuizations of a computational result in the paper.
More fundamentally, this paper does not have a genuine high-multiplicity population hidden inside it. Its \(n\) elements are simultaneously distinct assignments, distinct alternatives, and students who receive bundles. The ground truth is a strict permutation of those individual assignments. A complete type must therefore contain enough information to distinguish their true positions, as well as their grading abilities and any relevant bundle constraints. If exact rank is part of the type, then almost every type is a singleton: \(\tau\) grows with \(n\), and the supposed continuous population has disappeared. This is a large finite population, not high multiplicity.
If exact rank is omitted so that many assignments share a type, the paper’s target is no longer represented. Two equal-type assignments have no type-level distinction, yet Theorem 2 evaluates all individual pairwise relations under a strict ground truth. The proponent’s weighted objective explicitly removes within-type pairs,
\[ \frac{1}{1-\sum_t \mu_t^2} \sum_{t\ne u}\mu_t\mu_u\,\one{\text{the type order is correct}}, \]
which is not a harmless tie convention. When a type has substantial mass, within-type pairs can constitute a substantial part of the paper’s objective. The mirror has replaced recovery of the individual ranking by recovery of an ordering of coarse quality classes.
The strongest repair is to introduce a latent quality coordinate \(q\in[0,1]\) and retain a strict order almost everywhere. But that produces an atomless continuum of individualized assignments, not a finite-support high-multiplicity society. Every \(q\) has zero mass and almost every assignment remains a distinct type. The input is then a measure, density, or oracle over quality and bundle structure; its computational representation is unspecified. Discretizing \(q\) either restores the lost individual distinctions by making the number of types grow with the required accuracy, or again discards within-bin ranking information.
The proposed \(\rho\) also loses the paper’s essential combinatorial object. Theorem 2 is not controlled merely by the masses of graders and the type composition of their bundles. Its proof depends on the incidence geometry of the bundle graph, through quantities such as \(\lambda_{u,v}\), \(\theta_{u,v}\), and the girth condition. Two finite bundle graphs can have the same aggregate type-level bundle counts while having different common-neighbourhood structure, different girth, and different recovery behaviour. Expanding a rational \(\rho\) into a large finite population gives aggregate counts, but does not automatically give the graph topology required by the theorem, including the relevant overlaps and no-self-grading constraints.
One can repair this by carrying a full sparse graphing or local-neighbourhood process in the continuous model. That is faithful, but it defeats the proposed continuization: the model must retain individual graph positions, local incidence states, and the latent strict ranking. It becomes an infinite graph-limit or random-graph analysis, not a finite-type computational problem whose population has been compressed into masses. The alternative—keeping only \(\rho\)—is computationally manageable precisely because it has forgotten the structure on which the paper’s theorem depends.
Making \(\rho\) an optimization variable does not solve this problem. It creates a new bundle-design problem, with new graph-realizability constraints and a new objective. That may be interesting as a separate study, but it is not a mirror of Theorem 2. Likewise, a continuous Mallows model would merely add a distributional noise model to the same individualized ranking problem; it would not create a computational population object.
The honest boundary is that a graphing limit with a continuous quality coordinate could support an interesting probabilistic-combinatorics paper. But it would not be a worthwhile ChoCo mirror: finite repeated types erase the strict individual-ranking target and graph geometry, while the faithful limit has no finite high-multiplicity computational representation. Thus every plausible formulation falls on one side of that dilemma, and the proponent has not supplied a genuine computational anchor to rescue it.
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.