Semi-random Impossibilities of Condorcet Criterion
Authors: Lirong Xia
AAAI 2023 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We strengthen previous work by proving the first set of semirandom impossibilities for voting rules to satisfy CC and the more general, group versions of the four desiderata: for any sufficiently large number of voters n, any size of the group 1 B n, any voting rule r, and under a large class of semi-random models that include Impartial Culture, the likelihood for r to satisfy CC and PAR, CC and HM, CC and MM, or CC and SP is 1 Ω( B n). This matches existing lower bounds for CC&PAR (B = 1) and CC&SP and CC&HM (B n), showing that many commonly-studied voting rules are already asymptotically optimal in such cases. |
| Researcher Affiliation | Academia | RPI, Troy, NY, USA xialirong@gmail.com |
| Pseudocode | No | The paper does not contain any structured pseudocode or algorithm blocks. It describes proof steps and concepts through text and diagrams. |
| Open Source Code | No | The paper is theoretical and focuses on proving impossibility theorems; it does not describe a software methodology for which code would be released. There are no statements about releasing open-source code or links to a repository. |
| Open Datasets | No | This paper is theoretical and does not involve the use of datasets for training, validation, or testing. Therefore, it does not provide information about publicly available datasets. |
| Dataset Splits | No | This paper is theoretical and does not involve empirical experiments with data splits. No information regarding training/validation/test dataset splits is provided. |
| Hardware Specification | No | The paper is theoretical and does not describe empirical experiments. Therefore, no hardware specifications for running experiments are mentioned. |
| Software Dependencies | No | The paper is theoretical and does not involve implementation or execution of code that would require specific software dependencies with version numbers. |
| Experiment Setup | No | The paper is theoretical and does not describe an experimental setup with hyperparameters or system-level training settings. |