Justifying groups in multiwinner approval voting

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, where k is the target size of the committee. 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.

Authors

• Edith Elkind Northwestern University
• Piotr Faliszewski AGH University of Krakow
• Ayumi Igarashi The University of Tokyo & RIKEN AIP
• Pasin Manurangsi
• Ulrike Schmidt-Kraepelin TU Eindhoven
• Warut Suksompong National University of Singapore

Keywords

• Justified representation
• Multiwinner voting
• Computational social choice