On the complexity of extended and proportional justified representation
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; sub...
| Main Authors: | , , , , , |
|---|---|
| Format: | Conference item |
| Language: | English |
| Published: |
AAAI Press
2018
|
| _version_ | 1826264514304147456 |
|---|---|
| author | Aziz, H Elkind, E Huang, S Lackner, M Sánchez-Fernández, L Skowron, P |
| author_facet | Aziz, H Elkind, E Huang, S Lackner, M Sánchez-Fernández, L Skowron, P |
| author_sort | Aziz, H |
| collection | OXFORD |
| description | 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. |
| first_indexed | 2024-03-06T20:09:03Z |
| format | Conference item |
| id | oxford-uuid:29eed7f1-c89f-45a3-8c37-3d9e6f5c3bf1 |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-06T20:09:03Z |
| publishDate | 2018 |
| publisher | AAAI Press |
| record_format | dspace |
| spelling | oxford-uuid:29eed7f1-c89f-45a3-8c37-3d9e6f5c3bf12022-03-26T12:22:00ZOn the complexity of extended and proportional justified representationConference itemhttp://purl.org/coar/resource_type/c_5794uuid:29eed7f1-c89f-45a3-8c37-3d9e6f5c3bf1EnglishSymplectic ElementsAAAI Press2018Aziz, HElkind, EHuang, SLackner, MSánchez-Fernández, LSkowron, PWe 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. |
| spellingShingle | Aziz, H Elkind, E Huang, S Lackner, M Sánchez-Fernández, L Skowron, P On the complexity of extended and proportional justified representation |
| title | On the complexity of extended and proportional justified representation |
| title_full | On the complexity of extended and proportional justified representation |
| title_fullStr | On the complexity of extended and proportional justified representation |
| title_full_unstemmed | On the complexity of extended and proportional justified representation |
| title_short | On the complexity of extended and proportional justified representation |
| title_sort | on the complexity of extended and proportional justified representation |
| work_keys_str_mv | AT azizh onthecomplexityofextendedandproportionaljustifiedrepresentation AT elkinde onthecomplexityofextendedandproportionaljustifiedrepresentation AT huangs onthecomplexityofextendedandproportionaljustifiedrepresentation AT lacknerm onthecomplexityofextendedandproportionaljustifiedrepresentation AT sanchezfernandezl onthecomplexityofextendedandproportionaljustifiedrepresentation AT skowronp onthecomplexityofextendedandproportionaljustifiedrepresentation |