| paper | d4-conf-aaai-2010-0152 |
| 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 is a characterization of Plurality through a metric and consensus, not a result about computing an object or the difficulty of computation. The proposed mass-weighted nearest-consensus task is well posed, but it adds an algorithmic question absent from the anchored result, so it cannot pass the computational-result gate.
fails bit a — no named computational result to mirror
The proposed mirror covers Theorem 1's Plurality and strong-unanimity characterization; it does not cover the paper's MLE–distance-rationalizability comparison or its other named results.
Strictly, this paper has no named computational complexity result to anchor a continuous mirror to. Its numbered Theorems 1–4, all proved here, concern distance rationalizability: Theorem 1 establishes that Plurality is additively votewise distance-rationalizable with respect to strong unanimity; Theorem 2 shows that three-candidate Borda is not so rationalizable via a neutral additively votewise distance; Theorems 3 and 4 give corresponding impossibility results for STV. None says that a problem is in P, NP-hard, or belongs to another complexity class. The complexity claims one might want to attach to Kemeny or another rule are not established by this paper.
The best positive lead, if I relax the anchor requirement, is a continuous version of Theorem 1. Let a type be a complete ranking \(v\in L(C)\), and let the society be a rational distribution \(\mu\) over a support \(S\), with \(|S|=\tau\). Use the neutral metric \(d\) constructed in Theorem 1’s proof. For each ranking \(r\), define \(D_\mu(r)=\sum_{v\in S}\mu_v d(v,r)\). The problem is: return the candidates ranked first in the rankings minimizing \(D_\mu(r)\). In the paper’s construction, the nearest strong-unanimity consensus has exactly the Plurality winners. The proof’s cost comparisons are linear in voter counts, so they extend to rational masses. A plausible regime is a large ranking or recommendation platform with many users but a moderate number of distinct ranking types. The expected direction is tractable: aggregate first-place mass by candidate and return the maximizers.
That is a concrete population mirror of the paper’s central nearest-consensus idea, but it is not a qualifying computational anchor. The paper proves an axiomatic identity over finite elections; it does not identify a complexity gap that continuization resolves. Its main contribution is the comparison of MLE and distance-rationalizability, and turning that comparison into a computational question would change the paper’s question. So the positive case is plausible as a follow-on problem, but weak under the programme’s stated test.
The case against the proposed Plurality mirror is that it adds a computational question the paper never asks. Theorem 1 says that a particular metric makes Plurality winners coincide with the winners of a nearest strong consensus. It does not study the complexity of finding that consensus, or present nearest-consensus computation as a computational problem. The paper’s numbered results characterize which fixed rules admit certain explanations; they do not give complexity results about an input society.
The proponent’s continuous version is a sensible high-multiplicity object. With ranking types and rational masses \(\mu_t\), it asks for the rankings minimizing \(\sum_t \mu_t d(t,r)\). For the paper’s constructed metric, the resulting winners are exactly those maximizing \(q_c=\sum_{t:\,\mathrm{top}(t)=c}\mu_t\). That is a valid continuous-population question, and the rational masses do not make it a mistaken model. But turning the theorem’s explanatory witness into an algorithmic task changes the paper’s question: it asks us to compute a voting outcome from compressed input, rather than to explain why the rule selects that outcome. Scaling the masses to a common denominator recovers a finite profile; that fact is not itself a collision objection, but it underscores that the theorem establishes an identity, not an algorithmic landscape.
A richer version does not fix the gap. Making the distance part of the input asks about a model the paper does not analyze; asking an algorithm to find a suitable distance turns the task back into synthesizing the axiomatic characterization. Neither supplies a computational problem anchored in Theorem 1.
This is the strongest negative case for the anchor actually raised, but it is not airtight. The paper’s discussion of Kemeny gives a nearby, more substantial optimization objective: minimize expected Kendall distance over rankings for a distribution of ranking types. If the programme counts that latent winner-computation task as a mirror of the paper’s Kemeny discussion, the broader claim that no worthwhile mirror exists becomes much harder to defend.
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.