# Robust and Verifiable Proportionality Axioms for Multiwinner Voting

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

## Key facts

- Cited by 23 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 Feb 2023.

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

- [Generative Social Choice](https://mlsanity.com/paper/2309.01291/) (2023)
- [Proportional Aggregation of Preferences for Sequential Decision Making](https://mlsanity.com/paper/2306.14858/) (2023)
- [Proportional Fairness in Clustering: A Social Choice Perspective](https://mlsanity.com/paper/2310.18162/) (2023)
- [Generative Social Choice: The Next Generation](https://mlsanity.com/paper/2505.22939/) (2025)
- [Strengthening Proportionality in Temporal Voting](https://mlsanity.com/paper/2505.22513/) (2025)
- [Proportionally Representative Clustering](https://mlsanity.com/paper/2304.13917/) (2023)
- [Method of Equal Shares with Bounded Overspending](https://mlsanity.com/paper/2409.15005/) (2024)
- [Proportional Representation in Metric Spaces and Low-Distortion Committee Selection](https://mlsanity.com/paper/2312.10369/) (2023)
- [Full Proportional Justified Representation](https://mlsanity.com/paper/2501.12015/) (2025)
- [Bridging Voting and Deliberation with Algorithms: Field Insights from vTaiwan and Kultur Komitee](https://mlsanity.com/paper/2502.05017/) (2025)
- [The Price of Proportional Representation in Temporal Voting](https://mlsanity.com/paper/2605.11157/) (2026)
- [Representative Ranking for Deliberation in the Public Sphere](https://mlsanity.com/paper/2503.18962/) (2025)
- [Question the Questions: Auditing Representation in Online Deliberative Processes](https://mlsanity.com/paper/2511.04588/) (2025)
- [A Linear Theory of Multi-Winner Voting](https://mlsanity.com/paper/2503.03082/) (2025)
- [What Voting Rules Actually Do: A Data-Driven Analysis of Multi-Winner Voting](https://mlsanity.com/paper/2508.06454/) (2025)
- [Large Language Models for Designing Participatory Budgeting Rules](https://mlsanity.com/paper/2602.09349/) (2026)
- [Strengthening Full Justified Representation: Efficient Verification and Computation](https://mlsanity.com/paper/2608.11500/) (2026)
- [Data as Voters: Core Set Selection Using Approval-Based Multi-Winner Voting](https://mlsanity.com/paper/2304.09995/) (2023)
- [Fair Indivisible Payoffs through Shapley Value](https://mlsanity.com/paper/2510.24906/) (2025)
- [Fairness in the Multi-Secretary Problem](https://mlsanity.com/paper/2511.23097/) (2025)
- [A General Theory of Proportionality with Additive Utilities](https://mlsanity.com/paper/2602.08504/) (2026)
- [Algorithms for Structured Elections under Thiele Voting Rules](https://mlsanity.com/paper/2607.28575/) (2026)
- [Proportional Representation in Temporal Voting with Ranked Preferences](https://mlsanity.com/paper/2609.30555/) (2026)

## Abstract (arXiv)

When selecting a subset of candidates (a so-called committee) based on the preferences of voters, proportional representation is often a major desideratum. When going beyond simplistic models such as party-list or district-based elections, it is surprisingly challenging to capture proportionality formally. As a consequence, the literature has produced numerous competing criteria of when a selected committee qualifies as proportional. Two of the most prominent notions are Dummett's proportionality for solid coalitions (PSC) and Aziz et al.'s extended justified representation (EJR). Both guarantee proportional representation to groups of voters who have very similar preferences; such groups are referred to as solid coalitions by Dummett and as cohesive groups by Aziz et al. However, these notions lose their bite when groups are only almost solid or almost cohesive. In this paper, we propose proportionality axioms that are more robust: they guarantee representation also to groups that do not qualify as solid or cohesive. Further, our novel axioms can be easily verified: Given a committee, we can check in polynomial time whether it satisfies the axiom or not. This is in contrast to many established notions like EJR, for which the corresponding verification problem is known to be intractable. In the setting with approval preferences, we propose a robust and verifiable variant of EJR and a simply greedy procedure to compute committees satisfying it. In the setting with ranked preferences, we propose a robust variant PSC, which can be efficiently verified even for general weak preferences. In the special case of strict preferences, our notion is the first known satisfiable proportionality axiom that is violated by the Single Transferable Vote (STV). We also discuss implications of our results for participatory budgeting, querying procedures, and to the notion of proportionality degree.