Complexity Results for Preference Aggregation over (m)CP−Nets: Max and Rank Voting

Abstract

Aggregating preferences over combinatorial domains has a plethora of applications in AI. Due to the exponential nature of combinatorial preferences, compact representations are needed, and conditional ceteris paribus preference networks (CP-nets) are among the most studied compact representation formalisms. Unlike the problem of dominance over individual CP-nets, which received an extensive complexity analysis in the literature, mCP-nets (and global voting/preference aggregation over CP-nets) lacked such a thorough characterization, despite this being reported multiple times in the literature as an open problem. An initial complexity analysis for mCP-nets was carried out only recently. In this paper, we further explore the complexity of mCP-nets, giving a precise complexity analysis of the dominance semantics in mCP-nets when the max and rank voting schemes are considered. In particular, we show that deciding dominance under max voting is Θ_P^2-complete, while deciding optimal outcomes and their existence under max voting is complete for Π_P^2 and §igma_P^3, respectively. We also show that, under max voting, deciding optimum outcomes is Π_P^2-complete, and deciding their existence is Π_P^2-hard and in §igma_P^3. As for rank voting, apart from deciding whether mCP-nets have rank optimal outcomes, which is a trivial problem, since all mCP-nets have rank optimal outcomes, all the other rank voting tasks considered are tractable and in P. Interestingly, we show here that these problems are not only in P, but also P-hard (and hence P-complete). Furthermore, we show that deciding whether mCP-nets have Pareto optimum outcomes, which was known to be feasible in polynomial time, is actually P-complete, as well as that various tasks for CP-nets are P-complete. Hence, these problems are inherently sequential and cannot benefit from highly parallel computation.