Multiwinner Elections under Minimax Chamberlin-Courant Rule in Euclidean Space

Chinmay Sonar, Subhash Suri, Jie XueIJCAI 2022 · DOI

TL;DR

This paper tackles the challenge of selecting a committee of candidates that best represents voters' preferences in a spatial setting. They introduce new algorithms and hardness results for the "minimax Chamberlin-Courant rule" in Euclidean space, aiming to minimize the worst-case representation for any voter. The work provides efficient approximation schemes and sheds light on the inherent difficulty of finding perfectly fair committees.

What Problem Does This Paper Address?

Imagine you need to select a group of k representatives from a larger pool of candidates, and both voters and candidates are located in a geographical space (like a city or a region). How do you pick the committee so that no single voter feels their most preferred candidate is too far from their own location? This is the core problem of multiwinner elections, specifically when using the Chamberlin-Courant rule. This rule, in its simplest form (1-Borda), aims to minimize the rank of a voter's most preferred candidate within the chosen committee. When voters and candidates are placed in a d-dimensional Euclidean space, their preferences can be naturally inferred from their distances. The challenge is to find a committee that minimizes the maximum rank (or distance) experienced by any voter – the "minimax" objective. This is akin to the classic k-center problem but with ordinal preferences. While the problem is well-studied in 1D, its extension to higher dimensions presents significant computational hurdles.

Methods

The paper introduces several key algorithmic and theoretical contributions:

  • NP-Hardness and Inapproximability: They prove that the problem is NP-hard in any dimension d ≥ 2, and importantly, it's also hard to approximate. This means finding a near-optimal solution within a guaranteed factor is computationally difficult. Their proof relies on a clever reduction from a planar monotone 3-SAT problem, constructing a specific Euclidean election instance.
  • Polynomial-Time Approximation Schemes (PTAS): Despite the hardness, the authors develop efficient algorithms that find committees with provably good minimax scores.
  • For d=2, they achieve a committee with a score of O(m/k), where m is the number of candidates and k is the committee size.
  • For d ≥ 3, they achieve a score of O((m/k) log k). These bounds are shown to be nearly optimal.
  • They also present a "bicriterion" approach: by slightly increasing the committee size (to (1+ε)k for d=2 or O(k log m) for d ≥ 3), they can achieve a score that is at most the optimal score for a size-k committee.
  • δ-Optimality Criterion: Recognizing that exact minimax scores can be hard to achieve, they introduce a new notion of "δ-optimality." A committee is δ-optimal if, for every voter, their closest committee member is within δ times the distance to their ideal candidate (based on the optimal score). They show that a 3-optimal committee can be computed efficiently, but achieving better than 2-optimality is likely impossible without solving NP-hard problems.
  • r-Borda Generalization: The paper extends its findings to the more general r-Borda rule, where a voter's score is based on the sum of ranks of their r most preferred candidates in the committee.

Datasets

Not discussed in the paper. The paper focuses on theoretical hardness and algorithmic constructions for abstract Euclidean election instances.

Key Insights and Ideas

  • Euclidean Structure is Key: The geometric structure of Euclidean space, while making the problem harder than 1D, also provides combinatorial properties that allow for better approximation bounds than in completely unstructured preference settings.
  • Trade-off Between Committee Size and Score: The paper highlights a crucial trade-off: to achieve a score close to optimal, one might need to slightly relax the constraint on the committee size.
  • New Approximation Notion (δ-Optimality): The introduction of δ-optimality offers a practical way to evaluate committee fairness when exact minimax scores are unattainable. It provides a more robust measure of representation by considering a tolerance for distance.
  • Hardness in Higher Dimensions: The NP-hardness result for d ≥ 2 is significant, as it contrasts with the polynomial-time solvability in 1D and sets fundamental limits on what can be efficiently computed.

Key Results

  • NP-Hardness: The Euclidean minimax committee problem is NP-hard for d ≥ 2.
  • Inapproximability: The problem is hard to approximate within any sublinear factor of the number of candidates.
  • Approximation Algorithms:
    • For d=2, an O(m/k) minimax score is achievable in polynomial time.
  • For d ≥ 3, an O((m/k) log k) minimax score is achievable in polynomial time.
  • Relaxed Committee Size: A committee of size (1+ε)k (for d=2) or O(k log m) (for d ≥ 3) can achieve a score no worse than the optimal size-k committee.
  • δ-Optimal Committees: A 3-optimal committee of size k can be computed in polynomial time, but achieving better than 2-optimality is NP-hard.
  • r-Borda: Polynomial-time algorithms provide O(r²m/k) and O((r²m/k) log k) bounds for the r-Borda rule.

Limitations and Future Work

  • Exact Solvability: The paper focuses on approximation algorithms due to the NP-hardness of finding exact solutions.
  • General Preferences: The results are specific to Euclidean preferences; extending them to more general preference structures remains an open area.
  • Parameterized Complexity: The authors suggest investigating the parameterized complexity of these problems, particularly with respect to the committee size k or the number of candidates m.
  • Data Uncertainty: Future work could explore scenarios where voter and candidate positions are not precisely known but are instead represented by probability distributions (e.g., points within disks).
  • Other Voting Rules: Extending the analysis to other voting rules (like utilitarian variants or OWA rules) in Euclidean settings is a promising direction.

Summary updated

BibTeX
@inproceedings{sonar2022multiwinner,
  author = {Chinmay Sonar and Subhash Suri and Jie Xue},
  title = {{Multiwinner Elections under Minimax Chamberlin-Courant Rule in Euclidean Space}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2022},
  doi = {10.24963/ijcai.2022/68},
}
Figure