Notice: The reproducibility variables underlying each score are classified using an automated LLM-based pipeline, validated against a manually labeled dataset. LLM-based classification introduces uncertainty and potential bias; scores should be interpreted as estimates. Full accuracy metrics and methodology are described in [1].
Bypassing Combinatorial Protections: Polynomial-Time Algorithms for Single-Peaked Electorates
Authors: Felix Brandt, Markus Brill, Edith Hemaspaandra, Lane A. Hemaspaandra
JAIR 2015 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | This paper shows that for voters who follow the most central political-science model of electorates single-peaked preferences those hardness protections vanish. By using single-peaked preferences to simplify combinatorial covering challenges, we for the ๏ฌrst time show that NPhard bribery problems including those for Kemeny and Llull elections fall to polynomial time for single-peaked electorates. By using single-peaked preferences to simplify combinatorial partition challenges, we for the ๏ฌrst time show that NP-hard partition-of-voters problems fall to polynomial time for single-peaked electorates. We show that for single-peaked electorates, the winner problems for Dodgson and Kemeny elections, though ฮp 2-complete in the general case, fall to polynomial time. And we completely classify the complexity of weighted coalition manipulation for scoring protocols in single-peaked electorates. The paper primarily focuses on complexity theory, proofs, and algorithm design, indicating a theoretical research type. |
| Researcher Affiliation | Academia | Felix Brandt EMAIL Institut f ur Informatik TU M unchen 85748 Garching, Germany Markus Brill EMAIL Department of Computer Science Duke University Durham, NC 27708, USA Edith Hemaspaandra EMAIL Department of Computer Science Rochester Institute of Technology Rochester, NY 14623, USA Lane A. Hemaspaandra EMAIL Department of Computer Science University of Rochester Rochester, NY 14627, USA |
| Pseudocode | Yes | Algorithm 1 Dodgson winners 1: if V = 0 or C = 0 then 2: return C ... Algorithm 2 weak Condorcet Control by Partition of Voters 1: for all a, b, c, d C such that a L b, c L d, a L c, and p is a weak Condorcet winner in (C , V ) with C = {e C | a L e L b c L e L d} do ... Algorithm 3 Condorcet Control by Partition of Voters 1: for all candidates c that lose against p in a pairwise comparison do |
| Open Source Code | No | The paper does not contain any explicit statements or links indicating that source code for the described methodology is publicly available. Phrases like 'We release our code...' or repository URLs are absent. |
| Open Datasets | No | The paper analyzes theoretical computational complexity within election systems and does not describe or utilize any concrete datasets with access information for empirical evaluation. Therefore, there is no mention of publicly available datasets. |
| Dataset Splits | No | The paper is theoretical and does not describe experiments involving datasets, hence there is no information regarding dataset splits. |
| Hardware Specification | No | The paper is theoretical in nature, focusing on complexity analysis and algorithms. It does not describe experimental implementations or provide any details regarding the hardware used for computations. |
| Software Dependencies | No | The paper is theoretical and focuses on algorithmic complexity rather than empirical implementation. Therefore, it does not specify any software dependencies with version numbers required for replication. |
| Experiment Setup | No | The paper presents theoretical results and algorithms related to computational complexity in election systems. It does not include an experimental section or details on hyperparameter tuning, training configurations, or other specific experimental setup parameters. |