# A Linear Theory of Multi-Winner Voting

arXiv: https://arxiv.org/abs/2503.03082 · HTML: https://mlsanity.com/paper/2503.03082/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 42 references that are in the map.
- First posted on arXiv 5 Mar 2025.

## Builds on (most cited first, 22 of 22)

- [Generative Social Choice](https://mlsanity.com/paper/2309.01291/) (2023)
- [Justified Representation in Approval-Based Committee Voting](https://mlsanity.com/paper/1407.8269/) (2014)
- [Multi-Winner Voting with Approval Preferences](https://mlsanity.com/paper/2007.01795/) (2020)
- [Proportional Justified Representation](https://mlsanity.com/paper/1611.09928/) (2016)
- [Participatory Budgeting: Models and Approaches](https://mlsanity.com/paper/2003.00606/) (2020)
- [Robust and Verifiable Proportionality Axioms for Multiwinner Voting](https://mlsanity.com/paper/2302.01989/) (2023)
- [Fair Allocation of Indivisible Public Goods](https://mlsanity.com/paper/1805.03164/) (2018)
- [Proportionality and the Limits of Welfarism](https://mlsanity.com/paper/1911.11747/) (2019)
- [Properties of Multiwinner Voting Rules](https://mlsanity.com/paper/1506.02891/) (2015)
- [Finding a Collective Set of Items: From Proportional Multirepresentation to Group Recommendation](https://mlsanity.com/paper/1402.3044/) (2014)
- [Representation with Incomplete Votes](https://mlsanity.com/paper/2211.15608/) (2022)
- [Approximately Stable Committee Selection](https://mlsanity.com/paper/1910.14008/) (2019)
- [Consistent Approval-Based Multi-Winner Rules](https://mlsanity.com/paper/1704.02453/) (2017)
- [A Learning Framework for Distribution-Based Game-Theoretic Solution Concepts](https://mlsanity.com/paper/1903.08322/) (2019)
- [The Smoothed Possibility of Social Choice](https://mlsanity.com/paper/2006.06875/) (2020)
- [Approximate Core for Committee Selection via Multilinear Extension and Market Clearing](https://mlsanity.com/paper/2110.12499/) (2021)
- [Automated Search for Impossibility Theorems in Social Choice Theory: Ranking Sets of Objects](https://mlsanity.com/paper/1401.3866/) (2014)
- [How Likely Are Large Elections Tied?](https://mlsanity.com/paper/2011.03791/) (2020)
- [Justifying Groups in Multiwinner Approval Voting](https://mlsanity.com/paper/2108.12949/) (2021)
- [Proving the Incompatibility of Efficiency and Strategyproofness via SMT Solving](https://mlsanity.com/paper/1604.05692/) (2016)
- [The Core of Approval-Based Committee Elections with Few Seats](https://mlsanity.com/paper/2501.18304/) (2025)
- [The Complexity of Learning Approval-Based Multiwinner Voting Rules](https://mlsanity.com/paper/2110.00254/) (2021)

## Built on by (most cited first, 1 of 1)

- [Agreement, Diversity, and Polarization Indices for Approval Elections](https://mlsanity.com/paper/2605.14983/) (2026)

## Abstract (arXiv)

We introduces a general linear framework that unifies the study of multi-winner voting rules and proportionality axioms, demonstrating that many prominent multi-winner voting rules-including Thiele methods, their sequential variants, and approval-based committee scoring rules-are linear. Similarly, key proportionality axioms such as Justified Representation (JR), Extended JR (EJR), and their strengthened variants (PJR+, EJR+), along with core stability, can fit within this linear structure as well. Leveraging PAC learning theory, we establish general and novel upper bounds on the sample complexity of learning linear mappings. Our approach yields near-optimal guarantees for diverse classes of rules, including Thiele methods and ordered weighted average rules, and can be applied to analyze the sample complexity of learning proportionality axioms such as approximate core stability. Furthermore, the linear structure allows us to leverage prior work to extend our analysis beyond worst-case scenarios to study the likelihood of various properties of linear rules and axioms. We introduce a broad class of distributions that extend Impartial Culture for approval preferences, and show that under these distributions, with high probability, any Thiele method is resolute, CORE is non-empty, and any Thiele method satisfies CORE, among other observations on the likelihood of commonly-studied properties in social choice. We believe that this linear theory offers a new perspective and powerful new tools for designing and analyzing multi-winner rules in modern social choice applications.