TY - JOUR
AU - Elkind, Edith
AU - Faliszewski, Piotr
AU - Lackner, Martin
AU - Obraztsova, Svetlana
PY - 2015/02/16
Y2 - 2024/04/18
TI - The Complexity of Recognizing Incomplete Single-Crossing Preferences
JF - Proceedings of the AAAI Conference on Artificial Intelligence
JA - AAAI
VL - 29
IS - 1
SE - AAAI Technical Track: Game Theory and Economic Paradigms
DO - 10.1609/aaai.v29i1.9321
UR - https://ojs.aaai.org/index.php/AAAI/article/view/9321
SP -
AB - <p> 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. </p>
ER -