Complexity of Deliberative Coalition Formation
Authors: Edith Elkind, Abheek Ghosh, Paul Goldberg4975-4982
AAAI 2022 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | Our goal is to complement the analysis of Elkind et al. (2020), by exploring the complexity of the deliberation process in their model. We focus on two deliberation spaces: in the hypercube model, voters and proposals are vertices of the d-dimensional hypercube, with distances measured according to the Hamming distance, and in the Euclidean model voters and proposals are elements of the d-dimensional Euclidean space, with || ||2 being the underlying distance measure. We consider three types of questions: What is the computational complexity of identifying a proposal approved by as many voters as possible... How many transitions may be necessary... How many coalitions need to be involved... |
| Researcher Affiliation | Academia | Edith Elkind, Abheek Ghosh , Paul Goldberg Department of Computer Science, University of Oxford, UK {edith.elkind,abheek.ghosh,paul.goldberg}@cs.ox.ac.uk |
| Pseudocode | No | The paper focuses on theoretical analysis, proofs, and discussions of computational complexity; it does not include pseudocode or algorithm blocks. |
| Open Source Code | No | The paper provides a link to an extended version on arXiv, but it does not provide concrete access to source code for the methodology described. |
| Open Datasets | No | This is a theoretical paper focusing on complexity analysis and proofs. It does not use empirical data or datasets. |
| Dataset Splits | No | This is a theoretical paper and does not involve dataset splits for training, validation, or testing. |
| Hardware Specification | No | This is a theoretical paper and does not report on experiments run on specific hardware. |
| Software Dependencies | No | This is a theoretical paper; it does not list specific software dependencies with version numbers for reproducing experiments. |
| Experiment Setup | No | This is a theoretical paper and does not include details about an experimental setup, hyperparameters, or training configurations. |