UCP-Networks: A Directed Graphical Representation of Conditional Utilities

Abstract

We propose a new directed graphical representation of utility functions, called UCP-networks, that combines aspects of two existing graphical models: generalized additive models and CP-networks. The network decomposes a utility function into a number of additive factors, with the directionality of the arcs reflecting conditional dependence of preference statements - in the underlying (qualitative) preference ordering - under a {em ceteris paribus} (all else being equal) interpretation. This representation is arguably natural in many settings. Furthermore, the strong CP-semantics ensures that computation of optimization and dominance queries is very efficient. We also demonstrate the value of this representation in decision making. Finally, we describe an interactive elicitation procedure that takes advantage of the linear nature of the constraints on "`tradeoff weights" imposed by a UCP-network. This procedure allows the network to be refined until the regret of the decision with minimax regret (with respect to the incompletely specified utility function) falls below a specified threshold (e.g., the cost of further questioning.

Appears in Proceedings of the Seventeenth Conference on Uncertainty in Artificial Intelligence (UAI2001)

References in corpus (2)

• Graphical Models for Preference and Utility
• Expected Utility Networks

Cited by in corpus (11)

• CP-nets: A Tool for Representing and Reasoning withConditional Ceteris Paribus Preference Statements
• On Graphical Modeling of Preference and Importance
• Reasoning about soft constraints and conditional preferences: complexity results and approximation techniques
• Cooperative Negotiation in Autonomic Systems using Incremental Utility Elicitation
• Minimax regret based elicitation of generalized additive utilities
• Probabilistic Conditional Preference Networks
• Multiattribute Auctions Based on Generalized Additive Independence
• More-or-Less CP-Networks
• Unstructuring User Preferences: Efficient Non-Parametric Utility Revelation
• Regret Minimizing Equilibria and Mechanisms for Games with Strict Type Uncertainty
• A CP-Net based Qualitative Composition Approach for an IaaS Provider