The complexity of manipulative attacks in nearly single-peaked electorates
From MaRDI portal
Publication:490458
DOI10.1016/j.artint.2013.11.004zbMath1334.68098OpenAlexW1991113796MaRDI QIDQ490458
Edith Hemaspaandra, Piotr Faliszewski, Hemaspaandra, Lane A.
Publication date: 27 August 2015
Published in: Artificial Intelligence (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.artint.2013.11.004
multiagent systemscomputational social choicealgorithms and complexityelection controlelection manipulationnearly single-peaked preferences
Analysis of algorithms and problem complexity (68Q25) History, political science (91F10) Social choice (91B14) Agent technology and artificial intelligence (68T42)
Related Items
The likelihood of single-peaked preferences under classic and new probability distribution assumptions, Are there any nicely structured preference profiles nearby?, Schulze and ranked-pairs voting are fixed-parameter tractable to bribe, manipulate, and control, Testing a mixture model of single-peaked preferences, The control complexity of \(r\)-Approval: from the single-peaked case to the general case, A characterization of the single-peaked single-crossing domain, How hard is safe bribery?, On the likelihood of single-peaked preferences, Challenges to complexity shields that are supposed to protect elections against manipulation and control: a survey, Unnamed Item, On the complexity of bribery with distance restrictions, Manipulation can be hard in tractable voting systems even for constant-sized coalitions, Campaign management under approval-driven voting rules, The complexity of controlling candidate-sequential elections, Recognizing single-peaked preferences on an arbitrary graph: complexity and algorithms, Exact algorithms for weighted and unweighted Borda manipulation problems, Parameterized complexity of voter control in multi-peaked elections, Structured preferences: a literature survey, Combinatorial voter control in elections
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The shield that never was: societies with single-peaked preferences are more open to manipulation and control
- Generalized juntas and NP-hard sets
- Dichotomy for voting systems
- Anyone but him: the complexity of precluding an alternative
- Single transferable vote resists strategic voting
- How hard is it to control an election?
- A comparison of polynomial time reducibilities
- On reductions of NP sets to sparse sets
- Stable matching with preferences derived from a psychological model
- The computational difficulty of manipulating an election
- Incidence matrices and interval graphs
- Challenges to complexity shields that are supposed to protect elections against manipulation and control: a survey
- Search versus Decision for Election Manipulation Problems
- Classes of bounded nondeterminism
- Multimode Control Attacks on Elections
- Hybrid Elections Broaden Complexity-Theoretic Resistance to Control
- Sincere-Strategy Preference-Based Approval Voting Fully Resists Constructive Control and Broadly Resists Destructive Control
- When are elections with few candidates hard to manipulate?
- Swap Bribery
- Eliciting Single-Peaked Preferences Using Comparison Queries
- Llull and Copeland Voting Computationally Resist Bribery and Constructive Control
- How Hard Is Bribery in Elections?
- Average Case Complete Problems
- Refining Nondeterminism in Relativized Polynomial-Time Bounded Computations
- Polynomial-Time Bounded Truth-Table Reducibility of NP Sets to Sparse Sets
- Isomorphism Testing for Graphs, Semigroups, and Finite Automata are Polynomially Equivalent Problems
- A Polynomial Time Algorithm for Unidimensional Unfolding Representations
- Complete sets and closeness to complexity classes
- A Richer Understanding of the Complexity of Election Systems
