Approximating Electoral Control Problems

Much research in electoral control—one of the most studied forms ofelectoralattacks, inwhichanentityaltersthestructureofanelection to yield a preferred outcome—has focused on giving decisioncomplexity results. Approximability on the other hand has received little attention in electoral control, despite its prevalence in the study of other forms of electoral attacks, such as manipulation and bribery. Early work established preliminary results with respect to popular voting rules such as plurality, approval, and Condorcet. In this work, we completely determine for each of the “standard” control problems under the aforementioned voting rules whether they are approximable (for weighted and unweighted votes).

Authors

• Huy Vu Bui Denison University
• Michael C. Chavrimootoo Denison University
• Kien T. Le Denison University
• Son M. Nguyen Denison University

Keywords

• Approximation Algorithms
• Electoral Control
• Inapproximability
• Covering Integer Programs
• Minimum 𝑘-Union