Optimal Decision Making with CP-nets and PCP-nets

Probabilistic conditional preference networks (PCP-nets) are a generalization of CP-nets for compactly representing preferences over multi-attribute domains. We introduce the notion of a loss function whose inputs are a CP-net and an outcome. We focus on the optimal decision-making problem for acyclic and cyclic CP-nets and PCP-nets. Our motivations are threefold: (1) our framework naturally extends to allow reasoning on cyclic CP-nets and PCPnets for full generality, (2) in the multi-agent setting, we place no restriction on agents' preferences structure and voting rules under our framework have desirable axiomatic properties, (3) we generalize several previous approaches to finding the optimum outcome in individual and multi-agent contexts. We characterize the computational complexity of computing the loss of a given outcome and computing the outcomes with minimum loss for three natural loss functions: 0-1 loss, neighborhood loss, and global loss. While the optimal decision is NP-hard to compute for many cases, we give a polynomial-time algorithm for computing the optimal decision for tree-structured PCP-nets and profiles of CP-net preferences with a shared dependency structure, w.r.t. neighborhood loss function.