Source-linked AI summary
Continuous Computational Social Choice: A Case Study in Bribery
Martin Koutecký, Nikolaos Melissinos, Tung Anh Vu, Lluís Sabater
TL;DR
Computational social choice has largely modeled societies as discrete agents, leaving the complexity of its continuous counterpart unstudied. This paper initiates continuous computational social choice through election attacks and shows that many attacks become polynomial-time solvable, while some swap-bribery variants remain hard.
Problem
The complexity of modeling computational social choice with societies represented as continua of voter types has not previously been studied.
Method
The paper analyzes election attacks in the society continuum using continuous and discrete optimization, including Configuration LPs, separation oracles, and dynamic programming.
Results
A broad class of continuum election attacks is polynomial-time solvable, including scoring-rule bribery and several shift- and swap-bribery variants, while general-cost Borda and k-Approval swap bribery remain hard.
Takeaways & Limitations
The society-continuum model provides a tractable framework for several election attacks and motivates broader study of continuous computational social choice.
Takeaways & Limitations
The Configuration LP theorem does not apply directly to bribery because a bribed voter may move to any of the m! rankings, making the number of output rankings unbounded.
Abstract
from arXiv · showhide
Computational social choice seeks algorithmic answers to questions about preference aggregation, safety of elections, robustness of outcomes, stability, etc. It overwhelmingly models societies as composed of discrete agents. We propose to study computational social choice problems in a society continuum} setting, where a society is modeled as a distribution of infinitely many infinitesimal agents of different types. An analogous approach has been very useful in physics (it is the basis of statistical mechanics), economics (mean field games), and other fields. As an initial case study, we focus on election attacks (bribery and control), which have been extensively studied in the discrete setting. We show that a broad class of standard election attacks becomes polynomial-time solvable in the society continuum. The class contains problems that are NP-hard discretely, among them Borda- and Bucklin-CCDV and unit-cost Borda-SWAP BRIBERY. Furthermore, we give polynomial-time algorithms for $k$-Approval-SWAP BRIBERY when $k$ is constant for general costs, and when $k$ varies and the cost function is additively separable. The latter result contrasts with the discrete problem, which we prove NP-complete for additively separable costs and every fixed $k\ge 2$. In contrast, we prove that Borda-SWAP BRIBERY and $k$-Approval-SWAP BRIBERY, both with general costs, remain computationally hard in the society continuum. To obtain these results, we use both continuous and discrete optimization techniques, such as the Configuration LP framework and dynamic programming. Of particular note is the technique underlying our hardness proofs, which shows how to ''reverse the flow of hardness'' between LP formulations and pricing problems.
1 Introduction
The paper introduces continuous computational social choice, modeling elections as distributions of infinitely many infinitesimal voter types, and studies how this shift changes the complexity of election attacks. It develops Configuration-LP-based algorithms and matching hardness results for bribery and control problems in the society continuum.
- Model and motivation: The framework initiates computational-complexity research on continuous modeling in social choice through a first case study of election attacks.The perspective is motivated by analogous continuum approaches in statistical mechanics, economics, and other fields.
- Model and motivation: Continuous computational social choice replaces discrete electorates with voter-type distributions, allowing attackers to move arbitrary fractions of mass between types.The model is presented as a continuum limit of increasingly large elections with fixed type ratios.
- Techniques: The Configuration LP is the central technique: tractable pricing problems yield tractable attacks, while the paper develops arguments transferring pricing hardness to attack hardness.The underlying formulations have exponentially many variables but polynomially many constraints, and the pricing problems have polynomially many variables.
- Tractable cases: A broad class of continuum attacks is polynomial-time solvable, including scoring protocols, Condorcet’s rule, and Bucklin’s rule under Shift Bribery and CCDV.These results translate attacks into polynomially many polynomial-size linear programs.
- Results and boundaries: For continuum bribery, Borda-Shift Bribery and unit-cost Borda-Swap Bribery are polynomial-time solvable, whereas general-cost Borda-Swap Bribery is NP-hard.For k-Approval-Swap Bribery, the paper gives an XP algorithm with running time m^O(k) poly(L), polynomial for constant k, but general costs are unlikely to admit an FPT algorithm.
- Results and boundaries: The results use margin versions of the attacks, and with general costs margin requirements can be encoded using gadgets of unbribable voter types.The margin formulation requires the preferred candidate to beat every opponent by a prescribed margin rather than merely tie.
2 Preliminaries
The paper formalizes continuous elections through voter types, population-mass moves, and succinct polyhedral winner conditions. It establishes that positional scoring rules, weak Condorcet, and a boundary-inclusive Bucklin variant fit SPWR, while Copeland and strict-majority Bucklin do not.
- Elections: An election has candidates and voters represented by preference rankings, and the paper adopts the co-winner convention using non-strict inequalities.A voter may also be inactive, represented by ∅.
- Voter Types and Societies: A voter type is an initial ranking paired with a move-cost function, while a society records the nonnegative population mass of each type.Leaving mass at its initial ranking has zero cost.
- Bribery Actions as Moves: A bribery move redistributes each type’s mass among rankings subject to row-marginal feasibility, with Swap Bribery costs summing pairwise inversion costs.Allowed destinations are rankings reachable at finite cost, and move-cost functions have succinct O(m^2)-number encodings computable in poly(m) time.
- Winning Conditions: SPWR winning conditions are unions of polynomially many polyhedral regions with polynomial-size linear systems and efficiently computable restrictions to ranking subsets.Every positional scoring rule and weak-Condorcet rule is SPWR, as is the boundary-inclusive Bucklin variant, whereas Copeland is not.
- Bucklin: The boundary-inclusive Bucklin variant preserves closed winner regions, unlike strict-majority Bucklin, where an arbitrarily small shift can win at cost 2ε without a minimum-cost move.The variant coincides with the standard rule whenever no support equals the threshold exactly.
3 Positive Results
The section establishes polynomial-time solvability for broad classes of continuum election attacks using succinct winner regions, configuration LPs, and dynamic programming. It covers several attacks that are hard discretely, including scoring-rule bribery and unit-cost Borda-Swap Bribery, while also giving tractability results for k-Approval variants under specified costs.
- Succinct Winner Regions: a Polynomial-Size LP: SPWR winning conditions yield a polynomial-time algorithm for Minimum Move∞ when populations and finite costs are rational.The running time is poly(m, τ, T, L), assuming finite-cost type–destination pairs can be enumerated within that bound.
- Succinct Winner Regions: a Polynomial-Size LP: Theorem 1 also applies when winner regions are represented by polynomial-size extended formulations rather than explicit linear systems.Auxiliary variables are added to the LP, potentially extending applicability to more voting rules.
- Succinct Winner Regions: a Polynomial-Size LP: Condorcet, Score, and Bucklin Shift Bribery and CCDV, Condorcet-Bribery, and unit-cost Borda- and Condorcet-Swap Bribery are solvable in poly(m, τ, L) time.Unit-cost optimal moves use only shifts of the preferred candidate, bounding allowed outputs by O(mτ).
- Configuration LPs: Score-Bribery∞: For every scoring protocol, Score-Bribery∞ is solvable in polynomial time despite allowing all m! destination rankings.A configuration-LP pricing problem reduces to sorting opponents by dual variables, and the resulting separation oracle supports ellipsoid optimization.
- k-Approval Swap Bribery: k-Approval Margin-Swap Bribery∞ is solvable in m^O(k) poly(L) time, including additively separable swap costs.For additively separable costs, the pricing problem uses an O(mk) dynamic program with O(mk) states.
4 Hardness Results
The section establishes hardness results contrasting discrete and continuum swap bribery. It proves NP-completeness for additively separable discrete k-Approval and derives continuum hardness for Borda and k-Approval with general costs via pricing reductions.
- Hardness framework: The hardness framework reverses the usual implication by showing that hard pricing can imply hard bribery through a bridge lemma.Separation is reducible to polynomially many calls to the pricing algorithm, while feasibility and optimization over the relevant polyhedron provide the needed certificates.
- Discrete hardness: For every fixed k≥2, constructive k-Approval-Swap Bribery with additively separable nonnegative rational costs is NP-complete in discrete electorates.The result holds even under additional restrictions on the cost arrays.
- Borda: Borda-Swap Bribery∞ has no polynomial-time algorithm unless P=NP, even when only a single voter type is bribable and under polynomial-time Turing reductions.The proof encodes an NP-hard separation problem in the dual of the Borda margin formulation, then transfers margin hardness to ordinary bribery.
- k-Approval: k-Approval-Swap Pricing is W[1]-hard parameterized by k, even with rankσ(c∗)=1 and pairwise swap costs restricted to 0 or 1.The reduction uses k=r+1 and relates the optimum value to whether a graph contains a clique of size r.
- k-Approval: Unless FPT=W[1], k-Approval-Swap Bribery∞ cannot be solved in time f(k) poly(L) for any computable f.A polynomial-time padding construction converts margin-winner instances into winner instances while preserving budgets and finite-cost moves.
5 Future Work
The society continuum is proposed as a broader scientific program beyond bribery, with open questions about tractability, discrete embedding, and continuum-specific hardness. Future work also includes extending the framework across voting and other computational social choice domains.
- 5 Future Work: The society continuum applies to problems with populations of discrete agents partitionable into meaningful types, not only bribery.Future studies can ask whether the continuum makes each problem tractable, embeds its discrete version, or creates new hardness.
- 5 Future Work: Open voting directions include resolving Table 1’s question marks, candidate control, further cost models, and additional voting rules.Copeland is a framework-limit test because its winner regions are unions of exponentially many polyhedra, outside the obvious reach of Theorem 1 and Configuration LP.
- 5 Future Work: Discrete LP/IP proximity results can leave only f(m,τ) voters undecided, yielding kernels and additive OPT + f(m,τ) approximations when n≫m,τ.The open question is when this transfer works, when it stops, and why.
- 5 Future Work: The continuous variants of matching under preferences, coalition formation, and fair division are meaningful and computationally wide open.These areas extend the society continuum beyond voting to domains whose discrete formulations use discrete agent populations.
Funding
The authors acknowledge partial support from Charles University, Czech Republic’s Ministry of Education, the Czech Science Foundation, and specific university projects.
- Funding: The authors received partial funding from Charles University projects, the ERC-CZ project LL2406, and GA ČR project 25-17221S.Koutecký, Melissinos, Vu, and Sabater are supported by project 25-17221S; Koutecký and Melissinos also receive Charles University project support.