Vés al contingut (premeu Retorn)

LIMDA Joint Seminar Announcement: Martin Koutecký

Title: Voting and Bribing in Single-Exponential Time. Speaker: Martin Koutecký, Department of Applied Mathematics, Charles University, Prague.

15/11/2016 des de/d' 12:00"
Room S210 (floor -2), Omega Building, Campus Nord
Més informació
Afegeix un esdeveniment al calendari


In social choice theory, many combinatorial problems have been addressed from the viewpoint of parameterized complexity. For many of these problems, though, either their fixed-parameter tractability is not known, or the fastest known algorithms have doubly-exponential dependence on the parameters. These shortcomings (among others) led Bredereck et al. to pose their “Nine Research Challenges in Social Choice Theory”.

In this work we provide a general approach to many fundamental voting and bribing problems in social choice theory, when parameterized by the number of candidates. Our approach shows, for the first time, fixed-parameter tractability of those problems, or provides the first algorithms with singly-exponential dependence on the parameter. Thereby, we solve “Challenge #2” by Bredereck et al., and substantially contribute towards resolving their “Challenge #1”.

In particular, we show that R-Swap Bribery is fixed-parameter tractable parameterized by the number of candidates and solvable in single-exponential time, for many voting rules R; this extends an earlier double-exponential time algorithm by Dorn and Schlotter that is restricted to the unit-cost case.