On Minimal Achievable Quotas in Multiwinner Voting

Abstract

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 in mind, we take a step beyond the fixed-quota paradigm by studying instance-dependent proportionality notions. More specifically, we minimize the quota requirements for JR and EJR using the parameter $\hat{I}\pm$. We demonstrate that all commonly studied voting rules can have an additive gap to the optimum of $\frac{k^2}{(k+1{)}^2}$. Moreover, we examine the computational aspects of our instance-dependent quota and prove that determining the optimal value of $\hat{I}\pm$ for a given approval profile that allows some committee to satisfy $\hat{I}\pm$-JR is NP-complete. To address this, we introduce an integer linear programming (ILP) formulation for computing committees that satisfy $\hat{I}\pm$-JR, and we provide positive computational results in the voter interval (VI) and candidate interval (CI) domains.