Hybrid Elections Broaden Complexity-Theoretic Resistance to Control

DOI10.1002/malq.200810019zbMath1177.91066arXivcs/0608057OpenAlexW2037659828MaRDI QIDQ3392307

Edith Hemaspaandra, Hemaspaandra, Lane A., Jörg Rothe

Publication date: 14 August 2009

Published in: Mathematical Logic Quarterly (Search for Journal in Brave)

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

zbMATH Keywords

complexitycomputational complexitymanipulabilitymulti-agent systemscomputational social choicepreference aggregationvoting system

Mathematics Subject Classification ID

Voting theory (91B12) Individual preferences (91B08) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Social choice (91B14)

Related Items (20)

The complexity of online bribery in sequential elections ⋮ Studies in Computational Aspects of Voting ⋮ Optimal defense against election control by deleting voter groups ⋮ The complexity of probabilistic lobbying ⋮ The complexity of computing minimal unidirectional covering sets ⋮ Normalized range voting broadly resists control ⋮ Complexity of control in judgment aggregation for uniform premise-based quota rules ⋮ The shield that never was: societies with single-peaked preferences are more open to manipulation and control ⋮ Challenges to complexity shields that are supposed to protect elections against manipulation and control: a survey ⋮ Manipulation can be hard in tractable voting systems even for constant-sized coalitions ⋮ Is computational complexity a barrier to manipulation? ⋮ The complexity of manipulative attacks in nearly single-peaked electorates ⋮ Voting Procedures, Complexity of ⋮ Control complexity in Bucklin and fallback voting: a theoretical analysis ⋮ Complexity of control by partitioning veto elections and of control by adding candidates to plurality elections ⋮ A parameterized perspective on protecting elections ⋮ Binary linear programming solutions and non-approximability for control problems in voting systems ⋮ Hybrid Elections Broaden Complexity-Theoretic Resistance to Control ⋮ Computational Aspects of Approval Voting ⋮ Anyone but him: the complexity of precluding an alternative

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The complexity of Kemeny elections
• Guarantees for the success frequency of an algorithm for finding Dodgson-election winners
• Approximability of Dodgson's rule
• Anyone but him: the complexity of precluding an alternative
• 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
• Extending Condorcet's rule
• Boolean operations, joins, and the extended low hierarchy
• Exact complexity of the winner problem for Young elections
• The computational difficulty of manipulating an election
• Strategic manipulability without resoluteness or shared beliefs: Gibbard-Satterthwaite generalized
• Hybrid Elections Broaden Complexity-Theoretic Resistance to Control
• Sincere-Strategy Preference-Based Approval Voting Fully Resists Constructive Control and Broadly Resists Destructive Control
• Bounded Query Classes
• Copeland Voting Fully Resists Constructive Control
• When are elections with few candidates hard to manipulate?
• Sincere-Strategy Preference-Based Approval Voting Broadly Resists Control
• Llull and Copeland Voting Computationally Resist Bribery and Constructive Control
• How Hard Is Bribery in Elections?
• Average Case Complete Problems
• Sparse Sets, Lowness and Highness
• The Boolean Hierarchy I: Structural Properties
• Manipulation of Voting Schemes: A General Result
• A Consistent Extension of Condorcet’s Election Principle
• Exact analysis of Dodgson elections
• A Richer Understanding of the Complexity of Election Systems
• Algorithms and Computation

This page was built for publication: Hybrid Elections Broaden Complexity-Theoretic Resistance to Control