Proportional justified representation

dc.affiliation.dptoUC3M. Departamento de Ingeniería Telemáticaes
dc.affiliation.grupoinvUC3M. Grupo de Investigación: Aplicaciones y Servicios Telemáticos (GAST)es
dc.contributor.authorSánchez Fernández, Luis
dc.contributor.authorElkind, Edith
dc.contributor.authorLackner, Martin
dc.contributor.authorFernández García, Norberto
dc.contributor.authorArias Fisteus, Jesús
dc.contributor.authorBasanta Val, Pablo
dc.contributor.authorSkowron, Piotr
dc.descriptionProceedings of: 31st AAAI Conference on Artificial Intelligence (AAAI-17), San Francisco, California, USA, February 4-9, 2017.en
dc.description.abstractThe 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.en
dc.description.sponsorshipThis 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.en
dc.identifier.bibliographicCitationProceedings of the Thirty-First AAAI Conference on Artificial Intelligence and the Twenty-Ninth Innovative Applications of Artificial Intelligence Conference. California: AAAI Press, 2017, pp. 670-676.en
dc.identifier.issn2159-5399 (Print)
dc.identifier.issn2374-3468 (Online)
dc.identifier.publicationtitleProceedings of the Thirty-First AAAI Conference on Artificial Intelligence and the Twenty-Ninth Innovative Applications of Artificial Intelligence Conferenceen
dc.publisherAAAI Pressen
dc.relation.eventdateFebruary 4-9, 2017en
dc.relation.eventplaceSan Francisco, California, USAen
dc.relation.eventtitleAAAI Conference on Artificial Intelligence (AAAI-17)en
dc.relation.projectIDGobierno de España. TIN2013-46801-C4-2-Res
dc.relation.projectIDComunidad de Madrid. S2013/ICE-2715es
dc.rightsCopyright (c) 2017, Association for the Advancement of Artificial Intelligence ( All rights reserveden
dc.rights.accessRightsopen accessen
dc.subject.otherMulti-winner votingen
dc.subject.otherProportional justified representationen
dc.subject.otherComputational social choiceen
dc.subject.otherDistributed artificial intelligenceen
dc.subject.otherApproval ballotsen
dc.titleProportional justified representationen
dc.typeconference proceedings*
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
235.19 KB
Adobe Portable Document Format