Justified Representation in Approval-Based Committee Voting
Authors: Haris Aziz, Markus Brill, Vincent Conitzer, Edith Elkind, Rupert Freeman, Toby Walsh
AAAI 2015 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We propose a natural axiom for this setting, which we call justified representation (JR). This axiom requires that if a large enough group of voters exhibits agreement by supporting the same candidate, then at least one voter in this group has an approved candidate in the winning committee. We show that for every list of ballots it is possible to select a committee that provides JR. We then check if this axiom is fulfilled by well-known approval-based voting rules. We show that the answer is negative for most of the rules we consider, with notable exceptions of PAV (Proportional Approval Voting), an extreme version of RAV (Reweighted Approval Voting), and, for a restricted preference domain, MAV (Minimax Approval Voting). We then introduce a stronger version of the JR axiom, which we call extended justified representation (EJR), and show that PAV satisfies EJR, while other rules do not. We also consider several other questions related to JR and EJR, including the relationship between JR/EJR and unanimity, and the complexity of the associated algorithmic problems. |
| Researcher Affiliation | Academia | Haris Aziz NICTA and UNSW, Sydney 2033, Australia Markus Brill Duke University Durham, NC 27708, USA Vincent Conitzer Duke University Durham, NC 27708, USA Edith Elkind University of Oxford Oxford OX1 3QD, UK Rupert Freeman Duke University Durham, NC 27708, USA Toby Walsh NICTA and UNSW, Sydney 2033, Australia |
| Pseudocode | No | The paper describes the GAV algorithm in prose but does not present it as a formal pseudocode block or algorithm figure. "We start by setting C = C, A = A, and W = . As long as |W| < k and A is non-empty, we pick a candidate c C that has the highest approval score with respect to A , and set W := W {c}, C := C \ {c}. Also, we remove from A all ballots Ai such that c Ai." This is a textual description rather than a structured pseudocode block. |
| Open Source Code | No | The paper does not contain any explicit statements about releasing source code or provide a link to a code repository. |
| Open Datasets | No | The paper is theoretical and does not utilize or refer to publicly available datasets. It uses abstract "ballot profile A = (A1, . . . , An)" for theoretical analysis. |
| Dataset Splits | No | The paper is theoretical and does not involve empirical experiments with training, validation, or test splits of data. |
| Hardware Specification | No | The paper is theoretical and does not mention any specific hardware used for experiments. |
| Software Dependencies | No | The paper is theoretical and does not mention specific software dependencies with version numbers for experimental reproducibility. |
| Experiment Setup | No | The paper is theoretical and does not describe an experimental setup with hyperparameters or system-level training settings. |