Google Research

Justifying Committees in Multiwinner Approval Voting

  • Ayumi Igarashi
  • Edith Elkind
  • Pasin Manurangsi
  • Piotr Faliszewski
  • Ulrike Schmidt-Kraepelin
  • Warut Suksompong
SAGT 2022

Abstract

Justified representation (JR) is a well-known 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 that are smaller than the target size k. 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 approximation algorithms that compute a small n/k-justifying group for any given instance, and an 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.

Learn more about how we do research

We maintain a portfolio of research projects, providing individuals and teams the freedom to emphasize specific types of work