On the Complexity of Finding Justifications for Collective Decisions
Authors: Arthur Boixel, Ronald de Haan5194-5201
AAAI 2021 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | In this paper, we provide computational complexity results that address the problem of finding and verifying justifications for collective decisions. In particular, we focus on the recent development of a general notion of justification for outcomes in voting theory. Such a justification consists of a step-by-step explanation, grounded in a normative basis, showing how the selection of the target outcome follows from the normative principles considered. We consider a language in which normative principles can be encoded either as an explicit list of instances of the principles (by means of quantifier-free sentences), or in a succinct fashion (using quantifiers). We then analyse the computational complexity of identifying and checking justifications. For the case where the normative principles are given in the form of a list of instances, verifying the correctness of a justification is DP-complete and deciding on the existence of such a justification is complete for Sigma 2 P. For the case where the normative principles are given succinctly, deciding whether a justification is correct is in NEXP wedge co NEXP, and NEXP-hard, and deciding whether a justification exists is in EXP with access to an NP oracle and is NEXP-hard. |
| Researcher Affiliation | Academia | Arthur Boixel, Ronald de Haan Institute for Logic, Language and Computation (ILLC), University of Amsterdam a.boixel@uva.nl, me@ronalddehaan.eu |
| Pseudocode | No | The paper focuses on theoretical computational complexity results and proofs, not on providing pseudocode or algorithm blocks for an implementation. |
| Open Source Code | No | The paper is theoretical and does not mention any open-source code release for the described methodology. |
| Open Datasets | No | This paper is theoretical and does not involve experimental training on datasets. Therefore, no information about publicly available datasets is provided. |
| Dataset Splits | No | This paper is theoretical and does not involve empirical validation on datasets, so there are no training/test/validation splits discussed. |
| Hardware Specification | No | The paper is theoretical and does not describe any experimental setup that would require specific hardware. No hardware specifications are mentioned. |
| Software Dependencies | No | The paper is theoretical and does not describe any experimental setup that would require specific software dependencies with version numbers. |
| Experiment Setup | No | The paper is theoretical and focuses on computational complexity proofs. It does not include an experimental setup with hyperparameters or training settings. |