Combinatorial Preference Aggregation via Global Voting over CP-nets

In this talk we will introduce the problem of aggregating combinatorial preferences represented via CP-nets. Sequential and global voting are two ways to aggregate preferences over CP-nets, each of them with pros and cons. Sequential voting, despite it requires heavy structural restrictions over the input, has attracted extensive attention. On the other hand, global voting, which does not requires those restrictions, has not carefully been analyzed, although it was stated in the literature that a comparison between global and sequential voting was promising. We will show the results of a recent thorough complexity analysis of global voting over (m)CP-nets. These problems are shown to belong to the polynomial hierarchy, and some of them are even in PTIME or LOGSPACE, whereas EXPTIME was the previously known upper bound for most of them. Some of them are shown PTIME-complete, which makes these results among the very first of this kind in computational social choice.