The Complexity of Recognizing Incomplete Single-Crossing Preferences

Authors

  • Edith Elkind University of Oxford
  • Piotr Faliszewski AGH University of Science and Technology
  • Martin Lackner Vienna University of Technology
  • Svetlana Obraztsova Tel Aviv University and National Technical University of Athens

DOI:

https://doi.org/10.1609/aaai.v29i1.9321

Keywords:

single-crossing preferences, incomplete preferences, algorithms

Abstract

We study the complexity of deciding if a given profile of incomplete votes (i.e., a profile of partial orders over a given set of alternatives) 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.

Downloads

Published

2015-02-16

How to Cite

Elkind, E., Faliszewski, P., Lackner, M., & Obraztsova, S. (2015). The Complexity of Recognizing Incomplete Single-Crossing Preferences. Proceedings of the AAAI Conference on Artificial Intelligence, 29(1). https://doi.org/10.1609/aaai.v29i1.9321

Issue

Section

AAAI Technical Track: Game Theory and Economic Paradigms