24 March 2011, Computational Social Choice Seminar, Britta Dorn

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.

In this talk, we will focus on the case of k-approval and analyze the Swap Bribery problem from a parameterized and multivariate complexity point of view, providing further insight into how the complexity of the problem depends on different parameters such as the cost function, the budget, the number of candidates, or the number of votes. The presented results are joint work with Ildi Schlotter.

For more information, see http://www.illc.uva.nl/~ulle/seminar/, or contact Ulle Endriss (ulle.endriss at uva.nl).