The complexity of manipulative attacks in nearly single-peaked electorates

DOI10.1016/J.ARTINT.2013.11.004zbMATH Open1334.68098OpenAlexW1991113796MaRDI QIDQ490458FDOQ490458

Authors: Piotr Faliszewski, Edith Hemaspaandra, Lane A. Hemaspaandra 

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

Recommendations

• Computational aspects of nearly single-peaked electorates
• Manipulation of k-Approval in Nearly Single-Peaked Electorates
• Bypassing combinatorial protections: polynomial-time algorithms for single-peaked electorates
• The shield that never was: societies with single-peaked preferences are more open to manipulation and control
• Complexity of manipulative actions when voting with ties

zbMATH Keywords

multiagent systemscomputational social choicealgorithms and complexityelection controlelection manipulationnearly single-peaked preferences

Mathematics Subject Classification ID

History, political science (91F10) Social choice (91B14) Analysis of algorithms and problem complexity (68Q25) Agent technology and artificial intelligence (68T42)

Cites Work

• Social choice and individual values
• Title not available (Why is that?)
• Introduction to algorithms
• Title not available (Why is that?)
• Incidence matrices and interval graphs
• A Richer Understanding of the Complexity of Election Systems
• Polynomial-Time Bounded Truth-Table Reducibility of NP Sets to Sparse Sets
• When are elections with few candidates hard to manipulate?
• Anyone but him: the complexity of precluding an alternative
• Single transferable vote resists strategic voting
• How hard is it to control an election?
• The computational difficulty of manipulating an election
• Challenges to complexity shields that are supposed to protect elections against manipulation and control: a survey
• Search versus Decision for Election Manipulation Problems
• Multimode control attacks on elections
• Cloning in elections: finding the possible winners
• Swap bribery
• Llull and Copeland Voting Computationally Resist Bribery and Constructive Control
• How hard is bribery in elections?
• The shield that never was: societies with single-peaked preferences are more open to manipulation and control
• Dichotomy for voting systems
• Junta distributions and the average-case complexity of manipulating elections
• A comparison of polynomial time reducibilities
• Hybrid Elections Broaden Complexity-Theoretic Resistance to Control
• Average Case Complete Problems
• Sincere-Strategy Preference-Based Approval Voting Fully Resists Constructive Control and Broadly Resists Destructive Control
• Generalized juntas and NP-hard sets
• On reductions of NP sets to sparse sets
• Stable matching with preferences derived from a psychological model
• Classes of bounded nondeterminism
• Title not available (Why is that?)
• Eliciting single-peaked preferences using comparison queries
• Refining Nondeterminism in Relativized Polynomial-Time Bounded Computations
• Isomorphism Testing for Graphs, Semigroups, and Finite Automata are Polynomially Equivalent Problems
• Title not available (Why is that?)
• A Polynomial Time Algorithm for Unidimensional Unfolding Representations
• Complete sets and closeness to complexity classes

Cited In (22)

• The likelihood of single-peaked preferences under classic and new probability distribution assumptions
• Parameterized complexity of voter control in multi-peaked elections
• The control complexity of \(r\)-Approval: from the single-peaked case to the general case
• Recognizing single-peaked preferences on an arbitrary graph: complexity and algorithms
• On the likelihood of single-peaked preferences
• On the complexity of bribery with distance restrictions
• Are there any nicely structured preference profiles nearby?
• Title not available (Why is that?)
• Testing a mixture model of single-peaked preferences
• How hard is safe bribery?
• Exact algorithms for weighted and unweighted Borda manipulation problems
• Schulze and ranked-pairs voting are fixed-parameter tractable to bribe, manipulate, and control
• Manipulation can be hard in tractable voting systems even for constant-sized coalitions
• Campaign management under approval-driven voting rules
• The shield that never was: societies with single-peaked preferences are more open to manipulation and control
• Measuring nearly single-peakedness of an electorate: some new insights
• Combinatorial voter control in elections
• Challenges to complexity shields that are supposed to protect elections against manipulation and control: a survey
• Structured preferences: a literature survey
• Manipulation of k-Approval in Nearly Single-Peaked Electorates
• A characterization of the single-peaked single-crossing domain
• The complexity of controlling candidate-sequential elections

This page was built for publication: The complexity of manipulative attacks in nearly single-peaked electorates

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q490458)