| paper | d4-conf-aaai-2013-0087 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
The paper contains no numbered theorem, lemma, corollary, or proposition asserting a computational result. Its Kemeny hardness statement is background, while its own contribution is empirical comparison without a stated computational guarantee, so no anchor passes bit (a).
fails bit a — no named computational result to mirror
The proposed mirror covers Kemeny aggregation; it leaves the paper's empirical comparisons, human behavior findings, and noise model experiments without a computational mirror.
There is no eligible numbered anchor in this paper: it has no numbered theorem, lemma, corollary, or proposition asserting a computational complexity result. The closest is the unnumbered background statement in Section 2 that computing a Kemeny ranking is NP-hard. The paper does not prove that claim; it presents the study as an empirical comparison of voting methods.
The strongest plausible mirror, if that unnumbered claim is allowed as an anchor, is Kemeny Ranking\(_\infty\). An instance gives \(m\) alternatives and a support set \(S\) of complete rankings, each with a positive binary-rational mass \(\mu_\sigma\) summing to \(1\). A type is a ranking \(\sigma\); its mass is the fraction of workers who submit it for the same ranking task. The solution is a ranking \(\pi\) minimizing
\[
\sum_{\sigma\in S}\mu_\sigma K(\pi,\sigma),
\]
where \(K\) is Kendall tau distance. A credible high-multiplicity setting is a crowdsourcing platform asking thousands of workers to rank the same shortlist of proposals. With four alternatives there are at most \(24\) ranking types, though the paper’s own experiment had only about \(20\) rankings per task instance; the stronger regime is a scaled-up crowd task.
This mirror is close to the paper’s problem: Kemeny is one of the aggregation methods it defines and evaluates, and the continuous objective is precisely its total disagreement objective expressed per worker. I would expect hardness transfers: any finite voter profile maps to rational masses \(\mu_\sigma=n_\sigma/n\), preserving exactly the Kemeny minimizers. Natural follow-up questions concern algorithms parameterized by \(m\) or support size \(\tau\), and approximation when those parameters grow.
The weak point is decisive under your stated anchor rule: this is not a numbered result of the paper. Also, the experiments fix four alternatives, where Kemeny is easy to compute; the NP-hardness claim is background rather than a result the paper establishes or studies. So this is a plausible continuous form of a problem used in the paper, but it cannot support a compliant anchor-led positive case.
The only anchor the case for offers is Kemeny ranking. The paper defines it and mentions its NP-hardness, but does not establish or study that complexity result; it is background for an empirical comparison of ranking methods. So the proposed \(Kemeny_\infty\) problem is a legitimate high-multiplicity version of Kemeny, but it does not mirror a computational result of this paper. A larger crowdsourcing population makes the setting plausible; it does not change what the paper contributes.
A better mirror of the paper’s contribution might compare voting rules by their expected error over a population of workers. That needs a model of the ground truth, task distribution, and worker behavior as well as a distribution over rankings. It could be useful, but it is a statistical evaluation question, not a computational problem whose complexity or algorithms the paper studies. The paper’s own experiments report finite-sample comparisons; they do not formulate that population-risk problem.
That is the strongest negative case, and it is narrower than the requested universal claim. A continuous Kemeny problem could still be worthwhile as part of ChoCo; the evidence here does not show that no scenario or re-modeling could make a worthwhile mirror. It shows that the proposed Kemeny anchor is not a result of this paper, and that extending its empirical comparison would ask a different kind of question.
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.