Recognising Multidimensional Euclidean Preferences
Authors: Dominik Peters
AAAI 2017 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We show that, in contrast, for every other fixed dimension d > 1, the recognition problem is equivalent to the existential theory of the reals (ETR), and so in particular NP-hard. We further show that some Euclidean preference profiles require exponentially many bits in order to specify any Euclidean embedding, and prove that the domain of d-Euclidean preferences does not admit a finite forbidden minor characterisation for any d > 1. We also study dichotomous preferences and the behaviour of other metrics, and survey a variety of related work. |
| Researcher Affiliation | Academia | Dominik Peters Department of Computer Science University of Oxford, UK dominik.peters@cs.ox.ac.uk |
| Pseudocode | No | The paper does not contain pseudocode or clearly labeled algorithm blocks. |
| Open Source Code | No | The paper does not provide a statement about releasing source code or a link to a code repository. |
| Open Datasets | Yes | We have run some preliminary experiments on the PrefLib dataset (Mattei and Walsh 2013) using the nlsat solver (Jovanovi c and De Moura 2012) which appears to be the strongest ETR-solver available. |
| Dataset Splits | No | The paper mentions using the PrefLib dataset but does not specify any training, validation, or test splits for it. |
| Hardware Specification | No | The paper does not provide specific hardware details (e.g., CPU/GPU models, memory) used for running its experiments. |
| Software Dependencies | No | The paper mentions using the "nlsat solver" but does not specify its version number or any other software dependencies with versions. |
| Experiment Setup | No | The paper mentions attempting experiments with the nlsat solver and a time bound, but does not provide specific experimental setup details like hyperparameters or system-level training settings. |