On the Computational Complexity of Non-Dictatorial Aggregation
Authors: Lefteris Kirousis, Phokion G. Kolaitis, John Livieratos
JAIR 2021 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | Our goal is to investigate possibility domains using the algorithmic lens and, in particular, to study the following algorithmic problem: given a set X of feasible evaluations, determine whether or not X is a possibility domain. ... We design a polynomial-time algorithm that, given a set X of feasible evaluations (be it in the Boolean or the non-Boolean framework), decides whether X is a possibility domain. ... Theorems, lemmas, and corollaries are numbered per section, each referring to its own type, whereas claims are numbered within theorems. ... In Section 3, we present our polynomial time algorithms. Specifically, in Subsection 3.1, we present polynomial time algorithms that check whether a domain admits binary non-dictatorial aggregators [Theorem 3.1], whether a domain is totally blocked [Corollary 3.1], and whether a domain is a possibility domain [Theorem 3.2; first main result]. We also show that all domains admit maximum symmetric aggregators [Lemma 3.3] and give a polynomial time algorithm that produces one [Corollary 3.2]. |
| Researcher Affiliation | Collaboration | Lefteris Kirousis EMAIL Department of Mathematics, National and Kapodistrian University of Athens Zografos, GR-157 71 Phokion G. Kolaitis EMAIL Computer Science and Engineering Dept., University of California Santa Cruz and IBM Research 1156 High Street, Santa Cruz, CA 95064 John Livieratos EMAIL Department of Mathematics, National and Kapodistrian University of Athens Zografos, GR-157 71 |
| Pseudocode | No | The paper extensively discusses the design and analysis of polynomial-time algorithms and proves theorems and lemmas related to computational complexity. However, it describes these algorithms conceptually and logically, without presenting any structured pseudocode blocks or formal algorithm figures in the text. |
| Open Source Code | No | The paper does not contain any explicit statements about releasing source code for the methodologies described, nor does it provide links to any code repositories. |
| Open Datasets | No | The paper focuses on theoretical analysis of 'sets of feasible evaluations' or 'domains X' which are abstract or logically defined (e.g., 'Mod(φ)', 'Imp'). It does not use or refer to any publicly available real-world datasets for empirical evaluation, nor does it provide access information for any dataset. |
| Dataset Splits | No | The paper is theoretical and does not involve empirical experiments with datasets. Therefore, there is no mention of dataset splits (e.g., training, test, validation splits). |
| Hardware Specification | No | The paper is theoretical, focusing on computational complexity and algorithm design. It does not describe any empirical experiments that would require specific hardware, and thus no hardware specifications are provided. |
| Software Dependencies | No | The paper is theoretical and does not report on practical implementations or experiments that would require specific software dependencies with version numbers. Software is discussed in a conceptual context (e.g., 'Transitive Closure Logic', 'Least Fixed Point Logic') rather than as tools for implementation. |
| Experiment Setup | No | The paper is theoretical and focuses on mathematical and algorithmic properties. It does not describe any empirical experiments, and therefore no experimental setup details, hyperparameters, or training configurations are provided. |