| paper | d4-conf-atal-2009-0144 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
NP-hard→NP-hard discrete result → its continuous mirror
Answer: \(\mathrm{NP}\)-complete · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 3
statement extracted from the paper’s text layer
Given \(m\) candidates, a finite support \(T_+\) of strict rankings with positive rational masses \(\mu_t\) summing to \(1\), and a rational threshold \(B\), decide whether there is a strict ranking \(\ell\) such that \(r_a(\mu)\le 2\) and \(\sum_{t\in T_+}\mu_t\,\mathrm{KT}(\ell,t)\le B\), where \(r_a(\mu)=\frac{1}{m}\sum_c\left(1+\max_{t\in T_+}\operatorname{pos}_t(c)-\min_{t\in T_+}\operatorname{pos}_t(c)\right)\).
A population is a rational distribution \(\mu\) over complete ranking types. The decision variable is one consensus ranking \(\ell\); its cost is expected Kendall–Tau distance, \(\sum_t\mu_t\,\mathrm{KT}(\ell,t)\), subject to the support-based average candidate range being at most \(2\).
The support-extreme range constraint can change when a ranking type of arbitrarily small positive mass is added, so the parameter’s interpretation in terms of population shares is narrower than its literal definition suggests.
fatal: False
Theorem 3’s NP-completeness transfers through normalized ballot multiplicities; the weighted analogue of Theorem 1 covers low δ(μ). These mirrors leave Theorem 2’s maximum-range algorithm and the rest of the paper’s parameterized analysis aside.
My strongest anchor is Theorem 3, proved in this paper: Kemeny Score is NP-complete even for elections with average candidate range two. The paper proves this by reducing an arbitrary Kemeny Score instance: it appends \(m^2\) new candidates after the original candidates, in the same order on every ballot. The new candidates’ order is fixed in every optimum, so deleting them recovers the original optimum, while the constructed election has average range below two.
The continuous mirror is Range-2 Expected Kemeny Score. An instance consists of \(m\) candidates, a finite support \(T_+\) of strict rankings, positive binary-rational masses \(\mu_t\) summing to one, and a rational threshold \(B\). Define
\[
r_\mu(c)=1+\max_{t\in T_+}\operatorname{pos}_t(c)-\min_{t\in T_+}\operatorname{pos}_t(c),
\qquad
r_a(\mu)=\frac{1}{m}\sum_c r_\mu(c).
\]
For distributions with \(r_a(\mu)\le 2\), ask whether there is a strict ranking \(\ell\) with
\[
\sum_{t\in T_+}\mu_t\,\mathrm{KT}(\ell,t)\le B.
\]
A yes-instance has \(\ell\) as its certificate; the optimization form asks for a ranking minimizing this expected distance. This is the paper’s same Kemeny objective: the action remains one consensus ranking, and the loss remains Kendall–Tau distance. Only the population is represented by masses.
The hardness transfers exactly. Given an election with \(n\) ballots, set \(\mu_t\) to the fraction of ballots of type \(t\), and set \(B=k/n\). The continuous objective is the discrete Kemeny score divided by \(n\); the reduction’s support and average ranges are preserved. A ranking certificate and its rational expected score can be checked in polynomial time, so this continuous decision problem is NP-complete. I expect hardness transfers (Class B), with the reduction’s combinatorics coming from the alternatives and agenda. This is the strongest anchor because it gives a precise negative boundary for the continuous question.
The population regime is credible for rank aggregation: many users, voters, or respondents rank the same \(m\) products, policies, or candidates, and the mass of a ranking type is its share of the population. The number \(N\) of people can greatly exceed the number \(\tau\) of distinct rankings; replicating a profile preserves its distribution while making \(N/\tau\) arbitrarily large. The paper’s result is not already this continuous model: it studies an explicitly listed finite electorate, not a rational distribution input with complexity measured in \(m,\tau\), and mass bit length \(L\).
A second, independent anchor is Theorem 1, also proved here: Kemeny Score can be solved in
\[
O\!\left(16^d\bigl(d^2m+d\,m^2\log(m)\,n\bigr)+n^2m\log(m)\right)
\]
time for \(d=\lceil d_a\rceil\), where \(d_a\) is the average pairwise Kendall–Tau distance between distinct input votes; the dynamic-programming table has size \(O(16^d d m)\). This is an exact algorithm for the score, and the paper explains how to recover an optimal consensus ranking.
Its continuous mirror is Low-Disagreement Population Kemeny: on the same distribution input, return an optimal strict ranking and its expected score, parameterized by
\[
\delta(\mu)=\sum_{t,u\in T_+}\mu_t\mu_u\,\mathrm{KT}(t,u),
\]
the disagreement between two independently sampled agents. For an empirical distribution from \(N\) voters, \(\delta(\mu)=\frac{N-1}{N}d_a\), so this is the natural population counterpart of the paper’s parameter. I expect tractability (Class A): the paper’s localization and dynamic-programming approach appears suited to weighted contributions, with the continuous algorithm asked to run in \(f(\delta)\operatorname{poly}(m,\tau,L)\) time. The theorem itself is for explicitly listed voters; establishing this bit-complexity bound for rational masses is part of the mirror question.
The main weakness is that Theorem 3 transfers discrete hardness; it does not show hardness specifically caused by continuity, nor does it establish hardness when \(\tau\) is bounded. And the weighted algorithmic mirror of Theorem 1 still needs a proof. Those limits do not undermine the mirror: the decision problem keeps the authors’ ranking task intact, while the two anchors pose distinct questions about the same continuous population—hardness at average range two and tractability at low pairwise disagreement. The paper’s finite-electorate results support the proposed regime rather than colliding with it.
The strongest case against is that both proposed mirrors may be incremental versions of a problem already expressed through aggregate rankings. Kemeny loss is a sum of pairwise disagreements, so its expectation under \(\mu\) depends only on weighted pairwise margins. And every rational \(\mu\) has a common denominator \(Q\): replacing each type’s mass by its corresponding number of copies gives a finite election whose Kemeny score is \(Q\) times the expected score. That makes the continuous formulation compact and natural, but leaves little new structure in the objective itself.
That concern does not defeat Theorem 3. The paper’s average-range parameter uses the support’s extremes, so even a tiny positive mass can determine a candidate’s range. A mass-sensitive alternative might better reflect population shares, but it would be a different parameter and would not inherit this reduction. More decisively, the paper’s four-vote hardness result can be padded in the same way: the mirror remains hard with at most four ranking types, each with positive mass. That makes the result largely about the alternatives, but the programme explicitly treats transferred hardness as a worthwhile boundary, not an objection.
It also does not defeat Theorem 1. For an empirical distribution with \(Q\) people, the expected disagreement \(\delta(\mu)\) satisfies \(d_a=\frac{Q}{Q-1}\delta(\mu)\) when \(Q\ge2\). The algorithm’s \(n^2\) preprocessing can be computed over the \(\tau\) supported types with their weights; its dynamic program can use weighted sums and rational arithmetic, with bit complexity polynomial in \(L\). The parameter changes by at most a constant factor. This looks like a tractable high-multiplicity extension, even if much of the proof may carry over directly.
So the negative case is weak. Both anchors survive scrutiny: the first gives a valid low-support hardness mirror, and the second appears to yield a weighted fixed-parameter algorithm. Their close relationship to ordinary Kemeny ranking raises a fair question about how much new technique they require, but under this programme’s stated goals, that is not enough to argue that no worthwhile continuous mirror exists.
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.