Near-Tight Algorithms for the Chamberlin-Courant and Thiele Voting Rules

Krzysztof Sornat, Virginia Vassilevska Williams, Yinzhan Xu

Abstract

We present an almost optimal algorithm for the classic Chamberlin-Courant multiwinner voting rule (CC) on single-peaked preference profiles. Given $n$ voters and $m$ candidates, it runs in almost linear time in the input size, improving the previous best $O(nm^2)$ time algorithm of Betzler et al. (2013). We also study multiwinner voting rules on nearly single-peaked preference profiles in terms of the candidate-deletion operation. We show a polynomial-time algorithm for CC where a given candidate-deletion set $D$ has logarithmic size. Actually, our algorithm runs in $2^{|D|} \cdot poly(n,m)$ time and the base of the power cannot be improved under the Strong Exponential Time Hypothesis. We also adapt these results to all non-constant Thiele rules which generalize CC with approval ballots.

Introduction

Multiwinner voting rules are essential tools for selecting a representative committee of $k$ candidates from a larger set of $m$ candidates based on the preferences of $n$ voters. Among the most influential rules are the Chamberlin-Courant (CC) rule, which focuses on minimizing the total misrepresentation of voters, and the Thiele rules, a family of approval-based rules that include Proportional Approval Voting (PAV).

While these rules offer desirable axiomatic properties, they are generally NP-hard to compute in the general case. To circumvent this, researchers often focus on structured preferences. The most prominent structure is single-peaked (SP) preferences, where candidates can be ordered along a one-dimensional axis (e.g., a political spectrum) such that each voter's preference decreases as one moves away from their most-preferred candidate.

Improving Efficiency on Single-Peaked Profiles

Prior to this work, the state-of-the-art algorithm for computing the CC rule on single-peaked profiles required $O(nm^2)$ time. While polynomial, this quadratic dependence on the number of candidates becomes a bottleneck in large-scale elections.

The authors achieve a significant breakthrough by reducing the CC problem on SP profiles to the Minimum Weight $t$-Link Path problem in a Directed Acyclic Graph (DAG). The core innovation lies in the discovery that the weight function in this DAG satisfies the concave Monge property. This mathematical structure is highly exploitable; it allows for the use of advanced pathfinding algorithms that are far more efficient than standard dynamic programming.

To further optimize the process, the authors utilize edge-weight oracles. Instead of pre-calculating all possible edge weights—which would itself take $O(m^2)$ time—they construct a data structure that can compute any specific weight in $O(\log m)$ time. By combining these techniques, the complexity is reduced to approximately $O(nm \log n)$, effectively reaching almost linear time relative to the input size.

Handling Nearly Single-Peaked Preferences

Real-world data is rarely perfectly structured. To address this, the paper investigates "nearly" single-peaked profiles—those that become single-peaked after deleting a small set of "maverick" candidates $D$.

The authors propose a Fixed-Parameter Tractable (FPT) algorithm for these cases. The algorithm effectively "guesses" which candidates from the deletion set $D$ should be included in the winning committee and then solves the remaining single-peaked sub-problem. This approach yields a running time of $2^{|D|} \cdot \text{poly}(n,m)$.

Theoretical Tightness and SETH

A key contribution of this research is the establishment of lower bounds. Using the Strong Exponential Time Hypothesis (SETH), the authors prove that their algorithms are "near-tight." Specifically:

  1. For SP profiles, the almost linear time complexity is likely the best possible.
  2. For nearly-SP profiles, no algorithm can run in $(2-\epsilon)^{|D|} \cdot \text{poly}(n,m)$ time unless SETH is false.

This confirms that the exponential dependence on the size of the deletion set $D$ is a fundamental limit, not a weakness of the specific algorithm.

Generalization to Thiele Rules

The paper demonstrates that these efficiency gains are not limited to the CC rule. The authors successfully adapt their techniques to the broader class of Thiele rules. This generalization shows that the structural advantages of single-peakedness can be leveraged across a wide variety of approval-based voting systems, providing a unified framework for efficient multiwinner election computation.

Limitations and Future Work

Despite these advances, several challenges remain:

  • Axis Discovery: The current algorithms assume the "Left-to-Right" axis of candidates is known. If the axis must be inferred from "weak orders" (preferences with ties), the complexity remains $O(nm^2)$.
  • OWA Rules: The techniques do not yet extend to Ordered Weighted Averaging (OWA) rules, which are more general than Thiele rules.
  • Practical Constants: While theoretically superior, the complexity of implementing specialized pathfinding algorithms (like Schieber’s algorithm) means that for very small datasets, simpler $O(nm^2)$ methods might still be competitive in practice.

Summary updated

Abstract

We present an almost optimal algorithm for the classic Chamberlin-Courant multiwinner voting rule (CC) on single-peaked preference profiles. Given $n$ voters and $m$ candidates, it runs in almost linear time in the input size, improving the previous best $O(nm^2)$ time algorithm of Betzler et al. (2013). We also study multiwinner voting rules on nearly single-peaked preference profiles in terms of the candidate-deletion operation. We show a polynomial-time algorithm for CC where a given candidate-deletion set $D$ has logarithmic size. Actually, our algorithm runs in $2^{|D|} \cdot poly(n,m)$ time and the base of the power cannot be improved under the Strong Exponential Time Hypothesis. We also adapt these results to all non-constant Thiele rules which generalize CC with approval ballots.
BibTeX
@inproceedings{sornat2022near,
  author = {Krzysztof Sornat and Virginia Vassilevska Williams and Yinzhan Xu},
  title = {{Near-Tight Algorithms for the Chamberlin-Courant and Thiele Voting Rules}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2022},
  url = {https://openreview.net/forum?id=e89Qgyr_pI},
}
Figure