On Minimal Achievable Quotas in Multiwinner Voting

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 $\frac{k^2}{(k+1)^2}$. Moreover, we look into the computational aspects of our instance-dependent quota and prove that determining the optimal value of $\alpha$ for a given approval profile satisfying $\alpha$-JR is NP-complete. To address this, we introduce an integer linear programming (ILP) formulation for computing committees that satisfy $\alpha$-JR, and we provide positive results in the voter interval (VI) and candidate interval (CI) domains.