Influence Diagram


Based on [1], sections 3.

The paper [2] explains details about influence diagrams.


We define the influence diagram as a directed, acyclic graph such that part of its nodes have a finite number of states associated with them


The sets of nodes consists of chance nodes $C,$ decision nodes $D,$ and value nodes $V$. We index the nodes such that $C∪D=\{1,...,n\}$ and $V=\{n+1,...,n+|V|\}$ where $n=|C|+|D|.$ The set of arcs consists of pairs of nodes such that


where $|N|=|C|+|D|+|V|.$ The condition enforces that the graph is directed and acyclic, and there are no arcs from value nodes to other nodes.

Each chance and decision node $j∈C∪D$ is associates with a finite number of states $S_j.$ We use integers from one to number of states $|S_j|$ to encode individual states


We define the information set of node $j∈N$ to be its predecessor nodes


Practically, the information set is an edge list to reverse direction in the graph.


Paths in influence diagrams represent realizations of states for chance and decision nodes. Formally, a path is a sequence of states

\[𝐬=(s_1, s_2, ...,s_n),\]

where each state $s_i∈S_i$ for all chance and decision nodes $i∈C∪D.$

We define a subpath of $𝐬$ is a subsequence

\[(𝐬_{i_1}, 𝐬_{i_2}, ..., 𝐬_{i_{k}}),\]

where $1≤i_1<i_2<...<i_k≤n$ and $k≤n.$

The information path of node $j∈N$ on path $𝐬$ is a subpath defined as

\[𝐬_{I(j)}=(𝐬_i ∣ i∈I(j)).\]

We define the set of all paths as a product set of all states

\[𝐒=∏_{j∈C∪D} S_j.\]

The set of information paths of node $j∈N$ is the product set of the states in its information set

\[𝐒_{I(j)}=∏_{i∈I(j)} S_i.\]

We denote elements of the sets using notation $s_j∈S_j$, $𝐬∈𝐒$, and $𝐬_{I(j)}∈𝐒_{I(j)}.$


For each chance node $j∈C$, we denote the probability of state $s_j$ given information path $𝐬_{I(j)}$ as

\[ℙ(X_j=s_j∣X_{I(j)}=𝐬_{I(j)})=ℙ(s_j∣𝐬_{I(j)})∈[0, 1],\]


\[∑_{s_j∈S_j} ℙ(s_j∣𝐬_{I(j)}) = 1.\]

Implementation wise, we can think probabilities as functions of information paths concatenated with state $X_j : 𝐒_{I(j)};S_j → [0, 1]$ where $∑_{s_j∈S_j} X_j(𝐬_{I(j)};s_j)=1.$

Decision Strategy

For each decision node $j∈D,$ a local decision strategy maps an information path $𝐬_{I(j)}$ to a state $s_j$


Decision strategy $Z$ contains one local decision strategy for each decision node. Set of all decision strategies is denoted $ℤ.$

A decision stategy $Z∈ℤ$ is compatible with the path $𝐬∈𝐒$ if and only if $Z_j(𝐬_{I(j)})=s_j$ forall $Z_j∈Z$ and $j∈D.$

An active path is path $𝐬∈𝐒$ that is compatible with decision strategy $Z.$ We denote the set of all active paths using $𝐒^Z.$ Since each decision strategy $Z_j$ chooses only one state out of all of its states, the number of active paths is


Path Probability

We define the path probability (upper bound) as

\[p(𝐬) = ∏_{j∈C} ℙ(𝐬_j∣𝐬_{I(j)}).\]

The path probability $ℙ(𝐬∣Z)$ equals $p(𝐬)$ if the path $𝐬$ is compatible with the decision strategy $Z$. Otherwise, the path cannot occur and the probability is zero.


For each value node $j∈V$, we define the consequence given information path $𝐬_{I(j)}$ as


where $ℂ$ is the set of consequences. In the code, the consequences are implicit, and we map information paths directly to the utility values.

The utility function maps consequences to real-valued utilities


Path Utility

The path utility is defined as the sum of utilities for consequences of value nodes $j∈V$ with information paths $I(j)$

\[\mathcal{U}(𝐬) = ∑_{j∈V} U(Y_j(𝐬_{I(j)})).\]

Path Distribution

A path distribution is a pair

\[(ℙ(𝐬∣Z), \mathcal{U}(𝐬))\]

that comprises of path probability function and path utility function over paths $𝐬∈𝐒$ conditional to the decision strategy $Z.$


  • 1Salo, A., Andelmin, J., & Oliveira, F. (2019). Decision Programming for Multi-Stage Optimization under Uncertainty, 1–35. Retrieved from
  • 2Bielza, C., Gómez, M., & Shenoy, P. P. (2011). A review of representation issues and modeling challenges with influence diagrams. Omega, 39(3), 227–241.