Correlating Preferences and Attributes: Nearly Single-Crossing Profiles
Authors: Foram Lakhani, Dominik Peters, Edith Elkind
IJCAI 2019 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | The goal of this paper is to evaluate the computational feasibility of this approach. To this end, we investigate the complexity of computing these distances, obtaining an essentially complete picture for the distances we consider. While we develop an efficient algorithm to evaluate the voter deletion distance, for most other metrics we prove that evaluation is NP-hard (see Table 1). This should not be a major impediment to using our notions in practice, and we show that evaluating the swap-based metrics becomes easy (in the FPT or XP sense) if the profile in question is very close to being single-crossing. The literature on structured preferences has introduced and studied problems similar to ours. |
| Researcher Affiliation | Academia | Foram Lakhani , Dominik Peters and Edith Elkind University of Oxford, Oxford, UK foramlakhani@gmail.com, dominik.peters@cs.ox.ac.uk, elkind@cs.ox.ac.uk |
| Pseudocode | No | The paper describes algorithms (e.g., for Global Swaps in Theorem 3's proof) in narrative text rather than using structured pseudocode blocks or clearly labeled algorithm figures. |
| Open Source Code | No | The paper does not mention or provide any links to open-source code for the methodology described. |
| Open Datasets | No | This is a theoretical paper focused on computational complexity and algorithm design. It does not use datasets for empirical training or evaluation. |
| Dataset Splits | No | This is a theoretical paper. It does not involve empirical experiments with training, validation, or test dataset splits. |
| Hardware Specification | No | This is a theoretical paper. It does not mention any specific hardware used for running experiments or computations. |
| Software Dependencies | No | This is a theoretical paper focused on computational complexity. It does not describe any specific software dependencies with version numbers for experimental setup or implementation details. |
| Experiment Setup | No | This is a theoretical paper. It does not describe any experimental setup details such as hyperparameters or training configurations. |