direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments

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.


Andrzej Kaczmarczyk
TEL 512

Back to the research colloquium site.

Zusatzinformationen / Extras