More complexity results about reasoning over (m)CP-nets
International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS)
Reason for embargo
Under embargo until 16 July 2018 (completion of conference)
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.
This work was partly supported by the EPSRC grant EP/M025268/ “VADA: Value Added Data Systems – Principles and Architecture”
This is the author accepted manuscript. The final version is available from IFAAMAS via the links in this record
AAMAS (International Conference on Autonomous Agents and Multiagent Systems) 2018, 10-15 July 2018, Stockholm, Sweden, pp. 1540 - 1548