Campaign management under approval-driven voting rules
From MaRDI portal
Publication:513294
DOI10.1007/S00453-015-0064-0zbMATH Open1358.91048arXiv1501.00387OpenAlexW1698830886MaRDI QIDQ513294FDOQ513294
Authors: Piotr Faliszewski, Edith Elkind, Ildikó Schlotter 
Publication date: 6 March 2017
Published in: Algorithmica (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1501.00387
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
- Title not available (Why is that?)
- Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
- Parametrized complexity theory.
- Computational Aspects of Approval Voting
- Title not available (Why is that?)
- Color-coding
- Title not available (Why is that?)
- Title not available (Why is that?)
- Determining possible and necessary winners given partial orders
- On the parameterized complexity of multiple-interval graph problems
- A strongly polynomial minimum cost circulation algorithm
- Anyone but him: the complexity of precluding an alternative
- Multivariate complexity analysis of Swap Bribery
- Control complexity in Bucklin and fallback voting: a theoretical analysis
- Bypassing combinatorial protections: polynomial-time algorithms for single-peaked electorates
- Prices matter for the parameterized complexity of shift bribery
- Voting systems that combine approval and preference
- Swap bribery
- How hard is bribery in elections?
- The complexity of manipulative attacks in nearly single-peaked electorates
- Weighted electoral control
- The shield that never was: societies with single-peaked preferences are more open to manipulation and control
- On the computation of fully proportional representation
- Are there any nicely structured preference profiles nearby?
- Sincere-Strategy Preference-Based Approval Voting Fully Resists Constructive Control and Broadly Resists Destructive Control
- Normalized range voting broadly resists control
- Stable matching with preferences derived from a psychological model
- Eliciting single-peaked preferences using comparison queries
- A Polynomial Time Algorithm for Unidimensional Unfolding Representations
- Strategic, sincere, and heuristic voting under four election rules: an experimental study
- Control complexity in Bucklin and fallback voting: an experimental analysis
- A live experiment on approval voting
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
- How hard is safe bribery?
- Complexity of shift bribery for iterative voting rules
- 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)
