# Computational Aspects of Multi-Winner Approval Voting

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

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 11 Jul 2014.

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

- [Proportional Aggregation of Preferences for Sequential Decision Making](https://mlsanity.com/paper/2306.14858/) (2023)
- [Temporal Fairness in Multiwinner Voting](https://mlsanity.com/paper/2312.04417/) (2023)
- [Multiwinner Temporal Voting with Aversion to Change](https://mlsanity.com/paper/2408.11017/) (2024)
- [Full Proportional Justified Representation](https://mlsanity.com/paper/2501.12015/) (2025)
- [Subset Selection Based On Multiple Rankings in the Presence of Bias: Effectiveness of Fairness Constraints for Multiwinner Voting Score Functions](https://mlsanity.com/paper/2306.09835/) (2023)
- [Polynomial-Time Algorithm for Thiele Voting Rules with Voter Interval Preferences](https://mlsanity.com/paper/2604.05953/) (2026)
- [Bribery as a Measure of Candidate Success: Complexity Results for Approval-Based Multiwinner Rules](https://mlsanity.com/paper/2104.09130/) (2021)
- [Proportional Committee Elections with Positive and Negative Votes](https://mlsanity.com/paper/2503.01985/) (2025)
- [Computing Thiele Rules on Interval Elections and their Generalizations](https://mlsanity.com/paper/2605.03067/) (2026)
- [Algorithms for Structured Elections under Thiele Voting Rules](https://mlsanity.com/paper/2607.28575/) (2026)
- [Reverse Sequential Proportional Approval Voting Rule: Proportionality and Approximation Guarantees](https://mlsanity.com/paper/2609.35331/) (2026)

## Abstract (arXiv)

We study computational aspects of three prominent voting rules that use approval ballots to elect multiple winners. These rules are satisfaction approval voting, proportional approval voting, and reweighted approval voting. We first show that computing the winner for proportional approval voting is NP-hard, closing a long standing open problem. As none of the rules are strategyproof, even for dichotomous preferences, we study various strategic aspects of the rules. In particular, we examine the computational complexity of computing a best response for both a single agent and a group of agents. In many settings, we show that it is NP-hard for an agent or agents to compute how best to vote given a fixed set of approval ballots from the other agents.