A Parameter­ized Perspective on Protecting and Attacking Elections

Elections get attacked and defended, and both sides are working with budgets. I take a parameterized look at two such games. In the first, an attacker removes voter groups and a defender commits in advance to shielding some of them. Deciding whether the defender can protect the outcome is intractable even with three candidates, and W[2]-hard for either budget alone, yet fixed-parameter tractable when both budgets are considered together (while the attacker's problem stays W[1]-hard even in that case). In the second (set in district-based plurality elections), an attacker changes ballots and a defender orders recounts. Both problems are tractable for few voters but hard when parameterized by the budgets.