| paper | d4-conf-aaai-2021-0257 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
NP-hard→NP-hard discrete result → its continuous mirror
Answer: \(\mathrm{NP}\text{-hard}\), even for \(\tau\le 4\). · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 1
statement extracted from the paper’s text layer
Given a finite support \(S\) of rankings over \(m\) candidates, with positive binary-rational masses \(\mu_R\) summing to \(1\), compute a ranking \(W\) minimizing \(\sum_{R\in S}\mu_R\,\mathrm{KT}(W,R)\).
A society is a distribution \(\mu\) over complete ranking types. The decision variable is a ranking \(W\), and the objective is its expected Kendall tau distance to a voter drawn from \(\mu\); the input parameters include \(m\), support size \(\tau\), and mass bit length \(L\).
The mirrors cover Kemeny and Slater winner determination underlying Theorems 1 and 2. They do not mirror Proposition 1's BM-smoothed result or Theorem 3's Mallows-based typical-case runtime bound.
The strongest mirror is the deterministic high-multiplicity version of winner determination: a very large consultation or electorate ranks the same \(m\) candidates, and many people submit identical ballots. A type is a complete ranking \(R\); its mass \(\mu_R\) is the fraction of participants with that ballot. The regime is useful when the number of participants \(n\) is much larger than the number \(\tau\) of distinct rankings. That is plausible for a large electorate with repeated ballot types, though it is not a claim about every voting setting.
Lead: Continuous Kemeny Winner Determination. An instance consists of \(m\) candidates and a finite support \(S\) of rankings, each with positive binary-rational mass \(\mu_R\), where \(\sum_{R\in S}\mu_R=1\). The decision variable is a ranking \(W\). The question is to output a \(W\) minimizing \(\sum_{R\in S}\mu_R\,\mathrm{KT}(W,R)\), with ties between optimal rankings allowed. The relevant input parameters are \(m\), \(\tau=|S|\), and the total bit length \(L\) of the masses.
Its anchor is Theorem 1, “Smoothed Hardness of Kemeny,” proved in this paper. The theorem says that for any series of preference models satisfying Assumption 1—each model is polynomial-time samplable and neutral, and has a 3-cycle component of inverse-polynomial magnitude—if Kemeny has a smoothed polynomial-time algorithm with respect to that series, then \(\mathrm{NP}=\mathrm{RP}\). The paper proves this by reducing from Eulerian Feedback Arc Set. The theorem is conditional smoothed hardness; it does not itself assert hardness of the deterministic continuous problem above.
For the continuous problem, the expected direction is Class B: hardness transfers. Given a discrete profile \(P\), set \(\mu_R=n_R/n\), where \(n_R\) is the number of voters with ranking \(R\). The continuous objective is then the discrete Kemeny score divided by \(n\), so its minimizers are identical. The reverse representation also holds for rational masses: clearing denominators gives a finite profile with the same optimum. The paper cites discrete Kemeny NP-hardness, so this embedding makes the continuous problem NP-hard as well. The paper’s own proof lends plausibility to this mirror: it constructs fractional parameter profiles with prescribed weighted majority graphs, then rounds and samples them. Those parameters are distributions rather than our ranking types, but the proof already reasons about weighted aggregates of agents.
Second mirror: Continuous Slater Ranking. Use the same instance format. For each pair \(a,b\), define the population margin \(M_\mu(a,b)=\sum_{R\in S}\mu_R\,\operatorname{sgn}_R(a,b)\), where the sign is \(+1\) if \(a\) is ranked above \(b\) and \(-1\) otherwise. Form a directed graph with edge \(a\to b\) exactly when \(M_\mu(a,b)>0\); tied pairs contribute no edge. The question is to output a ranking minimizing the number of these majority edges it reverses. This is the Slater objective for the continuous society.
Its anchor is Theorem 2, “Smoothed Hardness of Slater Ranking,” proved in this paper. It says that for any series satisfying Assumption 1 and the additional condition that each model has a co-cycle component of inverse-polynomial magnitude, a smoothed polynomial-time algorithm for Slater Ranking implies \(\mathrm{NP}=\mathrm{RP}\). The proof reduces from Tournament Feedback Arc Set, whose NP-hardness the paper cites. Here too, the continuous problem’s expected direction is Class B: for \(\mu_R=n_R/n\), its majority graph is exactly the discrete profile’s unweighted majority graph, so the Slater optima coincide. Discrete Slater hardness, cited in the paper, transfers through this encoding.
These mirrors cover the underlying Kemeny and Slater winner-determination problems addressed by Theorems 1 and 2. They do not claim to mirror Proposition 1’s BM-smoothed framework or Theorem 3’s Mallows-based typical-case runtime bound. Further questions include whether either exact problem admits useful algorithms parameterized by support size \(\tau\), and, for Slater, how the difficulty changes when all nonzero population margins are bounded away from zero.
The weak point is that the paper’s actual question is about runtime on random finite profiles generated independently from potentially different agent-level distributions. A society \(\mu\) records aggregate ranking mass and loses that sampling process and its heterogeneity. In particular, the theorem’s conditional smoothed-hardness conclusion does not follow just from solving the continuous problem. The positive case is narrower: these are credible continuous versions of the underlying winner-determination problems, and the authors’ fractional-profile constructions make aggregate reasoning familiar within their proofs. The hardness prediction for the mirrors rests on the exact discrete-to-rational-mass embedding, not on treating the smoothed theorems as results about continuous societies.
The strongest negative case is that the proposed questions are credible continuous versions of Kemeny and Slater, but they are not direct continuizations of the results used to anchor them.
Theorem 1 concerns the worst expected runtime on a *random finite profile*, maximized over agent-specific sampling distributions. The continuous Kemeny question instead takes the expected ranking mass as its input and optimizes deterministically. Passing from the paper’s tuple of sampling laws to ballot masses loses the finite-sample fluctuations that the theorem’s reduction uses. A closer mirror would keep a population distribution over agents’ sampling laws and specify how finite-population noise scales. Without that extra stochastic structure, the paper’s smoothed-hardness conclusion does not answer the proposed continuous question.
The same mismatch applies to Theorem 2. The paper’s Slater hardness concerns a majority graph formed from sampled profiles; the proposed mirror computes the graph from exact population margins. One can define that problem cleanly, including how zero margins are treated, but the theorem does not establish its complexity. In fact, the better version of this mirror would give sampling-law types their own masses and retain fluctuations around their aggregate margins. That brings the question back to a stochastic finite-population model, rather than a deterministic society over ballot types.
That objection defeats the *anchors*, but it does not defeat the mirrors. For Kemeny, a rational-mass society gives the weighted objective \(\sum_R \mu_R\,\mathrm{KT}(W,R)\); for Slater, it gives the majority graph from the signs of the population margins. Both are sensible high-multiplicity questions, and explicit finite profiles embed in them. Calling them mere re-encodings is not a sound objection under ChoCo’s stated scope: the compact mass representation and its dependence on support size and bit length are part of the question.
Nor do obvious model details rescue the negative case. Slater’s zero-margin boundary can be defined naturally, and positive-margin instances remain meaningful. Kemeny’s and Slater’s objectives still depend on population masses. The continuum does not make either problem vanish.
So I would argue against treating Theorems 1 and 2 as evidence for these particular continuous questions: they study smoothed runtime, while the proposed mirrors study deterministic winner determination. But I cannot honestly make the stronger case that *no worthwhile continuous mirror exists in any scenario*. The deterministic Kemeny and Slater mirrors survive the programme’s test; the negative case is weak precisely there.
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.