TU Berlin

Research Group Algorithmics and Computational ComplexityTalk 24.05.2016

isti-logo

Inhalt

zur Navigation

Es gibt keine deutsche Übersetzung dieser Webseite.

Algorithms for Destructive Shift Bribery

Andrzej Kaczmarczyk (AGH University, Krakow, Poland)

 

We study the complexity of Destructive Shift Bribery. In this problem, we are given an election with a set of candidates and a set of voters (ranking the candidates from best to worst, each), a despised candidate d (typically, one of the current winners), a budget B, and prices for shifting d down in voters’ rankings. The goal is to ensure that d is not a winner of the election. We show that this problem is polynomial-time solvable for all scoring protocols (encoded in unary) and the Maximin rule, but is NP-hard for the Copeland rule. This contrasts with the results for the constructive setting (known from the literature), for which the problem is polynomial-time solvable for k-Approval family of rules, but is NP-hard for the Borda, Copeland, and Maximin rules.

 

Date
Speaker
Location
Language
24.05.2016
16:00
Andrzej Kaczmarczyk
TEL 512
english

Back to the research colloquium site.

Navigation

Direktzugang

Schnellnavigation zur Seite über Nummerneingabe