| paper | Prices Matter for the Parameterized Complexity of Shift Bribery |
| authors | Bredereck, Chen, Faliszewski, Nichterlein, Niedermeier |
| 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 |
Proposition 3
statement extracted from the paper’s text layer
Given candidates \(C\), preferred candidate \(p\), rational society masses \(\mu_t\) over finitely many types \(t=(\succ_t,\pi_t)\), budget \(B\), and reach bound \(A\), does there exist rational mass \(y_{t,j}\geq0\) with \(\sum_j y_{t,j}=\mu_t\), \(\sum_{t,j}\pi_t(j)y_{t,j}\leq B\), and \(\sum_{t,j\geq1}y_{t,j}\leq A\), such that shifting \(p\) upward by \(j\) positions in mass \(y_{t,j}\) makes \(p\) a Borda co-winner?
A high-multiplicity Borda society over types consisting of a complete ranking and a shared rational shift-cost schedule, with variables \(y_{t,j}\) allocating type mass among shift lengths and linear cost, reach, and winner constraints.
The mirror covers the paper's Borda Shift Bribery results parameterized by affected voters and total unit shifts; it leaves its Maximin and Copeland results unaddressed.
Yes—the paper has a strong continuous mirror for Borda, particularly for its affected-voter hardness result. My lead anchor is Proposition 3 (proved in this paper’s appendix; it supplies the Borda case of Theorem 5): *Borda Shift Bribery parameterized by the number of affected voters is W[2]-hard for every considered price family.*
Call the continuous question Borda Reach-Shift Bribery\(_\infty\). An instance has candidates \(C\), preferred candidate \(p\), and a finite catalogue \(T\) of population types. A type \(t\) consists of a complete ranking \(\succ_t\) and a nondecreasing rational response-cost schedule \(\pi_t(j)\): the cost, per unit population, of moving \(p\) up exactly \(j\) places. The society is rational mass \(\mu_t\) on each type. Choose rational variables \(y_{t,j}\geq0\), where \(y_{t,j}\) is the mass of type \(t\) induced to shift \(p\) exactly \(j\) places, subject to \(\sum_j y_{t,j}=\mu_t\).
The question is whether there is such an action with
\[ \sum_{t,j}\pi_t(j)y_{t,j}\leq B,\qquad \sum_{t,j\geq1}y_{t,j}\leq A, \]
for which \(p\) is a Borda co-winner. Here \(A\) is campaign reach—the fraction of society whose ranking is changed—not a count of named people. A solution is the matrix \(y\); its induced post-campaign society puts \(y_{t,j}\) mass on the ranking obtained by shifting \(p\) up \(j\) positions in \(\succ_t\).
This is not a cosmetic rewording. Every Borda score after intervention is linear in \(y\), as are cost and affected mass, so this is an explicit rational LP with \(O(\tau m)\) variables and \(O(\tau+m)\) basic constraints. Thus I expect Class A: exact polynomial-time solvability in the explicit-type input size. Proposition 3’s Set Cover reduction relies on having to choose whole, atomic voters corresponding to sets. In the continuous version, a campaign can distribute reach fractionally across segments, precisely the relaxation one would want when “contact at most \(k\) people” becomes “reach at most \(A\%\) of the electorate.”
The regime is quite plausible, though it is not the paper’s most literal one-on-one bribery story. Think of a national campaign, product ranking, or public-information intervention with millions of recipients and a finite segmentation model. A type is, for example, “voters with this ranking and this measured response curve to a standardized campaign or product improvement.” Costs are per converted person within the segment, and mass is the segment’s population share. There may be millions of people but hundreds or thousands of ranking/response types. This is especially natural for the paper’s own non-corruption interpretations—campaign management, product development, or training—where standardized interventions are more credible than a bespoke price negotiation with every individual.
The discrete high-multiplicity dictionary is exact. If \(N\) agents occur in counts \(n_t\), set \(\mu_t=n_t/N\), restrict \(y_{t,j}\) to multiples of \(1/N\), and scale monetary quantities by \(1/N\). The original problem is recovered for populations whose members have the same ranking and price schedule within each type. Letting \(y\) be arbitrary rational mass is the high-multiplicity relaxation.
A secondary but compatible anchor is Theorem 1 (proved here): *Borda Shift Bribery parameterized by the total number \(t\) of unit shifts is in FPT for arbitrary price functions.* Its direct continuous counterpart is Borda Intensity-Shift Bribery\(_\infty\): use the same instance and variables, replace the reach constraint by
\[ \sum_{t,j} j\,y_{t,j}\leq S, \]
where \(S\) is total shift intensity per capita, and ask for a Borda-winning action within budget \(B\). It too is an LP, hence Class A. Theorem 1’s key observation survives exactly: total intensity raises \(p\)’s Borda score by that amount. The continuous result is stronger in one sense—ordinary polynomial time for the stated explicit-type model—but it is recognizably the same intervention question, with “number of positions shifted across voters” normalized into social mass.
I would not stretch this argument to the paper’s Maximin and Copeland results. Their winner conditions introduce different nonlinear or threshold-like structure, and the clean LP claim above is specifically a Borda case. Nor does this automatically settle compactly represented type spaces: if the type catalogue is implicit over permutations and response schedules, the relevant question becomes pricing/separation, rather than merely solving the displayed LP.
The weakest point is the price model. The paper emphasizes voter-specific prices, and a regime with nearly unique private response curves has \(\tau\approx n\), so continuization offers little compression. But that is not a defect in the mirror; it identifies the regime boundary. When intervention response is genuinely individualized, high multiplicity is not the right abstraction. When the campaign uses standardized treatments over recurring preference-and-response segments, it is—and the paper’s own anonymous election setting and non-bribery applications make that regime substantial rather than contrived.
The strongest negative case is only a scope warning, not a defeater. This paper’s central feature—voter-specific shift-price functions—often means that every person is effectively their own type. In that regime, a continuum formulation has no useful compression and the one-to-one negotiation story does not naturally become a mass-transfer problem.
But that does not establish the required universal claim. It cannot defeat either anchor.
For Proposition 3, the proponent’s type must include both the ranking and the complete response-cost schedule. That is exactly the right high-multiplicity type definition, not an illicit erasure of the paper’s prices. In a segmented campaign, standardized product-improvement programme, or training intervention, many people can genuinely share both. “Reach” as a fraction of the electorate is then an honest resource constraint, and splitting a segment across different induced rank changes is meaningful aggregate targeting. Borda’s outcome, costs, and changed mass all remain defined from the resulting distribution. The fact that bespoke bribery lacks this regime merely marks a boundary of applicability; it does not eliminate the plausible segmented regime.
Theorem 1 is weaker as motivation, because total unit shifts is a somewhat artificial discrete parameter: an average ordinal movement cap is less immediately observable than campaign reach or money. Still, it does not degenerate. A bound on aggregate rank improvement per capita can represent bounded persuasion intensity or bounded aggregate intervention effect, alongside the monetary budget. Once people occur in recurring response types, the same mass model is coherent.
Nor is it a valid objection that the proposed Borda formulations become straightforward finite LPs, or that they may retain all explicit types. The programme expressly permits tractable continuous mirrors and treats high multiplicity as the regime test, not as a promise of compression in every instance.
So I would not recommend a negative verdict. The paper’s personalized-price emphasis identifies an important regime where continuization is unhelpful, but Proposition 3 survives under a substantial and natural type-uniform intervention regime. One surviving anchor is enough.
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.