# More Efforts Towards Fixed-Parameter Approximability of Multiwinner Rules

arXiv: https://arxiv.org/abs/2505.12699 · HTML: https://mlsanity.com/paper/2505.12699/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 19 May 2025.

## Built on by (most cited first, 2 of 2)

- [Polynomial-Time Algorithm for Thiele Voting Rules with Voter Interval Preferences](https://mlsanity.com/paper/2604.05953/) (2026)
- [Algorithms for Structured Elections under Thiele Voting Rules](https://mlsanity.com/paper/2607.28575/) (2026)

## Abstract (arXiv)

Multiwinner Elections have emerged as a prominent area of research with numerous practical applications. We contribute to this area by designing parameterized approximation algorithms and also resolving an open question by Yang and Wang [AAMAS'18]. More formally, given a set of candidates, C, a set of voters,V, approving a subset of candidates (called approval set of a voter), and an integer k, we consider the problem of selecting a ``good'' committee using Thiele rules. This problem is computationally challenging for most Thiele rules with monotone submodular satisfaction functions, as there is no (1-frac1e-ε)footnoteHere, e denotes the base of the natural logarithm.-approximation algorithm in f(k)(|C| + |V|)o(k) time for any fixed ε > 0 and any computable function f, and no sf PTAS even when the length of approval set is two. Skowron [WINE'16] designed an approximation scheme running in FPT time parameterized by the combined parameter, size of the approval set and k. In this paper, we consider a parameter d+k (no d voters approve the same set of d candidates), where d is upper bounded by the size of the approval set (thus, can be much smaller). With respect to this parameter, we design parameterized approximation schemes, a lossy polynomial-time preprocessing method, and show that an extra committee member suffices to achieve the desired score (i.e., 1-additive approximation). Additionally, we resolve an open question by Yang and Wang~[AAMAS'18] regarding the fixed-parameter tractability of the problem under the PAV rule with the total score as the parameter, demonstrating that it admits an FPT algorithm.