Skip to main content

Combinatorial Preference Aggregation via Global Voting over CP-nets

Enrico Malizia ( University of Exeter )

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.

Speaker bio

Enrico Malizia is Lecturer at the University of Exeter, UK. Before joining the University of Exeter, he was a postdoctoral researcher at the University of Oxford working in theoretical computer science and artificial intelligence with Prof. Georg Gottlob and Prof. Thomas Lukasiewicz. Previous to that, he was a postdoctoral researcher at the University of Calabria, Italy, working mainly in computational game theory with Prof. Francesco Scarcello. His research interests include artificial intelligence, computational complexity, computational game theory & social choice, knowledge representation and reasoning, and algorithms on (hyper)graphs.

Share this: