Proportional Justified Representation

Authors

  • Luis Sánchez-Fernández Universidad Carlos III de Madrid
  • Edith Elkind University of Oxford
  • Martin Lackner University of Oxford
  • Norberto Fernández Escuela Naval Militar
  • Jesús Fisteus Universidad Carlos III de Madrid
  • Pablo Basanta Val Universidad Carlos III de Madrid
  • Piotr Skowron University of Oxford

Keywords:

representation, multi-winner voting rules, approval ballots

Abstract

The goal of multi-winner elections is to choose a fixed-size committee based on voters’ preferences. An important concern in this setting is representation: large groups of voters with cohesive preferences should be adequately represented by the election winners. Recently, Aziz et al. proposed two axioms that aim to capture this idea: justified representation (JR) and its strengthening extended justified representation (EJR). In this paper, we extend the work of Aziz et al. in several directions. First, we answer an open question of Aziz et al., by showing that Reweighted Approval Voting satisfies JR for k = 3; 4; 5, but fails it for k >= 6. Second, we observe that EJR is incompatible with the Perfect Representation criterion, which is important for many applications of multi-winner voting, and propose a relaxation of EJR, which we call Proportional Justified Representation (PJR). PJR is more demanding than JR, but, unlike EJR, it is compatible with perfect representation, and a committee that provides PJR can be computed in polynomial time if the committee size divides the number of voters. Moreover, just like EJR, PJR can be used to characterize the classic PAV rule in the class of weighted PAV rules. On the other hand, we show that EJR provides stronger guarantees with respect to average voter satisfaction than PJR does.

Downloads

Published

2017-02-10

How to Cite

Sánchez-Fernández, L., Elkind, E., Lackner, M., Fernández, N., Fisteus, J., Basanta Val, P., & Skowron, P. (2017). Proportional Justified Representation. Proceedings of the AAAI Conference on Artificial Intelligence, 31(1). Retrieved from https://ojs.aaai.org/index.php/AAAI/article/view/10611

Issue

Section

AAAI Technical Track: Game Theory and Economic Paradigms