UCP-Networks: A Directed Graphical Representation of Conditional Utilities
This work addresses the challenge of modeling preferences in decision-making systems, offering a novel representation that improves efficiency, but it appears incremental as it builds on existing graphical models.
The authors tackled the problem of representing utility functions for decision-making by proposing UCP-networks, a directed graphical model that combines generalized additive models and CP-networks, resulting in efficient computation for optimization and dominance queries. They also introduced an interactive elicitation procedure to refine the network until regret falls below a threshold.
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.