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

Craig Boutilier, Ronen I. Brafman, Carmel Domshlak, Holger H. Hoos, David PooleJAIR 2004 · OpenReview

TL;DR

This paper introduces CP-nets, a novel graphical model for representing qualitative user preferences. CP-nets leverage "ceteris paribus" (all else being equal) statements to compactly capture conditional dependencies between preferences, enabling efficient reasoning for tasks like outcome optimization and comparison.

What Problem Does This Paper Address?

Automated decision-making systems often require understanding user preferences. However, eliciting detailed, quantitative utility functions from users can be arduous and impractical, especially for non-expert users. Users often express preferences qualitatively, using statements like "I prefer X over Y, all else being equal." This paper addresses the challenge of representing and reasoning with these natural, qualitative preference statements in a structured and computationally tractable way.

Methods

The core contribution is the CP-net (Conditional Preference network). CP-nets are directed graphical models where nodes represent variables and edges represent conditional dependencies in preferences. The key innovation is the use of conditional ceteris paribus preference statements. For each variable, users specify their preference ordering over its values, given specific instantiations of its parent variables, assuming all other variables remain unchanged. This structure allows for compact representation and efficient inference. The paper formalizes the semantics of CP-nets and develops algorithms for:

  • Outcome Optimization: Finding the best outcome given a partial assignment.
  • Dominance Queries: Determining if one outcome is strictly preferred to another.
  • Ordering Queries: Determining if one outcome can be consistently ordered over another.

The paper also explores techniques like flipping sequences and search algorithms (e.g., TreeDT) to address these queries, analyzing their complexity for various network structures (trees, polytrees, etc.).

Datasets

Not discussed in the paper. The paper focuses on the theoretical framework and algorithms for preference representation and reasoning, rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • "All Else Being Equal" is Powerful: The ceteris paribus assumption, when formalized within a graphical model, allows for surprisingly compact and natural preference representations.
  • Structure Enables Efficiency: The conditional independence encoded in the CP-net structure is crucial for efficient inference, avoiding the need to consider all possible outcomes explicitly.
  • Parental Importance: The semantics implicitly assign higher priority to preferences related to parent variables, meaning violations of parent preferences are generally worse than violations of child preferences.
  • Qualitative is Sufficient: For many decision-making tasks, qualitative preference information is sufficient and more easily elicited than quantitative utility functions.

Key Results

  • Satisfiability of Acyclic CP-nets: Theorem 1 proves that every acyclic CP-net is satisfiable, meaning there exists at least one preference ordering consistent with the specified preferences.
  • Efficient Outcome Optimization: An outcome optimization query can be answered in time linear in the number of variables using a forward sweep algorithm.
  • Ordering Queries are Easy: Ordering queries with respect to acyclic CP-nets can be answered in time linear in the number of variables.
  • Dominance Queries are Harder: Dominance queries are generally NP-complete for binary-valued, directed-path singly connected CP-nets, though polynomial algorithms exist for tree and polytree structures.
  • Flipping Sequences as Proofs: The concept of "flipping sequences" provides a constructive proof for dominance relationships.

Limitations and Future Work

  • Cyclic Networks: While acyclic CP-nets are guaranteed to be satisfiable, cyclic networks present consistency challenges and require further research.
  • Indifference and Partial Specifications: Extending the framework to handle user indifference between outcomes and incompletely specified preferences is an ongoing area of work, with some results presented but open problems remaining.
  • Complexity of Dominance Queries: The exact complexity of dominance testing for general acyclic CP-nets remains an open question.
  • Expressive Power: Understanding the full expressive power of CP-nets and characterizing which preference orderings can be represented is an area for future investigation.
  • Applications: The authors highlight potential applications in adaptive multimedia presentation, distributed meeting scheduling, product database sorting, and constraint-based product configuration, suggesting further research in these areas.

Summary updated

Abstract

Information about user preferences plays a key role in automated decision making. In many domains it is desirable to assess such preferences in a qualitative rather than quantitative way. In this paper, we propose a qualitative 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.
BibTeX
@article{boutilier2004cp,
  author = {Craig Boutilier and Ronen I. Brafman and Carmel Domshlak and Holger H. Hoos and David Poole},
  title = {{CP-nets: A Tool for Representing and Reasoning with Conditional Ceteris Paribus Preference Statements}},
  journal = {J. Artif. Intell. Res.},
  year = {2004},
  url = {https://openreview.net/forum?id=hO4aQsWpyiQ},
}
Figure