The Complexity of Recognizing Incomplete Single-Crossing Preferences
Authors: Edith Elkind, Piotr Faliszewski, Martin Lackner, Svetlana Obraztsova
AAAI 2015 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We study the complexity of deciding if a given profile of incomplete votes... can be extended to a single-crossing profile of complete votes (total orders). This problem models settings where we have partial knowledge regarding voters preferences and we would like to understand whether the given preference profile may be single-crossing. We show that this problem admits a polynomial-time algorithm when the order of votes is fixed and the input profile consists of top orders, but becomes NP-complete if we are allowed to permute the votes and the input profile consists of weak orders or independent-pairs orders. Also, we identify a number of practical special cases of both problems that admit polynomial-time algorithms. |
| Researcher Affiliation | Academia | Edith Elkind University of Oxford Oxford, United Kingdom; Piotr Faliszewski AGH University of Science and Technology Krak ow, Poland; Martin Lackner Vienna University of Technology Vienna, Austria; Svetlana Obraztsova Tel Aviv University, Tel Aviv, Israel & National Technical University of Athens, Athens, Greece |
| Pseudocode | Yes | Algorithm E : The algorithm takes as input a profile R = (r1, . . . , rn) of top orders... Algorithm L : We compute the relation over {r2, . . . , rn} and extend it to relation over R... |
| Open Source Code | No | The paper is theoretical, focusing on computational complexity and algorithms. It does not mention any open-source code release for the methodology described. |
| Open Datasets | No | The paper is theoretical and focuses on computational complexity. It does not use or refer to any datasets for training or evaluation in the context of empirical experiments. |
| Dataset Splits | No | The paper is theoretical and does not involve empirical experiments with dataset splits (e.g., training, validation, test splits) for model evaluation. |
| Hardware Specification | No | The paper is theoretical and does not describe any specific hardware used for running experiments. |
| Software Dependencies | No | The paper is theoretical and discusses algorithms and complexity. It does not mention any specific software dependencies or versions required to replicate a computational setup. |
| Experiment Setup | No | The paper is theoretical, analyzing computational complexity and designing algorithms. It does not describe any empirical experiment setup details, hyperparameters, or system-level training settings. |