Sincere-Strategy Preference-Based Approval Voting Fully Resists Constructive Control and Broadly Resists Destructive Control
From MaRDI portal
Publication:3392309
Abstract: We study sincere-strategy preference-based approval voting (SP-AV), a system proposed by Brams and Sanver [Electoral Studies, 25(2):287-305, 2006], and here adjusted so as to coerce admissibility of the votes (rather than excluding inadmissible votes a priori), with respect to procedural control. In such control scenarios, an external agent seeks to change the outcome of an election via actions such as adding/deleting/partitioning either candidates or voters. SP-AV combines the voters' preference rankings with their approvals of candidates, where in elections with at least two candidates the voters' approval strategies are adjusted--if needed--to approve of their most-preferred candidate and to disapprove of their least-preferred candidate. This rule coerces admissibility of the votes even in the presence of control actions, and hybridizes, in effect, approval with pluralitiy voting. We prove that this system is computationally resistant (i.e., the corresponding control problems are NP-hard) to 19 out of 22 types of constructive and destructive control. Thus, SP-AV has more resistances to control than is currently known for any other natural voting system with a polynomial-time winner problem. In particular, SP-AV is (after Copeland voting, see Faliszewski et al. [AAIM-2008, Springer LNCS 5034, pp. 165-176, 2008]) the second natural voting system with an easy winner-determination procedure that is known to have full resistance to constructive control, and unlike Copeland voting it in addition displays broad resistance to destructive control.
Recommendations
- Sincere-Strategy Preference-Based Approval Voting Broadly Resists Control
- Llull and Copeland Voting Computationally Resist Bribery and Constructive Control
- Copeland Voting Fully Resists Constructive Control
- Anyone but him: the complexity of precluding an alternative
- Normalized range voting broadly resists control
Cites work
- scientific article; zbMATH DE number 3854738 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- A Richer Understanding of the Complexity of Election Systems
- Anyone but him: the complexity of precluding an alternative
- Approximability of Dodgson's rule
- Complexity of strategic behavior in multi-winner elections
- Computational Aspects of Approval Voting
- Copeland Voting Fully Resists Constructive Control
- 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?
- 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
- On Approximating Optimal Weighted Lobbying, and Frequency of Correctness Versus Average-Case Polynomial Time
- Parameterized Complexity of Candidate Control in Elections and Related Digraph Problems
- Sincere-Strategy Preference-Based Approval Voting Broadly Resists Control
- 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 computational difficulty of manipulating an election
- The strategy-proofness landscape of merging
- Voting schemes for which it can be difficult to tell who won the election
- Voting systems that combine approval and preference
Cited in
(23)- Studies in Computational Aspects of Voting
- Parameterized complexity of voter control in multi-peaked elections
- Complexity of control by partitioning veto elections and of control by adding candidates to plurality elections
- Preference–Approval Structures in Group Decision Making: Axiomatic Distance and Aggregation
- The control complexity of \(r\)-Approval: from the single-peaked case to the general case
- The complexity of probabilistic lobbying
- Sincere-Strategy Preference-Based Approval Voting Broadly Resists Control
- Control complexity in Borda elections: solving all open cases of offline control and some cases of online control
- Resolute control: forbidding candidates from winning an election is hard
- Copeland Voting Fully Resists Constructive Control
- Optimal defense against election control by deleting voter groups
- The complexity of manipulative attacks in nearly single-peaked electorates
- Campaign management under approval-driven voting rules
- 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
- Parameterized complexity of control problems in Maximin election
- A parameterized perspective on protecting elections
- Anyone but him: the complexity of precluding an alternative
- Parameterized computational complexity of control problems in voting systems
- Computational Aspects of Approval Voting
- 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: Sincere-Strategy Preference-Based Approval Voting Fully Resists Constructive Control and Broadly Resists Destructive Control
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3392309)
