Very Hard Electoral Control Problems

Zack Fitzsimmons, Edith Hemaspaandra, Alexander Hoover, David E. NarváezAAAI 2019 · DOI

Abstract

In the field of Computational Social Choice, electoral control—the act of altering an election's outcome by modifying its structure—is a central topic of study. While control is typically NP-complete for simple voting rules, this paper explores rules like Kemeny, Young, and Dodgson, where winner determination is already hard. The authors prove that control for these rules jumps to the second level of the polynomial hierarchy ($\Sigma^p_2$-completeness). They introduce novel graph-based reductions and demonstrate how Answer Set Programming (ASP) can be used to solve these highly complex problems.

Introduction

Electoral control involves an external agent (the "organizer") attempting to ensure a specific candidate wins by adding or deleting candidates or voters. For most common systems like Plurality, this task is NP-complete. However, more sophisticated rules like Kemeny, Young, and Dodgson possess superior social-choice properties but come with a higher computational cost: their winner-determination problems are already $\Theta^p_2$-complete. This paper fills a significant gap by formally proving that electoral control for these rules is even harder—specifically $\Sigma^p_2$-complete—and provides a practical framework for solving them.

Theoretical Complexity and Reductions

Proving $\Sigma^p_2$-completeness is challenging due to the lack of "simple" base problems. The authors overcome this by defining new $\Sigma^p_2$-complete graph problems: Vertex-Cover-Member-Add and Vertex-Cover-Member-Select. These serve as accessible starting points for reductions to electoral control.

The core theoretical contribution is the classification of various control actions under Kemeny, Young, and Dodgson rules. As shown in Figure 4, these problems consistently reside at the second level of the polynomial hierarchy.

Theoretical complexity results for electoral control under Kemeny, Young, and Dodgson rules.

This "complexity jump" represents a significant computational shield, making these elections exceptionally resistant to structural manipulation compared to standard voting rules.

Solving "Very Hard" Problems with ASP

Standard SAT solvers are not natively designed for $\Sigma^p_2$ problems, which involve nested "exists" and "for all" quantifiers. To address this, the authors utilize Answer Set Programming (ASP), a declarative logic programming paradigm. They employ a specialized "saturation technique" that allows the solver to verify if a candidate is a winner (a hard sub-problem) while simultaneously searching for a valid control strategy.

Empirical Evaluation

The authors tested their ASP encoding for Kemeny control (Constructive Control by Adding Candidates - CCAC) using 215 instances from Preflib, a library of real-world preference data. The solver successfully handled 114 out of 215 instances within a one-hour timeout.

Performance of the ASP solver on selected Preflib instances for Kemeny control.

As illustrated in Figure 5, the solver is highly efficient for smaller instances (5-7 candidates), often returning results in seconds. However, performance degrades as the number of candidates increases, primarily due to the "grounding bottleneck"—the memory-intensive process of expanding logical rules into ground instances.

Conclusion and Future Work

This research provides the first natural $\Sigma^p_2$-completeness results in the context of elections, establishing a new benchmark for electoral complexity. While ASP proves to be a powerful tool for these problems, future work is needed to optimize grounding or utilize non-grounding solvers to handle larger candidate sets. Additionally, the newly defined $\Sigma^p_2$-complete graph problems offer a promising foundation for proving hardness in other complex social choice scenarios.

Summary updated

BibTeX
@inproceedings{fitzsimmons2019very,
  author = {Zack Fitzsimmons and Edith Hemaspaandra and Alexander Hoover and David E. Narváez},
  title = {{Very Hard Electoral Control Problems}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2019},
  doi = {10.1609/aaai.v33i01.33011933},
}
Figure