Even More Effort Towards Improved Bounds and Fixed-Parameter Tractability for Multiwinner Rules

Sushmita Gupta, Pallavi Jain, Saket Saurabh, Nimrod TalmonIJCAI 2021 · DOI

TL;DR

This paper tackles the computational complexity of finding winning committees in multiwinner elections, focusing on improving existing algorithms and identifying new tractable cases for various voting rules. The authors present faster algorithms for some rules and establish new hardness results for others, offering a more nuanced understanding of when these complex election problems can be solved efficiently.

What Problem Does This Paper Address?

In multiwinner elections, the goal is to select a committee of a specified size (k) from a set of candidates, based on voters' ranked preferences. While this seems straightforward, determining the "winning" committee according to various voting rules can be computationally very challenging, often falling into NP-hard categories. This intractability hinders the practical application of these rules, especially when dealing with a large number of voters or candidates.

Much research in this area focuses on two main approaches:

  1. Improving algorithms for specific rules: Finding faster ways to compute winners, even if the worst-case complexity remains high.
  2. Parameterized complexity: Identifying specific parameters (like committee size k or number of voters n) that, when small, allow for efficient computation. This is known as Fixed-Parameter Tractability (FPT).

This paper builds upon existing work by:

  • Improving the efficiency of algorithms for well-known rules like Chamberlin-Courant (CC).
  • Investigating the parameterized complexity of other rules, such as Pessimist and Egalitarian-Median, to pinpoint when they become tractable or remain intractable.
  • Extending the analysis to egalitarian versions of committee scoring rules, which are less studied.

The core problem is to understand the computational landscape of multiwinner elections, specifically identifying the boundaries between computationally feasible and infeasible scenarios, and developing more efficient algorithms where possible.

Methods

The paper employs a combination of algorithmic techniques and theoretical computer science tools, primarily from parameterized complexity theory.

  • Algorithmic Improvements: For the Chamberlin-Courant (CC) rule, the authors present an algorithm with a significantly improved time complexity of $O^*(2^n)$, which is shown to be optimal under the Set Cover Conjecture. This is a substantial improvement over previous $O^*(n^n)$ algorithms. The technique involves a clever use of polynomial multiplication to represent and combine voter preferences and potential committee scores.
  • Parameterized Complexity Analysis: The core of the paper involves establishing hardness results (NP-hard, W[1]-hard, W[2]-hard) and tractability results (FPT) for various voting rules with respect to parameters like committee size (k) and number of voters (n). This is achieved through:
  • Parameterized Reductions: Transforming known hard problems (like HITTING SET, INDEPENDENT SET) into instances of the voting problems. If the source problem is hard for a specific parameter, the target voting problem is also likely hard for that parameter.
  • Specific Case Analysis: Examining how the complexity changes when certain parameters or conditions are met (e.g., when $\lambda$ is a constant, or when $\lambda = \epsilon k$).
  • Novel Polynomial Representations: For the CC rule, the authors utilize polynomials where monomials represent subsets of voters and their degrees correspond to characteristic vectors of these subsets. The multiplication of these polynomials allows for testing disjointness and summing scores efficiently.
  • Dynamic Programming and Exact Algorithms: For some tractable cases, the authors leverage existing exact algorithms for problems like SET MULTICOVER or develop dynamic programming approaches to solve the voting problem within a specific parameter bound.

Datasets

Not discussed in the paper. The paper focuses on theoretical complexity and algorithmic analysis, not empirical evaluation on specific datasets.

Key Insights and Ideas

  • The Power of Polynomials for Elections: The paper demonstrates a sophisticated application of polynomial algebra for solving election problems. By encoding voter sets and scores as polynomials, operations like checking for disjoint partitions and aggregating scores become manageable through polynomial multiplication. This is particularly evident in the CC algorithm.
  • Nuanced Complexity Landscape: The research reveals that multiwinner voting rules don't fit neatly into "easy" or "hard" categories. Their complexity is highly dependent on the specific rule, the parameter being considered (k vs. n), and even sub-parameters like $\lambda$ in egalitarian rules. This suggests that a one-size-fits-all approach to solving these problems is unlikely.
  • Optimal Bounds are Achievable (Sometimes): The $O^*(2^n)$ algorithm for CC, proven to be optimal, highlights that significant algorithmic improvements are possible even for established problems, provided the right theoretical tools are applied.
  • Egalitarian Rules are Tricky: The analysis of Egalitarian-Median and Egalitarian-Best rules shows they can be W[2]-hard with respect to committee size (k), even when other parameters are fixed. This suggests that ensuring fairness (minimizing the worst-off voter) can be computationally demanding.
  • Tractability Under Specific Conditions: The paper identifies several scenarios where these complex rules become tractable, particularly when the number of voters (n) is small or when the satisfaction threshold ($\eta$) is constrained in a specific way. This offers practical avenues for using these rules in real-world applications.

Key Results

  • Chamberlin-Courant (CC): An optimal $O^*(2^n)$ algorithm is presented, improving upon previous $O^*(n^n)$ algorithms. This is optimal assuming the Set Cover Conjecture.
  • Pessimist Rule: Shown to be W[1]-hard with respect to committee size (k), and polynomial-time solvable with respect to the number of voters (n). This is a stronger hardness result than previously known NP-hardness.
  • Egalitarian-Median Rule:
    • NP-hard for $\lambda \in [1, k-1]$.
  • W[2]-hard with respect to k when $\lambda$ is constant or $\lambda = \epsilon k$.
  • FPT with respect to k when the satisfaction threshold $\eta$ is of the form $m - g(k)$.
  • Solvable in $O^*(2^n \log(1+\lambda))$ time, and $O^*(2^n)$ for Egalitarian-CC ($\lambda=1$).
  • Egalitarian-Best Rule:
    • NP-hard and W[2]-hard with respect to k when $\lambda$ is a constant or $\lambda = \epsilon k$.
  • Solvable in polynomial time when n and $\lambda$ are constants.

Limitations and Future Work

  • Theoretical Focus: The paper is primarily theoretical, focusing on complexity classes and asymptotic running times. It does not present empirical evaluations on real-world election data.
  • Specific Rules: The analysis is limited to a specific set of committee scoring rules. Further research could extend these findings to other classes of multiwinner voting rules.
  • Parameter Choices: The paper explores complexity with respect to parameters like k and n. Investigating other potential parameters or combinations of parameters could yield further insights.
  • Future Work: The authors suggest exploring other egalitarian rules and committee scoring rules. They also hint at the possibility of further algorithmic improvements and a deeper understanding of the trade-offs between different parameters. The journal version is mentioned to contain formal proofs, indicating that this conference paper is a condensed version of a more extensive work.

Summary updated

BibTeX
@inproceedings{gupta2021even,
  author = {Sushmita Gupta and Pallavi Jain and Saket Saurabh and Nimrod Talmon},
  title = {{Even More Effort Towards Improved Bounds and Fixed-Parameter Tractability for Multiwinner Rules}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2021},
  doi = {10.24963/ijcai.2021/31},
}
Figure