Protecting Election from Bribery: New Approach and Computational Complexity Characterization

The bribery problem in elections has received a considerable amount of attention. In this paper, we initiate the study of a related, but new problem, the protection problem, namely protecting elections from bribery. In this problem, there is a defender who is given a defense budget and can use the budget to award some of the voters such that they cannot be bribed anymore. This naturally leads to the following bi-level decision problem: Is it possible for the defender with a given defense budget to protect an election from being manipulated by the attacker with a given attack budget for bribing voters? We characterize the computational complexity of the protection problem. We show that it is in general significantly harder than the bribery problem. However, the protection problem can be solved, under certain circumstances, in polynomial time.