Approximability of Manipulating Elections

Abstract

In this paper, we set up a framework to study approximation of manipulation, control, and bribery in elections. We show existence of approximation algorithms (even fully polynomial-time approximation schemes) as well as obtain inapproximability results. In particular, we show that a large subclass of scoring protocols admits fully polynomial-time approximation schemes for the coalitional weighted manipulation problem and that if certain families of scoring protocols (e.g., veto) admitted such approximation schemes then P = NP. We also show that bribery for Borda count is NP-complete and that there is no approximation algorithm that achieves even a polynomial approximation ratio for bribery in Borda count for the case where voters have prices. 1