TU Berlin

Research Group Algorithmics and Computational ComplexityTalk 16.01.2014

isti-logo

Inhalt

zur Navigation

Es gibt keine deutsche Übersetzung dieser Webseite.

Prices Matter for the Parameterized Complexity of Shift Bribery

Dipl.-Inf. Jiehua Chen (TU Berlin)

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 a shift comes at a price, depending on the voter and on the extent of the shift and we may not exceed the given budget.

We study the parameterized complexity of Shift Bribery with respect to a number of parameters and several classes of price functions. If we parameterize by the number of positions by which p is shifted in total, then the problem is fixed-parameter tractable for Borda and Maximin voting rules, and is W[1]-hard for Copeland voting rule. If we parameterize by the budget for the cost of shifting, then the results depend on the price function class. We also show that Shift Bribery tends to be easy when parameterized by the number of voters, but that the results for the number of candidates are more enigmatic.

Date
Speaker
Location
Language
16.01.2014 16:15
Jiehua Chen
TEL 512
english

Back to the research colloquium site.

Navigation

Direktzugang

Schnellnavigation zur Seite über Nummerneingabe