Hybrid Elections Broaden Complexity-Theoretic Resistance to Control
From MaRDI portal
Publication:3392307
DOI10.1002/MALQ.200810019zbMATH Open1177.91066arXivcs/0608057OpenAlexW2037659828MaRDI QIDQ3392307FDOQ3392307
Authors: Edith Hemaspaandra, Lane A. Hemaspaandra, Jörg Rothe 
Publication date: 14 August 2009
Published in: Mathematical Logic Quarterly (Search for Journal in Brave)
Abstract: Electoral control refers to attempts by an election's organizer ("the chair") to influence the outcome by adding/deleting/partitioning voters or candidates. The groundbreaking work of Bartholdi, Tovey, and Trick [BTT92] on (constructive) control proposes computational complexity as a means of resisting control attempts: Look for election systems where the chair's task in seeking control is itself computationally infeasible. We introduce and study a method of combining two or more candidate-anonymous election schemes in such a way that the combined scheme possesses all the resistances to control (i.e., all the NP-hardnesses of control) possessed by any of its constituents: It combines their strengths. From this and new resistance constructions, we prove for the first time that there exists an election scheme that is resistant to all twenty standard types of electoral control.
Full work available at URL: https://arxiv.org/abs/cs/0608057
Recommendations
- Challenges to complexity shields that are supposed to protect elections against manipulation and control: a survey
- The complexity of controlling candidate-sequential elections
- The complexity of priced control in elections
- A Richer Understanding of the Complexity of Election Systems
- Combinatorial voter control in elections
- Combinatorial voter control in elections
- Complexity of control by partitioning veto elections and of control by adding candidates to plurality elections
- The computational difficulty of manipulating an election
- Complexity of control by partitioning veto and maximin elections and of control by adding candidates to plurality elections
computational complexitycomplexitymulti-agent systemspreference aggregationcomputational social choicevoting systemmanipulability
Individual preferences (91B08) Social choice (91B14) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Voting theory (91B12)
Cites Work
- Social choice and individual values
- Title not available (Why is that?)
- Title not available (Why is that?)
- Voting schemes for which it can be difficult to tell who won the election
- Title not available (Why is that?)
- A Consistent Extension of Condorcet’s Election Principle
- A Richer Understanding of the Complexity of Election Systems
- The complexity of Kemeny elections
- Strategy-proofness and Arrow's conditions: existence and correspondence theorems for voting procedures and social welfare functions
- Strategic manipulability without resoluteness or shared beliefs: Gibbard-Satterthwaite generalized
- Manipulation of Voting Schemes: A General Result
- When are elections with few candidates hard to manipulate?
- Bounded Query Classes
- The Boolean Hierarchy I: Structural Properties
- Anyone but him: the complexity of precluding an alternative
- Single transferable vote resists strategic voting
- How hard is it to control an election?
- Extending Condorcet's rule
- Exact complexity of the winner problem for Young elections
- The computational difficulty of manipulating an election
- Complexity of strategic behavior in multi-winner elections
- Llull and Copeland Voting Computationally Resist Bribery and Constructive Control
- How hard is bribery in elections?
- Exact analysis of Dodgson elections
- Algorithms and Computation
- Title not available (Why is that?)
- Junta distributions and the average-case complexity of manipulating elections
- Hybrid Elections Broaden Complexity-Theoretic Resistance to Control
- Title not available (Why is that?)
- Average Case Complete Problems
- Sincere-Strategy Preference-Based Approval Voting Fully Resists Constructive Control and Broadly Resists Destructive Control
- Title not available (Why is that?)
- Boolean operations, joins, and the extended low hierarchy
- Copeland Voting Fully Resists Constructive Control
- Sparse Sets, Lowness and Highness
- Guarantees for the success frequency of an algorithm for finding Dodgson-election winners
- Approximability of Dodgson's rule
- Sincere-Strategy Preference-Based Approval Voting Broadly Resists Control
Cited In (21)
- Studies in Computational Aspects of Voting
- Complexity of control by partitioning veto elections and of control by adding candidates to plurality elections
- Voting procedures, complexity of
- The complexity of probabilistic lobbying
- The complexity of online bribery in sequential elections
- Complexity of control in judgment aggregation for uniform premise-based quota rules
- Optimal defense against election control by deleting voter groups
- Hybrid Elections Broaden Complexity-Theoretic Resistance to Control
- Manipulation can be hard in tractable voting systems even for constant-sized coalitions
- The complexity of manipulative attacks in nearly single-peaked electorates
- The shield that never was: societies with single-peaked preferences are more open to manipulation and control
- A parameterized perspective on protecting elections
- Is computational complexity a barrier to manipulation?
- Anyone but him: the complexity of precluding an alternative
- Binary linear programming solutions and non-approximability for control problems in voting systems
- How hard is it to control an election?
- Computational Aspects of Approval Voting
- Multimode control attacks on elections
- Control complexity in Bucklin and fallback voting: a theoretical analysis
- Challenges to complexity shields that are supposed to protect elections against manipulation and control: a survey
- Normalized range voting broadly resists control
This page was built for publication: Hybrid Elections Broaden Complexity-Theoretic Resistance to Control
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3392307)
