Solving Influence Diagrams with Simple Propagation

Abstract

Recently, Simple Propagation was introduced as an algorithm for belief update in Bayesian networks using message passing in a junction tree. The algorithm differs from other message passing algorithms such as Lazy Propagation in the message construction process. The message construction process in Simple Propagation identifies relevant potentials and variables to eliminate using the one-in, one-out-principle. This paper introduces Simple Propagation as a solution algorithm for influence diagrams with discrete variables. The one-in, one-out-principle is not directly applicable to influence diagrams. Hence, the principle is extended to cope with decision variables, utility functions, and precedence constraints to solve influence diagrams. Simple Propagation is demonstrated on an extensive example and a number of useful and interesting properties of the algorithm are described.

1 Introduction

An influence diagram [1] is a natural representation of a decision problem where a single decision maker has to make a sequence of decisions under uncertainty. An influence diagram is essentially a Bayesian network [2, 3] augmented with facilities (decision variables, utility functions and precedence constraints) to support decision making under uncertainty. In essence, the solution to a decision problem represented as an influence diagram consists of an optimal strategy specifying which decision option the decision maker should take at each decision depending on the information known to her at that point in time.

Various extensions of traditional influence diagrams have been introduced. These include limited-memory influence diagrams [4], unconstrained influence diagrams [5], and influence diagrams with mixed variables [6]. The focus of this paper is on traditional influence diagrams with discrete variables. The solution of an influence diagram is extended to consist of the optimal strategy, the expected utility of adhering to the optimal strategy and the probability of future decisions. The probability of future decisions under a (optimal) strategy can be determined by encoding the decision policy for each decision as a conditional probability distribution (CPD) [7]. We consider this part of the process of solving an influence diagram.

Some of the popular algorithms for solving the traditional influence diagram include [8,9,10,11,12,13]. One of the first methods for solving influence diagrams was based on Cooper’s technique [14] of transforming the influence diagram into a Bayesian network and using a Bayesian network inference algorithm to solve the influence diagram. Other methods include message passing in a tree and approximation algorithms based on sampling. A recent review of methods for solving influence diagrams can be found here [15] and a survey of probabilistic decision graphs can be found in this paper [16]. Recent work on solving influence diagrams include finding bounds for influence diagrams using join graph decomposition [17] and an improved method for solving hybrid influence diagrams [18].

Simple Propagation [19] is a new algorithm for belief update in Bayesian networks. It proceeds by message passing in a junction tree representation of the Bayesian network taking advantage of a decomposition of clique and separator potentials. In Simple Propagation, message construction is based on a one-in, one-out-principle meaning that a potential relevant for a message has at least one non-evidence variable in the separator and at least one non-evidence variable not in the separator. The advantage of Simple Propagation is its simplicity compared to, for instance, Lazy Propagation [20]. This paper extends Simple Propagation to the solution of traditional influence diagrams, where the solution consists of an optimal strategy, the expected utility of adhering to this strategy and the probability of future decisions under the strategy.

Simple Propagation is extended to cover solutions of traditional influence diagrams by identifying an optimal strategy computing the expected utility, which involves computing the probability of future decisions under the optimal strategy. To achieve this, the one-in, one-out-principle is extended such that it considers both probability and utility potentials. Our approach supports exploitation of probabilistic barren variables [9] and the decomposition of utility potentials reducing the number of calculation operations.

2 Background

A traditional influence diagram over discrete variables is a triple $N=(G, \varPhi ,\varPsi )$ where $G=(V,E)$ is a DAG (directed, acyclic graph) over vertices V and edges $E\subseteq V\times V$. Each vertex $v\in V$ represents a random (or chance) variable, a decision variable, or a utility function. Let $\mathcal{{D}}=\{D_1,\ldots ,D_n\}$ be the set of decision variables and let $\mathcal{{X}}$ be the set of random variables and $\mathcal{{U}}$ be the set of utility nodes. Each random variable $X\in \mathcal{{X}}$ has a CPD $P(X\!\mid \!\mathrm {pa}(X))$, where $\mathrm {pa}(X)$ are the parent vertices of X in G, and each utility node $u\in \mathcal{{U}}$ represents a utility function $u(\mathrm {pa}(u))$ (we use u to denote both the utility node and the utility function). Finally, we denote $\varPhi =\{P(X\!\mid \!\mathrm {pa}(X))\in \mathcal{{X}}\}$, $\varPsi =\{u (\mathrm {pa}(u)) \!\mid \!u\in \mathcal{{U}}\}$, and $\mathrm {dom}(\phi )$ (or $\mathrm {dom}(\psi )$) the domain of $\phi$ ($\psi$).

The influence diagram $N=(G, \varPhi , \varPsi )$ is an efficient representation of a joint expected utility function:

$$\begin{aligned} EU(\mathcal{{X}}, \mathcal{{D}}) = \prod _{X\in \mathcal{{X}}}P(X\!\mid \!\mathrm {pa}(X)) \times \sum _{u\in \mathcal{{U}}} u(\mathrm {pa}(u)). \end{aligned}$$

(1)

The regularity constraints of the traditional influence diagram state that there must be a total order on the decisions and that the decision maker has perfect recall. Assuming decisions are ordered according to index, the random variables can be partitioned into information sets using a partial precedence ordering $\prec$: $\mathcal{{I}}_0\prec D_1\prec \mathcal{{I}}_1\prec \cdots \prec \mathcal{{I}}_{n-1}\prec D_n\prec \mathcal{{I}}_n$. The set $\mathcal{{I}}_i$ is the set of random variables observed (by the decision maker) after making decision $D_i$ and before decision $\mathcal{{I}}_{i+1}$, i.e., $\mathcal{{I}}_0$ is the random variables initially observed and $\mathcal{{I}}_n$ is the set of random variables never observed or observed after the last decision.

In a Bayesian network, a variable X is a barren node when X is never observed, P(X) is of no interest, and the same holds true for each of X’s descendants (if any) [9]. A variable X in an influence diagram is a probabilistic barren node when X is a barren node if only the set of probability potentials are considered [9, 21].

2.1 Strategies, Decision Policies and Future Decisions

A decision policy $\delta _{D_i}(\mathrm {rel}(D_i))$ is a mapping from $\mathrm {rel}(D_i)$ to $D_i$ where $\mathrm {rel}(D_i)\subseteq \bigcup _{j<i}\mathcal{{I}}_j\cup \{D_j\}$ is defined below. A strategy is a collection of decision policies $\varDelta =\{\delta _D \!\mid \!D\in \mathcal{{D}}\}$, one for each decision. A decision policy $\delta _D(\mathrm {rel}(D))$ is encoded as a CPD $P(D\!\mid \!\mathrm {rel}(D))$ as follows:

$$\begin{aligned} P_\varDelta (D=d\!\mid \!\mathrm {rel}(D)=z) = {\left\{ \begin{array}{ll} 1 &{} \text {if } \delta _D(\mathrm {rel}(D)=z) = d \\ 0 &{} \text {otherwise.} \end{array}\right. } \end{aligned}$$

(2)

The strategy $\varDelta$ induces a joint probability distribution:

$$\begin{aligned} P_\varDelta (\mathcal{{X}}\cup \mathcal{{D}}) = \prod _{X\in \mathcal{{X}}}P(X\!\mid \!\mathrm {pa}(X)) \times \prod _{D\in \mathcal{{D}}}P_\varDelta (D\!\mid \!\mathrm {rel}(D)). \end{aligned}$$

(3)

This factorization can be used to compute the probability of future decisions [7]. Notice that the probability of future decisions can be computed under any strategy D.

The expected utility $EU(\varDelta )$ of a strategy $\varDelta$ is the expectation of the total utility $U(\bigcup _{u\in \mathcal{{U}}} \mathrm {pa}(u))=\sum _{u\in \mathcal{{U}}} u(\mathrm {pa}(u))$ under the probability distribution $P_\varDelta (\mathcal{{X}}\cup \mathcal{{D}})$, $\sum _{Y\in \mathcal{{X}}\cup \mathcal{{D}}} U (\bigcup _{u\in \mathcal{{U}}} \mathrm {pa}(u)) \times P_\varDelta (\mathcal{{X}}\cup \mathcal{{D}})$ [22]. A strategy that maximizes the expected utility is an optimal strategy, denoted $\hat{\varDelta }$, and has the property $EU(\hat{\varDelta })\ge EU(\varDelta )$, for all $\varDelta$.

An optimal strategy $\hat{\varDelta }$ and its expected utility of $EU(\hat{\varDelta })$ can be computed as:

$$\begin{aligned} EU(\hat{\varDelta }) = \sum _{\mathcal{{I}}_0}\max _{D_1}\sum _{\mathcal{{I}}_1}\cdots \sum _{\mathcal{{I}}_{n-1}}\max _{D_n}\sum _{\mathcal{{I}}_{n}} EU(\mathcal{{X}},\mathcal{{D}}). \end{aligned}$$

(4)

Under the regularity constraints, the decision policy $\delta _{D_i}$ for decision variable $D_{i}$ can, in principle, be a mapping from all past observations and decisions $\bigcup _{j<i}\mathcal{{I}}_j\cup \{D_j\}$ onto $D_i$ making the policy exponentially large in the number of observations. Luckily, this is often not the case though. That is, not every past observation or decision variable is requisite for a decision, i.e., not all past observations may impact the choice of the decision maker at a decision D. A variable $Y\in \mathrm {pa}(D)\subseteq \mathcal{{X}}\cup \mathcal{{D}}$, $D\in \varDelta$ is non-requisite, if $(\mathcal{{U}}\cap \mathrm {de}(D))\perp \{Y\} \!\mid \!(\mathrm {fa}(D)\setminus \{Y\})$ [4, 23, 24]. This condition states that Y is non-requisite, if it is separated from the utility nodes that are descendents of D given the family of D except Y, i.e., the value of Y does not affect the optimal choice at D. If a variable is not non-requisite, then it is requisite and belongs to the relevant past [7], denoted $\mathrm {rel}(D)$.

2.2 Strong Junction Tree Construction

Simple propagation is performed in a strong junction tree representation. The strong junction tree ensures that variables are eliminated in the reverse order of $\prec$ during evaluation. In addition, it serves as a caching structure through the message passing process.

The construction of a strong junction tree representation $T=(\mathcal{{C}},\mathcal{{S}})$ with cliques $\mathcal{{C}}$ and separators $\mathcal{{S}}$ of influence diagram $N=(G, \varPhi , \varPsi )$ proceeds in four steps [12]:

 

Minimalization :

where information arcs from non-requisite parents of decision nodes are removed.

Moralization :

where each pair of parents $X_i$ and $X_j$ with a common child (representing either a random variable or a utility function) are connected by an undirected edge, all edges are made undirected and utility nodes are removed to produce $G^M$.

Strong Triangulation :

where $G^M$ is triangulated to produce $G^T$ using an elimination order $\sigma$ such that $\sigma (\mathcal{{I}}_{i+1})< \sigma (D_{i+1}) < \sigma (\mathcal{{I}}_{i})$, for all $i\in [0,n-1]$.

Strong Junction Tree Structure :

where the cliques $\mathcal{{C}}$ are connected by separators $\mathcal{{S}}$ producing a tree $T=(\mathcal{{C}},\mathcal{{S}})$ with strong root $R\in \mathcal{{C}}$.

Initialization of Junction Tree :

is the process of assigning $\phi \in \varPhi$ and $\psi \in \varPsi$ to cliques such that $\mathrm {dom}(\phi )\subseteq C$ and $\mathrm {dom}(\psi )\subseteq C$.

 

Notice that in the last step, the initial clique potential $\pi _A=(\varPhi _A,\varPsi _A)$ consists of the set of probability distributions $\varPhi _A=\{P_1,\ldots ,P_l\}$ and the set of utility functions $\varPsi _A=\{u_1,\ldots ,u_m\}$ assigned to A. Simple Propagation proceeds by message passing between neighboring cliques of T. The message from clique B to clique A is denoted $\pi _{B\rightarrow A}=(\varPhi _{B\rightarrow A},\varPsi _{B\rightarrow A})$. The combination of a clique potential $\pi _A=\{\varPhi _A, \varPsi _A\}$ and the message $\pi _{B\rightarrow A}=(\varPhi _{B\rightarrow A},\varPsi _{B\rightarrow A})$ is denoted $\otimes$ and simply amounts to set union, i.e., $\pi _A \otimes \pi _{B\rightarrow A} = (\varPhi _A \cup \varPhi _{B\rightarrow A}, \varPsi _A \cup \varPsi _{B\rightarrow A})$.

If $C\in \mathcal{{C}}$, then $\mathcal{{X}}(C)$ denotes the variables of C and $\mathrm {adj}(C)$ denotes the cliques adjacent to C. Let $A\in \mathrm {adj}(B)$ with A closer to R, then $\mathrm {pa}(B)=A$ denotes the parent clique and $S=A\cap B$ is denoted the parent separator.

3 Simple Propagation

Simple Propagation was introduced by [19] as a message passing algorithm for belief update in Bayesian networks. In this section, Simple Propagation is extended to cover solutions of traditional influence diagrams by identifying an optimal strategy $\hat{\varDelta }$, computing $EU(\hat{\varDelta })$, and computing $P_{\hat{\varDelta }}(D)$, for each ${D\in \mathcal{{D}}}$ under $\hat{\varDelta }$.

When constructing the message $\pi _{A\rightarrow B}$ from clique A to clique B over separator S, Simple Propagation uses the one-in, one-out-principle to order the computations. This means that Simple Propagation is not driven by identifying an elimination order. Instead the elimination order is induced by the order in which potentials satisfying the one-in, one-out-principle are processed. The next potential to consider is selected randomly among the potentials satisfying the principle. In the case of influence diagrams, the induced elimination order must satisfy the partial order $\prec$. This is achieved by applying an extended one-in, one-out-principle relative to the decision variables in clique A, not in clique B, in reverse order of $\prec$ when computing a message up the junction tree.

Let A and B be adjacent cliques with $B=\mathrm {pa}(A)$ and $\pi _A\otimes _{C\in \mathrm {adj}(A)\setminus \{B\}}\pi _{C\rightarrow A}=(\varPhi , \varPsi )$. The one-in, one-out-principle is extended such that it considers both probability and utility potentials, i.e., $\varPhi \cup \varPsi$, when selecting a potential. When constructing the message $\pi _{A\rightarrow B}$, the principle is applied relative to each decision variable $D\in A\setminus B$ in reverse order of $\prec$. For decision variable $D_i\in A\setminus B$ any potential $\omega$ with $D_i\in \mathrm {dom}(\omega )$ such that $\omega$ has a $Y\in \mathrm {dom}(\omega )\cap \mathcal{{I}}_i$ is selected. If, for decision variable $D_i\in \mathcal{{D}}$, there is no potential $\omega$ such that $D_i\in \mathrm {dom}(\omega )$, then D has no descendants and any policy can be assigned to D. Each time a variable must be eliminated, Variable Elimination is applied as the marginalization operation (see Algorithm 3).

Let $\mathcal{{D}}(A)=\{D_{A_1},\ldots ,D_{A_m}\}\subseteq \mathcal{{D}}$ be the set of decision variables in clique A. The variables $\mathcal{{X}}(A)$ of clique A can be partitioned according to the partial precedence ordering $\prec$ and must be processed in reverse order to produce correct results. However, when sending a message from clique A to B, we only have to consider the order of decisions in $A\setminus B$ that must be eliminated when constructing the message $\pi _{A\rightarrow B}$. Once the decisions $A\setminus B$ have been eliminated, the one-in, one-out-principle is applied on the result relative to parent separator $S=A\cap B$ between A and B.

Algorithm 1 shows the general Simple Propagation algorithm for influence diagrams. It solves the influence diagram to identify $\hat{\varDelta }$ and computes $EU(\hat{\varDelta })$ as well as constructs a Bayesian network $N^*$ to compute $\{P_{\hat{\varDelta }}(D) \!\mid \!D\in \mathcal{{D}}\}$. The Bayesian network $N^*$ is constructed from N by changing decision variables to random variables, removing utility functions, and keeping the structure of G induced by the random and decision variables. The algorithm performs a collect operation where messages are passed from the leaf cliques towards R. Next, a Bayesian network is constructed where each decision policy $\delta _{D} (\mathrm {rel}(D))$ is encoded as a CPD $P_{\hat{\varDelta }}(D\!\mid \!\mathrm {rel}(D))$. This is followed by a distribute operation where messages are passed from R towards the leaf cliques. This operation only involves elimination of random variables and proceeds as in Simple Propagation for Bayesian networks [19].

All probability and utility potentials satisfying the one-in, one-out-principle have variables to be eliminated. In addition, any potential $\phi$ (or $\psi$) with $\mathrm {dom}(\phi )\subseteq S$ (or $\mathrm {dom}(\psi )\subseteq S$) must be included in the message.

Algorithm 2 is the Simple Message Computation algorithm applied during the collect operation (SMC-CE). It applies the extended one-in, one-out-principle when processing $\mathcal{{D}}(A)$ in reverse order of $\prec$.

To complete the collect operation, the potential $\pi _R\otimes \bigotimes _{A\in \mathrm {adj}(R)}\pi _{A\rightarrow R}$ of the strong root R of T is marginalized to $\emptyset$ to determine $EU(\hat{\varDelta })$. After the last decision variable to consider in the solution process, i.e., $D_1$, is eliminated, the remaining potentials are processed to compute $EU(\hat{\varDelta })$.

Algorithm 2 applies Algorithm 3 to eliminate a variable (decision or chance) in the message construction process. It is essentially Variable Elimination.

In Algorithm 3, $\varPhi ^{\downarrow -Y}$ denotes marginalization of Y over the set $\varPhi$ using $\sum$ for random variables, i.e., $Y\in \mathcal{{X}}$ and $\max$ for decision variables, i.e., $Y\in \mathcal{{D}}$. In the process of performing a $\max$-marginalization of $D\in \mathcal{{D}}$, the maximizing alternatives for each parent configuration are recorded as the optimal decision rule for D.

Theorem 1

Simple Propagation in an Influence Diagram N computes:

• 1. an optimal strategy $\hat{\varDelta }$ for the decision problem represented as N,

• 2. the expected utility $EU(\hat{\varDelta })$ of $\hat{\varDelta }$, and

• 3. the probability of future decisions $\{P_{\hat{\varDelta }}(D) \!\mid \!D\in \mathcal{{D}}\}$ under $\hat{\varDelta }$.

Proof

Simple Propagation processes the variables in reverse order of $\prec$. Each variable (random or decision) is eliminated using Algorithm 3, which is equivalent to Variable Elimination. Message passing proceeds as in Lazy Propagation. Hence, the calculations performed during the collect operation correspond to solving the influence diagram with Lazy Propagation using the induced elimination ordering [20]. The Bayesian network for computing the probability of future decisions is constructed as described by [7]. The distribute operation proceeds as Simple Propagation in a Bayesian network [19].

4 Analysis

This section considers solving two different influence diagrams with Simple Propagation illustrating the process and the properties of the algorithm.

4.1 Influence Diagram with Four Decisions

Figure 1 shows a commonly used example of an influence diagram $N_{JJD}$ with four decisions introduced by [12]. The figure does not include non-forgetting information links in order to reduce the clutter to a minimum.

Fig. 1.

An influence diagram $N_{JJD}$ with four decisions [12].

Figure 2 shows a strong junction tree representation $T_{JJD}$ of $N_{JJD}$ with strong root $R=BD_1ACDEF$. This is not an optimal junction tree in terms of, for instance, total clique weight, but it serves to illustrate important properties of Simple Propagation for solving influence diagrams. For simplicity, we refer to the two leaf cliques as A and B as indicated in the subscripts of the clique potentials $\pi _A$ and $\pi _B$ in the figure.

Fig. 2.

A junction tree representation $T_{JJD}$ of $N_{JJD}$.

Collect Operation. Simple Propagation solves $N_{JJD}$ by first performing a collect operation on R passing messages $\pi _{A\rightarrow R}$ and $\pi _{B\rightarrow R}$ from the leaf cliques A and B, respectively. The message $\pi _{A\rightarrow R}$ is computed from $\pi _A=(\{P(G\!\mid \!E),P(I\!\mid \!G,D_2),P(L\!\mid \!I,D_4)\},\{u_3(L)\})$, while the message is computed from $\pi _B=(\{P(H\!\mid \!F), P(J\!\mid \!H), P(K\!\mid \!H, D_3)\},\{u_2(D_3),u_4(J,K)\})$.

Consider the construction of the message $\pi _{A\rightarrow R}$ passed from A to R during the collect operation. As $D_2,D_4\in \mathcal{{D}}(A)\setminus R$ and $D_2\prec D_4$, the process of constructing $\pi _{A\rightarrow R}$ starts with $D_4$. In this case, the potential including $D_4$ satisfying the one-in, one-out-principle is $P(L\!\mid \!D_4,I)$, where $I,L\in \mathcal{{I}}_4$ must be eliminated. The vanilla version of Simple Propagation selects randomly between $I,L\in \mathcal{{I}}_4$.

Assume L is selected first. The elimination of L (Algorithm 3) produces $\phi (\cdot \!\mid \!D_4,I) = \sum _L P(L\!\mid \!D_4,I) = 1_{D_4,I}$ and $\psi _X (D_4,I) = \sum _L P(L\!\mid \!D_4,I) u_3(L)$, where $1_{D_4,I}$ is the unity potential indexed by $D_4,I$, i.e., L is probabilistic barren and we do not need to compute this potential nor the division in Algorithm 3. Hence, $\pi _A^{\downarrow -L} = (\{P(G\!\mid \!E),P(I\!\mid \!G,D_2)\},\{\psi (D_4,I)\})$. The next set of potentials satisfying the one-in, one-out-principle is $\{P(I\!\mid \!G,D_2),\psi (D_4,I)\}$. Here, I is the only out-variable and must be eliminated producing $\pi _A^{\downarrow -\{L,I\}} = (\{P(G\!\mid \!E)\},\{\psi (D_4,G,D_2)\})$ as I is probabilistic barren. Now, the variables $\mathcal{{I}}_4$ have been eliminated. Decision variables $D_4$ is eliminated from $\psi (D_4,G,D_2)$ and the decision policy $\delta _{D_4}(G,D_2)$ is identified producing $(\{P(G\!\mid \!E)\},\{\psi (G,D_2)\})$. Finally, variables G and $D_2$ are eliminated to produce the message $\pi _{A\rightarrow R}=\pi _A^{\downarrow E}=(\{\},\{\psi (E)\})$. The induced elimination order is $\sigma =(L,I,D_4,G,D_2)$.

Now assume I is selected first. The elimination of I (Algorithm 3) produces $\phi (L\!\mid \!D_2,G,D_4) = \sum _I P(I\!\mid \!G,D_2)P(L\!\mid \!I,D_4)$. That is, $\pi _A^{\downarrow -I} = (\{P(G\!\mid \!E),P(L\!\mid \!D_2,G,D_4)\},\{\psi (L)\})$. The elimination of I is followed by the elimination of L as $P(L\!\mid \!D_2,G,D_4)$ is the only potential satisfying the one-in, one-out-principle and $L\in \mathcal{{I}}_4$. The process continues as above producing the message $\pi _{A\rightarrow R}=\pi _A^{\downarrow E}=(\{\},\{\psi (E)\})$ with the induced elimination order $\sigma =(I,L,D_4,G,D_2)$. For the message $\pi _{A\rightarrow R}$ the only random element is the selection of the variable to eliminate from $P(L\!\mid \!D_4,I)$.

Next, the construction of the message $\pi _{B\rightarrow R}$ passed from B to R during the collect operation is constructed. The message is $\pi _{B\rightarrow R}=(\{\},\{\psi (F)\})$. Following the collect operation, the root R is processed to identify $\delta _{D_1}(B)$ and compute $EU(\varDelta )$ for $\varDelta =\{\delta _{D_1}(B), \delta _{D_2}(E), \delta _{D_3}(F), \delta _{D_4}(D_2,G)\})$.

The root node is processed similarly.

Distribute Operation. The purpose of the distribute operation is to compute the probability of future decisions under the optimal strategy $\hat{\varDelta }$, i.e., $P_{\hat{\varDelta }} (D)$, for each $D\in \mathcal{{D}}$. Following the collect operation, the Bayesian network $N_{JJD}^*$ is constructed over $\mathcal{{X}}\cup \mathcal{{D}}$, where each decision policy $\delta _D(\mathrm {rel}(D))$ of the optimal strategy $\hat{\varDelta }$ is encoded as a CPD $P(D\!\mid \!\mathrm {rel}(D))$ and D is turned into a random variable. Subsequently, the distribute operation is performed to compute P(D) for each $D\in \mathcal{{D}}$. This process proceeds as the distribute operation in a Bayesian network using Simple Propagation [19].

4.2 Distributive Law

Figure 3(a) shows the structure of a simple influence diagram N with one decision $\mathcal{{D}}=\{D\}$, three random variables $\mathcal{{X}}=\{C_1,C_2,C_3\}$ and two utility functions $\mathcal{{Y}}=\{u_1 (C_1,C_3), u_2(D,C_2)\}$ and Fig. 3(b) shows a strong junction tree T with root $R=C_1DC_3$.

Fig. 3.

An influence diagram and its junction tree representation.

Simple Propagation solves N by first performing a collect operation on R passing the message from clique $DC_2C_3$ to clique $C_1DC_3$. The collect message $\pi _{DC_2C_3\rightarrow C_1DC_3}$ from clique $DC_2C_3$ to clique $C_1DC_3$ is computed as:

$$\begin{aligned} \pi _{DC_2C_3\rightarrow C_1DC_3}= & {} (\emptyset ,\{\sum _{C_2}P(C_2\!\mid \!D,C_3)u_2(D,C_2)\}) \\= & {} (\emptyset ,\{\psi (D,C_3)\}), \end{aligned}$$

where $C_2$ is probabilistic barren making $\varPhi _{DC_2C_3\rightarrow C_1DC_3}=\emptyset$. At the root, we need to determine the policy $\delta _D$ of D and process all potentials to compute $EU(\hat{\varDelta })$. The identification of $\delta _D$ starts from $\psi (D,C_3)$ as this is the only probability or utility potential associated with R and incoming messages that contains D, i.e., $\pi _R\otimes \pi _{DC_2C_3\rightarrow C_1DC_3}$.

The decomposition of clique probability and utility potentials gives a number of advantages. One advantage is the option to exploit the distributive law of algebra when eliminating variables [20, 21]. The distributive law can be exploited when eliminating $C_3$:

$$\begin{aligned}&P(C_1)\times (\psi (C_1) + \psi (C_1,D)) \\= & {} \sum _{C_3} P(C_3)P(C_1\!\mid \!C_3) (u_1(C_1,C_3) + \psi (D,C_3)) \\= & {} \sum _{C_3} (P(C_3)P(C_1\!\mid \!C_3) u_1(C_1,C_3)) + \sum _{C_3}(P(C_3)P(C_1\!\mid \!C_3)\psi (D,C_3)). \end{aligned}$$

This approach supports exploitation of probabilistic barren variables and the decomposition of utility potentials reducing the number of calculation operations.

5 Conclusion

This paper has introduced Simple Propagation as a method for solving influence diagrams with discrete variables exactly and with optimality. The main advantage of Simple Propagation over other methods for finding an optimal strategy and computing the probability of future decisions under an optimal strategy is its simplicity through the absence of the need for graph theoretical considerations to identify the potentials relevant for a message.

The paper has extended the one-in, one-out-principle to cope with decision variables and utility functions to solve influence diagrams. It has also illustrated and described properties of solving influence diagrams with Simple Propagation.

Future work includes considering other algorithms than VE as the variable elimination algorithm as well as solving limited-memory and mixed influence diagrams using Simple Propagation. It also includes considered other computational structures than the strong junction tree as well as any-time approximation.