\documentclass[oribibl]{llncs}
\usepackage{subfig}
\usepackage{graphicx}
\usepackage{amsmath,amssymb}
\usepackage[numbers,sectionbib]{natbib}
\usepackage{times}
%\usepackage{amsthm}
\include{ymacros}

\renewcommand\bibsection{\section*{\refname}}


%\theoremstyle{plain}
%\newtheorem{theorem}{Theorem}
%\newtheorem{lemma}{Lemma}
%\newtheorem{corollary}{Corollary}

%\newcommand{\dom}[1]{\mathcal{D}(#1)}


\title{Directional Decomposition of Multiattribute Utility Functions}

\author{Ronen I. Brafman\inst{1} and Yagil Engel\inst{2}}
\institute{Department of Computer Science, Ben Gurion University, Israel \email{brafman@cs.bgu.ac.il}\and Industrial Engineering \& Management, Technion, Israel\\ \email{yagile@ie.technion.ac.il}}
\begin{document}

\maketitle
\begin{abstract}
Several schemes have been proposed for compactly representing multiattribute utility functions, yet none seems to achieve the level of success achieved by Bayesian and Markov models for probability distributions. In an attempt to bridge the gap, we propose a new representation for utility functions which follows its probabilistic analog to a greater extent. Starting from a simple definition of ÒmarginalÓ utility by utilizing reference values, we define a notion of conditional utility which satisfies additive analogues of the chain rule and Bayes rule. We farther develop the analogy to probabilities by describing a directed graphical representation that relies on our concept of conditional independence.  One advantage of this model is that it leads to a natural structured elicitation process, very similar to that of Bayesian networks.
\end{abstract}

\section{Introduction}
Specifying a multi-variate utility function is known to be a difficult task, and often considered a bottleneck in implementation of intelligent systems. It
requires quantifying one's preferences -- a non-trivial cognitive
task which involves contemplating a large number of questions
about the relative desirability of uncertain outcomes, or gambles. Furthermore, the very personal and subjective nature of utility information makes it harder to reuse and learn, unlike probabilistic knowledge, which can often be learned from data and reused for various instances of a system.
Yet, the preference and utility elicitation tasks must be carried out when analyzing
decision problems. A number of attempts have been made to aid this
elicitation process by structuring it so that either the type of
questions that must be answered is simpler and/or the number of
questions is smaller. Often, this process is aided by some graphical
structure that captures some properties of the utility function.
 
The level of success of current formalisms is not clear, partly because assessing
the benefit of various utility elicitation processes is difficult. Even given that current models provide significant theoretical simplifications, the cognitive burden imposed by the elicitation process may still be prohibitive for practical applications. Given the well recognized practical benefits yielded by probabilistic graphical models, it is likely that much more can be done for utilities, too. In this work we attempted to follow the footsteps of probability theory more closely than before, by defining a notion of conditional utility that is closer in form to its probabilistic analog. We then show how this concept leads naturally to milestones such as the chain rule and Bayes rule analogies, and finally to a graphical representation based on a directed acyclic graph.
While our new method of representing and eliciting utilities bears certain similarities to existing methods, as detailed below, it
offers an elicitation process -- both for qualitative
structure and numeric values -- that is clear, simple, and intuitive. Furthermore, it provides immediate computational benefits, and several promising direction for future research that are based on the close resemblance to probabilistic models.
We believe that this method can become an essential part of the
toolkit of decision analysts and an important component in
real-world decision support systems.

\commentout{ 
The essential definition underlying our formalism is one of
conditional utility. Our concept of conditional utility satisfies an
additive form of the chain rule, i.e.,:
$$u(x_1,\ldots,x_n) = u(x_1) + u(x_2|x_1) + \cdots +
u(x_n|x_1,\ldots,x_{n-1}).$$ This means that many of the same
intuitions behind the construction of Bayesian networks~\citep{}
apply here leading to an intuitive process of structure elicitation,
which yields a directed acyclic graphs over the attributes, with the
property that
$$u(x_1,\ldots,x_n) = \sum_{i=1}^n u(x_i|\pa{x_i}).$$}
%Moreover, the questions required to fill the local utility tables
%are local in nature.
 
In the remainder of this paper we define a new notion of
conditional utility and utilize it to define \emph{\net s}. We explain their elicitation process and
compare them to existing formalism for representing structured
utility functions. Finally, we discuss a few open questions.
 
\section{Background and Related Work}
Let $\domain$ denote the space of possible outcomes, with $\prefOrder$ a
preference relation (weak total order) over $\domain$\@.
Let $\attrs = \{\attr{1},\ldots,\attr{n}\}$ denote a set of attributes describing \domain\@. Each attribute $a\in \attrs$ has a domain $\dom{a}$, so that
$\domain \subseteq \prod_{i=1}^n \dom{a_i}$.
We use prime signs and superscripts to denote specific assignment for an attribute, and a concatenation of assignment symbols (as in $\attr{i}'\attr{j}''$) means that each of the attributes gets a respective value. We use $\ssattr{}$ and $\ssattr{i}$ to denote subsets of $\attrs$, and the same notation as before to denote assignments to all the attributes in the set. For example, if $\ssattr{1} = \{\attr{i},\attr{j}\}$, then $\refassign{\ssattr{1}}=\refassign{\attr{i}}\refassign{\attr{j}}$. Finally, we use $\dom{\ssattr{}}$ to denote the set of all possible assignments to $\ssattr{}$, that is the projection of $\domain$ over $\prod_{\attr{i}\in \ssattr{}} \dom{\attr{i}}$.

\begin{definition} Let $\ssattr{1},\ssattr{2}\subset \attrs$.
$\ssattr{1}$ and $\ssattr{2}$ are \emph{conditionally additive independent (CAI)} given their complement $\attrs\setminus (\ssattr{1}\cup\ssattr{2})$, if preferences over lotteries on $\attrs$ depend only on their marginal conditional probability distributions over $\ssattr{1}$ and $\ssattr{2}$.
\end{definition}

Graphical models have been employed for the representation of decomposed utility, as early as by \citep{gorman:ut,Tatman90}. However, the first representation that relies on \emph{conditional independence}, and thus follow the footsteps of probabilistic models, can be attributed to \citet{bg:cai}. These authors show that conditional additive independence has a perfect map, meaning that given a set of attributes and a preference order, there exists a graph whose node separation expresses the exact set of independence conditions. Further, they show that the utility function decomposes to a sum over lower dimensional functions, each defined over a maximal clique of the graph. This decomposition is a special type of \emph{generalized additive independence (GAI)}, a global independence condition introduced originally by \citet{fish:GAI}.

\begin{definition} Let $\ssattr{1},\ldots, \ssattr{g}\subseteq \attrs$ such that $\bigcup_{i=1}^{g} \ssattr{i}=\attrs$.
$\ssattr{1},\ldots, \ssattr{g}$ are called \emph{generalized additive
independent} (GAI) if preferences over lotteries on $\attrs$ depend only
on their marginal distributions over $\ssattr{1},\ldots, \ssattr{g}$.
\label{defn:GAI}
\end{definition}

An (expected) utility function $u(\cdot)$ can be decomposed
additively according to its (possibly overlapping) GAI
sub-configurations.
\begin{theorem} [\cite{fish:GAI}] \label{thm:gai-decomp}
Let $\ssattr{1},\ldots, \ssattr{g}$ be GAI\@. Then there exist functions
$f_{1},\ldots,f_{g}$ such that
\begin{equation}\label{eq:decomp-gai}
u(a_{1},\ldots,a_{m}) = \sum_{r=1}^{g}f_{r}(\ssattr{r}).
\end{equation}
\end{theorem}

Bacchus and Grove revived this notion and named it GAI. This opened the way to an increasing body of research on representation and reasoning with GAI. \citet{bou:ucp} introduce UCP networks, which is a directed form of CAI-maps. The directionality though is obtained from identifying preferential independence conditions over sets of attributes, that is exogenously to the GAI decomposition. \citet{gonzperny:gai} introduce GAI nets, which is a graphical representation for GAI, where nodes represent subsets of attributes, and nodes are connected if their respective subsets intersect. \citet{Braziunas:2005lk} provide a method of elicitation that takes advantage of the locality property of GAI. 

CAI and GAI require comparisons of probability distributions and preferences over lotteries. In applications in which uncertainty is not a crucial element (e.g., electronic commerce applications), it is not required and usually not desired to involve probabilities in user interaction. \citet{Engel:2007cj} extend the work of \cite{ds:measurable} and introduce \emph{conditional difference independence (CDI)}. Intuitively, attributes $x$ and $y$ are CDI of each other if any difference in value over assignments to $x$ does not depend on the current assignment of $y$, for any possible assignment to the rest of the variables. CDI is very similar to CAI, and therefore has a perfect map as well. 

\begin{definition}\footnote{Difference independence and CDI are defined given a preference order over preference differences, and its numeric representation is a measurable value function. For brevity of presentation we describe it in terms of utilities.} 
Let $\ssattr{1},\ssattr{2}\subset \attrs$.
$\ssattr{1}$ and $\ssattr{2}$ are \emph{conditionally difference independent} given $\ssattr{3}=\attrs\setminus (\ssattr{1}\cup\ssattr{2})$, 
denoted as $\mbox{CDI}(X,Y)$, if
\begin{multline*}
\forall \text{ assignments } \hat{\ssattr{3}},  \ssattr{1}',\ssattr{1}'',\ssattr{1}',\ssattr{2}''\\
\utilf{\ssattr{1}' \ssattr{2}' \hat{\ssattr{3}}} - \utilf{\ssattr{1}'' \ssattr{2}' \hat{\ssattr{3}}} = \utilf{\ssattr{1}' \ssattr{2}'' \hat{\ssattr{3}}} - \utilf{\ssattr{1}'' \ssattr{2}'' \hat{\ssattr{3}}}
\end{multline*}
\end{definition}

Our new concept of independence and graphical model most closely resemble CDI. However, in comparison to CDI, it introduces several benefits: (i) it is directional, allowing for a more intuitive elicitation process and (ii) the independence condition is weaker, meaning it can be applied in some cases wherein which CDI does not hold. 

Another direction of research relied on other types of utility independence. CUI networks \citep{Engel:2008wu} is a graphical model that relies on the concept of \emph{conditional utility independence} \citep{keeney}, which intuitively requires the (cardinal) preference order over a subset of the attributes to be independent of another subset of attributes. Earlier works by \citet{shoham:symmetric} and \citet{lms:eun} are also seeking utility representation that is similar to a probability distribution. \citet{shoham:symmetric} proposes a redefinition of utility function as a set function, over additive factors in the domain that together contribute to the decision maker's well being. \citet{lms:eun} propose only a redefinition of the utility independence concept, which is a multiplicative version of difference independence (that is, refers to utility ratios rather than differences). In non-probabilistic settings, and especially in situations in which decision outcomes can be measured against monetary differences (as in purchasing), we believe that utility differences are more natural to elicit than ratios.

A common drawback of most previous models is that most focus is given to the process of data elicitation, whereas the process of \emph{structure elicitation}, in which the independence structure is identified, is usually left to domain experts. This is particularly true for GAI based representations, as UCP and GAI networks, because there is no explicit and intuitive process for identifying and/or verifying GAI conditions. Our novel model, in contrast, has the benefit of an intuitive and incremental structure elicitation process. 

\section{Reference and Conditional Utility}
There are inherent differences between probability distributions and utility functions, which make any analogy between the two problematic. Arguably, the most primal difference is the fact that probability distribution is a set function, defined over events that encapsulate a set of atomic outcomes. In contrast, there is no meaning for the utility of a set of atomic outcomes. For probability distributions, there is a natural definition for a function over a subspace of the world on which the problem is defined. Technically, if the world is represented by a set of attributes $\attrs$, one can define a probability distribution over some $\ssattr{}\subset\attrs$ by summing over the atomic outcomes that hold for any assignment to $\ssattr{}$, thus marginalize out the irrelevant parameters (namely, $\attrs\setminus\ssattr{}$). 

Whereas there is no meaning for marginalizing parameters of a utility function, a similar effect can be achieved by fixing those parameters on some \emph{reference value}. For probabilities, we ask the question \emph{what is the probability of outcomes in $\ssattr{}$ when we don't know the value of $\attrs\setminus\ssattr{}$}. While we do not have an exact analogy for utilities, with reference values we get ask: \emph{what is the utility of outcomes in $\ssattr{}$ when the value of $\attrs\setminus\ssattr{}$ is fixed on the reference}. The idea of using a reference value has been exploited in previous works \citep{fish:GAI,Braziunas:2005lk,Engel:2008wu}, however it was never taken quite as far in driving the analogy to probabilities. 

Let $\refassign{\attr{1}}\ldots\refassign{\attr{n}}\in\domain$ denote a predetermined complete assignment, which we call \emph{the reference assignment}. The reference assignment allows us to define a utility function over a subspace of the joint domain. Let $\overline{\ssattr{}} = \attrs\setminus\ssattr{}$.
\begin{definition}\label{defn:refUtil} The \emph{reference utility function} is defined as follows
 $$\refutilf{\ssattr{}} = \utilf{\ssattr{} \refassign{\overline{\ssattr{}}}}$$
\end{definition}
The next step is to define the notion of conditioning, within a subspace of the domain.
\begin{definition}\label{defn:condUtil} The \emph{conditional utility function} is defined as follows
$$\condutilf{\ssattr{1}}{\ssattr{2}} = \refutilf{\ssattr{1}\ssattr{2}} - \refutilf{\refassign{\ssattr{1}}\ssattr{2}}$$ where $\overline{\ssattr{}} = \attrs\setminus\{\ssattr{1}\cup\ssattr{2}\}$.
\end{definition}
This definition has a direct rooting in the definition of conditional probabilities. The definition of the latter is
$$p(\ssattr{1}|\ssattr{2}) = \frac{p(\ssattr{1}\ssattr{2})}{\ssattr{2}}$$
As common in probabilistic reasoning, we take a log of the definition in order to replace multiplication with additivity. This results exactly in Definition~\ref{defn:condUtil}.

Given that, it is not surprising that the utility function exhibits an additive decomposition which is similar to the multiplicative decomposition of a probability function. We first have to normalize the utility function (henceforth) such that $\utilf{\refassign{\attrs}}=0$.
\begin{theorem}[The chain rule]\label{thm:chain}
$$ \utilf{\attrs} =   \sum_{i=1}^{n} \condutilf{\attr{i}}{\{\attr{j}\}_{j=1}^{i-1}} $$
\end{theorem}
\begin{proof}
By definitions of conditional utility and reference utility,
\begin{multline*}
\condutilf{\attr{i}}{\{\attr{j}\}_{j=1}^{i-1}} =  \refutilf{\attr{1}\ldots\attr{i-1}\attr{i}} - \refutilf{\attr{1}\ldots\attr{i-1}\refassign{\attr{i}}} =\\ \utilf{\attr{1}\ldots\attr{i-1}\attr{i}\refassign{\attr{i+1}}\ldots \refassign{\attr{n}}} - \utilf{\attr{1}\ldots\attr{i-1}\refassign{\attr{i}}\refassign{\attr{i+1}}\ldots \refassign{\attr{n}}}
\end{multline*}
Summing over $i=1,\ldots,n$ on both sides yields the desired result, because: (1) the negative term for $i=1$ is $\utilf{\refassign{\attr{1}}\ldots \refassign{\attr{n}}}=0$, (2) the negative term for $i$ cancels out with the positive term for $i-1$ (both are $\utilf{\attr{1}\ldots\attr{i-1}\refassign{\attr{i}}\refassign{\attr{i+1}}\ldots \refassign{\attr{n}}})$, and (3) the positive term for $i=n$ is $\utilf{\attrs}$.
\qed\end{proof}
Finally, it is easy to see that this definition obeys an additive adaptation of Bayes rule. Again, taking log over the probabilistic equation we obtain the following

\begin{theorem}[Bayes Rule Analog]\label{thm:bayes}
$$ \condutilf{\ssattr{1}}{\ssattr{2}} =  \condutilf{\ssattr{2}}{\ssattr{1}} + \refutilf{\ssattr{1}} - \refutilf{\ssattr{2}}$$
\end{theorem}


\subsection{Conditional Independence}
The chain rule by itself does not provide significant computational value, because the last term ($i=n$) includes the left-hand side of the equation $\utilf{\attrs}$. The idea, similar to the one employed to achieve compact probability functions, is that the conditional utility function $\condutilf{\attr{i}}{\attr{1},\ldots,\attr{i-1}}$ may not depend on all of the attributes $\attr{1},\ldots,\attr{i-1}$, but only on some subset of them, in which case the terms considered by the chain rule have lower dimensionality. This is formalized as follows.

\begin{definition} $\ssattr{1}$ is said to be \emph{conditionally independent} of $\ssattr{2}$ given $\ssattr{3}$ ($\condInd{\ssattr{1}}{\ssattr{2}}{\ssattr{3}}$) if for any $\ssattr{3}'\in \dom{\ssattr{3}}$,
$$ \condutilf{\ssattr{1}}{\ssattr{2}\ssattr{3}'} = \condutilf{\ssattr{1}}{\ssattr{3}'} $$
%$\ssattr{1}$ is said to be \emph{unconditionally independent} of $\ssattr{2}$ if $\ssattr{1}$ is conditionally independent of $\ssattr{2}$ given $\ssattr{3}$, for $\ssattr{3} = \attrs\setminus\{\ssattr{1}\cup\ssattr{2}\}$.
\end{definition}


When $\ssattr{3} = \attrs\setminus \ssattr{1}\cup\ssattr{2}$, then $\condInd{\ssattr{1}}{\ssattr{2}}{\ssattr{3}}$ is equivalent to $\ssattr{1}$ and 
$\ssattr{2}$ being CDI. Therefore, \cind\ is a generalization of $CDI$. The novelty of this definition is that it refers to a subset of the attributes. Whereas in previous independence concepts the conditional set must always be ``the rest of the attributes'', here we specifically select a conditional set, and can ignore the attributes which are not relevant to $\ssattr{1}$.

As an example, consider the values in Table~\ref{table:ex}, which provides the value for the eight different instantiations of three boolean attributes, $x$, $y$, and $z$. The difference between the two values in each column corresponds to the difference in $x$ given difference instantiations of $yz$. 
\begin{table}
\begin{center}
\begin{tabular}{|c|c||c|c|}
  \hline
  $x^{0}yz$ &$x^{0}y^{0}z$&$x^{0}yz^{0}$&$x^{0}y^{0}z^{0}$\\
  $9$&$6$&$6$&$3$\\
  \hline
  $xyz$ &$xy^{0}z$&$xyz^{0}$&$xy^{0}z^{0}$\\
  $12$&$7$&$8$&$5$\\
  \hline \end{tabular}
\caption{Utility for each assignment to attributes $x$, $y$, and $z$.}\label{table:ex}
\end{center}
\end{table}

We see that $\mbox{CDI}(x,y)$ does not hold because $\utilf{xyz}-\utilf{x^{0}yz}\ne \utilf{xy^{0}z}-\utilf{x^{0}y^{0}z}$ (according to the two left columns). In our terms it means that $\condInd{x}{y}{z}$ does not hold. However, $\condInd{x}{y}$ does hold, because the difference is equal for the reference value $z^{0}$ (see the two right columns): $\utilf{xyz^{0}}-\utilf{x^{0}yz^{0}}= \utilf{xy^{0}z^{0}}-\utilf{x^{0}y^{0}z^{0}}$ (or, equivalently, $\condutilf{x}{y}=\condutilf{x}{}$).

\section{\netc s}

Loyal to the Bayes-net analogy, we seek a directed graphical structure, with a node for each attribute, and the following property: each attribute is conditionally directional independent, given its parents, of all its other non-descendants. Let $\pa{\attr{}}$ denote the parents of a node $\attr{}$ in a graph, and let $\dn{\attr{}}$ denote its descendants. Furthermore, let $\co{\attr{}} = \attrs\setminus \{\attr{}\}\cup \pa{\attr{}}\cup \dn{\attr{}}$.
\begin{definition}\label{defn:DAG} A \emph{\net} is a DAG $G=(V,E)$, with $V$ corresponding to a set of attributes $\attrs$, and for any $\attr{}\in \attrs$, $\condInd{\attr{}}{\pa{\attr{}}}{\co{\attr{}}}$.
\end{definition}
The utility computation from the directed graph is again very similar to how probabilities are computed from a Bayes-net. The following theorem is a direct result of the chain rule and Definition~\ref{defn:DAG}.
\begin{theorem}\label{thm:utilComp} The utility function can be computed from the \net\ as follows
$$ \utilf{\attrs} =   \sum_{i=1}^{n} \condutilf{\attr{i}}{\pa{\attr{i}}} $$
\end{theorem}

Previous graphical models usually assume that the model is given, obtained by some domain expert. In particular, how to identify a GAI decomposition remains an unsolved question (except for the case that the GAI structure is a result of a collection of CAI or CDI conditions). Note also that while each pairwise CDI condition requires in theory the verification of order of $\exp(n)$ equalities for utility differences (because a verification is required for each instantiation of the rest of the attributes), with our new notion of conditional independence we only need to consider the independent attributes and the conditioning set. However, we note that when creating a full network this is not a significant advantage, because the number of queries for the \emph{last} variable in the ordering will reach the same order of magnitude as in CDI. %However, it becomes significant when constructing a network or attempting to 

%A common task in decision support system is to query the user for the utility of a specific outcome. Our representation lends itself easily for this task: as evident from Theorem~\ref{thm:utilComp}, it requires $n$ local, natural queries. In contrast, under CDI  and GAI-based models this simple task turns out quite involved - it requires to extract all of the terms in [refer to Fishburn's equation? put it in the background?], which in some (extreme) cases may even be a number of terms which is exponential in the size of largest maximal GAI element.

\subsection{Elicitation}
The process of obtaining a \net\ structure is similar in spirit to that used for Bayesian networks. It is summarized by the following procedure. As is the case in Bayesian network, the result depends on the \emph{variable ordering} that is used by the procedure, and the choice of variable ordering is usually based on heuristic assessments. Intuitively, we would like to place the most important variables first, because these are the variables that are likely to have many connections to other variables. By keeping them on top we avoid having to represent all of these dependencies as parents of the same variable. Furthermore, it makes intuitive sense to have the important variables first, so the dependence between other variables are conditioned on them.

For each variable in its turn, we find a set of parents: those attributes that are required in order to render the current variable independent of the rest. 
We use the notation $\attrs{}^{i}=\{\attr{1},\ldots,\attr{i}\}$, and $(x,y)$ refers to a directed arc from $x\in V$ to $y\in V$.

%\begin{figure}[t]
\begin{tabbing}
{\bf algorithm} $\underline{\procStruct}(\attrs)$\\
\hspace{0.2cm} \= \hspace{0.2cm} \= \hspace{0.2cm} \= \kill
\>\>\> {\it input: $\attrs$, ordered as $\{\attr{1},\ldots,\attr{n}\}$}\\
\>\>\> {\it output: a \net\ over $\attrs$}\\
{\bf for} i=1 to n:\\
\>\> find minimal $\hat{\attrs{}^{i}}\subseteq\attrs{}^{i-1}$ such that $\condInd{\attr{i}}{\attrs{}^{i-1}\setminus\hat{\attrs{}^{i}}}{\hat{\attrs{}^{i}}}$\\
\>\> For each $x\in \hat{\attrs{}^{i}}$, Add $(x,\attr{i})$ to $\arcs$\\
\>{\bf return} $G=(\attrs{},\arcs)$
\end{tabbing}
%\end{figure}
 
The data in the nodes of a \net\ is in form of conditional utility function, that is obtained by querying a user for preference differences. For example, the node $\attr{}$ with parents $\ssattr{}$ requires the function $\condutilf{\attr{}}{\ssattr{}}$, which is obtained by queries for the differences $\refutilf{\attr{}\ssattr{}} - \refutilf{\refassign{\attr{}}\ssattr{}}$.

\subsection{Example}
In order to demonstrate the difference between CDI and \cind, we consider the hard-drive example used by \citet{Engel:2007cj}, and we show their CDI-map of the problem in Figure~\ref{fig:cdi}. The example describes various decision criteria that a procurement department of a company evaluates when purchasing some quantity of new hard-drives. Below, each attribute is listed with a designated attribute name (the first letter), and its (sometimes arbitrary) domain.
\begin{description}
\item [RPM ($R$)]  3600, 4200, 5400 RPM
\item [Transfer rate ($T$)] 3.4, 4.3, 5.7 MBS
\item [Volume ($V$)] 60, 80, 120, 160 GB
\item [Supplier ranking ($S$)] 1, 2, 3, 4, 5
\item [Quality rating ($Q$)] (of the HD brand) 1, 2, 3, 4, 5
\item [Delivery time ($D$)] 10, 15, 20, 25, 30, 35 days
\item [Warranty ($W$)] 1, 2, 3 years
\item [Insurance ($I$)] (for the case the deal is signed but not implemented) $\alpha$, $\beta$, $\gamma$
\item [Payment timeline ($P$)] 10, 30, 90 days
\end{description}
Intuitively, the most salient criterion is volume, and the other important ones are RPM, warranty, and quality; hence the ordering prefix $V, R, W, Q$ seems sensible. The rest of the ordering is less crucial, and we use $I, D, P, T$. First, $V$ is placed as a root. When $R$ is considered next, we find that it depends on $V$ because for high volume hard-drives the marginal utility of improving RPM is higher. We find that $W$ depends on $V$,  because larger hard-drives tend to fail more. Now when considering $Q$, we might find that there is similar dependence between $Q$ and $V$. However, if the  reference value of $W$ is the maximum value (3 years), we might find that given the reference value of $W$ (and the rest of the variables), $Q$ and $V$ are independent because the longer warranty alleviates (substitutes) quality concerns. Further down in the network we might see a similar effect: a convenient value for insurance alleviates the dependency of delivery terms on the payment terms.
In addition, we find the CDI conditions as described by \citet{Engel:2007cj}. For example, given any fixed value of $V$ the marginal value of improving the quality rating does not depend on the RPM. Also, $S$ is CDI and therefore \cind\ of all the rest. We obtain the DAG depicted in Figure~\ref{fig:cdi-r}. The \net\ does not achieve lower dimension than the corresponding CDI-map, however it provides directionality that can be exploited for a more natural elicitation process.

\begin{figure}\centering
\subfloat[]{
\includegraphics[width=170pt]{hdrives_cdi}
\label{fig:cdi}}
\subfloat[]{
\includegraphics[width=150pt]{hdrives}
\label{fig:cdi-r}}\caption{Networks for the example: \subref{fig:cdi} CDI-map \subref{fig:cdi-r} \net.}
\end{figure}

\section{Discussion}\label{sec:discussion}
CDI is a stronger condition than \cind, and as such the locality property it achieves is stronger. To see this, consider the elicitation of data for an attribute $x$. In a CDI-map, the marginal utility over $x$ is independent of the value of any node outside its local neighborhood. Therefore, the marginal utility of $x$ can be elicited using local queries that involve differences over $x$ and given a fixed value of the neighbors, without even knowing the value of the rest of the variables. In \net\, the marginal utility of $x$ may in some cases depend on the value of a non-neighbor $y$. For example, if $y$ is an ancestor of $x$, the marginal value of $x$ is independent of $y$ given any value of $x$'s parents, but only \emph{given that the rest of the variables are fixed on the reference value}. It is possible that there is some instantiation of the rest of the variables, under which the independence is lost. Therefore, elicitation must specify explicitly that the the rest of the variables are fixed on the reference value. 

In fact, this can be seen as an advantage of \net. In CDI-map, such $x$ and $y$ will necessarily have an edge connecting them, whereas in a \net\ such edge can be omitted. In that sense, \net\ refines CDI. Furthermore, if $x$ is fully CDI of $y$, this can be exploited in \net s as well; as long as a local query makes sense to the user there is no need to indicate explicitly that the rest of the variables are fixed on the reference value.

A promising direction coming out of this representation is in introducing a form of Bayesian Learning for utilities. Consider a digital camera manufacturer that wishes to obtain information about customers' preferences. The company may be able to observe some limited set of choices made by customers. Perhaps we can also assume that single dimensional utilities (e.g., how much worths an improvement in a single attribute, all else being equal) is easy to estimate, or elicit. The company can now use the evidence (customer's choices) and Theorem~\ref{thm:bayes}, in order to obtain data regarding future choices of the customer. For example, the customer may have chosen to pay an extra $\$60$ for a camera with $10_{\times}$ zoom and $6_{\mbox{mgp}}$, over one with $7_{\times}$ zoom and $6_{\mbox{mgp}}$. Now (given the single dimensional data, in the form of reference utilities over each attribute) the company can compute the amount that the customer is willing to pay to get $6_{\mbox{mgp}}$ over $4_{\mbox{mgp}}$, given that the zoom is $10_{\times}$.

Practical problem with this direction are yet to be resolved: this assumes that the outcomes above differ only in these two attributes, and in addition the rest of the attributes are fixed on the reference value (or, alternatively, difference independence holds between the two attributes we considered and any other attribute). Furthermore, we should theoretically be able to infer information about a customer only according to choices made by that customer. It is possible though that in some cases heuristic information can be inferred across different customers.

\section{Conclusions}

We propose a new representation scheme for utility functions. Starting from a definition of utility for a subspace of the domain, with respect to reference value of the rest of the attributes, we proceed with a definition of conditional utility as the marginal utility of an attribute, conditioned on some other attributes, and relative to the reference value. We show that conditional utility accommodates the logarithmic adaptations of the chain rule and Bayes rule, and develop the analogy to probabilities further by describing a directed graphical representation that relies on a concept of conditional independence.

In comparison with previous directed models \citep{bou:ucp,Engel:2008wu}, we believe that our representation is simpler and easier to construct. \netc s can be considered an adaptation of CDI-maps into a DAG, and though does not provide reduction of dimensionality, we believe that it has the potential to benefit the field in a similar way to how Bayesian Networks facilitated probabilistic reasoning in comparison to Markov Networks. 

There are several direction to explore following this work. One is the form of Bayesian Learning proposed in Section~\ref{sec:discussion}. Furthermore, the fact that conditional utilities satisfy the chain rule and Bayes rule, implies that it may be possible to perform utility inference using algorithms similar to those that are used for belief propagation. Partial information obtained from observing the agent behavior, possibly coupled with observations about single dimensional preferences of similar users, can be used to infer other preferences. Value conditioning stemming from partial user choices or product constraints can be reasoned with, much like evidence in belief propagation, yielding estimates of the utility of various choices for other attributes.

\section*{Acknowledgements}
Ronen Brafman is partially supported by ISF grant 8254320, by the Paul Ivanier Center for Robotics Research and Production Management, and by the
Lynn and William Frankel Center for Computer Science.
Yagil Engel is supported in part by an Aly Kaufman fellowship at the Technion.

\begin{thebibliography}{13}
\providecommand{\natexlab}[1]{#1}
\providecommand{\url}[1]{\texttt{#1}}
\expandafter\ifx\csname urlstyle\endcsname\relax
  \providecommand{\doi}[1]{doi: #1}\else
  \providecommand{\doi}{doi: \begingroup \urlstyle{rm}\Url}\fi

\bibitem[Bacchus and Grove(1995)]{bg:cai}
Fahiem Bacchus and Adam Grove.
\newblock Graphical models for preference and utility.
\newblock In \emph{Eleventh Conference on Uncertainty in Artificial
  Intelligence}, pages 3--10, Montreal, 1995.

\bibitem[Boutilier et~al.(2001)Boutilier, Bacchus, and Brafman]{bou:ucp}
Craig Boutilier, Fahiem Bacchus, and Ronen~I. Brafman.
\newblock {UCP}-networks: A directed graphical representation of conditional
  utilities.
\newblock In \emph{Seventeenth Conference on Uncertainty in Artificial
  Intelligence}, pages 56--64, Seattle, 2001.

\bibitem[Braziunas and Boutilier(2005)]{Braziunas:2005lk}
Darius Braziunas and Craig Boutilier.
\newblock Local utility elicitation in {GAI} models.
\newblock In \emph{Twenty-first Conference on Uncertainty in Artificial
  Intelligence}, pages 42--49, Edinburgh, 2005.

\bibitem[Dyer and Sarin(1979)]{ds:measurable}
James~S. Dyer and Rakesh~K. Sarin.
\newblock Measurable multiattribute value functions.
\newblock \emph{Operations Research}, 27:\penalty0 810--822, 1979.

\bibitem[Engel and Wellman(2007)]{Engel:2007cj}
Yagil Engel and Michael~P. Wellman.
\newblock Generalized value decomposition and structured multiattribute
  auctions.
\newblock In \emph{Eighth ACM Conference on Electronic Commerce}, pages
  227--236, 2007.

\bibitem[Engel and Wellman(2008)]{Engel:2008wu}
Yagil Engel and Michael~P. Wellman.
\newblock {CUI} networks: A graphical representation for conditional utility
  independence.
\newblock 31:\penalty0 83--112, 2008.

\bibitem[Fishburn(1967)]{fish:GAI}
Peter~C. Fishburn.
\newblock Interdependence and additivity in multivariate, unidimensional
  expected utility theory.
\newblock \emph{International Economic Review}, 8:\penalty0 335--342, 1967.

\bibitem[Gonzales and Perny(2004)]{gonzperny:gai}
Christophe Gonzales and Patrice Perny.
\newblock \uppercase{GAI} networks for utility elicitation.
\newblock In \emph{Ninth International Conference on Principles of Knowledge
  Representation and Reasoning}, pages 224--234, Whistler, BC, Canada, 2004.

\bibitem[Gorman(1968)]{gorman:ut}
William~M. Gorman.
\newblock The structure of utility functions.
\newblock \emph{Review of Economic Studies}, 35:\penalty0 367--390, 1968.

\bibitem[Keeney(1971)]{keeney}
Ralph~L. Keeney.
\newblock Utility independence and preferences for multiattributed
  consequences.
\newblock \emph{Operations Research}, 19\penalty0 (4):\penalty0 875--893, 1971.

\bibitem[La~Mura and Shoham(1999)]{lms:eun}
Piero La~Mura and Yoav Shoham.
\newblock Expected utility networks.
\newblock In \emph{Fifteenth Conference on Uncertainty in Artificial
  Intelligence}, pages 366--373, Stockholm, 1999.

\bibitem[Shoham(1997)]{shoham:symmetric}
Yoav Shoham.
\newblock A symmetric view of probabilities and utilities.
\newblock In \emph{Fifteenth International Joint Conference on Artificial
  Intelligence}, pages 1324--1329, Nagoya, Japan, 1997.

\bibitem[Tatman and Shachter(1990)]{Tatman90}
Joseph~A. Tatman and Ross~D. Shachter.
\newblock Dynamic programming and influence diagrams.
\newblock 20:\penalty0 365--379, 1990.

\end{thebibliography}

%\bibliographystyle{plainnat}
%\bibliography{Engel_ADT}
\end{document}



