Single-Peakedness and Total Unimodularity: New Polynomial-Time Algorithms for Multi-Winner Elections

Dominik PetersAAAI 2018 · DOI

Abstract

This paper introduces a powerful new algorithmic technique for solving multi-winner elections by leveraging Integer Programming (IP) formulations that become "totally unimodular" under structured voter preferences. Specifically, it demonstrates that NP-hard voting rules, such as Proportional Approval Voting (PAV) and Chamberlin–Courant, can be solved in polynomial time when preferences are single-peaked. This result disproves a long-standing conjecture that PAV remained computationally hard even under such structural restrictions.

Introduction

In multi-winner elections, the objective is to select a committee of $k$ candidates that best represents the electorate. While simple rules like plurality are computationally efficient, they often fail to provide adequate representation for minorities. More sophisticated rules, such as Proportional Approval Voting (PAV) and the Chamberlin–Courant rule, offer superior representation but are generally NP-hard to compute.

To bridge this gap between representativeness and tractability, researchers often look for structured preferences. The most prominent of these is single-peakedness, where candidates are arranged along a one-dimensional axis (e.g., a political spectrum). In this model, each voter has a "peak" preference, and their utility decreases as candidates move further from that peak along the axis.

Single-peaked preferences along a one-dimensional axis.

Methodology: Total Unimodularity and IP Formulations

Rather than relying on traditional dynamic programming approaches, this research utilizes Integer Linear Programming (IP) and the concept of Total Unimodularity (TU). A matrix is TU if every square submatrix has a determinant of 0, 1, or -1. This property is highly desirable in optimization because if the constraint matrix of an IP is TU, its Linear Programming (LP) relaxation is guaranteed to yield an integer solution, making the problem solvable in polynomial time.

The methodology involves three primary steps:

  1. Novel IP Formulations: Designing specific IP models for PAV, Chamberlin–Courant, and broader Ordered Weighted Averaging (OWA) rules.
  2. Mapping to Matrix Properties: Proving that under single-peaked preferences, the constraint matrices of these IPs exhibit the "consecutive ones property," where the 1s in each row appear in a contiguous block.
  3. Proving TU: Since matrices with the consecutive ones property are known to be totally unimodular, the complex voting problems are reduced to simple, efficient Linear Programs.
Mapping voter preferences to a matrix exhibiting the consecutive ones property.

Key Results and Insights

  • Disproving the PAV Conjecture: The paper provides the first polynomial-time algorithm for PAV under single-peaked preferences, settling a major open question in computational social choice.
  • Axis Independence: Unlike previous algorithms for structured preferences, this IP approach does not require a preprocessing step to identify the candidate axis. The TU property is inherent in the matrix structure regardless of row or column permutations, allowing standard solvers to find optimal solutions "accidentally" during their first LP relaxation iteration.
  • Unification via OWA: The TU property extends to the broad family of OWA-based rules, provided the weight vectors are non-increasing. This generalizes the efficiency gains across multiple voting systems.

Discussion and Future Directions

While this technique is transformative, it has limitations. It does not apply to rules with additional constraints that break TU, such as Monroe’s rule, which requires committee members to represent roughly equal numbers of voters. Furthermore, the OWA results are restricted to non-increasing weight vectors.

Future research may explore whether other preference structures, such as "single-crossing" preferences, also lead to TU formulations. Additionally, empirical studies comparing the performance of these IP formulations against existing specialized algorithms on large-scale datasets would provide valuable practical insights.

Summary updated

BibTeX
@inproceedings{peters2018single,
  author = {Dominik Peters},
  title = {{Single-Peakedness and Total Unimodularity: New Polynomial-Time Algorithms for Multi-Winner Elections}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2018},
  doi = {10.1609/aaai.v32i1.11460},
}
Figure