Insight into Voting Problem Complexity Using Randomized Classes

Zack Fitzsimmons, Edith HemaspaandraIJCAI 2022 · DOI

TL;DR

This paper explores the complexity of electoral control problems, specifically "constructive control by replacing voters" (CCRV) for voting rules like First-Last and 2-Approval. By connecting these problems to the well-studied Exact Perfect Bipartite Matching, the authors show that these voting control problems are likely "easy" (in RP, Randomized Polynomial time), potentially solving long-standing open problems and offering a new perspective on classifying computational complexity.

What Problem Does This Paper Address?

Classifying the computational complexity of problems is a fundamental task in computer science. Typically, this involves determining if a problem is in P (solvable efficiently) or NP-complete (likely not solvable efficiently). However, some problems resist this binary classification, falling into classes like RP (solvable efficiently by a randomized algorithm) but not necessarily being in P.

This paper focuses on electoral control problems, which model how an agent (like an election chair) can manipulate an election to ensure a preferred outcome. Specifically, they investigate "constructive control by replacing voters" (CCRV) for two voting rules: First-Last (where voters rank candidates first and last, with intermediate rankings ignored) and 2-Approval (where voters approve of up to two candidates). While many electoral control problems have been classified as P or NP-complete, some, like CCRV for 2-Approval, have remained open. The authors propose that considering RP as a potential complexity class can provide valuable insights into these "hard-to-classify" problems.

Methods

The core of this paper's methodology lies in establishing equivalences between electoral control problems and graph-theoretic problems, particularly Exact Perfect Bipartite Matching (EPBM) and its variants. They employ a chain of reductions, which are polynomial-time transformations that show one problem can be solved by using a solver for another problem.

Key techniques include:

  • Logspace many-one reductions: A strong form of reduction where the transformation can be computed using only logarithmic space.
  • Disjunctive truth-table (dtt) reductions: A more flexible reduction where a problem instance is transformed into a list of instances for another problem, and the original instance is solvable if any of the transformed instances are solvable.
  • Equivalence: Establishing that two problems are equivalent under a certain type of reduction means they can be reduced to each other, implying they have the same computational complexity within that framework.
  • Leveraging existing results: The paper builds upon prior work on EPBM and its efficient randomized parallel algorithms (RNC), as well as known complexities of other electoral control problems.

The authors introduce intermediate problems like "Exact Cycle Sum" and "Exact Red-Blue Perfect Bipartite b-Matching" to bridge the gap between the voting problems and EPBM.

Datasets

Not discussed in the paper. The paper deals with abstract computational problems defined by their input structure (e.g., election descriptions, graph structures) rather than specific datasets.

Key Insights and Ideas

  • RP as a valuable complexity class: The paper argues that considering RP (Randomized Polynomial time) as a potential complexity class, rather than just P or NP-complete, can unlock new insights into problems that have resisted traditional classification.
  • Voting problems linked to matching: A significant contribution is showing that electoral control problems for First-Last and 2-Approval voting rules are computationally equivalent to Exact Perfect Bipartite Matching. This is a novel connection that hadn't been established before.
  • "Easy" problems can solve "hard" problems (and vice-versa): The equivalences found imply that if the voting control problems are NP-complete, then RP = NP (highly unlikely). Conversely, if EPBM is in P, then these voting problems are also in P, which would solve a 40-year-old open problem in graph theory. This highlights the interconnectedness of computational problems.
  • Resolving open cases: The paper successfully classifies the complexity of 2-Approval-CCRV, which was the last remaining open case in a comprehensive table of electoral control problem complexities. They show it's in RP, and thus considered "easy" under the common assumption that P=RP.

Key Results

  • First-Last CCRV!, CCRV!, and CCRV are equivalent to Exact Perfect Bipartite Matching (EPBM). This implies these voting problems are in RP and RNC (Randomized NC, efficient parallel randomized algorithms).
  • 2-Approval-CCRV! is equivalent to Exact Perfect Matching. This also places the problem in RP and RNC.
  • 2-Approval-CCRV is shown to be in RNC via a reduction to Exact Perfect Matching.
  • 2-Approval-CCAV! is shown to be in P.
  • The paper provides a unified approach to classifying several electoral control problems by linking them to well-understood matching problems.

Limitations and Future Work

  • RP vs. P: While the paper shows problems are in RP, it doesn't definitively prove they are in P. The assumption P=RP is widely believed but not proven.
  • Logspace vs. Polynomial-time reductions: While many reductions are logspace, some intermediate steps might rely on polynomial-time dtt reductions, which are more flexible. The authors note that the specific reduction from EPBM to Exact Cycle Sum is a dtt, not a many-one reduction.
  • Generalization: The paper focuses on specific voting rules (First-Last, 2-Approval) and control types (adding/replacing voters). Future work could explore other voting rules and control mechanisms.
  • Open questions: The paper mentions that it remains open if a reduction exists in the other direction for 2-Approval-CCRV to Exact Perfect Matching.
  • Practical implications: While the theoretical complexity is addressed, the practical implications of these findings for real-world election design or manipulation detection are not explored.

The authors suggest that their approach of linking voting problems to matching problems could be a valuable strategy for tackling other voting problems that have resisted classification.

Summary updated

BibTeX
@inproceedings{fitzsimmons2022insight,
  author = {Zack Fitzsimmons and Edith Hemaspaandra},
  title = {{Insight into Voting Problem Complexity Using Randomized Classes}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2022},
  doi = {10.24963/ijcai.2022/42},
}
Figure