| paper | d4-conf-atal-2010-0327 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
parameterized→NP-hard discrete result → its continuous mirror
Answer: \(\Delta_2^p\)-complete, hence \(\mathrm{NP}\)-hard; fixed-parameter tractable with parameter \(m\), in time \(O(\tau L^2+(\tau m^2+m^2 2^m)(L+\log(m+1)))\). · discrete side: parameterized · adjudication: proved
full proof & adversarial review →
Theorem 4.14
statement extracted from the paper’s text layer
Given a candidate set \(C\), a distribution \(\mu\) with binary-rational masses over \(\tau\) complete rankings, and a candidate \(c\), decide whether \(c\) is first in some ranking minimizing \(\sum_t \mu_t\,\operatorname{Kendall}(t,\pi)\) over all rankings \(\pi\) of \(C\).
Represent the population by ranking types \(t\) and masses \(\mu_t\). Choose a target ranking \(\pi\), equivalently a unanimous target society with all mass on \(\pi\), to minimize expected swap cost \(\sum_t \mu_t\,\operatorname{Kendall}(t,\pi)\); report the candidates ranked first by at least one minimizer.
Kemeny’s objective depends only on aggregate pairwise counts, so the ranking distribution may be compressible beyond its support; this bounds the role of τ but does not remove the well-posed population-mass question.
fatal: False
The mirror covers Kemeny winner determination through its application of Theorem 4.14. It leaves the paper’s other results on distance rationalizability, votewise properties, scoring-rule characterizations, and other voting rules aside.
The strongest case is a continuous-population version of Kemeny winner determination. The paper has no numbered theorem asserting hardness, so I use Theorem 4.14 as the anchor. The paper does state that finite Kemeny winner determination is \(\Theta_2^p\)-complete, citing prior work [15]; I use that as evidence about the mirror’s expected complexity, not as a numbered anchor.
Theorem 4.14, proved in this paper, says: if a voting rule \(R\) is rationalizable by any consensus class \(K\in\{S,U,M,C\}\) and a normal \(\ell_1\)-votewise distance \(d\), then the \(R\)-winner problem is fixed-parameter tractable in the number \(m\) of candidates. Here, “normal” means integer-valued and polynomial-time computable; “\(\ell_1\)-votewise” means that the distance between profiles is the sum of the per-voter distances between their ballots. The paper sketches a proof using an integer linear program with \(O(m!)\) variables and Lenstra’s algorithm. Kemeny is rationalizable via strong unanimity \(S\) and swap distance, so it is an instance of this theorem.
Here is the mirror I would hand to a prover, Continuous Kemeny Winner. An instance is a candidate set \(C\) and a distribution \(\mu\) over a support of \(\tau\) complete rankings \(t_1,\ldots,t_\tau\), with positive binary-rational masses \(\mu_{t_i}\) summing to \(1\). For each ranking \(\pi\), define
\[ \operatorname{cost}_{\mu}(\pi) = \sum_{i=1}^{\tau}\mu_{t_i}\,\operatorname{Kendall}(t_i,\pi), \]
where \(\operatorname{Kendall}\) counts the pairwise disagreements between rankings. The task is to find the Kemeny winners
\[ W(\mu)= \{c\in C:\text{some cost-minimizing ranking }\pi\text{ has }\pi(1)=c\}. \]
The decision version takes a candidate \(c\) and asks whether \(c\in W(\mu)\); a solution can report the winner set and an optimal ranking. In distance-rationalization terms, choose a strong-unanimity target society—all mass assigned to one ranking \(\pi\)—minimizing the per-capita swap distance from \(\mu\). The target ranking is the decision variable; the objective is expected swap cost.
This is a plausible high-multiplicity regime: for example, a large electorate ranks a fixed, small slate of candidates, many voters share each ballot, and everyone’s cost is measured by the same swap distance. With \(m=8\), there are at most \(40{,}320\) possible ranking types, while the electorate could have millions of members. A type fully specifies the preference used by the problem, and all members of that type face the same distance. The paper’s finite population is still a list of individual voters; its sum of voter-level distances does not itself make the population continuous.
For an empirical profile with \(n_t\) voters of each type, set \(\mu_t=n_t/n\). Then \(\operatorname{cost}_{\mu}(\pi)\) is the finite Kemeny cost divided by \(n\), so the continuous and discrete winner sets are exactly the same. Thus finite Kemeny embeds in this mirror: converting an explicit profile to its type counts gives a polynomial-size rational distribution with identical winners. The paper says finite Kemeny winner determination is \(\Theta_2^p\)-complete, citing [15], so I expect hardness to transfer in the unbounded-\(m\) problem. This is a Class B mirror, not a claim that continuization dissolves Kemeny’s hardness.
The other side of the result is parameterized tractability. Theorem 4.14 predicts FPT in \(m\), and this continuous question is directly solvable by evaluating all \(m!\) rankings against the \(\tau\) supported types, in \(m!\operatorname{poly}(\tau,L)\) time, where \(L\) is the mass encoding length. The mirror therefore asks a useful high-multiplicity question: can the population be represented by its support and binary masses, without an algorithm whose runtime depends polynomially on the headcount?
My weakest point is that strong unanimity forces every unit of mass to the same target ranking, so the continuous model creates no fractional choice over consensus outcomes. For empirical distributions it reproduces ordinary Kemeny exactly; its contribution is the high-multiplicity input regime and its complexity boundary, not a new optimizer or a new winner rule. That limitation is also why this is a credible mirror: it preserves the paper’s question closely enough that the authors could recognize it as theirs. Further questions include whether the binary-rational version has an exact \(\Theta_2^p\) classification, and whether small support \(\tau\) enables algorithms better than enumeration in \(m\).
The sole anchor is Theorem 4.14 through Kemeny. The strongest case against its mirror is that it adds little beyond a compact encoding of weighted Kemeny. For rational masses, choose a common denominator \(q\) and set \(n_t=q\mu_t\). Then for every ranking \(\pi\),
\[ q\,\operatorname{cost}_{\mu}(\pi)=\sum_t n_t\,\operatorname{Kendall}(t,\pi). \]
The winners are exactly those of the corresponding finite election. Moreover, Kemeny’s objective depends only on aggregate pairwise counts, so the full distribution over rankings is more detail than the optimization needs. Theorem 4.14 already gives fixed parameter tractability in \(m\); the continuous formulation mainly replaces a list of voters with binary encoded weights.
That makes the contribution look incremental: the continuous input offers compactness when the electorate is huge, but it does not expose a new optimization structure or a population effect specific to Kemeny. The support size also satisfies \(\tau\le m!\), so it cannot provide an independent support parameter beyond a function of \(m\).
I cannot make this a decisive objection under ChoCo’s stated standard. The mirror is a well-posed computational problem, the large electorate with repeated rankings is a plausible high multiplicity regime, and rational masses preserve a meaningful normalized cost. The paper does have a named computational result, and the objective does not track individual voters. The exact correspondence to finite Kemeny is not itself a collision or a disqualifier under the programme’s rules. So the negative case is weak: this mirror may be incremental, but I do not have a sound basis for saying it is not worthwhile.
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.