Parameterized Complexity of Control and Bribery for d-Approval Elections
Conference Paper
Overview
Research
Identity
Additional Document Info
Other
View All
Overview
abstract
A d-Approval election consists of a set C of candidates and a set V of votes, where each vote v can be presented as a set of d candidates. For a vote v V, the protocol assigns one point to each candidate in v. The candidate getting the most points from all votes wins the election. An important aspect of studying election systems is the strategic behavior such as control and bribery problems. The control by deleting votes problem decides whether for a given election (C, V ), a specific candidate c, and an integer k, it is possible to delete at most k votes such that c wins the resulting election. In the control by adding votes setting, one has two sets V and U of votes and asks for a subset U U such that |U| k and c becomes the winner in V U. The bribery problem has the same input as the vote deleting control problem and asks for changing at most k votes to make c win. All three problems have been shown NP-hard. We initialize the study of the parameterized complexity of these problems and present a collection of tractability and intractability results. In particular, we derive polynomial-size problem kernels for the standard parameterizations of the control by deleting votes and bribery problems, the seemingly first non-trivial problem kernels for the control and bribery problems of elections. Springer International Publishing 2013.
name of conference
Combinatorial Optimization and Applications - 7th International Conference, COCOA 2013, Chengdu, China, December 12-14, 2013, Proceedings
