On Minimal Achievable Quotas in Multiwinner Voting
Authors
Patrick Becker
Fabian Frank
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 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 $α$ 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.
