Frugal bribery in voting

We show that the Frugal-bribery problem is polynomial time solvable for the k-approval, k-veto, and plurality with run off voting rules for unweighted elections. These results establish success in finding practically appealing as well as polynomial time solvable special cases of the sophisticated $Bribery and Swap-bribery problems. On the other hand, we show that the Frugal-bribery problem is NP-complete for the Borda voting rule and the Frugal-$bribery problem is NP-complete for most of the voting rules studied here barring the plurality and the veto voting rules for unweighted elections. Our hardness results of the Frugal-bribery and the Frugal-$bribery problems thus subsumes and strengthens the hardness results of the $Bribery problem from the literature. For the weighted elections, we show that the Frugal-bribery problem is NP-complete for all the voting rules studied here except the plurality voting rule even when the number of candidates is as low as 3 (for the STV and the plurality with run off voting rules) or 4 (for the maximin, the Copelandα with α∈[0,1), and the simplified Bucklin voting rules). In our view, the fact that the simplest Frugal-bribery problem becomes computationally intractable for many important voting rules (except the plurality voting rule) even with very few candidates is surprising as well as interesting.