Kemeny Consensus Complexity

Zack Fitzsimmons, Edith HemaspaandraIJCAI 2021 · DOI

TL;DR

This paper dives into the computational complexity of finding a "Kemeny consensus" – a single ranking that best represents a group's preferences. They prove that simply checking if a given ranking is a Kemeny consensus is surprisingly hard (coNP-complete), but for manipulators aiming to achieve a specific consensus, the optimal strategy is simple: just vote for it.

What Problem Does This Paper Address?

In many decision-making scenarios, we don't just want to pick a single winner; we want a full ranking of all options. Think of meta-search engines combining results or genetic mapping. The Kemeny rule is a popular way to achieve this, aiming for a consensus ranking that minimizes the "distance" to individual voters' preferences. However, computing this ideal ranking is known to be computationally difficult. This paper tackles two main questions:

  1. How hard is it to verify if a given ranking is already the Kemeny consensus? This is crucial for trust and auditing election outcomes.
  2. When people try to manipulate an election to achieve a specific Kemeny consensus, what's the best strategy, and how complex is it to figure out? This relates to understanding the robustness of voting systems against strategic behavior.

Methods

The authors employ a range of standard and advanced computational complexity theory techniques.

  • Complexity Classes: They leverage established classes like P, NP, and coNP, and delve into the more complex $\Sigma_2^P$ (second level of the polynomial hierarchy).
  • Reductions: A core technique is using reductions to prove hardness. They show that if problem A is at least as hard as problem B, then solving A can be used to solve B. They reduce known hard problems (like Minimum Vertex Cover Recognition, Minimum Feedback Arc Set Recognition, and QSAT2) to the problems they study.
  • Proof Techniques: For coNP-completeness, they often show membership in coNP (easy to verify a "no" answer) and then prove coNP-hardness via reductions. For $\Sigma_2^P$-completeness, they use more intricate reductions involving oracles or nested quantifiers.
  • Constructing Elections: A key part of their proofs involves constructing specific election scenarios (elections with voters and candidates) that mimic the structure of the problems they are reducing from. This allows them to translate the properties of the original problem into properties of the Kemeny consensus.

Datasets

Not discussed in the paper. The paper focuses on theoretical computational complexity and does not involve empirical evaluation on real-world datasets.

Key Insights and Ideas

  • Verification is Hard: It's surprisingly difficult (coNP-complete) to simply check if a given ranking is the Kemeny consensus. This means that even if someone claims a ranking is the best representation of preferences, verifying it is a computationally challenging task.
  • Manipulation Strategy is Simple: Despite the difficulty of verification, the optimal strategy for manipulators aiming for a specific Kemeny consensus is remarkably simple: they should just vote for their desired consensus directly. This suggests that Kemeny consensus is somewhat robust to manipulation in terms of strategy, even if achieving it is hard.
  • The "Why" of Simplicity: The paper provides evidence that this simple manipulation strategy for Kemeny is due to the specific combination of the Kemeny rule itself, the action of manipulation (voting), and the goal (achieving a consensus). They contrast this with other voting rules (like Borda) where the optimal manipulation strategy is not simple.
  • New Complexity Frontiers: The paper establishes new completeness results for problems at the second level of the polynomial hierarchy ($\Sigma_2^P$), particularly for optimal solution recognition and control problems in elections. This pushes the boundaries of our understanding of computational complexity in social choice theory.

Key Results

  • Kemeny Consensus Recognition is coNP-complete: Determining if a given ranking is a Kemeny consensus is computationally hard.
  • Kemeny Manipulation-to-Consensus is easy (for the optimal action): The optimal strategy for manipulators to achieve a desired Kemeny consensus is to simply vote for that consensus. The associated decision problem (can manipulators achieve it?) is coNP-complete, but the action itself is simple.
  • Control-to-Consensus is $\Sigma_2^P$-complete: Problems involving modifying the election structure (like deleting candidates) to achieve a Kemeny consensus are significantly harder, residing in $\Sigma_2^P$. This implies that finding the optimal control action is not polynomial-time computable.
  • Slater Rule Complexity: The paper also analyzes the complexity of a related rule, the Slater rule, showing it has similar hardness properties for recognition (coNP-complete) and manipulation ( $\Sigma_2^P$-complete for manipulation-to-winner).
  • New $\Sigma_2^P$ Completeness Results: The paper presents the first completeness results at the $\Sigma_2^P$ level for electoral manipulation and optimal solution recognition.

Limitations and Future Work

  • Kemeny Manipulation-to-Winner Conjecture: While they show manipulation for Slater (a qualitative version of Kemeny) is $\Sigma_2^P$-complete, they conjecture that Kemeny manipulation-to-winner is also $\Sigma_2^P$-complete but haven't fully proven it.
  • Weights in Elections: The paper touches on candidates with weights but primarily focuses on unary weights for Slater. Exploring elections with binary or arbitrary weights for Kemeny and Slater remains an interesting avenue.
  • Other Control Mechanisms: The paper mentions other control mechanisms like adding/deleting voters, which are considered more compelling and are left for future work.
  • Tournaments: While they show results for tournaments (a special case of elections), the proofs for tournaments are more difficult and some questions remain open.

Summary updated

BibTeX
@inproceedings{fitzsimmons2021kemeny,
  author = {Zack Fitzsimmons and Edith Hemaspaandra},
  title = {{Kemeny Consensus Complexity}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2021},
  doi = {10.24963/ijcai.2021/28},
}
Figure