Unravelling Expressive Delegations: Complexity and Normative Analysis
Authors: Giannis Tyrovolas, Andrei Constantinescu, Edith Elkind
AAAI 2024 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We consider binary group decision-making under a rich model of liquid democracy: agents submit ranked delegation options, where each option may be a function of multiple agents votes; e.g., I vote yes if a majority of my friends vote yes. Such ballots are unravelled into a proļ¬le of direct votes by selecting one entry from each ballot so as not to introduce cyclic dependencies. We study delegation via monotonic Boolean functions, and two unravelling procedures: MINSUM, which minimises the sum of the ranks of the chosen entries, and its egalitarian counterpart, MINMAX. We provide complete computational dichotomies: MINSUM is hard to compute (and approximate) as soon as any nontrivial functions are permitted, and polynomial otherwise; for MINMAX the easiness results extend to arbitrary-arity logical ORs and ANDs taken in isolation, but not beyond. |
| Researcher Affiliation | Academia | Giannis Tyrovolas1, Andrei Constantinescu2, Edith Elkind3 1Independent 2ETH Zurich 3University of Oxford |
| Pseudocode | No | Fulkerson s algorithm is given in the full version. |
| Open Source Code | No | The paper does not include any statement or link indicating that open-source code for the described methodology is provided. |
| Open Datasets | No | This is a theoretical paper on computational complexity and algorithms; therefore, no datasets are used or referenced for public availability. |
| Dataset Splits | No | This is a theoretical paper and does not involve empirical experiments with data splits for training, validation, or testing. |
| Hardware Specification | No | The paper does not mention any specific hardware used for experiments, as it is a theoretical work. |
| Software Dependencies | No | The paper does not mention any specific software dependencies with version numbers. |
| Experiment Setup | No | The paper is theoretical and does not describe any experimental setup details such as hyperparameters or system-level training settings. |