Manipulation can be hard in tractable voting systems even for constant-sized coalitions

DOI10.1016/j.cosrev.2012.03.001zbMath1298.68101arXiv1108.4439MaRDI QIDQ465694

Curtis Menton, Preetjot Singh

Publication date: 24 October 2014

Published in: Computer Science Review (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1108.4439

zbMATH Keywords

complexity; voting theory; computational social choice; manipulation

Mathematics Subject Classification ID

91B12: Voting theory

68-02: Research exposition (monographs, survey articles) pertaining to computer science

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

91B14: Social choice

Related Items

Schulze and ranked-pairs voting are fixed-parameter tractable to bribe, manipulate, and control

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Complexity of and algorithms for the manipulation of Borda, Nanson's and Baldwin's voting rules
• The complexity of manipulative attacks in nearly single-peaked electorates
• Campaign management under approval-driven voting rules
• Independence of clones as a criterion for voting rules
• A characterization of the single-peaked domain
• The shield that never was: societies with single-peaked preferences are more open to manipulation and control
• A simplified NP-complete satisfiability problem
• The complexity of Kemeny elections
• Algorithms for the coalitional manipulation problem
• Dichotomy for voting systems
• Voting schemes for which it can be difficult to tell who won the election
• Single transferable vote resists strategic voting
• How hard is it to control an election?
• Strategy-proofness and Arrow's conditions: existence and correspondence theorems for voting procedures and social welfare functions
• Manipulation of social choice functions
• The Borda method is most likely to respect the Condorcet principle
• The computational difficulty of manipulating an election
• How large should a coalition be to manipulate an election?
• Strategic manipulability without resoluteness or shared beliefs: Gibbard-Satterthwaite generalized
• Minimizing makespan in a two-machine flow shop with delays and unit-time operations is NP-hard
• Why the Count de Borda cannot beat the Marquis de Condorcet
• Critical Behavior in the Satisfiability of Random Boolean Expressions
• Stability in Voting
• Hybrid Elections Broaden Complexity-Theoretic Resistance to Control
• When are elections with few candidates hard to manipulate?
• Swap Bribery
• Llull and Copeland Voting Computationally Resist Bribery and Constructive Control
• How Hard Is Bribery in Elections?
• Manipulation of Voting Schemes: A General Result
• Manipulation of Schemes that Mix Voting with Chance
• Straightforwardness of Game Forms with Lotteries as Outcomes
• A Consistent Extension of Condorcet’s Election Principle
• Exact analysis of Dodgson elections
• Social Choice Scoring Functions
• Aggregation of Preferences with Variable Electorate
• A theory of measuring, electing, and ranking
• The subgraph homeomorphism problem
• Quasi-Transitivity, Rational Choice and Collective Decisions
• Financial Cryptography and Data Security