Computer Science – Computational Complexity
Scientific paper
2010-11-05
Computer Science
Computational Complexity
20 pages. Conference version published at IPEC 2010
Scientific paper
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.
Dorn Britta
Schlotter Ildikó
No associations
LandOfFree
Multivariate Analyis of Swap Bribery does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Multivariate Analyis of Swap Bribery, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Multivariate Analyis of Swap Bribery will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-453797