More complexity results about reasoning over (m)CP-nets
Malizia, E
Date: 1 July 2018
Publisher
International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS)
Related links
Abstract
Aggregating preferences over combinatorial domains has several
applications in artificial intelligence. Due to the exponential nature
of combinatorial preferences, compact representations are
needed, and (m)CP-nets are among the most studied formalisms.
Unlike CP-nets, which received an extensive complexity analysis,
mCP-nets, as ...
Aggregating preferences over combinatorial domains has several
applications in artificial intelligence. Due to the exponential nature
of combinatorial preferences, compact representations are
needed, and (m)CP-nets are among the most studied formalisms.
Unlike CP-nets, which received an extensive complexity analysis,
mCP-nets, as mentioned several times in the literature, lacked
such a thorough characterization. An initial complexity analysis for
mCP-nets was carried out only recently. In this paper, we further
investigate the complexity of mCP-nets. In particular, we prove
the Σ
P
3
-completeness of checking the existence of max optimal outcomes,
which was left as an open problem. We furthermore prove
that various tasks known to be feasible in polynomial time are
actually P-complete. This shows that these problems are inherently
sequential, and hence they cannot benefit from highly parallel computation.
The P-completeness results here proven are among the
very first of this kind in the computational social choice literature.
Computer Science
Faculty of Environment, Science and Economy
Item views 0
Full item downloads 0