Conditional Preference Networks: Constraints, Genuine Decision, and Aggregation

Abstract

A Conditional Preference Network (CP-net) graphically represents user's conditional ceteris paribus (all else being equal) preference statements, while a Tradeoffs enhanced CP-net (TCP-net) extends the CP-net with conditional relative importance statements. To construct the CP-net, a user specifies a (strict) partial order over the values of each variable, which is usually a total order. In case the order is not a total order, a Partial CP-net is used to capture the preferences. On the other hand, a Lexicographic Preference Tree (LP-tree) represents user's conditional lexicographic preferences. This thesis contributes to the models listed above. First, solving the Constrained CP-net model, a CP-net augmented to a set of hard constraints, requires dominance testing. Dominance testing is generally a PSPACEcomplete problem. This makes the Constrained CP-net very hard to apply in practice. In this regard, we alter the CP-net model by eliciting additional preferences and propose the CPR-net model. We show that constrained optimization with the CPRnet or the LP-tree does not require dominance testing, which allows us to develop efficient solving algorithms. However, both the CPR-net and the LP-tree are less expressive than the CP-net. Hence, we suggest a divide and conquer algorithm to answer dominance queries in the CP-net. In theory, the new algorithm outperforms the existing implementation of dominance testing. Second, we propose an algorithm that we call Search-Partial-CP to solve the Constrained Partial CP-net model. The anytime property of Search-Partial-CP ensures that the user can stop the execution as soon as a desired number of solutions is obtained. Then, we propose a linear time method to answer ordering queries in Partial

CP-nets. Interestingly, applying ordering queries instead of dominance testing, in Search-Partial-CP, results in an efficient but incomplete solver. The solver can be applied if time is critical and completeness is not required. Third, to represent user's genuine decision, we introduce the notion of \comfort". We define new binary relations and their semantics to capture both preferences and comfort. Then, we extend the CP-net to represent both preferences and comfort in a multi-attribute case. Fourth, we propose the Probabilistic TCP-net model that can be used to aggregate multi-users' preferences, or to represent single user's preferences with uncertainty. ii