Models for Conditional Preferences as extensions of CP-nets

Cristina CornelioIJCAI 2015 · OpenReview

Abstract

Conditional Preference networks (CP-nets) have long served as a standard graphical tool for representing preferences in AI. However, their rigidity and inability to handle uncertainty or multi-agent aggregation limit their utility in complex environments. This paper presents two significant generalizations: LCP-theories, a first-order logic framework for expressive and recursive preferences, and PCP-networks, a probabilistic extension designed for uncertainty and preference aggregation.

Introduction

In artificial intelligence, modeling agent preferences is fundamental to recommendation systems, decision support, and autonomous behavior. While CP-nets effectively capture conditional statements (e.g., "If I am eating fish, I prefer white wine over red"), they suffer from three primary limitations: a specialized syntax that is difficult to integrate with broader logic systems, an inability to represent probabilistic uncertainty, and significant mathematical hurdles when aggregating preferences from multiple agents.

To address these gaps, this research introduces two frameworks that extend the reach of CP-nets into more nuanced, multi-agent, and uncertain domains without sacrificing computational efficiency.

Logical Conditional Preference (LCP) Theories

The LCP framework replaces the specialized graphical syntax of CP-nets with First-Order Logic (FOL). By expressing preferences as universally quantified formulas, LCP-theories provide a more "universal" language for preference modeling.

A key advantage of this logical approach is the ability to represent recursive preferences. In multi-agent systems, one agent's preference may depend on another's (e.g., "If Alice prefers the cinema, then Bob prefers it too"). Standard CP-nets cannot easily model such dependencies, but LCP-theories handle them naturally through logical implication. Furthermore, because it utilizes standard FOL, LCP-theory does not require ad hoc algorithms, allowing for better integration with existing automated reasoning tools.

Probabilistic CP-nets (PCP-nets)

While LCP-theories address expressivity and logic, PCP-networks address uncertainty and aggregation. This framework extends the dependency graph of a CP-net by replacing deterministic preference orderings with probability distributions.

Aggregation and Reasoning

PCP-nets are particularly useful for summarizing the preferences of a group. The paper explores two methods for merging a "profile" of multiple agents into a single PCP-net:

  1. PR (Relative Frequency): Based on the frequency of preferences within the group.
  2. LS (Least Squares): Minimizes the mean squared error between the individual distributions and the collective model.

Reasoning within PCP-nets involves identifying the "most probable optimal outcome" and performing dominance queries—determining if outcome A is collectively preferred over outcome B.

Evaluation and Key Insights

The evaluation of these frameworks relies on mathematical proofs and experimental simulations (referenced from the author's previous work) comparing aggregation accuracy and computational efficiency.

  • Unification and Expressivity: LCP-theories allow for complex social dependencies and recursive logic that were previously impossible to model in standard CP-nets.
  • Compact Multi-Agent Modeling: PCP-nets provide a compact "summary" of a group's preferences. Instead of storing individual models for hundreds of users, a single PCP-net can represent the collective distribution, facilitating efficient storage and communication.
  • Efficient Approximation: Dominance queries are generally NP-hard. However, the author proposes using an approximation interval. For "separable" nets, the lower bound of this interval matches the true value, offering a significant computational shortcut.

Results

Experimental results indicate that LCP-theories maintain computational complexity comparable to state-of-the-art models despite their increased expressivity. In the probabilistic domain, the PR (Relative Frequency) method proved more accurate than the LS approach for aggregation. Additionally, the "optimal outcome of the most probable induced CP-net" was identified as the most reliable metric for determining optimality in uncertain settings.

Limitations and Future Directions

The current frameworks provide a robust foundation but leave room for expansion. Future work includes:

  • Hard Constraints: Integrating strictly forbidden outcomes into the LCP framework.
  • Richer Uncertainty: Utilizing Dempster-Shafer theory to provide more robust approximations for dominance in highly uncertain scenarios.
  • Hybrid Models: Developing a unified framework that incorporates probabilities directly into the LCP logic formulation.

Summary updated

Abstract

This paper presents two frameworks that generalize Conditional Preference networks (CP-nets). The first generalization is the LCP-theory, first order logic theory that provides a rich framework to express preferences. The the second generalization, the PCP-networks, is a probabilistic generalization of CP-nets that models conditional preferences with uncertainty.
BibTeX
@inproceedings{cornelio2015models,
  author = {Cristina Cornelio},
  title = {{Models for Conditional Preferences as extensions of CP-nets}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2015},
  url = {https://openreview.net/forum?id=ry-XYBG_WS},
}
Figure