Talks and Poster Presentations (with Proceedings-Entry):
E. Elkind, P. Faliszewski, M. Lackner, S. Obraztsova:
"The Complexity of Recognizing Incomplete Single-Crossing Preferences";
Talk: Twenty-Ninth AAAI Conference on Artificial Intelligence,
Austin, Texas, USA;
- 2015-01-30; in: "Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence, January 25-30, 2015, Austin, Texas, USA",
B. Bonet, S. Koenig (ed.);
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.
single-crossing preferences; incomplete preferences; algorithms
Electronic version of the publication:
Project Head Reinhard Pichler:
SEE: SPARQL Evaluation and Extensions
Created from the Publication Database of the Vienna University of Technology.