| paper | d4-conf-ijcai-2021-0588 |
| 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}\)-hard under polynomial-time Turing reductions; more precisely, \(\mathrm{coNP}\)-complete under polynomial-time many-one reductions. · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 5
statement extracted from the paper’s text layer
Given a candidate set \(C\), a finite support \(T\) of complete rankings with rational masses \(\mu_t>0\) summing to \(1\), and a total order \(X\), determine whether \(X\) minimizes \(\sum_{t\in T}\mu_t d_{\mathrm{KT}}(t,Y)\) over all total orders \(Y\) of \(C\).
A population of ranking types \(t\in T\), each carrying mass \(\mu_t\); the decision object is a proposed total order \(X\), evaluated by its expected Kendall tau distance \(\sum_t\mu_t d_{\mathrm{KT}}(t,X)\).
The direct mirror covers Theorem 5; the separate mass-allocation mirror also covers Theorem 17. It leaves the candidate-control and Slater manipulation results without a proposed mirror.
The paper is unusually easy to mirror honestly: its main subject is aggregating a population’s rankings into a consensus. In a large rank aggregation service, for example, the population can be represented by the fractions of users with each recurring ranking type, with \(\tau\) observed types and far more users than types. The ranking stays the outcome; the society becomes continuous.
My lead is Theorem 17, proved in this paper using a construction from Davies et al. The theorem says that Borda-Manipulation-to-Consensus is NP-complete: given an election, a coalition of manipulators, and a desired consensus, can the coalition cast votes so that the resulting Borda consensus is exactly the desired one? The paper derives this from the cited Borda manipulation construction, whose target consensus has a tied top block and a lower-scoring candidate.
A precise mirror is Continuous Borda-Manipulation-to-Consensus. An instance has a candidate set \(C\), a background society \(\mu\) over complete rankings of \(C\), a rational manipulator mass \(\alpha>0\), and a desired weak order \(X=(B_1\succ\cdots\succ B_r)\). A solution assigns nonnegative mass \(y_\pi\) to each possible reported ranking \(\pi\), with \(\sum_\pi y_\pi=\alpha\). Each \(y_\pi\) is the share of the homogeneous manipulator bloc that casts \(\pi\); each person still casts one ballot. The resulting Borda score is
\[
S(c)=\sum_t \mu_t s(t,c)+\sum_\pi y_\pi s(\pi,c),
\]
where \(s(\pi,c)\) is the Borda score of \(c\) under ranking \(\pi\). The question is whether some such allocation makes candidates tie within each block of \(X\) and gives each higher block strictly greater scores than the next. There is no cost objective in Theorem 17; the decision goal is reaching \(X\).
This looks like a plausible Class A mirror. The constraints on the \(y_\pi\) form a linear program with exponentially many ranking variables. Strict gaps between adjacent blocks can be handled by maximizing a gap variable \(\delta\) and asking whether its optimum is positive. The dual pricing step optimizes a weighted sum of Borda scores over rankings. That is an assignment problem: assign candidates to Borda positions to maximize the weighted score. Thus the pricing problem is polynomial, suggesting an exact polynomial algorithm through separation and LP machinery, with running time polynomial in \(m,\tau,L\). This would answer a useful question raised by the paper’s NP-hardness result: does the hardness of distributing an indivisible coalition’s ballots disappear when the coalition is a genuinely large, homogeneous population?
A concrete regime is a large ranking platform or consultation where many users have recurring preference rankings and an organized bloc shares a target consensus, with common voting rights and no idiosyncratic report costs. Background rankings and the manipulator bloc are then naturally described by masses. This is the most promising mirror computationally, though the tractability claim is an analysis of the mirror, not a result of the paper. It also suggests follow-up questions about restricted ballot menus, individual report costs, and whether useful sparse solutions can always be produced.
A second, stronger mirror by directness is Theorem 5, proved in this paper through the FAS and Kemeny constructions, using a cited minimum vertex cover recognition result. It states that Kemeny Consensus Recognition is coNP-complete: given an election \((C,V)\) and a total order \(X\), is \(X\) a Kemeny consensus, meaning that it minimizes total Kendall tau distance to the voters’ rankings?
Its continuous form takes \(C\), a rational distribution \(\mu\) over ranking types, and a total order \(X\), and asks whether
\[
\sum_t\mu_t d_{\mathrm{KT}}(t,X)
\le
\sum_t\mu_t d_{\mathrm{KT}}(t,Y)
\quad\text{for every total order }Y.
\]
The expected classification is Class B: discrete hardness embeds directly. Given an election with \(n_t\) voters of each ranking type and \(n\) voters total, set \(\mu_t=n_t/n\). Expected Kendall distance is the discrete total distance divided by \(n\), so the consensus orders are identical. This map is polynomial from an explicitly listed election, and a better order \(Y\) certifies the complement with an exact rational comparison. The scenario is especially natural for the paper’s rank aggregation settings, such as web search or consensus genetic maps.
These two mirrors cover Theorems 17 and 5 only; they do not claim to continuize the paper’s candidate-control or Slater results. Theorem 5 gives the clearest case that the authors should recognize the population mirror as their problem. Theorem 17 gives the more interesting prospect of continuous optimization changing the complexity picture.
The weakest point is the Theorem 17 regime: a large manipulator coalition with a shared target is less routine than a large population of ordinary users. Its mirror depends on treating ballot choices as a mass allocation, so the discrete integrality that drives the paper’s hardness can vanish. I think that is a legitimate high-multiplicity question, especially for a large coordinated bloc, but it is the part authors may challenge first.
I can make a limited case against the Borda mirror, but I cannot honestly defeat both anchors. The universal negative position is weak here.
Theorem 17’s continuous Borda manipulation problem depends on treating the manipulators as a sizeable, coordinated bloc with a shared target. That is a less routine population regime than ordinary rank aggregation: the paper specifies a coalition and desired consensus, not a distribution of manipulators’ underlying preferences. A model that adds distinct preference types, report permissions, or costs may be useful, but those are extra assumptions. Still, a large bloc with a common mandate is coherent, and the paper’s decision question itself permits the mass-allocation formulation. The LP has exact tie constraints and a positive score-gap variable; its ranking-pricing step is an assignment problem. So the modeling caveat does not defeat the strongest version of this mirror.
Theorem 5 is harder to rebut. In a large rank-aggregation setting with repeated ballot types, represent the society by rational masses \(\mu_t\) and ask whether a proposed order \(X\) minimizes expected Kendall distance. For a discrete election with \(n_t\) voters of each type and \(n\) voters total, set \(\mu_t=n_t/n\). Every order’s expected distance is its discrete total distance divided by \(n\), so the consensus orders coincide. The input transformation is polynomial, and a better order remains a certificate that \(X\) is not optimal. Complete rankings capture everything this objective uses; it does not depend on voter identities.
One can object that rational masses merely encode weighted ballots, or that real rank-aggregation data may contain many distinct rankings. Neither defeats the mirror under this programme’s criteria: the first is the high-multiplicity bridge itself, and the second limits the regime’s reach without eliminating plausible large populations with recurring ballot types.
So the strongest honest negative point is that Theorem 17 relies on a more contestable coalition scenario. Theorem 5 survives that objection as a direct, sensible population mirror. I cannot make the requested case 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.