Justified representation in approval-based committee voting

Published

Journal Article

Copyright © 2015, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved. We consider approval-based committee voting, i.e., the setting where each voter approves a subset of candidates, and these votes are then used to select a fixed-size set of winners (committee). We propose a natural axiom for this setting, which we call justified representation (JR). This axiom requires that if a large enough group of voters exhibits agreement by supporting the same candidate, then at least one voter in this group has an approved candidate in the winning committee. We show that for every list of ballots it is possible to select a committee that provides JR. We then check if this axiom is fulfilled by well-known approval-based voting rules. We show that the answer is negative for most of the rules we consider, with notable exceptions of PAV (Proportional Approval Voting), an extreme version of RAV (Reweighted Approval Voting), and, for a restricted preference domain, MA V (Minimax Approval Voting). We then introduce a stronger version of the JR axiom, which we call extended justified representation (EJR), and show that PAV satisfies EJR, while other rules do not. We also consider several other questions related to JR, and EJR, including the relationship between JR./EJR and unanimity, and the complexity of the associated algorithmic problems.

Duke Authors

Cited Authors

  • Aziz, H; Brill, M; Conitzer, V; Elkind, E; Freeman, R; Walsh, T

Published Date

  • June 1, 2015

Published In

  • Proceedings of the National Conference on Artificial Intelligence

Volume / Issue

  • 2 /

Start / End Page

  • 784 - 790

Citation Source

  • Scopus