The computational difficulty of manipulating an election
From MaRDI portal
Publication:1824524
DOI10.1007/BF00295861zbMath0682.90007OpenAlexW2003296459MaRDI QIDQ1824524
Michael A. Trick, John J. III Bartholdi, Craig A. Tovey
Publication date: 1989
Published in: Social Choice and Welfare (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf00295861
Related Items (79)
The complexity of online bribery in sequential elections ⋮ Tennis manipulation: can we help Serena Williams win another tournament? Or can we control a knockout tournament with reasonable complexity? ⋮ Complexity of Safe Strategic Voting ⋮ Isomorphic Distances Among Elections ⋮ Algorithms for gerrymandering over graphs ⋮ Algorithms for the coalitional manipulation problem ⋮ On the difficulty of making social choices ⋮ Resolute control: forbidding candidates from winning an election is hard ⋮ Manipulation complexity of same-system runoff elections ⋮ Schulze and ranked-pairs voting are fixed-parameter tractable to bribe, manipulate, and control ⋮ Studies in Computational Aspects of Voting ⋮ The complexity of online manipulation of sequential elections ⋮ Vote trading in public elections ⋮ Computational complexity of manipulation: a survey ⋮ Dichotomy for voting systems ⋮ A quantitative Gobbard-Satterthwaite theorem without neutrality ⋮ The complexity of probabilistic lobbying ⋮ Voting schemes for which it can be difficult to tell who won the election ⋮ Normalized range voting broadly resists control ⋮ Comparing multiagent systems research in combinatorial auctions and voting ⋮ Complexity of control in judgment aggregation for uniform premise-based quota rules ⋮ Is it ever safe to vote strategically? ⋮ Byzantine preferential voting ⋮ Complexity of manipulation and bribery in judgment aggregation for uniform premise-based quota rules ⋮ Bounded incentives in manipulating the probabilistic serial rule ⋮ The shield that never was: societies with single-peaked preferences are more open to manipulation and control ⋮ On the complexity of achieving proportional representation ⋮ On the complexity of bribery and manipulation in tournaments with uncertain information ⋮ Pervasive domination ⋮ Efficient and accurate inference for mixtures of Mallows models with Spearman distance ⋮ Complexity of manipulation and bribery in premise-based judgment aggregation with simple formulas ⋮ Kernelization complexity of possible winner and coalitional manipulation problems in voting ⋮ A note on the complexity of manipulating weighted Schulze voting ⋮ Strategic voting in negotiating teams ⋮ The nonmanipulative vote-deficits of voting rules ⋮ Challenges to complexity shields that are supposed to protect elections against manipulation and control: a survey ⋮ Bribery in voting with CP-nets ⋮ Unnamed Item ⋮ Local distance constrained bribery in voting ⋮ Complexity of and algorithms for the manipulation of Borda, Nanson's and Baldwin's voting rules ⋮ Manipulation can be hard in tractable voting systems even for constant-sized coalitions ⋮ Popular ranking ⋮ Parameterized complexity of control problems in Maximin election ⋮ Is computational complexity a barrier to manipulation? ⋮ The complexity of manipulative attacks in nearly single-peaked electorates ⋮ Voting Procedures, Complexity of ⋮ Distance restricted manipulation in voting ⋮ On complexity of lobbying in multiple referenda ⋮ Control complexity in Borda elections: solving all open cases of offline control and some cases of online control ⋮ Complexity of manipulation with partial information in voting ⋮ On random social choice functions with the tops-only property ⋮ How hard is it to control an election? ⋮ Frugal bribery in voting ⋮ Computability of simple games: A characterization and application to the core ⋮ On the evaluation of election outcomes under uncertainty ⋮ Control complexity in Bucklin and fallback voting: a theoretical analysis ⋮ Control complexity in Bucklin and fallback voting: an experimental analysis ⋮ Computability of simple games: a complete investigation of the sixty-four possibilities ⋮ How to allocate review tasks for robust ranking ⋮ Cognitive hierarchy and voting manipulation in \(k\)-approval voting ⋮ Computer science and decision theory ⋮ Sincere-Strategy Preference-Based Approval Voting Broadly Resists Control ⋮ Human centered processes and decision support systems ⋮ Complexity of control by partitioning veto elections and of control by adding candidates to plurality elections ⋮ A new perspective on implementation by voting trees ⋮ Exact algorithms for weighted and unweighted Borda manipulation problems ⋮ Binary linear programming solutions and non-approximability for control problems in voting systems ⋮ Hybrid Elections Broaden Complexity-Theoretic Resistance to Control ⋮ Sincere-Strategy Preference-Based Approval Voting Fully Resists Constructive Control and Broadly Resists Destructive Control ⋮ A brief history of social choice and welfare theory ⋮ Computational Aspects of Approval Voting ⋮ Anyone but him: the complexity of precluding an alternative ⋮ Parameterized computational complexity of control problems in voting systems ⋮ The Nakamura numbers for computable simple games ⋮ Parameterized complexity of candidate control in elections and related digraph problems ⋮ Controlling sub-tournaments: easy or hard problem? Theoretical vs. practical analysis ⋮ Gibbard-Satterthwaite games for \(k\)-approval voting rules ⋮ Complexity of shift bribery for iterative voting rules ⋮ Structural control in weighted voting games
Cites Work
- Unnamed Item
- Unnamed Item
- Choice and complexity
- A simplified NP-complete satisfiability problem
- On effectively computable realizations of choice functions
- Voting schemes for which it can be difficult to tell who won the election
- Strategy-proofness and Arrow's conditions: existence and correspondence theorems for voting procedures and social welfare functions
- Manipulation of social choice functions
- The Voting Problem
- Manipulation of Voting Schemes: A General Result
This page was built for publication: The computational difficulty of manipulating an election
