2025/05/19 by Sushmita Gupta, Pallavi Jain, Gupta, Sushmita +7 · 1 citation
Computer Science · Economics, Econometrics and Finance · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Computer Science and Game Theory (cs.GT) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Game Theory and Voting Systems
paper · pdf · doi:10.48550/arxiv.2505.12699
openalex publication_date 2025/05/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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-(1)/(e)-ε)\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.