The Complexity of Recognizing Incomplete Single-Crossing Preferences


  • 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



single-crossing preferences, incomplete preferences, algorithms


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.




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).



AAAI Technical Track: Game Theory and Economic Paradigms