| paper | Swap Bribery |
| authors | Elkind, Faliszewski, Slinko |
| venue | control |
| filed under | voting · bribery-control |
| judged by | gpt-5.6-terra / high (triple__gpt-5.6-terra__high__ctx2r8-rejudge1) |
| judge confidence | high |
| authors would recognise it | yes |
Theorem 5.1
statement extracted from the paper’s text layer
Given candidates \(C\), a target \(p\), rational masses \(\mu_t\) over finitely many types \(t\), each with ranking \(r_t\) and shift-cost menu \(\rho_t(\ell)\), choose masses \(y_{t,\ell}\geq0\) with \(\sum_{\ell}y_{t,\ell}=\mu_t\) minimizing \(\sum_{t,\ell}\rho_t(\ell)y_{t,\ell}\), subject to \(p\) being a Borda winner after each mass \(y_{t,\ell}\) is shifted by \(\ell\) positions.
Borda-Shift Campaign\(_\infty\): voter types carry an initial ranking and common shift-response costs; decision variables allocate type mass among shifts, and the objective is minimum campaign cost subject to aggregate Borda victory for \(p\).
Independent linear per-unit response costs omit campaign saturation, spillovers, and correlated responses across voter segments.
fatal: False
The primary mirror covers Theorem 5.1; the complementary swap mirror covers Theorem 4.1. It leaves the paper's remaining rule-specific results, including Theorem 4.5, unclaimed.
The cleanest positive case is Borda shift bribery, anchored in Theorem 5.1, proved in this paper: *Shift bribery for Borda is NP-complete*. I would make this the lead mirror.
Call the continuous problem Borda-Shift Campaign\(_\infty\). An instance has candidates \(C\), target \(p\), and a finite set of voter types \(T\). A type \(t\) specifies a complete ranking \(r_t\) and a shift-price function \(\rho_t(\ell)\): the per-unit cost of moving \(p\) up \(\ell\) places for a member of that type. The society is rational mass \(\mu_t\) over types. We choose nonnegative masses \(y_{t,\ell}\), with \(\sum_\ell y_{t,\ell}=\mu_t\): \(y_{t,\ell}\) is the fraction of type \(t\) reached by a campaign that shifts \(p\) by \(\ell\) positions. The cost is
\[ \sum_{t,\ell}\rho_t(\ell)y_{t,\ell}. \]
The resulting Borda score of each candidate is the corresponding linear combination of the Borda scores in the shifted rankings. The question is to find minimum-cost \(y\) making \(p\) a winner (or, equivalently, decide whether this is possible within a given budget).
This is not merely a renamed fractional version. It matches the paper’s own campaign reading particularly well: a campaign manager does not naturally say “persuade voters 17, 381, and 12,008”; they allocate effort across groups with the same initial ranking and response profile. A plausible regime is a large election or referendum campaign with millions of potential voters, partitioned into perhaps hundreds or thousands of empirically meaningful segments—same intended ballot, demographic/media environment, and estimated response curve to a pro-\(p\) message. The number of people is vastly larger than the number of such types. The price function is then a property of a type because it describes the common intervention required for that segment, exactly as high multiplicity intends.
Unlike discrete Theorem 5.1, this continuous question is a polynomial-size LP: there are only \(|T|\cdot m\) action variables. I therefore expect Class A, exact tractability. The X3C combinatorics in the discrete proof are the need to choose whole voters/sets; the continuous campaign can split effort across a segment. This makes Theorem 5.1 an especially persuasive example of continuization revealing an optimization problem that the original discrete formulation hides behind integrality. The paper’s Theorem 5.2, also proved here, gives a discrete 2-approximation; that is useful corroboration that the authors themselves see Borda shift bribery as an optimization problem, rather than only a hardness construction.
A second, complementary mirror is justified by Theorem 4.1, proved here: for every fixed \(k\geq3\), swap bribery for \(k\)-approval is NP-complete even when swap costs lie in \(\{0,1,2\}\).
Call it \(k\)-Approval-Swap Campaign\(_\infty\). A type \(t\) consists of an initial ranking \(r_t\) and the paper’s adjacent-swap cost function \(\pi_t(a,b)\), with mass \(\mu_t\). For every final ranking \(q\), let
\[ d_t(q)=\sum_{(a,b)\text{ inverted from }r_t\text{ to }q}\pi_t(a,b), \]
which is exactly the cheapest transformation cost by Proposition 3.2. Choose \(x_{t,q}\geq0\), the mass of type \(t\) transformed into ranking \(q\), subject to \(\sum_qx_{t,q}=\mu_t\). The objective is \(\sum_{t,q}d_t(q)x_{t,q}\), and \(p\) must have at least every other candidate’s \(k\)-approval score in the resulting distribution.
This is a genuine exponential-column LP, not an artificially simplified model: the output rankings remain all \(m!\) rankings, and the question remains whether targeted local preference changes can elect \(p\). Its natural regime is again a large campaign, but one that may influence comparative messages among several candidates rather than solely promote \(p\). Types bundle a ballot intention with a common estimated matrix of pairwise message costs.
I expect this second mirror to be Class A as well. Its pricing problem is precisely of the form highlighted by the continuization programme: optimize a top-\(k\) score contribution against an additively separable inversion cost over permutations. The programme’s stated \(k\)-Approval-Swap Pricing result is polynomial for such costs, which should unlock the LP through separation/column generation. Theorem 4.1’s discrete X3C hardness is therefore not a reason to reject the mirror; it is evidence that the continuous model is testing a meaningful relaxation of a genuinely difficult problem.
I would not try to mirror all of the paper. In particular, Theorem 4.5—NP-completeness for variable-\(k\) \(k\)-approval swap bribery even with one voter—is a warning that some candidate-side combinatorics may survive population continuization, but it is not needed for the affirmative case. Nor does this argument claim to settle continuous Borda *swap* bribery, whose permutation pricing can be substantially harder.
The soft spot is indivisibility. Literal vote buying, ballot alteration, or a small committee is poorly represented by fractional mass: one cannot bribe 0.03 of an identified person. The case survives because the paper expressly includes campaigning, and large-scale campaign intervention is the scenario where group-level fractions, rather than named voters, are the honest quantities. It also assumes linear per-unit intervention costs within a type; saturation or network effects would require richer types or a nonlinear extension. Those are real modeling limits, not objections to the high-multiplicity mirrors above.
I cannot honestly defeat the two anchors. The negative case is weak precisely where it needs to be universal.
For Theorem 5.1, Borda shift bribery has an unusually clean high-multiplicity interpretation. The original paper itself treats shift bribery as campaigning for the preferred candidate. In a large electorate, a type can naturally contain a ballot intention together with a common response/cost curve for a pro-\(p\) intervention; allocating campaign effort to a fraction of such a segment is meaningful. Nothing in the Borda objective tracks identities, and no essential feature vanishes when each voter is replaced by mass. The best objection is empirical rather than fundamental: real campaigns have saturation, spillovers, and correlated responses, so independently applying a linear per-unit shift menu to arbitrary fractions of every segment is stylized. But that is a limitation of one intervention model, not a reason that the high-multiplicity Borda-shift problem is not a sensible object. Those effects can also be excluded in a legitimate regime of independently targetable, broadly similar voters.
Theorem 4.1 is harder still to reject. Its \(k\)-approval swap version is essentially the programme’s representative R-Swap Bribery setup: rankings are types, adjacent-pair costs define the cost of changing a type, and the outcome condition is determined solely by aggregate masses. A broad comparative campaign—or an aggregate correction/noise model—gives a plausible interpretation for type-level local ranking changes. The proponent’s final-ranking formulation does not smuggle in identity information: it simply records what fraction of a homogeneous type receives each attainable transformation. The fact that a realistic public campaign may jointly affect several types is again a motivation for richer coupled models, not a basis for declaring this independent-intervention mirror worthless.
One could object that literal ballot tampering and person-specific vote buying are inherently discrete. That is true, but it does not survive the paper’s own campaign interpretation, nor the task’s requirement to consider a better scenario than the paper’s immediate story. Likewise, arbitrary voter-specific price functions do not block high multiplicity: they describe a heterogeneous regime, whereas the continuous instance deliberately groups agents with the same relevant response profile.
So the strongest negative recommendation is not to reject this paper. At most, one should insist that any resulting work state its regime carefully: large, segmentable electorates with additive per-person intervention costs, not small committees, identified bribe recipients, or a single undifferentiated mass-public campaign. But either Theorem 5.1 alone, and even more clearly Theorem 4.1, survives that qualification.
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.