Research Group Algorithmics and Computational ComplexityTalk 04.05.2017

# On the Computational Complexity of Variants of Combinatorial Voter Control in Elections

Leon Kellerhals (TU Berlin)

Voter control problems model situations in which an external agent tries to affect the result of an election
by adding or deleting the fewest number of voters. The goal of the agent is to make a specific candidate
either win (constructive control) or lose (destructive control) the election. We study the constructive and
destructive voter control problems when adding and deleting voters have a combinatorial flavor, meaning
that if we add or delete a voter v, we also add or delete a bundle κ(v) of voters that are associated with v.
We analyze the computational complexity of the four voter control problems for the Plurality rule.

We obtain that, in general, making a candidate lose is computationally easier than making her win.
In particular, if the bundling relation is symmetric (i.e. ∀w : w ∈ κ(v) ⇔ v ∈ κ(w)), and if each voter
has at most two voters associated with him, then destructive control by deleting the fewest number of
voters or candidates are polynomial-time solvable while the constructive variants remain NP-hard. Even
if the bundling relation consists of disjoint cliques (i.e. ∀w : w ∈ κ(v) ⇔ κ(v) = κ(w)), the constructive
problem variants remain intractable.

This talk is based on joint work with Viatcheslav Korenwein, Philipp Zschoche, Robert Bredereck, and
Jiehua Chen.

Date
Speaker
Location
Language
04.05.2017
16:15
Leon Kellerhals
TEL 512
English

Back to the research colloquium site.