More Efforts Towards Fixed-Parameter Approximability of Multiwinner Rules

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.