On the Complexity of Extended and Proportional Justified Representation
| Autor: | Aziz, H., Martin Lackner, Elkind, E., Sánchez-Fernández, L., Huang, S., Skowron, P. |
|---|---|
| Rok vydání: | 2018 |
| Předmět: | |
| Zdroj: | Scopus-Elsevier |
| ISSN: | 2374-3468 2159-5399 |
| DOI: | 10.1609/aaai.v32i1.11478 |
| Popis: | We consider the problem of selecting a fixed-size committee based on approval ballots. It is desirable to have a committee in which all voters are fairly represented. Aziz et al. (2015a; 2017) proposed an axiom called extended justified representation (EJR), which aims to capture this intuition; subsequently, Sanchez-Fernandez et al. (2017) proposed a weaker variant of this axiom called proportional justified representation (PJR). It was shown that it is coNP-complete to check whether a given committee provides EJR, and it was conjectured that it is hard to find a committee that provides EJR. In contrast, there are polynomial-time computable voting rules that output committees providing PJR, but the complexity of checking whether a given committee provides PJR was an open problem. In this paper, we answer open questions from prior work by showing that EJR and PJR have the same worst-case complexity: we provide two polynomial-time algorithms that output committees providing EJR, yet we show that it is coNP-complete to decide whether a given committee provides PJR. We complement the latter result by fixed-parameter tractability results. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|