Abstract
Complexity of voting manipulation is a prominent
topic in computational social choice. In this work,
we consider a two-stage voting manipulation scenario. First, a malicious party (an attacker) attempts
to manipulate the election outcome in favor of a
preferred candidate by changing the vote counts in
some of the voting districts. Afterwards, another
party (a defender), which cares about the voters’
wishes, demands a recount in a subset of the manipulated districts, restoring their vote counts to their
original values. We investigate the resulting Stackelberg game for the case where votes are aggregated using two variants of the Plurality rule, and
obtain an almost complete picture of the complexity landscape, both from the attacker’s and from the
defender’s perspective