TY - JOUR AU - Aziz, Haris AU - Brill, Markus AU - Conitzer, Vincent AU - Elkind, Edith AU - Freeman, Rupert AU - Walsh, Toby PY - 2015/02/16 Y2 - 2024/03/29 TI - Justified Representation in Approval-Based Committee Voting JF - Proceedings of the AAAI Conference on Artificial Intelligence JA - AAAI VL - 29 IS - 1 SE - AAAI Technical Track: Game Theory and Economic Paradigms DO - 10.1609/aaai.v29i1.9324 UR - https://ojs.aaai.org/index.php/AAAI/article/view/9324 SP - AB - <p> 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 agree- ment 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, MAV (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. </p> ER -