On the Complexity of Extended and Proportional Justified Representation
Authors: Haris Aziz, Edith Elkind, Shenwei Huang, Martin Lackner, Luis Sanchez-Fernandez, Piotr Skowron
AAAI 2018 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | 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 co NP-complete to decide whether a given committee provides PJR. We complement the latter result by fixedparameter tractability results. |
| Researcher Affiliation | Academia | Haris Aziz Data61, CSIRO and UNSW Sydney, Australia Edith Elkind University of Oxford Oxford, UK Shenwei Huang University of New South Wales Sydney, Australia Martin Lackner TU Wien Vienna, Austria Luis S anchez-Fern andez Universidad Carlos III de Madrid, Spain Piotr Skowron TU Berlin Berlin, Germany |
| Pseudocode | Yes | Algorithm 1: LS-PAV: a local search algorithm for PAV |
| Open Source Code | No | The paper does not provide any explicit statements about making source code for its methodology available, nor does it include links to code repositories. |
| Open Datasets | No | The paper is theoretical and does not involve training models or using publicly available datasets for empirical evaluation. Example 1 serves as an illustration, not a dataset. |
| Dataset Splits | No | The paper is theoretical and does not involve experimental training, validation, or test splits of data. |
| Hardware Specification | No | The paper is theoretical and focuses on algorithms and proofs; it does not report on computational experiments that would require specifying hardware details. |
| Software Dependencies | No | The paper is theoretical and does not involve computational experiments that would require specifying software dependencies with version numbers. |
| Experiment Setup | No | The paper is theoretical and does not describe any experimental setup details such as hyperparameters or training configurations. |