Committees providing EJR can be computed efficiently

2017/04/02 by Luis Sánchez Fernández, Sánchez-Fernández, Luis, Edith Elkind +3 · 1 citation
Computer Science · Decision Sciences · Economics, Econometrics and Finance · #91A35 #Auction Theory and Applications #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Computer Science and Game Theory (cs.GT) #F.2 #FOS: Computer and information sciences #Game Theory and Voting Systems #I.2.11

paper · pdf · doi:10.48550/arxiv.1704.00356

openalex publication_date 2017/04/02 · openalex created_date 2017/05/19 · openalex updated_date 2026/07/28

Abstract

We identify a whole family of approval-based multi-winner voting rules that satisfy PJR. Moreover, we identify a subfamily of voting rules within this family that satisfy EJR. All these voting rules can be computed in polynomial time as long as the subalgorithms that characterize each rule within the family are polynomial. One of the voting rules that satisfy EJR can be computed in O(n m k).

Cited by

• Robust Committee Voting, or The Other Side of Representation

Related

• A Polynomial-time Algorithm to Achieve Extended Justified Representation
• Justified Representation in Approval-Based Committee Voting
• On the Parallelizability of Approval-Based Committee Rules
• Optimal Average Satisfaction and Extended Justified Representation in Polynomial Time
• The Degree of (Extended) Justified Representation and Its Optimization