On the Satisfiability and Consistency for CP-nets

The conditional preference networks (CP-nets) is a simple and intuitive graphical tool for representing conditional ceteris paribus (all else being equal) preference statements over the values of a set of variables, which has become a research hotspot in artificial intelligence field recently. However, by now there are few works to address its characteristics of satisfiability and consistency, and there are neither strict definition of them, further discussion of their relationships, nor a general algorithm to get a satisfactory ranking. By analyzing the relationships between satisfiability and consistency, two algorithms are proposed to judge the satisfiability and to generate the satisfactory ranking for any structured binary-valued CP-nets. Firstly, by constructing an induced graph of CP-nets and studying its properties, the related theorems on satisfiability and consistency are obtained. Secondly, by analyzing the relations between them, a conclusion is drawn that the satisfiability for CP-nets is equivalent to its consistency. Therefore, the satisfactory ranking for any structured binary-valued CP-nets can be generated with the method of topology sort. What’s more, the syntax, semantics and some definitions of CP-nets are collated and introduced. All these studies can be seen as the improvement and refinement of Boutilier’s related works, and can deepen the basic theory research of CP-nets.