UCP-Networks: A Directed Graphical Representation of Conditional
  Utilities
  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.
