BIRS Workshop Lecture Videos

Banff International Research Station Logo

BIRS Workshop Lecture Videos

FPT approximation schemes for Shift Bribery Nichterlein, André

Description

In the Shift Bribery problem, we are given an election (based on preference orders), a preferred candidate p, and a budget. The goal is to ensure that p wins by shifting p higher in some voters' preference orders. However, each such shift request comes at a price (depending on the voter and on the extent of the shift) and we have to minimize the overall costs. In this talk, we show FPT approximation schemes for the Copeland voting rule (the winner is the candidate winning the most head-to-head competitions) with respect to each of the parameters number of voters and number of candidates.This is joint work with Robert Bredereck, Jiehua Chen, Piotr Faliszewski, and Rolf Niedermeier.

Item Media

Item Citations and Data

Rights

Attribution-NonCommercial-NoDerivatives 4.0 International