2025/10/22 by Becker, Patrick, Frank, Fabian
#Computational Complexity (cs.CC) #Computer Science and Game Theory (cs.GT) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2510.19620
Justified representation (JR) and extended justified representation (EJR) are well-established proportionality axioms in approval-based multiwinner voting. Both axioms are always satisfiable, but they rely on a fixed quota (typically Hare or Droop), with the Droop quota being the smallest one that guarantees existence across all instances. With this observation in mind, we take a first step beyond the fixed-quota paradigm and introduce proportionality notions where the quota is instance-dependent. We demonstrate that all commonly studied voting rules can have an additive distance to the optimum of (k2)/((k+1)2). Moreover, we look into the computational aspects of our instance-dependent quota and prove that determining the optimal value of α for a given approval profile satisfying α-JR is NP-complete. To address this, we introduce an integer linear programming (ILP) formulation for computing committees that satisfy α-JR, and we provide positive results in the voter interval (VI) and candidate interval (CI) domains.