Hybrid Elections Broaden Complexity-Theoretic Resistance to Control
From MaRDI portal
Publication:3392307
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.
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
Cites work
- scientific article; zbMATH DE number 3148878 (Why is no real title available?)
- scientific article; zbMATH DE number 5764882 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 2080215 (Why is no real title available?)
- scientific article; zbMATH DE number 2182815 (Why is no real title available?)
- scientific article; zbMATH DE number 3405712 (Why is no real title available?)
- A Consistent Extension of Condorcet’s Election Principle
- A Richer Understanding of the Complexity of Election Systems
- Algorithms and Computation
- Anyone but him: the complexity of precluding an alternative
- Approximability of Dodgson's rule
- Average Case Complete Problems
- Boolean operations, joins, and the extended low hierarchy
- Bounded Query Classes
- Complexity of strategic behavior in multi-winner elections
- Copeland Voting Fully Resists Constructive Control
- Exact analysis of Dodgson elections
- Exact complexity of the winner problem for Young elections
- Extending Condorcet's rule
- Guarantees for the success frequency of an algorithm for finding Dodgson-election winners
- How hard is bribery in elections?
- How hard is it to control an election?
- Hybrid Elections Broaden Complexity-Theoretic Resistance to Control
- Junta distributions and the average-case complexity of manipulating elections
- Llull and Copeland Voting Computationally Resist Bribery and Constructive Control
- Manipulation of Voting Schemes: A General Result
- Sincere-Strategy Preference-Based Approval Voting Broadly Resists Control
- Sincere-Strategy Preference-Based Approval Voting Fully Resists Constructive Control and Broadly Resists Destructive Control
- Single transferable vote resists strategic voting
- Social choice and individual values
- Sparse Sets, Lowness and Highness
- Strategic manipulability without resoluteness or shared beliefs: Gibbard-Satterthwaite generalized
- Strategy-proofness and Arrow's conditions: existence and correspondence theorems for voting procedures and social welfare functions
- The Boolean Hierarchy I: Structural Properties
- The complexity of Kemeny elections
- The computational difficulty of manipulating an election
- Voting schemes for which it can be difficult to tell who won the election
- When are elections with few candidates hard to manipulate?
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
- Manipulation can be hard in tractable voting systems even for constant-sized coalitions
- The complexity of manipulative attacks in nearly single-peaked electorates
- Hybrid Elections Broaden Complexity-Theoretic Resistance to Control
- 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)
