LIMDA Joint Seminar Announcement: Martin Koutecký
- LIMDA Joint Seminar Announcement: Martin Koutecký
- Title: Voting and Bribing in Single-Exponential Time. Speaker: Martin Koutecký, Department of Applied Mathematics, Charles University, Prague.
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ó
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.