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.

Quan
15/11/2016 des de/d' 12:00"
On
Room S210 (floor -2), Omega Building, Campus Nord
Més informació
https://combgraph.upc.edu/en/courses-and-seminars/limda-joint-seminar-announcements-2016-2017
iCal

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.