Gregory Kehne's paper cuts sample complexity for proportional committees from O(k^5) to O(k^4)

In a new arXiv paper, Gregory Kehne tackles a fundamental question in computational social choice: how many random voters must you ask to ensure a multiwinner committee fairly represents the population? Using approval voting (each voter approves a subset of candidates), Kehne designs a rule that requires only Õ(k⁴ log(m/δ)) sampled ballots for a committee of k candidates and m total candidates—improving on the prior best of Õ(k⁵ log(m/δ)). This matches the minimal sample complexity needed for a simple additive approximation to the Chamberlin-Courant coverage objective, which he shows is Θ(k⁵ log(m/δ)), thereby separating the two problems.

The paper also proves lower bounds: for some instances, Ω(k³) sampled ballots are necessary to find any committee satisfying the justified representation property, and a logarithmic dependence on m is unavoidable. Strikingly, Kehne demonstrates that the stronger Droop JR and Droop PSC axioms cannot be guaranteed by any finite number of sampled ballots—a sobering result for using sampling in ranked-choice settings. However, slight relaxations of JR work with far fewer samples, and real-world preference data often outperforms worst-case bounds. The work has implications for reducing voter fatigue in large-scale elections and for algorithmic fairness in participatory budgeting and AI alignment.