Campaign management under approval-driven voting rules
From MaRDI portal
Publication:513294
Abstract: Approval-like voting rules, such as Sincere-Strategy Preference-Based Approval voting (SP-AV), the Bucklin rule (an adaptive variant of -Approval voting), and the Fallback rule (an adaptive variant of SP-AV) have many desirable properties: for example, they are easy to understand and encourage the candidates to choose electoral platforms that have a broad appeal. In this paper, we investigate both classic and parameterized computational complexity of electoral campaign management under such rules. We focus on two methods that can be used to promote a given candidate: asking voters to move this candidate upwards in their preference order or asking them to change the number of candidates they approve of. We show that finding an optimal campaign management strategy of the first type is easy for both Bucklin and Fallback. In contrast, the second method is computationally hard even if the degree to which we need to affect the votes is small. Nevertheless, we identify a large class of scenarios that admit fixed-parameter tractable algorithms.
Recommendations
- Control complexity in Bucklin and fallback voting: a theoretical analysis
- On the manipulability of approval voting and related scoring rules
- Sincere-Strategy Preference-Based Approval Voting Fully Resists Constructive Control and Broadly Resists Destructive Control
- Possible winners in approval voting
- Classical Electoral Competition Under Approval Voting
Cites work
- scientific article; zbMATH DE number 1261820 (Why is no real title available?)
- scientific article; zbMATH DE number 1161563 (Why is no real title available?)
- scientific article; zbMATH DE number 3231692 (Why is no real title available?)
- scientific article; zbMATH DE number 2234775 (Why is no real title available?)
- A Polynomial Time Algorithm for Unidimensional Unfolding Representations
- A live experiment on approval voting
- A strongly polynomial minimum cost circulation algorithm
- Anyone but him: the complexity of precluding an alternative
- Are there any nicely structured preference profiles nearby?
- Bypassing combinatorial protections: polynomial-time algorithms for single-peaked electorates
- Color-coding
- Computational Aspects of Approval Voting
- Control complexity in Bucklin and fallback voting: a theoretical analysis
- Control complexity in Bucklin and fallback voting: an experimental analysis
- Determining possible and necessary winners given partial orders
- Eliciting single-peaked preferences using comparison queries
- How hard is bribery in elections?
- Multivariate complexity analysis of Swap Bribery
- Normalized range voting broadly resists control
- On the computation of fully proportional representation
- On the parameterized complexity of multiple-interval graph problems
- Parametrized complexity theory.
- Prices matter for the parameterized complexity of shift bribery
- Sincere-Strategy Preference-Based Approval Voting Fully Resists Constructive Control and Broadly Resists Destructive Control
- Stable matching with preferences derived from a psychological model
- Strategic, sincere, and heuristic voting under four election rules: an experimental study
- Swap bribery
- 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
- Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
- Voting systems that combine approval and preference
- Weighted electoral control
Cited in
(11)- Studies in Computational Aspects of Voting
- The complexity of campaigning
- The complexity of online bribery in sequential elections
- Approximation and hardness of shift-bribery
- Complexity of shift bribery for iterative voting rules
- How hard is safe bribery?
- On the hardness of bribery variants in voting with CP-nets
- Manipulation can be hard in tractable voting systems even for constant-sized coalitions
- Local distance constrained bribery in voting
- Mixed integer programming with convex/concave constraints: fixed-parameter tractability and applications to multicovering and voting
- Path-disruption games: bribery and a probabilistic model
This page was built for publication: Campaign management under approval-driven voting rules
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q513294)
