Approximating Electoral Control Problems

Much research in electoral control -- one of the most studied form of electoral attacks, in which an entity running an election alters the structure of that election to yield a preferred outcome -- has focused on giving decision complexity results, e.g., membership in P, NP-completeness, or fixed-parameter tractability. Approximation algorithms on the other hand have received little attention in electoral control, despite their prevalence in the study of other forms of electoral attacks, such as manipulation and bribery. Early work established some preliminary results with respect to popular voting rules such as plurality, approval, and Condorcet. In this paper, we establish for each of the ``standard'' control problems under plurality, approval, and Condorcet, whether they are approximable, and we prove our results in both the weighted and unweighted voter settings. For each problem we study under either approval or Condorcet, we show that any approximation algorithm we give is optimal, unless P=NP. Our approximation algorithms leverage the fact that Covering Integer Programs (CIPs) can be approximated within a factor of $O(\log n)$. Under plurality, we give an $O(m)$-approximation algorithm, and give as lower bound $\Omega(m^{1/4})$, by using a known lower bound on the Minimum $k$-Union (M$k$U) problem. To our knowledge, this is the first application of M$k$U in computational social choice. We also generalize our $O(m)$-approximation algorithm to work with respect to an infinite family of voting rules using an axiomatic approach. Our work closes a long list of open problems established 18 years ago.