LIMDA Joint Seminar Announcement: Martin Koutecký
Title: Voting and Bribing in Single-Exponential Time. Speaker: Martin Koutecký, Department of Applied Mathematics, Charles University, Prague.
- https://mat.upc.edu/ca/activitats/limda-joint-seminar-announcement-martin-koutecky
- LIMDA Joint Seminar Announcement: Martin Koutecký
- 2016-11-15T12:00:00+01:00
- 2016-11-15T23:59:59+01:00
- Title: Voting and Bribing in Single-Exponential Time. Speaker: Martin Koutecký, Department of Applied Mathematics, Charles University, Prague.
15/11/2016 des de 12:00 (Europe/Madrid / UTC100)
Room S210 (floor -2), Omega Building, Campus Nord
Abstract
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.