The paper reports a split result for formal election attacks. In its society-continuum model, several named attacks have polynomial-time algorithms. Yet constructive k-Approval-Swap Bribery in the discrete model is NP-complete for every fixed k at least 2 when costs are additively separable, nonnegative and rational, even under restricted cost values. General-cost Borda Swap Bribery remains conditionally hard in the continuum, including both its margin and ordinary formulations.
A mathematical electorate
The electorate here is not a finite list of named individuals. It is represented as a distribution of infinitely many infinitesimal agents divided into voter types. A vector records the population mass assigned to each type. Because the mass is divisible by design, the formal problems can move population between types rather than choosing changes from one fixed roll call of voters.
That setup is analyzed with a Configuration LP, a linear-programming formulation for possible configurations of voter types. Its dual has polynomially many variables but exponentially many constraints. The ellipsoid method and a separation oracle are used to solve the dual by testing the relevant constraints.
At the broadest level, the paper proves a polynomial-time result for a minimum-move problem when the winner condition meets a condition the authors call SPWR. The theorem applies to rational populations and finite costs, provided all finite-cost type-to-destination pairs can be enumerated in polynomial time. Those requirements define the theorem's scope.
Several attacks have polynomial-time algorithms
Several named combinations fall within the positive side of that boundary. In the continuum, Condorcet, scoring and Bucklin have polynomial-time algorithms under Shift Bribery. Condorcet-Bribery is also tractable, as are unit-cost Borda and Condorcet Swap Bribery. For every scoring protocol, Score-Bribery∞ is polynomial-time solvable when populations and prices are rational.
k-Approval produces a more qualified result. The continuum k-Approval Margin-Swap Bribery∞ problem has an XP algorithm parameterized by k and is polynomial-time solvable when k is fixed. In this classification, XP means the running-time exponent may depend on k, so the result does not establish fixed-parameter tractability when k is allowed to vary.
Cost rules matter
Cost structure is another dividing line. With additively separable swap costs, k-Approval-Swap Pricing is polynomial-time solvable using a dynamic program with O(mk) states. The same restriction yields a polynomial-time algorithm for continuum k-Approval Margin-Swap Bribery∞. The result does not cover all general cost functions.
The discrete counterpart is classified differently. For every fixed k at least 2, constructive k-Approval-Swap Bribery with additively separable nonnegative rational costs is NP-complete, even when every a_iv is restricted to 0 or 1 and every b_iv to 1 or 2. It is a worst-case complexity classification, not a measurement of how difficult real elections are to manipulate.
The hard cases remain
General swap costs expose a separate hard case. Borda Margin-Swap Bribery∞ in the continuum has no polynomial-time algorithm unless P = NP, even with a single voter type. The corresponding ordinary Borda-Swap Bribery∞ problem has the same conditional hardness. The statement therefore depends on the assumption that P and NP are not equal.
Parameterized complexity adds another barrier for k-Approval. k-Approval-Swap Pricing is W[1]-hard when k is the parameter, even when the preferred candidate starts in rank 1 and every pairwise swap cost is 0 or 1. The associated continuum k-Approval-Swap Bribery∞ problem cannot be solved in f(k) poly(L) time for any computable f unless FPT = W[1]. That running-time form allows computable dependence on k while keeping the remaining part polynomial in L.
A boundary inside a formal model
This is a formal modeling study, not an analysis of observed elections or human participants. Its instances specify candidate rankings, voter types, population masses, voting rules and move-cost functions, and its conclusions concern algorithms and complexity. The divisible-mass assumption means the findings do not establish how a particular finite electorate would behave.
The positive findings also have a narrow scope. The general minimum-move theorem requires SPWR, rational populations, finite costs and polynomial-time enumeration of finite-cost type-to-destination pairs. Other algorithmic results cover selected voting rules and cost models, while the hardness claims are conditional worst-case statements based on assumptions such as P not equaling NP and FPT not equaling W[1].
The document is an arXiv preprint dated 26 Aug 2026. Within the defined formal model, the case study draws a two-sided boundary: some continuum attacks have polynomial-time algorithms, while general-cost Borda and parameterized k-Approval cases retain hardness.
Paper data and sources
Original title: Continuous Computational Social Choice: A Case Study in Bribery
Authors: Martin Koutecký, Nikolaos Melissinos, Tung Anh Vu, Lluís Sabater
Journal/Repository: arXiv
Status: Preprint, not yet peer-reviewed
First online: 2026-08-26
DOI: Not available
Original paper · Full text