On the Complexity of Extended and Proportional Justified Representation

Authors

  • Haris Aziz Data61, CSIRO and UNSW, Sydney
  • Edith Elkind University of Oxford, Oxford
  • Shenwei Huang University of New South Wales, Sydney
  • Martin Lackner TU Wien, Vienna
  • Luis Sanchez-Fernandez Universidad Carlos III de Madrid
  • Piotr Skowron TU Berlin, Berlin

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.

Downloads

Published

2018-04-25

How to Cite

Aziz, H., Elkind, E., Huang, S., Lackner, M., Sanchez-Fernandez, L., & Skowron, P. (2018). On the Complexity of Extended and Proportional Justified Representation. Proceedings of the AAAI Conference on Artificial Intelligence, 32(1). Retrieved from https://ojs.aaai.org/index.php/AAAI/article/view/11478

Issue

Section

AAAI Technical Track: Game Theory and Economic Paradigms