# Robustness of Greedy Approval Rules

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 1 Aug 2022.

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

- [Representative Ranking for Deliberation in the Public Sphere](https://mlsanity.com/paper/2503.18962/) (2025)
- [Reverse Sequential Proportional Approval Voting Rule: Proportionality and Approximation Guarantees](https://mlsanity.com/paper/2609.35331/) (2026)

## Abstract (arXiv)

We study the robustness of GreedyCC, GreedyPAV, and Phargmen's sequential rule, using the framework introduced by Bredereck et al. for the case of (multiwinner) ordinal elections and adopted to the approval setting by Gawron and Faliszewski. First, we show that for each of our rules and every committee size k, there are elections in which adding or removing a certain approval causes the winning committee to completely change (i.e., the winning committee after the operation is disjoint from the one before the operation). Second, we show that the problem of deciding how many approvals need to be added (or removed) from an election to change its outcome is NP-complete for each of our rules. Finally, we experimentally evaluate the robustness of our rules in the presence of random noise.