# The Complexity of Learning Approval-Based Multiwinner Voting Rules

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 49 references that are in the map.
- First posted on arXiv 1 Oct 2021.

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

- [Multi-Winner Voting with Approval Preferences](https://mlsanity.com/paper/2007.01795/) (2020)
- [On the Computation of Fully Proportional Representation](https://mlsanity.com/paper/1402.0580/) (2014)
- [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)
- [Aggregating partial rankings with applications to peer grading in massive online open courses](https://mlsanity.com/paper/1411.4619/) (2014)
- [How effective can simple ordinal peer grading be?](https://mlsanity.com/paper/1602.07985/) (2016)
- [Optimizing positional scoring rules for rank aggregation](https://mlsanity.com/paper/1609.07460/) (2016)
- [On the complexity of Winner Verification and Candidate Winner for Multiwinner Voting Rules](https://mlsanity.com/paper/2004.13933/) (2020)
- [Committee Scoring Rules: Axiomatic Characterization and Hierarchy](https://mlsanity.com/paper/1802.06483/) (2018)

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

- [A Linear Theory of Multi-Winner Voting](https://mlsanity.com/paper/2503.03082/) (2025)

## Abstract (arXiv)

We study the PAC learnability of multiwinner voting, focusing on the class of approval-based committee scoring (ABCS) rules. These are voting rules applied on profiles with approval ballots, where each voter approves some of the candidates. According to ABCS rules, each committee of k candidates collects from each voter a score, which depends on the size of the voter's ballot and on the size of its intersection with the committee. Then, committees of maximum score are the winning ones. Our goal is to learn a target rule (i.e., to learn the corresponding scoring function) using information about the winning committees of a small number of sampled profiles. Despite the existence of exponentially many outcomes compared to single-winner elections, we show that the sample complexity is still low: a polynomial number of samples carries enough information for learning the target rule with high confidence and accuracy. Unfortunately, even simple tasks that need to be solved for learning from these samples are intractable. We prove that deciding whether there exists some ABCS rule that makes a given committee winning in a given profile is a computationally hard problem. Our results extend to the class of sequential Thiele rules, which have received attention recently due to their simplicity.