RT Conference Proceedings
T1 Proportional justified representation
A1 Sánchez Fernández, Luis
A1 Elkind, Edith
A1 Lackner, Martin
A1 Fernández García, Norberto
A1 Arias Fisteus, Jesús
A1 Basanta Val, Pablo
A1 Skowron, Piotr
AB 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.
PB AAAI Press
SN 2159-5399 (Print)
SN 2374-3468 (Online)
YR 2017
FD 2017-02-13
LK https://hdl.handle.net/10016/26166
UL https://hdl.handle.net/10016/26166
LA eng
NO Proceedings of: 31st AAAI Conference on Artificial Intelligence (AAAI-17), San Francisco, California, USA, February 4-9, 2017.
NO This research was supported in part by the Spanish Ministerio de Economía y Competitividad (project HERMES-SMARTDRIVER TIN2013-46801-C4-2-R), by the Autonomous Community of Madrid (project e-Madrid S2013/ICE-2715), and by ERC Starting Grant 639945.
DS e-Archivo
RD 17 jul. 2024