| paper | d4-conf-ecai-2024-0194 |
| 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: Both the unrestricted and restricted variants are \(\mathrm{NP}\)-complete. · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 4
statement extracted from the paper’s text layer
Given candidates \(M\), supported ranking types \(T\) with rational masses \(\mu_t\), a tie-breaking order, and target \(x^\star\), does there exist a rational report \(y\in\mathbb{Q}_{\ge0}^{M}\) with \(\sum_c y_c=1\) whose induced type responses make \(x^\star\) the plurality winner? For the restricted variant, also require \(\frac12\sum_c|y_c-q_c|\le\alpha\), where \(q_c\) is the truthful plurality share.
The society is a distribution \(\mu\) over complete ranking types. The polling institute chooses score shares \(y\); with \(P(y)\) the reported top-score candidates and \(w\) their lexicographic winner, type \(t\) considers \(A_t(y)=\{w\}\cup(P(y)\setminus\{a_t\})\), where \(a_t\) is its top-ranked candidate. Each type sends its mass to its most-preferred candidate in \(A_t(y)\) if that candidate differs from \(w\), and otherwise keeps its sincere ballot. The decision question is whether some report makes the resulting plurality winner \(x^\star\).
Finite reports whose shares converge to the same vector can induce different responses because \(O(1/n)\) score offsets affect pivotality; the atomless model selects exact ties and applies each type’s response to its full mass, a convention the paper does not derive.
fatal: False
The mirror covers the unrestricted decision problem of Theorem 4 and the score-distance-restricted question related to Theorem 9. It leaves the culture-based probability bounds, destructive manipulation, and the generalized-response results aside.
The strongest mirror I see is constructive poll manipulation in an atomless electorate with plurality voting. It fits the paper’s political-election setting: imagine millions of voters whose complete rankings fall into a relatively small number \(\tau\) of ballot types. A type is a ranking \(t\in T\), and its rational mass \(\mu_t\) is the fraction of society with that ranking. The society is the distribution \(\mu\), not a random finite profile drawn from a culture.
The poll reports shares. Write \(a_t\) for type \(t\)’s top-ranked candidate and \(q_c=\sum_{t:a_t=c}\mu_t\) for candidate \(c\)’s truthful plurality share. The polling institute chooses a rational score-share vector \(y\in\mathbb{Q}_{\ge0}^m\) with \(\sum_c y_c=1\). Let \(P(y)\) be the candidates tied for the largest reported share, and let \(w\) be the lexicographic winner among them.
To specify voters’ response, treat an individual as infinitesimal: type \(t\) regards candidate \(c\) as a potential winner if switching a vanishing amount of ballot mass from \(a_t\) to \(c\) makes \(c\) win for all sufficiently small switches. Equivalently,
\[
A_t(y)=\{w\}\cup\bigl(P(y)\setminus\{a_t\}\bigr).
\]
The type’s best-ranked candidate in \(A_t(y)\) is \(d_t(y)\). If \(d_t(y)\ne w\), that type switches its mass to \(d_t(y)\); otherwise it keeps its sincere ballot. Summing these masses gives the post-response plurality shares.
My lead question is Atomless Unrestricted Poll Manipulation: given \(M\), the supported rankings \(T\) and rational masses \(\mu\), a tie-breaking order, and target \(x^\star\), does there exist a rational report \(y\) whose induced responses make \(x^\star\) the winner? A solution is such a vector \(y\). This is the same constructive question the paper asks—can a polling institute make its target win by changing only the poll?—with the society and reported scores expressed as shares. The response is computed from the ranking types, not from random draws.
The anchor is Theorem 4, proved in this paper: the unrestricted manipulation problem is NP-complete. In the paper’s finite problem, the input is an election with plurality voting and lexicographic tie-breaking plus a target candidate; the question is whether some integer score vector summing to \(n\) induces the voters’ specified one-time best responses and makes the target win. The authors prove membership in NP and hardness by reduction from a restricted X3C instance. I expect the atomless problem to remain NP-hard, hence a likely Class B case: the reduction’s combinatorial choices are among candidates and preference patterns, not just among individual voters. That is a prediction, not a transferred proof. In the atomless version, behavior depends on which candidates can be made jointly credible, a finite menu choice that may still encode the reduction. An algorithm could enumerate those menus in \(2^m\) time; whether that search can be avoided is a concrete complexity question.
A second, worthwhile anchor is Theorem 9, also proved in this paper: restricted manipulation is W[1]-hard when parameterized by \(k\), the maximum number of vote changes between the truthful and announced score vectors. Its reduction is from \(k\)-Clique. The corresponding continuous question is \(\alpha\)-Restricted Atomless Poll Manipulation: use the same input and response rule, add a rational budget \(\alpha\in[0,1]\), and ask whether a successful report exists subject to
\[
\frac12\sum_{c\in M}|y_c-q_c|\le\alpha.
\]
The report \(y\) is again the solution. This is the direct per-capita translation of the paper’s score-distance bound: dividing its number of vote changes by \(n\) gives this total-variation distance between score shares. I expect ordinary hardness may survive, again because the graph’s combinatorics live in the candidate and ranking structure. But Theorem 9’s W[1]-hardness does not itself transfer: fixed \(k\) becomes \(\alpha=k/n\), which tends to zero as the electorate grows. A prover should separately ask about the complexity of the fractional-budget problem and its dependence on \(\alpha\), \(m\), and \(\tau\).
The authors would likely recognize both as their poll-manipulation questions: plurality, truthful rankings, a reported poll, strategic responses based on that poll, and a target winner all remain. The paper’s culture results are relevant context but not a collision. Those results study success probabilities over IID finite profiles; these questions give a deterministic population distribution as input and ask a worst-case computational question. The mirror covers the constructive unrestricted and score-distance-restricted results, not the paper’s probabilistic theorems, destructive manipulation, or social-network variants.
The weak point is the pivotality convention. A finite voter can change a score by one vote; an atomless voter cannot change an aggregate share. The model above defines response through infinitesimal deviations, so a voter can act on exact poll ties. But normalizing scores loses the one-vote boundary: both a \(1/n\) gap and a \(2/n\) gap become zero in the limit, even though only the first may satisfy the finite pivotality test. Thus this is a well-defined continuous analogue, not a claim that the paper’s finite response rule has a unique limit determined by \(\mu\). The question of whether the authors accept that atomless pivotality rule is the main point the opposing case can press.
The paper does have computational results: Theorem 4 proves NP-completeness, and Theorem 9 proves W[1]-hardness. So “there is nothing computational to mirror” cannot support the negative case. Nor is a large population of voters with repeated rankings implausible. The issue is the response rule that makes these results the paper’s problems.
A voter is pivotal in the paper because they are one vote: their ballot can change the reported score vector by one, and the paper tests potential winners after removing that voter’s ballot. Normalizing scores removes precisely that unit. Two sequences of reports can converge to the same score shares while giving voters different potential winners. For example, let \(c\) beat \(w\) in the tie-break. The reports \((n/3,n/3,n/3)\) and \((n/3+1,n/3,n/3-1)\), ordered as \(c,w,z\), have the same limiting shares. In the first, \(c\) wins the tie, and a voter whose sincere top choice is \(w\) can switch to \(c\). In the second, \(w\) wins by one vote; that voter can choose to stay with \(w\). If such voters make up positive mass, the responses differ by positive mass even though the limiting society and poll are the same.
The proposed atomless rule selects the exact-tie case as its convention. That is coherent as a new model, but an individual of measure zero cannot change aggregate scores. The rule instead uses a vanishing switch as a counterfactual, then applies the resulting choice to the whole type mass. That collective response may be a reasonable mean-field assumption; the paper does not supply it. Its finite rule does not determine this convention: first-order score offsets, erased by normalization, can change who responds. A limit faithful to those effects must retain the one-vote scale or a discrete offset around tied shares. That extra microscopic information is exactly what the continuous report \(y\) omits.
This leaves Theorem 4’s proposed mirror as a complexity question about choosing a tied set of candidates under the new mass-response convention. It may be worthwhile on its own, and its hardness could be investigated. The paper’s X3C reduction, however, does not establish that result: its score counts and individual pivot tests have been replaced by different response semantics. Calling the resulting problem the atomless version of Theorem 4 needs the authors’ endorsement of that behavioral change.
The gap is sharper for Theorem 9. Its parameter \(k\) counts individual vote changes. After normalization, a fixed \(k\) becomes \(\alpha=k/n\to0\); retaining its scale requires carrying \(n\) or an equivalent finite-granularity parameter. A fixed share budget \(\alpha\) is a sensible question, and the paper itself studies proportional budgets in its asymptotic results. But that does not preserve Theorem 9’s parameterized hardness question. Its proposed mirror may be a new computational problem, while the raw-vote parameterization has disappeared.
So the strongest objection is that both anchors rely on an atomic pivotality mechanism that the proposed continuum does not inherit from the paper. This is a serious gate problem, not a proof that no author could accept an atomless poll-manipulation model. If the authors endorse the type-wide response convention, the two questions survive as worthwhile new problems. I cannot honestly rule that out, which makes the universal negative case weak.
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.