The Complexity of Succinct Elections

Zack Fitzsimmons, Edith HemaspaandraAAAI 2017 · DOI

Abstract

This paper investigates the computational implications of representing election data succinctly—by recording the counts of distinct vote types rather than listing every individual ballot. While this compression can be exponential, the authors demonstrate that it rarely increases computational complexity for most common election problems. The notable exception is the Kemeny election, which shifts from $\Theta_2^p$-complete to $\Delta_2^p$-complete, marking it as uniquely sensitive to input representation.

Introduction

In the field of computational social choice, researchers typically represent an electorate as a long list of individual votes, known as a nonsuccinct representation. However, in many real-world scenarios and AI applications, it is more natural to represent preferences succinctly. For example, instead of listing the preference "A > B > C" one hundred times, a succinct representation simply records the preference and a count of 100.

While succinct representations are significantly smaller, they can represent a massive number of voters. This raises a critical question: Does this compression make it harder to determine a winner or to manipulate the election? In the related case of weighted elections—where voters have different "voting power"—complexity often jumps from polynomial time (P) to NP-hard. This research explores whether succinct representation causes a similar "complexity explosion."

Methodology

The authors employ a combination of algorithmic adaptation and complexity-theoretic proofs to map the landscape of succinct elections:

  • Algorithmic "Lifting": The researchers demonstrate that many standard techniques used to prove election problems are in P—such as greedy algorithms, network flow, and matching—can be adapted to handle succinct counts without a significant loss in efficiency. This "lifting" allows algorithms to process counts of votes rather than iterating through individual ballots.
  • Complexity Mapping: The study analyzes "Control" problems (where an authority attempts to alter the outcome by adding or deleting voters) and "Manipulation" problems.
  • Reductions for Kemeny Elections: To determine the complexity of Kemeny elections, the authors "lift" a chain of existing reductions. They define weighted versions of intermediate problems to prove that the succinct version of the Kemeny winner problem is complete for $\Delta_2^p$ (the class of problems solvable in polynomial time with an NP oracle).

Key Insights

Succinctness vs. Weighting

A common intuition in social choice is that succinct votes are functionally identical to weighted votes. The authors prove this intuition is false. While weighted voter problems are usually hard even for a fixed number of candidates, succinct problems often remain computationally easy. This suggests that the structure of multiple identical voters is more manageable than the structure of voters with arbitrary weights.

The "Tame" Nature of Succinctness

Most polynomial-time algorithms for standard elections are robust enough to be adapted to succinct inputs. The authors show that the "dichotomy" (the boundary between what is easy and what is hard) for certain control problems remains identical between nonsuccinct and succinct cases. This indicates that for most voting rules, the jump in representation size does not translate to a jump in computational difficulty.

The Kemeny Exception

The authors identified Kemeny elections as the only "natural" case where succinctness increases complexity. In a standard Kemeny election, the goal is to find a consensus ranking that minimizes the distance to all votes. Because the succinct representation can represent a massive number of voters in a small space, the complexity shifts from $\Theta_2^p$ (parallel queries to an NP oracle) to $\Delta_2^p$ (adaptive/sequential queries). This confirms that Kemeny elections are uniquely sensitive to how the input is represented.

Key Results

  1. CCAV Dichotomy: For "Constructive Control by Adding Voters" (CCAV) under pure scoring rules, the cases that are in P for standard elections remain in P for succinct elections.
  2. Fixed Candidate Manipulation: Manipulation remains in P for any fixed number of candidates when using succinct votes. This is achieved by using Integer Linear Programming (ILP) with a fixed number of variables, which can be solved in polynomial time.
  3. Kemeny Complexity: The paper settles an open question by proving that Kemeny-Succinct-Winner is $\Delta_2^p$-complete. This result highlights a rare instance where the efficiency of data representation directly impacts the theoretical complexity class of the problem.

Conclusion

While the paper shows that many P-time algorithms can be adapted to succinct representations, it identifies Kemeny elections as a significant outlier. A major open question remains: Are there any other natural election systems where succinctness changes the complexity class? Future work may involve exhaustive case studies of other election systems and control types to see if the "tame" nature of succinctness holds across the broader field of social choice.

Summary updated

BibTeX
@inproceedings{fitzsimmons2017complexity,
  author = {Zack Fitzsimmons and Edith Hemaspaandra},
  title = {{The Complexity of Succinct Elections}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2017},
  doi = {10.1609/aaai.v31i1.11122},
}
Figure