A Control Dichotomy for Pure Scoring Rules
Authors: Edith Hemaspaandra, Lane Hemaspaandra, Henning Schnoor
AAAI 2014 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We obtain the first dichotomy theorem for pure scoring rules for a control problem. In particular, for constructive control by adding voters (CCAV), we show that CCAV is solvable in polynomial time for k-approval with k ≤ 3, k-veto with k ≥ 2, every pure scoring rule in which only the two top-rated candidates gain nonzero scores, and a particular rule that is a hybrid of 1-approval and 1-veto. For all other pure scoring rules, CCAV is NP-complete. We also investigate the descriptive richness of different models for defining pure scoring rules, proving how more rule-generation time gives more rules, proving that rationals give more rules than do the natural numbers, and proving that some restrictions previously thought to be w.l.o.g. in fact do lose generality. |
| Researcher Affiliation | Academia | Edith Hemaspaandra Department of Computer Science Rochester Institute of Technology Rochester, NY 14623, USA Lane A. Hemaspaandra Department of Computer Science University of Rochester Rochester, NY 14627, USA Henning Schnoor Institut f ur Informatik Christian-Albrechts-Universit at zu Kiel 24098 Kiel, Germany |
| Pseudocode | No | The paper contains detailed descriptions of reductions and algorithms within the text, but no formally labeled pseudocode or algorithm blocks. |
| Open Source Code | No | The paper does not provide any explicit statements about releasing source code for the described methodology or links to code repositories. |
| Open Datasets | No | This is a theoretical paper focusing on computational complexity and formal proofs related to election systems, and as such, it does not use or reference any datasets for training or evaluation. |
| Dataset Splits | No | This is a theoretical paper focusing on computational complexity and formal proofs related to election systems, and as such, it does not use or specify validation dataset splits. |
| Hardware Specification | No | This is a theoretical paper focused on computational complexity and proofs; it does not describe any specific hardware used for experiments. |
| Software Dependencies | No | This is a theoretical paper focused on computational complexity and proofs; it does not list specific software dependencies with version numbers for experimental reproducibility. |
| Experiment Setup | No | This is a theoretical paper focused on computational complexity and proofs; it does not describe experimental setup details such as hyperparameters or training configurations. |