Some notes on justified representation

Proceedings of 10th Multidisciplinary Workshop on Advances in Preference Handling (MPREF) in conjunction with IJCAI 2016, New York City, USA, July 9thMulti-winner voting systems are often applied to scenarios in which it is desirable that the set of winners represents the different opinions or preferences of the agents involved in the election. Because of that, the development of axioms that capture the idea of representation and the study of multi-winner voting rules with such axioms is of great interest. In the context of approval-based committee voting, Aziz et al. proposed in 2015 at the AAAI Conference two axioms related to the concept of repre sentation. These axioms are called justified representation (JR) and extended justified representation (EJR). In this paper we present new results related to these axioms. First of all, we close an issue that was left open by Aziz et al. regarding the maximum number of seats for which the Reweighted Approval Voting satisfies JR. Second, we discuss a problem in the definition of EJR: a set of candidates can provide perfect representation for a given election and fail to provide EJR. We propose an alternative axiom which we have called proportional justified representation (PJR). We prove that PJR remedies that problem, while providing precisely the same results as EJR for all the voting systems that Aziz et al. analyzed in their paper.This work was supported in part by the Spanish Ministerio de Economa y Competitividad (project HERMES-SMARTDRIVER TIN2013-46801-C4-2-R) and by the Autonomous Community of Madrid (project e-Madrid S2013/ICE-2715)