Advertisement
Published in:
2010 | OriginalPaper | Chapter
Multivariate Complexity Analysis of Swap Bribery
Authors : Britta Dorn, Ildikó Schlotter
Published in: Parameterized and Exact Computation
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
We consider the computational complexity of a problem modeling
bribery
in the context of voting systems. In the scenario of
Swap Bribery
, each voter assigns a certain price for swapping the positions of two consecutive candidates in his preference ranking. The question is whether it is possible, without exceeding a given budget, to bribe the voters in a way that the preferred candidate wins in the election.
We initiate a parameterized and multivariate complexity analysis of
Swap Bribery
, focusing on the case of
k
-approval. We investigate how different cost functions affect the computational complexity of the problem. We identify a special case of
k
-approval for which the problem can be solved in polynomial time, whereas we prove NP-hardness for a slightly more general scenario. We obtain fixed-parameter tractability as well as W[1]-hardness results for certain natural parameters.