Campaign Management Under Approval-Driven Voting Rules
详细信息 查看全文
- 作者：Ildiko Schlotter ; Piotr Faliszewski ; Edith Elkind
- 关键词：Approval voting ; Bucklin voting ; Fallback voting ; Campaign management ; Bribery ; Parameterized complexity
- 刊名：Algorithmica
- 出版年：2017
- 出版时间：January 2017
- 年：2017
- 卷：77
- 期：1
- 页码：84-115
- 全文大小：
- 刊物类别：Computer Science
- 刊物主题：Algorithm Analysis and Problem Complexity; Theory of Computation; Mathematics of Computing; Algorithms; Computer Systems Organization and Communication Networks; Data Structures, Cryptology and Inform
- 出版者：Springer US
- ISSN：1432-0541
- 卷排序：77
文摘
Approval-like voting rules, such as sincere-strategy preference-based approval voting (SP-AV), the Bucklin rule (an adaptive variant of k-approval voting), and the Fallback rule (a hybrid of the Bucklin rule and 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.