A Characterization of the Single-Peaked Single-Crossing Domain
Authors: Edith Elkind, Piotr Faliszewski, Piotr Skowron
AAAI 2014 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We investigate elections that are simultaneously singlepeaked and single-crossing (SPSC). We show that the domain of 1-dimensional Euclidean elections (where voters and candidates are points on the real line, and each voter prefers the candidates that are close to her to the ones that are further away) is a proper subdomain of the SPSC domain, by constructing an election that is single-peaked and singlecrossing, but not 1-Euclidean. We then establish a connection between narcissistic elections (where each candidate is ranked first by at least one voter), single-peaked elections and single-crossing elections, by showing that an election is SPSC if and only if it can be obtained from a narcissistic singlecrossing election by deleting voters. We show two applications of our characterization. We omit many of our proofs due to space restrictions, but all the proofs (and extended discussions) are available as supplementary material. Theorem 14 There is an algorithm that given a SPSC election E with m candidates, a positive integer k m, and a dissatisfaction function α, finds a set of k egalitarian Monroe winners for E. This algorithm runs in time O(m2n). |
| Researcher Affiliation | Academia | Edith Elkind University of Oxford, UK elkind@cs.ox.ac.uk Piotr Faliszewski AGH University, Poland faliszew@agh.edu.pl Piotr Skowron University of Warsaw, Poland p.skowron@mimuw.edu.pl |
| Pseudocode | No | The paper describes algorithmic ideas and theoretical complexity but does not provide structured pseudocode or algorithm blocks. |
| Open Source Code | No | The paper does not provide concrete access to source code for the described methodology. |
| Open Datasets | No | The paper is theoretical and does not use or reference any publicly available datasets for training or evaluation. |
| Dataset Splits | No | The paper is theoretical and does not describe training, validation, or test data splits. |
| Hardware Specification | No | The paper is theoretical and does not mention any specific hardware used for experiments. |
| Software Dependencies | No | The paper is theoretical and does not specify any software dependencies with version numbers. |
| Experiment Setup | No | The paper is theoretical and does not describe an experimental setup. |