[Back]


Talks and Poster Presentations (with Proceedings-Entry):

M. Lackner, H. Aziz, E. Elkind, S. Huang, L. Sánchez-Fernández, P. Skowron:
"On the Complexity of Extended and Proportional Justified Representation";
Talk: AAAI 2018, New Orleans, Lousiana, USA; 2018-02-02 - 2018-02-07; in: "Proceedings of the Thirty-Second {AAAI} Conference on Artificial Intelligence, (AAAI-18), the 30th innovative Applications of Artificial Intelligence (IAAI-18), and the 8th {AAAI} Symposium on Educational Advances in Artificial Intelligence (EAAI-18)", AAAI Press, (2018), 902 - 909.



English abstract:
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.

Keywords:
Complexity of Extended; Proportional Justified Representation


Electronic version of the publication:
https://publik.tuwien.ac.at/files/publik_273476.pdf



Related Projects:
Project Head Reinhard Pichler:
Effiziente, parametrisierte Algorithmen in Künstlicher Intelligenz und logischem Schließen

Project Head Stefan Woltran:
START


Created from the Publication Database of the Vienna University of Technology.