{"ID":2851750,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2510.19620","arxiv_id":"2510.19620","title":"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 $α$. 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 $α$ for a given approval profile that allows some committee to satisfy $α$-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 computational results in the voter interval (VI) and candidate interval (CI) domains.","short_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...","url_abs":"https://arxiv.org/abs/2510.19620","url_pdf":"https://arxiv.org/pdf/2510.19620v2","authors":"[\"Patrick Becker\",\"Fabian Frank\"]","published":"2025-10-22T14:18:45Z","proceeding":"cs.GT","tasks":"[\"cs.GT\",\"cs.CC\"]","methods":"[]","has_code":false}