direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments

On Coalitional Manipulation for Multiwinner Elections: Shortlisting

Andrzej Kaczmarczyk (TU Berlin)

Shortlisting of candidates—selecting a group of "best" candidates—is a special case of multiwinner elections. We provide the first in-depth study of the computational complexity of strategic voting for shortlisting based on the most natural and simple voting rule in this scenario, l-Bloc (every voter approves l candidates). In particular, we investigate the influence of several tie-breaking mechanisms (e.g. pessimistic versus optimistic) and group evaluation functions (e.g. egalitarian versus utilitarian) and conclude that in an egalitarian setting strategic voting may indeed be computationally intractable regardless of the tie-breaking rule. We provide a fairly comprehensive picture of the computational complexity landscape of this neglected scenario.

This is joint work with Robert Bredereck and Rolf Niedermeier.

Date
Speaker
Location
Language
15.06.2017
16:15
Andrzej Kaczmarczyk
TEL 512
English

Back to the research colloquium site.

Zusatzinformationen / Extras