Computational Aspects of Nearly Single-Peaked Electorates

Gábor Erdélyi, Martin Lackner, Andreas PfandlerAAAI 2013 · DOI

Introduction

In social choice theory, the concept of single-peakedness is a cornerstone for ensuring efficient decision-making. An electorate is considered single-peaked if all candidates can be ordered along a linear axis (such as a left-to-right political spectrum) such that every voter's preference decreases as candidates move away from their most preferred choice. This structure makes finding winners computationally fast and simplifies many voting problems—such as manipulation, bribery, and control—that are otherwise NP-hard.

However, real-world elections are rarely perfectly structured. A single "maverick" voter or an outlier candidate can disrupt this property, even if the rest of the data is perfectly aligned. This paper investigates "nearly" single-peaked elections, categorizing various distance measures that quantify how much noise must be removed to restore single-peakedness and determining the computational complexity of calculating these distances.

Categorizing Distance Measures

The authors analyze seven distinct distance measures, representing different ways an election might deviate from the ideal single-peaked state:

  • Voter-based: Removing $k$ "maverick" voters to achieve consistency.
  • Candidate-based: Deleting $k$ candidates globally (Global Candidate Deletion) or $k$ candidates per individual vote (Local Candidate Deletion).
  • Structural: Utilizing multiple axes (Additional Axes) or partitioning candidates into single-peaked subsets (Candidate Partition).
  • Edit-based: Performing a limited number of adjacent candidate "swaps" globally or locally.

The Complexity Hierarchy

A central contribution of this work is establishing the relationships between these measures. The authors use a Hasse diagram to visualize the partial ordering of these distances, showing how different definitions of "nearness" relate to one another. For instance, they prove that the number of "Local Swaps" is always bounded by "Global Swaps."

Hasse diagram illustrating the relationships between different distance measures to single-peakedness.

Through rigorous complexity theory proofs and reductions from known NP-complete problems like Minimum Radius, the paper demonstrates that most of these measures are NP-complete. This suggests that for large elections, we likely cannot find the "perfect" distance for most definitions of nearness.

Notion Complexity
$k$-Maverick NP-complete
$k$-Candidate Deletion In P (Polynomial)
$k$-Local Candidate Deletion NP-complete
$k$-Additional Axes NP-complete
$k$-Global Swaps NP-complete
$k$-Local Swaps NP-complete
$k$-Candidate Partition Open

Algorithmic Breakthroughs: The "Easy" Exception

Despite the general hardness of these problems, the paper identifies a significant exception: Global Candidate Deletion (CD). While other measures are NP-complete, determining the minimum number of candidates to remove to achieve single-peakedness can be solved in polynomial time.

The authors present a dynamic programming algorithm with a complexity of $O(|V| \cdot |C|^5)$, where $V$ is the number of voters and $C$ is the number of candidates. This algorithm builds upon previous structural insights to efficiently navigate the candidate space and find the optimal set for deletion.

Dynamic programming algorithm for finding the minimum number of candidates to delete to achieve single-peakedness.

Conclusion and Future Directions

The study reveals that while single-peakedness is a fragile property, certain ways of measuring its absence are more computationally accessible than others. While most measures provide a "computational shield" due to their NP-hardness, the efficiency of Candidate Deletion suggests that some manipulative actions might still be easy to execute in nearly structured societies.

Future research remains focused on resolving the complexity of $k$-Candidate Partition and developing Fixed-Parameter Tractable (FPT) algorithms for the NP-complete measures to handle real-world instances more effectively. Additionally, the authors suggest exploring how these measures of "nearness" specifically impact the difficulty of bribing or controlling an election in practice.

Summary updated

BibTeX
@inproceedings{erdelyi2013computational,
  author = {Gábor Erdélyi and Martin Lackner and Andreas Pfandler},
  title = {{Computational Aspects of Nearly Single-Peaked Electorates}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2013},
  doi = {10.1609/aaai.v27i1.8608},
}
Figure