Optimal Bounds for Dissatisfaction in Perpetual Voting
Authors: Alexander Kozachinskiy, Alexander Shen, Tomasz Steifer
AAAI 2025 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We provide a tight upper bound on the growth of dissatisfaction under bounded conflicts, using techniques from Kolmogorov complexity. We also observe that the approval voting with binary choices mimics the machine learning setting of prediction with expert advice. This allows us to present a voting method with sublinear guarantees on dissatisfaction under bounded conflicts, based on the standard techniques from prediction with expert advice. (...) Our proof of Theorem 1 uses the Kolmogorov complexity technique which does not yield an efficient strategy achieving this bound. (...) Next two section contain proofs of Theorems 2 and 1, respectively. Proof of Theorem 3 is omitted due to the space constraints. |
| Researcher Affiliation | Academia | Alexander Kozachinskiy1, Alexander Shen2, Tomasz Steifer34 1Centro Nacional de Inteligencia Artificial, Santiago, Chile 2LIRMM, Univ Montpellier, CNRS, Montpellier, France 3Institute of Fundamental Technological Research, Polish Academy of Sciences, Warsaw, Poland 4Pontificia Universidad Cat olica de Chile, Santiago, Chile EMAIL, EMAIL, EMAIL |
| Pseudocode | No | Our strategy is as follows. Fixing ε, the strategy works by assigning a weight to every agent, initially 1 for everybody, that is multiplied by (1+ε) each time an agent is dissatisfied. The strategy chooses the option that minimally increases the sum of the weights, breaking ties arbitrarily. |
| Open Source Code | No | The paper does not provide any explicit statement about releasing source code, nor does it include links to repositories or mention code in supplementary materials. |
| Open Datasets | No | The paper is theoretical in nature, defining a 'perpetual voting' game as a theoretical model, and does not involve the use of any specific datasets for empirical evaluation or experimentation. |
| Dataset Splits | No | No datasets are used in the paper for experiments; therefore, there is no discussion or specification of dataset splits. |
| Hardware Specification | No | The paper presents theoretical research, including mathematical proofs and algorithmic descriptions, and does not involve an experimental setup that would require specific hardware specifications. |
| Software Dependencies | No | The paper is theoretical and does not describe any implementation of algorithms or experiments that would necessitate listing specific software dependencies with version numbers. |
| Experiment Setup | No | The paper focuses on theoretical analysis, proofs, and algorithms. There are no experiments described, and thus no details regarding hyperparameters, training configurations, or system-level settings are provided. |