Notice: The reproducibility variables underlying each score are classified using an automated LLM-based pipeline, validated against a manually labeled dataset. LLM-based classification introduces uncertainty and potential bias; scores should be interpreted as estimates. Full accuracy metrics and methodology are described in Coakley et alK. L. Coakley, T. Snelleman, H. Hoos, and O. E. Gundersen, "The embrace of open science: An analysis of a decade of AI research and 56 800 conference papers," Under Review, 2026..
On the Complexity of Finding Justifications for Collective Decisions
Authors: Arthur Boixel, Ronald de Haan5194-5201
AAAI 2021 | Venue PDF | 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 EMAIL, EMAIL |
| 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. |