Proportional Representation under Single-Crossing Preferences Revisited
Authors: Andrei Costin Constantinescu, Edith Elkind5286-5293
AAAI 2021 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We study the complexity of determining a winning committee under the Chamberlin Courant voting rule when voters preferences are single-crossing on a line, or, more generally, on a tree. For the line, Skowron et al. (2015) describe an O(n2mk) algorithm (where n, m, k are the number of voters, the number of candidates and the committee size, respectively); we show that a simple tweak improves the time complexity to O(nmk). We then improve this bound for k = Ω(log n) by reducing our problem to the k-link path problem for DAGs with concave Monge weights, obtaining a nm2O( log k log log n) algorithm for the general case and a nearly linear algorithm for the Borda misrepresentation function. For trees, we point out an issue with the algorithm proposed by Clearwater, Puppe, and Slinko (2015), and develop a O(nmk) algorithm for this case as well. |
| Researcher Affiliation | Academia | Andrei Costin Constantinescu, Edith Elkind University of Oxford |
| Pseudocode | No | The paper describes algorithms (dynamic programming, reduction) but does not contain structured pseudocode or algorithm blocks. |
| Open Source Code | No | The paper states: "Full version The full version of the paper is available on arXiv (Constantinescu and Elkind 2020).". This is a preprint server for papers, not a code repository. No other concrete access to source code is provided. |
| Open Datasets | No | The paper describes theoretical algorithms and complexity analysis. It does not use or refer to any publicly available datasets for training or evaluation. |
| Dataset Splits | No | The paper describes theoretical algorithms and complexity analysis. It does not involve experimental validation with dataset splits. |
| Hardware Specification | No | The paper is theoretical and focuses on algorithm complexity. It does not mention any specific hardware used for running experiments. |
| Software Dependencies | No | The paper describes algorithms theoretically and does not specify any software dependencies with version numbers. |
| Experiment Setup | No | The paper is theoretical and focuses on algorithm design and complexity. It does not describe an experimental setup, hyperparameters, or training configurations. |