The shield that never was: societies with single-peaked preferences are more open to manipulation and control

Redirect to:

• The shield that never was: societies with single-peaked preferences are more open to manipulation and control

DOI10.1016/J.IC.2010.09.001MaRDI QIDQ627120zbMATH OpenOpenAlexFDO

Authors Piotr Faliszewski, Edith Hemaspaandra, Jörg Rothe, Lane A. Hemaspaandra

Publication date 21 February 2011

Published in Information and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ic.2010.09.001

zbMATH Keywords

algorithmscomplexity theorycomputational social choicecontrol and manipulation of electionsmultiagent systemspreference aggregation

Mathematics Subject Classification ID

Social choice (91B14)

Recommendations

• The complexity of manipulative attacks in nearly single-peaked electorates
• Bypassing combinatorial protections: polynomial-time algorithms for single-peaked electorates
• Challenges to complexity shields that are supposed to protect elections against manipulation and control: a survey
• Manipulation of k-Approval in Nearly Single-Peaked Electorates
• Modeling single-peakedness for votes with ties

Cites work

• A characterization of the single-peaked domain
• A heuristic technique for multi-agent planning
• A Polynomial Time Algorithm for Unidimensional Unfolding Representations
• A Richer Understanding of the Complexity of Election Systems
• An introduction to strategy-proof social choice functions
• Anyone but him: the complexity of precluding an alternative
• Bypassing combinatorial protections: polynomial-time algorithms for single-peaked electorates
• Computational Aspects of Approval Voting
• Constant scoring rules, Condorcet criteria and single-peaked preferences
• Dichotomy for voting systems
• Eliciting single-peaked preferences using comparison queries
• How hard is bribery in elections?
• How hard is it to control an election?
• scientific article; zbMATH DE number 3148878 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Hybrid Elections Broaden Complexity-Theoretic Resistance to Control
• Incidence matrices and interval graphs
• Junta distributions and the average-case complexity of manipulating elections
• Llull and Copeland Voting Computationally Resist Bribery and Constructive Control
• Recognizing single-peaked preferences on a tree
• Sincere-Strategy Preference-Based Approval Voting Fully Resists Constructive Control and Broadly Resists Destructive Control
• Single transferable vote resists strategic voting
• Stable matching with preferences derived from a psychological model
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• The computational difficulty of manipulating an election
• The shield that never was: societies with single-peaked preferences are more open to manipulation and control
• Voting cycles and the structure of individual preferences
• When are elections with few candidates hard to manipulate?

Cited in

(33)

• Anyone but him: the complexity of precluding an alternative
• Optimal defense against election control by deleting voter groups
• On the likelihood of single-peaked preferences
• On the complexity of bribery with distance restrictions
• Towards a dichotomy for the possible winner problem in elections based on scoring rules
• A parameterized perspective on protecting elections
• Structured preferences: a literature survey
• A characterization of the single-peaked single-crossing domain
• Control complexity in Borda elections: solving all open cases of offline control and some cases of online control
• Control complexity in Bucklin and fallback voting: a theoretical analysis
• Parameterized complexity of voter control in multi-peaked elections
• Combinatorial voter control in elections
• The control complexity of \(r\)-Approval: from the single-peaked case to the general case
• Challenges to complexity shields that are supposed to protect elections against manipulation and control: a survey
• Are there any nicely structured preference profiles nearby?
• Group control for consent rules with consecutive qualifications
• Bypassing combinatorial protections: polynomial-time algorithms for single-peaked electorates
• The complexity of priced control in elections
• Normalized range voting broadly resists control
• Manipulation can be hard in tractable voting systems even for constant-sized coalitions
• The complexity of manipulative attacks in nearly single-peaked electorates
• Single-peaked consistency for weak orders is easy
• Campaign management under approval-driven voting rules
• Exact algorithms for weighted and unweighted Borda manipulation problems
• Complexity of manipulation and bribery in premise-based judgment aggregation with simple formulas
• Resilient heuristic aggregation of judgments in the pairwise comparisons method
• Structure of single-peaked preferences
• The shield that never was: societies with single-peaked preferences are more open to manipulation and control
• Is computational complexity a barrier to manipulation?
• Recovering single-crossing preferences from approval ballots
• Recognizing and eliciting weakly single crossing profiles on trees
• How to tamper with a parliament: strategic campaigns in apportionment elections
• Strategic candidacy with reluctance

This page was built for publication: The shield that never was: societies with single-peaked preferences are more open to manipulation and control

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