Institute for Logic, Language and Computation

24 March 2011, Computational Social Choice Seminar, Britta Dorn

Speaker: Britta Dorn (Ulm)
Title: A Multivariate Complexity Analysis of Swap Bribery
Date: Thursday 24 March 2011
Time: 16:00
Location: Room D1.113, Science Park 904, Amsterdam

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, or contact Ulle Endriss ().

The websites of the UvA make use of cookiesThis site uses cookies More informationMore info Hide this message XHide X