Pareto and Majority Voting in mCP-nets

Aggregating preferences over combinatorial domains has several applications in AI. Due to the exponential nature of combinatorial preferences, compact representations are needed, and CP-nets are among the most studied formalisms. mCP-nets are an intuitive formalism based on CP-nets to reason about preferences of groups of agents. The dominance semantics of mCP-nets is based on voting, and different voting schemes give rise to different dominance semantics for the group. Unlike CP-nets, which received an extensive complexity analysis, mCP-nets, as reported multiple times in the literature, lacked such a thorough characterization. In this paper, we start to fill this gap by carrying out a precise computational complexity analysis of Pareto and majority voting on acyclic binary polynomially-connected mCP-nets.