direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments

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.

Zusatzinformationen / Extras