Chamberlin-Courant Rule with Approval Ballots: Approximating the MaxCover Problem with Bounded Frequencies in FPT Time

Piotr Skowron, Piotr Faliszewski

TL;DR

This paper tackles the computational challenge of selecting a committee of candidates using the Chamberlin-Courant voting rule with approval ballots. The authors develop novel algorithms that efficiently find near-optimal committee selections, especially when voters approve a limited number of candidates, offering a significant improvement over existing methods for this NP-hard problem.

What Problem Does This Paper Address?

The Chamberlin-Courant rule is a multiwinner voting system designed to elect a committee that best represents diverse voter preferences. In the context of approval ballots, voters simply indicate which candidates they approve of. The core problem is to select a committee of a fixed size (K) that maximizes the number of voters who approve at least one member of the committee. This problem is computationally equivalent to the well-known NP-hard MaxCover problem. While a standard greedy algorithm provides a 1-1/e approximation, this paper aims to find algorithms that can achieve arbitrarily good approximation ratios, particularly in "fixed-parameter tractable" (FPT) time, which means their runtime depends exponentially on a small parameter (like K) but polynomially on the input size. The authors focus on specific scenarios: when voters approve at most p candidates (upper-bounded frequencies) and when they approve at least p candidates (lower-bounded frequencies).

Methods

The paper introduces several algorithms for approximating the MaxCover problem, tailored to different frequency constraints.

  • FPT Approximation Schemes for Upper-Bounded Frequencies: For the case where each element (voter) approves at most p candidates, the authors present FPT approximation schemes. Their primary algorithm (Algorithm 1) involves selecting a subset of candidates with the highest cardinalities and then exhaustively checking all K-element subcollections from this subset. This approach achieves an approximation ratio of (1 - γ) for a given parameter γ, with a runtime that is FPT in K and p.
  • Improved Analysis for Lower-Bounded Frequencies: For the case where each voter approves at least p candidates, the paper provides a tighter analysis of the standard greedy algorithm, showing it achieves a better approximation ratio than in the unrestricted case.
  • Exponential-Time Approximation Schemes for Unrestricted Case: For the general MaxCover problem without frequency bounds, the authors propose exponential-time approximation schemes (Algorithm 3 and 4). These algorithms combine an exact solver for a small part of the problem with the greedy algorithm for the remainder, allowing for a trade-off between runtime and approximation quality.

Datasets

Not discussed in the paper. The paper focuses on theoretical algorithm design and complexity analysis for the abstract MaxCover problem, rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • FPT Algorithms for Practical Scenarios: The core insight is that for scenarios where voters have limited "approval energy" (i.e., approve only a few candidates), efficient FPT algorithms can provide near-optimal committee selections. This is a significant theoretical advancement for practical applications.
  • MaxCover as a Proxy for Voting: The paper effectively bridges the gap between theoretical computer science (MaxCover) and social choice theory (Chamberlin-Courant rule), showing how advancements in one field can directly benefit the other.
  • Trade-offs in Approximation: The work highlights the fundamental trade-off between approximation ratio and running time, particularly in the unrestricted case, where exponential-time schemes offer flexibility.
  • W[1]-Completeness for Bounded Frequencies: A key complexity result is showing that MaxCover with upper-bounded frequencies is W[1]-complete, indicating its inherent computational difficulty even with parameterization.

Key Results

  • FPT Approximation Schemes: The paper presents FPT approximation schemes for MaxCover with upper-bounded frequencies, achieving approximation ratios of (1 - γ) in time parameterized by K and p.
  • Improved Greedy Analysis: For lower-bounded frequencies, the standard greedy algorithm's approximation ratio is shown to be better than the general case.
  • Exponential-Time Schemes: For the unrestricted MaxCover problem, exponential-time approximation schemes are provided, allowing for a tunable balance between solution quality and runtime.
  • Complexity Results: The paper establishes W[1]-completeness for MaxCover with upper-bounded frequencies and W[2]-completeness for the joint parameterization of K and T' (uncovered elements) for MinNonCovered.

Limitations and Future Work

  • Theoretical Focus: The algorithms are primarily theoretical, with practical feasibility for large K and p being a concern for some FPT schemes.
  • Unrestricted Case is Not FPT: For the general MaxCover problem, the authors provide exponential-time approximation schemes, not FPT ones, suggesting that such schemes might not exist unless P=NP.
  • Open Questions: The paper identifies several directions for future research, including:
  • Obtaining FPT approximation schemes for MaxCover with lower-bounded frequencies.
  • Determining the exact parameterized complexity of MaxCover (with and without lower-bounded frequencies).
  • Investigating the complexity of MaxCover where the ratio of p to m is bounded.
  • Exploring the exact complexity of a-MaxCover (where the ratio of covered elements is at least α).
  • Derandomizing the randomized FPT approximation scheme for MinNonCovered.

Summary updated

BibTeX
@article{skowron2017chamberlin,
  author = {Piotr Skowron and Piotr Faliszewski},
  title = {{Chamberlin-Courant Rule with Approval Ballots: Approximating the MaxCover Problem with Bounded Frequencies in FPT Time}},
  journal = {J. Artif. Intell. Res.},
  year = {2017},
  url = {https://openreview.net/forum?id=pvaAl2Esjt},
}
Figure