Protecting Elections with Minimal Resource Consumption

In democratic elections, malicious agents may attempt to control elections to achieve their own goals. To guarantee impartiality, it is necessary to protect the election outcomes from control. In this paper, we consider how to protect election outcome from control using minimal resources. We assume malicious agents attempt to prevent a specific candidate from winning a democratic election with plurality rule through denial-of-service (deletion) attacks on voter groups (e.g., polling places). First, we show that the problem is NP-hard. Second, we propose a (|C|-1)-approximation algorithm for the problem, where |C| is the number of candidates. Finally, we validate the efficiency of our approximation algorithm based on simulation experiments.