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].
Preferences Single-Peaked on a Tree: Multiwinner Elections and Structural Results
Authors: Dominik Peters, Lan Yu, Hau Chan, Edith Elkind
JAIR 2022 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We study the complexity of multiwinner elections under several variants of the Chamberlin Courant rule for preferences single-peaked on trees. We show that in this setting the egalitarian version of this rule admits a polynomial-time winner determination algorithm. For the utilitarian version, we prove that winner determination remains NP-hard for the Borda scoring function; indeed, this hardness results extends to a large family of scoring functions. However, a winning committee can be found in polynomial time if either the number of leaves or the number of internal vertices of the underlying tree is bounded by a constant. To benefit from these positive results, we need a procedure that can determine whether a given profile is single-peaked on a tree that has additional desirable properties (such as, e.g., a small number of leaves). To address this challenge, we develop a structural approach that enables us to compactly represent all trees with respect to which a given profile is single-peaked. We show how to use this representation to efficiently find the best tree for a given profile for use with our winner determination algorithms: Given a profile, we can efficiently find a tree with the minimum number of leaves, or a tree with the minimum number of internal vertices among trees on which the profile is single-peaked. We then explore the power and limitations of this framework: we develop polynomial-time algorithms to find trees with the smallest maximum degree, diameter, or pathwidth, but show that it is NP-hard to check whether a given profile is single-peaked on a tree that is isomorphic to a given tree, or on a regular tree. |
| Researcher Affiliation | Collaboration | Dominik Peters EMAIL Department of Computer Science University of Toronto, Toronto, ON, Canada Lan Yu EMAIL Google Inc. Mountain View, CA, USA Hau Chan EMAIL Department of Computer Science and Engineering University of Nebraska Lincoln, NE, USA Edith Elkind EMAIL Department of Computer Science University of Oxford, UK |
| Pseudocode | Yes | Algorithm 1 Trick s algorithm to decide whether a profile is single-peaked on a tree Algorithm 2 Build attachment digraph D = (C, A) of P Algorithm 3 Find T T (P) with fewest internal vertices Algorithm 4 Find T T (P) with fewest leaves Algorithm 5 Decide whether there is T T (P) with maximum degree at most k Algorithm 6 Find a tree T T (P) of minimum pathwidth |
| Open Source Code | No | The paper does not provide an explicit statement about releasing source code for the methodology described, nor does it include a link to a code repository. |
| Open Datasets | No | The paper focuses on theoretical analysis of computational complexity and algorithms for multiwinner elections. It does not use any specific datasets for empirical evaluation, hence no information about publicly available datasets is provided. |
| Dataset Splits | No | The paper is theoretical and does not involve empirical experiments with datasets. Therefore, there is no mention of dataset splits for training, validation, or testing. |
| Hardware Specification | No | The paper describes theoretical algorithms and complexity results. It does not report on any experimental evaluations or computational implementations that would require specific hardware specifications. |
| Software Dependencies | No | The paper presents theoretical algorithms and complexity analysis. It does not describe any software implementations or dependencies with specific version numbers. |
| Experiment Setup | No | The paper is purely theoretical, focusing on algorithm design and complexity analysis. There are no experimental results, and consequently, no experimental setup details or hyperparameters are described. |