| paper | Winner Robustness via Swap- and Shift-Bribery: Parameterized Counting Complexity and Experiments |
| authors | N. Boehmer, Robert Bredereck, Piotr Faliszewski, R. Niedermeier |
| venue | IJCAI 2021 |
| filed under | voting · bribery-control |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
NP-hard→P discrete result → its continuous mirror
Answer: Deterministic polynomial time in \(m,\tau,L,\log(1/\varepsilon)\), including exact identification of \(-\infty\). · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 1
statement extracted from the paper’s text layer
Given \(m\) candidates, a rational distribution \(\mu\) over ranking types \(\sigma\in S_m\), target \(p\), and rational normalized radius \(\rho\), take \(N\)-voter realizations with \(N\mu_\sigma\in\mathbb{Z}\) and uniformly count labelled final profiles at exact swap distance \(N\rho\). Compute or approximate \(\Lambda_p(\mu,\rho)=\lim_{N\to\infty}N^{-1}\log P_{p,N}(N\rho)\), equivalently the maximum entropy of feasible mass transfers making \(p\) a Plurality winner minus the unconstrained maximum.
Types are rankings \(\sigma\in S_m\) with masses \(\mu_\sigma\); \(x_{\sigma,\pi}\) is transferred mass, constrained by row sums \(\mu_\sigma\), total Kendall distance \(\rho\), and a Plurality-winning condition. Maximize \(H(x)=-\sum_{\sigma,\pi}x_{\sigma,\pi}\log(x_{\sigma,\pi}/\mu_\sigma)\), or the difference between its constrained and unconstrained maxima.
The proposed \(\Lambda_p\) is determined only after selecting a labelled multinomial thermodynamic sequence; \(\mu\) alone does not determine the finite probability, and tractability over implicit \(S_m\) remains unproved.
fatal: False
The mirror covers Theorem 1 and the paper’s Plurality robustness-counting framework, but not Theorems 2–6, the Borda results, the swap-radius open problem, or the empirical findings except through possible extensions.
My lead mirror is a high-multiplicity version of the paper’s central robustness quantity, anchored in Theorem 1.
Theorem 1 states that PLURALITY #SWAP-BRIBERY is \(\#\mathrm P\)-hard and \(\#\mathrm W[1]\)-hard when parameterized by the swap radius, even for unit prices. The counting problem asks, given an election, designated candidate \(p\), and radius \(r\), how many elections at exactly swap distance \(r\) make \(p\) a Plurality winner. This theorem is proved by the authors in the paper, via a reduction from \(\#\mathrm{MATCHING}\); it is not merely a cited result.
The corresponding continuous problem I would propose is Continuous Plurality Swap-Entropy.
An instance consists of candidates \(C\), the ranking-type space \(T=S_m\), a rational population distribution \(\mu\in\mathbb Q^{T}\), a designated candidate \(p\), and a rational normalized swap radius \(\rho\). A type is a complete ranking \(\sigma\in S_m\), and \(\mu_\sigma\) is the fraction of the population with that ranking. The regime is high multiplicity: millions of voters may share a relatively small collection of ranking types.
The action variable is a mass-transfer plan \(x=(x_{\sigma,\pi})_{\sigma,\pi\in T}\). Here \(x_{\sigma,\pi}\) is the mass initially of type \(\sigma\) whose final ranking is \(\pi\). It satisfies
\(x_{\sigma,\pi}\ge 0\),
\(\sum_{\pi}x_{\sigma,\pi}=\mu_\sigma\) for every \(\sigma\), and
\(\sum_{\sigma,\pi} d_{\mathrm{sw}}(\sigma,\pi)x_{\sigma,\pi}=\rho\),
where \(d_{\mathrm{sw}}\) is Kendall swap distance. The resulting society has mass \(\mu'_\pi=\sum_\sigma x_{\sigma,\pi}\). Candidate \(p\) wins when
\(\sum_{\pi:\,\pi(1)=p}\mu'_\pi \ge \sum_{\pi:\,\pi(1)=c}\mu'_\pi \] for every c\in C\).
To mirror the paper’s counting objective rather than merely its feasibility problem, define the conditional entropy of a transfer plan by
\[ H(x)= \sum_{\sigma:\mu_\sigma>0} \mu_\sigma \left( -\sum_{\pi} \frac{x_{\sigma,\pi}}{\mu_\sigma} \log \frac{x_{\sigma,\pi}}{\mu_\sigma} \right). \]
The continuous problem asks for a transfer plan \(x^\star\) maximizing \(H(x)\) subject to the swap-radius constraints and the requirement that \(p\) wins. It may equivalently output the robustness exponent
\[ \Lambda_p(\mu,\rho) = H_p(\mu,\rho)-H_{\mathrm{all}}(\mu,\rho), \]
where \(H_p\) is the maximum entropy among \(p\)-winning transfers and \(H_{\mathrm{all}}\) is the maximum without the winning constraint. An approximation version asks for these quantities within additive error \(\varepsilon\).
This is genuinely the high-multiplicity analogue of the paper’s count. Take \(N\) voters with \(N\mu_\sigma\) voters of each type and let \(r=N\rho\). For a transfer matrix \(x\), with \(Nx_{\sigma,\pi}\) integral, the number of labeled elections realizing that aggregate transfer is
\[ \prod_{\sigma} \frac{(N\mu_\sigma)!} {\prod_{\pi}(Nx_{\sigma,\pi})!}. \]
Stirling’s formula gives normalized logarithm \(H(x)+o(1)\). Consequently, the paper’s finite probability \(P_p(r)\) has exponential rate \(\Lambda_p(\mu,\rho)\). The continuous problem therefore asks what happens to the paper’s robustness count in the thermodynamic, high-multiplicity limit.
The regime is plausible outside the paper’s small university-department story: a national consultation, party primary, or large online electorate may contain millions of voters but only dozens or hundreds of recurring complete ranking types. The type includes every feature relevant to the problem; with unit prices, that is the ranking itself. A mass transfer represents a fraction of one ranking bloc experiencing each possible pattern of adjacent misranking. Rankings remain discrete; only population mass and aggregate perturbations are continuous.
I expect this mirror to be Class A. The winner constraints and swap-budget constraints are linear, while entropy maximization is a standard concave optimization problem. With the ranking types explicitly represented, both \(H_p\) and \(H_{\mathrm{all}}\) should admit polynomial-time additive approximation in the number of types, input bit length, and \(\log(1/\varepsilon)\). Thus the paper’s discrete \(\#\mathrm P\)-hardness can disappear at the macroscopic level, not because the election rule has been weakened, but because the object being computed has changed from an exact finite count to its high-multiplicity free-energy limit.
This also generates useful follow-up questions: whether the implicit \(m!\)-type version has an efficient pricing oracle; whether second-order terms recover the paper’s \(50\%\)-winner thresholds; whether the same entropy formulation works for Borda and shift-bribery; and whether nonuniform swap prices preserve convex tractability.
The weakest point is real: \(\Lambda_p\) captures only the exponential rate of the winning probability. If the winning and losing regions have equal entropy, it does not determine the limiting probability itself, so a referee wanting the paper’s exact \(P_p(r)\) would demand a second-order theory. Also, Theorem 1’s particular reduction is not itself a high-multiplicity construction. But the mirror is still faithful to the paper’s main object—probability of winning after a prescribed amount of random swapping—and gives that object a precise population-continuum limit with a nontrivial, tractable computational question.
The strongest negative case is that Theorem 1’s object is not intrinsically a population observable. It counts finite, labelled final elections uniformly on the exact-distance sphere. A continuous society \( \mu \) contains no canonical set of such microstates and no canonical uniform measure over them. The same \( \mu \) can represent \(N=10^3\) or \(N=10^9\) voters, with different exact counts and different probabilities \(P_p(r)\).
The proposed entropy \(H(x)\) repairs this only by adding a particular microscopic convention: voters of the same type remain individually labelled, and all assignments to final rankings are counted with multinomial weight. Thus \(H(x)\) is not supplied by the continuous society; it is the free energy of one chosen sequence of finite labelled models. Removing those labels makes the multinomial factor, and hence the entropy, disappear. Choosing volume, a Gibbs measure, or a different labelling convention produces a different “continuous” robustness problem.
The reduction behind Theorem 1 also does not itself support the claimed high-multiplicity interpretation. Its matching is encoded by distinct edge-voter ranking types. Repeating those types creates fractional flow rather than matching choices; retaining one type per edge leaves the population support essentially as detailed as the original instance. The theorem therefore supplies no evidence that its counting difficulty is meaningfully about repeated population mass.
A stronger repair would explicitly define the thermodynamic limit \(N\to\infty\), \(r=N\rho\), and declare the multinomial microcanonical measure part of the model. That is mathematically coherent, but it is then a new statistical-mechanical free-energy problem, not a continuous version of the paper’s \(P_p(r)\). The exponent \( \Lambda_p \) does not recover the finite winning probability or its \(50\%\)-robustness threshold when competing regions have equal entropy. Moreover, with the implicit type space \(S_m\), entropy maximization involves partition functions rather than the LP pricing oracle central to the continuization programme; polynomial solvability is therefore not established by “standard convex optimization.”
Still, this does not defeat the anchor completely. Large electorates with repeated ranking types are plainly plausible, and Theorem 1 is a genuine numbered computational result. The entropy limit is a defensible and potentially worthwhile new question. The honest negative verdict is therefore limited: the proponent has oversold it as a direct mirror and as an evidently tractable Class A problem, but I cannot honestly maintain the universal claim that no worthwhile continuous mirror exists. Theorem 1 survives.
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.