# Justifying Groups in Multiwinner Approval Voting

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 Aug 2021.

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

- [Representative Ranking for Deliberation in the Public Sphere](https://mlsanity.com/paper/2503.18962/) (2025)
- [A Linear Theory of Multi-Winner Voting](https://mlsanity.com/paper/2503.03082/) (2025)
- [Computing Thiele Rules on Interval Elections and their Generalizations](https://mlsanity.com/paper/2605.03067/) (2026)

## Abstract (arXiv)

Justified representation (JR) is a standard notion of representation in multiwinner approval voting. Not only does a JR committee always exist, but previous work has also shown through experiments that the JR condition can typically be fulfilled by groups of fewer than k candidates. In this paper, we study such groups -- known as n/k-justifying groups -- both theoretically and empirically. First, we show that under the impartial culture model, n/k-justifying groups of size less than k/2 are likely to exist, which implies that the number of JR committees is usually large. We then present efficient approximation algorithms that compute a small n/k-justifying group for any given instance, and a polynomial-time exact algorithm when the instance admits a tree representation. In addition, we demonstrate that small n/k-justifying groups can often be useful for obtaining a gender-balanced JR committee even though the problem is NP-hard.