CP-nets: A Tool for Representing and Reasoning with Conditional Ceteris Paribus Preference Statements

Craig Boutilier
Department of Computer Science
University of Toronto
Toronto, ON M5S 3H5, Canada
email: cebly@cs.toronto.edu

Ronen I. Brafman
Department of Math and Computer Science
Ben-Gurion University
Beer Sheva, ISRAEL 84105
email: brafman@cs.bgu.ac.il

Carmel Domshlak
Department of Computer Science
Cornell University
Ithaca, NY 14853, USA
email: dcarmel@cs.cornell.edu

Holger H. Hoos
Department of Computer Science
University of British Columbia
Vancouver, BC, CANADA, V6T 1Z4
email: hoos@cs.ubc.ca

David Poole
Department of Computer Science
University of British Columbia
Vancouver, BC, CANADA, V6T 1Z4
email: poole@cs.ubc.ca

Abstract
In many domains it is desirable to assess the preferences of users in a qualitative rather than quantitative way. Useful representations of qualitative preference orderings form an important component of automated decision tools. We propose a graphical representation of preferences that reflects conditional dependence and independence of preference statements under a ceteris paribus (all else being equal) interpretation. Such a representation is often compact and arguably quite natural in many circumstances. We provide a formal semantics for this model, and describe how the structure of the network can be exploited in several inference tasks, such as determining whether one outcome dominates (is preferred to) another, ordering a set outcomes according to the preference relation, and constructing the best outcome subject to available evidence.

To appear, Journal of Artificial Intelligence Research (JAIR)

Return to List of Papers