On Recognising Nearly Single-Crossing Preferences
Authors: Florian Jaeckle, Dominik Peters, Edith Elkind
AAAI 2018 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We prove that it can be efficiently decided if voters can be split into two single-crossing groups. Also, for every fixed k ≥ 1 we can decide in polynomial time if a profile can be made single-crossing by performing at most k candidate swaps per vote. In contrast, for each k ≥ 3 it is NP-complete to decide whether candidates can be partitioned into k sets so that the restriction of the input profile to each set is single-crossing. Our results are summarised in Table 1. |
| Researcher Affiliation | Academia | Florian Jaeckle, Dominik Peters, Edith Elkind Department of Computer Science University of Oxford, UK |
| Pseudocode | No | The paper describes algorithms in prose, for example, 'Our algorithm proceeds by creating and solving several instances of 2SAT', but it does not include formally structured pseudocode or algorithm blocks. |
| Open Source Code | No | The paper does not provide any statement about the availability of open-source code for the described methodology. |
| Open Datasets | No | This paper is theoretical research and does not use or provide access to any dataset for training. |
| Dataset Splits | No | This paper is theoretical research and does not specify any dataset splits for validation. |
| Hardware Specification | No | This paper is theoretical research and does not describe any specific hardware used for running experiments. |
| Software Dependencies | No | This paper is theoretical research and does not specify any software dependencies with version numbers. |
| Experiment Setup | No | This paper is theoretical research and does not describe any experimental setup details such as hyperparameters or training configurations. |