Complexity Results for Preference Aggregation over (m)CP-nets: Pareto and Majority Voting
Lukasiewicz, T; Malizia, E
Date: 31 January 2019
Journal
Artificial Intelligence
Publisher
Elsevier
Publisher DOI
Abstract
Aggregating preferences over combinatorial domains has many applications in artificial intelligence (AI). Given the
inherent exponential nature of preferences over combinatorial domains, compact representation languages are needed
to represent them, and (m)CP-nets are among the most studied ones. Sequential and global voting are two ...
Aggregating preferences over combinatorial domains has many applications in artificial intelligence (AI). Given the
inherent exponential nature of preferences over combinatorial domains, compact representation languages are needed
to represent them, and (m)CP-nets are among the most studied ones. Sequential and global voting are two different
ways of aggregating preferences represented via CP-nets. In sequential voting, agents’ preferences are aggregated
feature-by-feature. For this reason, sequential voting may exhibit voting paradoxes, i.e., the possibility to select
sub-optimal outcomes when preferences have specific feature dependencies. To avoid paradoxes in sequential voting,
one has often assumed the (quite) restrictive constraint of O-legality, which imposes a shared common topological
order among all the agents’ CP-nets. On the contrary, in global voting, CP-nets are considered as a whole during the
preference aggregation process. For this reason, global voting is immune from the voting paradoxes of sequential
voting, and hence there is no need to impose restrictions over the CP-nets’ structure when preferences are aggregated
via global voting. Sequential voting over O-legal CP-nets received much attention, and O-legality of CP-nets has
often been required in other studies. On the other hand, global voting over non-O-legal CP-nets has not carefully been
analyzed, despite it was explicitly stated in the literature that a theoretical comparison between global and sequential
voting was highly promising and a precise complexity analysis for global voting has been asked for multiple times.
In quite a few works, only very partial results on the complexity of global voting over CP-nets have been given. In
this paper, we start to fill this gap by carrying out a thorough computational complexity analysis of global voting
tasks, for Pareto and majority voting, over not necessarily O-legal acyclic binary polynomially connected (m)CP-nets.
We show that all these problems belong to various levels of the polynomial hierarchy, and some of them are even in
P or LOGSPACE. Our results are a notable achievement, given that the previously known upper bound for most of
these problems was the complexity class EXPTIME. We provide various exact complexity results showing tight lower
bounds and matching upper bounds for problems that (up to now) did not have any explicit non-obvious lower bound.
Computer Science
Faculty of Environment, Science and Economy
Item views 0
Full item downloads 0
Except where otherwise noted, this item's licence is described as © 2019 Elsevier B.V. All rights reserved.