| paper | d4-conf-aaai-2015-0342 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Theorem 1
statement extracted from the paper’s text layer
Given \(m\) alternatives, a support \(S\) of \(\tau\) ranking types with positive binary-rational masses \(\mu_\sigma\) summing to \(1\), one of the paper’s distance metrics \(d\), and a bound \(t\), promised that \(G_d(\mu,t)=\{\sigma^*\in\mathcal L(A):\sum_{\sigma\in S}\mu_\sigma d(\sigma,\sigma^*)\le t\}\) is nonempty, compute a ranking \(\hat\sigma\) minimizing \(\max_{\sigma^*\in G_d(\mu,t)}d(\hat\sigma,\sigma^*)\), and its minimum radius.
A crowd is a distribution \(\mu\) over reported ranking types; \(\mu_\sigma\) is the fraction reporting \(\sigma\). The decision is a ranking \(\hat\sigma\), chosen to minimize its worst-case distance to any ground truth in \(G_d(\mu,t)\).
The paper gives no tractable running-time bound for computing \(\mathrm{OPT}_d\) and flags possible NP-hardness, leaving its scalability for variable \(m\) open; this limits the guarantee’s practical reach but not the mirror.
fatal: False
The mirror covers the minimax ranking rule and its error guarantees in Theorems 1–4 for rational mass distributions. It leaves the paper’s MLE background, comparisons with other rules, and dataset experiments outside the computational question.
The paper has no admissible named computational anchor. Theorem 1 gives a \(2t\) worst-case error bound; Theorems 2 and 3 give lower bounds, with Theorem 3 tightening the bound for four distance metrics under stated conditions; Theorem 4 gives a \(4t\) guarantee when the supplied error bound is too small. These are guarantees about the quality of the minimax ranking, not results about computational complexity or an algorithm for finding it. The Discussion cites Kemeny ranking’s NP-hardness and says this *suggests* hardness for computing \(\mathrm{OPT}_{d_{\mathrm{KT}}}\), but that observation is neither a numbered result of this paper nor a proved complexity result here. So I can’t honestly present any of these as the required anchor.
The strongest candidate mirror I see is Continuous Minimax Ranking Aggregation. An instance gives \(m\) alternatives, a support \(S\) of \(\tau\) reported ranking types, rational masses \(\mu_\sigma>0\) summing to \(1\), one of the paper’s distance metrics \(d\), and an error bound \(t\). The feasible ground truths are
\[
G_d(\mu,t)=\left\{\sigma^*\in\mathcal L(A):
\sum_{\sigma\in S}\mu_\sigma d(\sigma,\sigma^*)\le t\right\},
\]
with the promise that this set is nonempty. The task is to return a ranking \(\hat\sigma\) minimizing
\[
\max_{\sigma^*\in G_d(\mu,t)}d(\hat\sigma,\sigma^*),
\]
and the corresponding minimum radius.
Here, a type is a ranking submitted by a crowd worker, and its mass is the fraction of workers who submitted it. A plausible regime is a large crowdsourced evaluation of a small set of alternatives: millions of submissions, but relatively few distinct rankings, with workers who submit the same ranking indistinguishable for the objective in this paper. This preserves the paper’s adversarial noise assumption and its minimax decision; it changes the population input to a mass distribution, not the outcome being selected. For every finite profile \(\pi\), setting \(\mu_\sigma\) to the fraction of votes equal to \(\sigma\) gives exactly the same feasible ground truths and minimax objective. Conversely, every rational \(\mu\) can be represented by a finite profile after scaling to a common denominator. The continuous input is therefore a high-multiplicity, potentially much more succinct representation.
I would expect this candidate to be Class B for variable \(m\): a hardness result for the discrete minimax computation would transfer through that exact embedding. The paper’s Kemeny discussion points in that direction, but does not establish the needed reduction for this task. The questions it raises are whether the exact problem or its approximation is hard, and whether algorithms parameterized by \(m\), \(\tau\), or the mass bit length \(L\) can do better. The candidate covers the paper’s minimax ranking problem and its error guarantees, not its MLE background or empirical comparisons.
The soft spot is that the paper already works with profiles and average distances, so its input is naturally summarized by empirical masses. The mirror is credible as a compressed high-multiplicity computational problem, but it may look like a change in representation more than a new mathematical model. Also, because the paper gives no numbered computational result, this candidate cannot satisfy the requested anchor condition; that is the main limit on the positive case.
There is no admissible computational result here to anchor a mirror to. Theorems 1–4 bound the error of the minimax ranking; they say nothing about the time needed to find it. The paper’s discussion only says Kemeny hardness “suggests” hardness for computing \(\mathrm{OPT}_{d_{\mathrm{KT}}}\); it neither proves that claim nor makes it a result of this paper. The authors even say that with a constant number of alternatives they can enumerate all rankings. So the proposed minimax problem is not a continuous mirror of a computational result the paper establishes.
That does not make the proposed problem ill-posed. Its best version is quite credible: millions of crowd workers rank a small set of alternatives, and \(\mu_\sigma\) records the fraction who submit ranking \(\sigma\). The paper’s objective depends only on those fractions, so the types preserve everything it uses. Arbitrary rational masses can be scaled to a finite profile, and finite profiles give empirical mass distributions. This is a sensible high-multiplicity formulation; invoking high multiplicity or the paper’s existing use of averages as objections would be a mistake.
The strongest negative point is narrower: the proponent turns the paper’s defined rule into a new complexity question. Studying exact, approximate, or parameterized computation for that rule may be worthwhile ChoCo work, but it is not anchored in a named computational result of this paper. Adding worker attributes could produce richer types, but that would change the model rather than supply the missing result.
That is the honest limit of the negative case. I cannot defend the universal claim that no scenario yields a worthwhile continuous mirror: the crowd-worker regime makes the mass model natural, and the implied computational problem could be interesting in its own right. The case against succeeds only on the requested paper-to-result connection.
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.