Influence Diagram

Introduction

Decision programming uses influence diagrams, a generalization of Bayesian networks, to model multi-stage decision problems under uncertainty. This section defines the influence diagrams and discusses their properties. It is based on the definitions in ^[1], ^[2], and ^[3].

Definition

We define the influence diagram as a directed, acyclic graph $G=(C,D,V,A,S).$ We describe the nodes $N=C∪D∪V$ with $C∪D=\{1,...,n\}$ and $n=|C|+|D|$ as follows:

1. Chance nodes $C⊆\{1,...,n\}$ (circles) represent uncertain events associated with random variables.
2. Decision nodes $D⊆\{1,...,n\}$ (squares) correspond to decisions among discrete alternatives.
3. Value nodes $V=\{n+1,...,n+|V|\}$ (diamonds) represent consequences that result from the realizations of random variables at chance nodes and the decisions made at decision nodes.

The connections between different nodes (arrows) are called arcs $a \in A$. The arcs represent different dependencies between the nodes.

We define the information set $I$ of node $j∈N$ as the set of predecessors of $j$ in the graph:

\[I(j)⊆\{i∈C∪D ∣ (i,j) \in A\, i<j\}\]

Practically, the information set is a collection of arcs in the reverse direction in the graph. Informally, it tells us which node's information is available to the current node. The conditions enforce that the graph is acyclic, and there are no arcs from value nodes to other nodes.

In an influence diagram, each chance and decision node $j∈C∪D$ is associates with a finite number of states $S_j$ that we encode using integers $S_j=\{1,...,|S_j|\}$ from one to number of states $|S_j|≥1.$ A node $j$ is trivial if it has only one state, $|S_j|=1.$ We refer to the collection of all states $S=\{S_1,...,S_n\}$ as the state space.

Root and Leaf Nodes

A chance or decision node is a root node if it is not affected by other chance or decision nodes. Formally, node $j∈C∪D$ is a root node if $I(j)=∅.$

A chance or decision node is a leaf node if it does not affect other chance or decision nodes. Formally, node $j∈C∪D$ is a leaf node if $j∉I(i)$ for all $i∈C∪D.$

Drawing Nodes and Arcs

We use a circle to represent chance nodes, a square to represent decision nodes, and a diamond to represent value nodes. The symbol $i$ represents the node's index and symbol $S_i$ the states of the chance or decision node. We use the following colors and styling:

• Chance nodes: Fill color F5F5F5 and line color 666666.
• Decision nodes: Fill color D5E8D4 and line color 82B366
• Value nodes: Fill color FFE6CC and line color D79B00
• Linewidth 2pt and perimeter 2pt (padding around the node).

We represent directed arcs using arrows from a source node to a target node, colored with the target node's line color. We recommend diagrams.net for drawing graphs.

Drawing Layered Graph

We showed the influence diagram as a linear graph in the Definition section. We can also draw a more concise layered graph, which is better at displaying the influence relationship structure — only nodes at smaller depth influence nodes at greater depth. Also, root and leaf nodes are visible from the layered form.

We define the depth of a node $j∈N$ as follows. Root nodes have a depth of one

\[\operatorname{depth}(j)=1,\quad I(j)=∅.\]

Other nodes have a depth of one greater than the maximum depth of its predecessors

\[\operatorname{depth}(j)=\max_{i∈I(j)} \operatorname{depth}(i) + 1,\quad I(j)≠∅.\]

We can then draw the layered graph by grouping the nodes by their depth, ordering the groups by increasing depth and increasing indices order within each group.

Paths

In influence diagrams, paths represent realizations of states for chance and decision nodes. For example, the above tree represents generating all paths with states $S_1=\{1,2\}$ and $S_2=\{1,2,3\}.$

Formally, a path is a sequence of states

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

where a state $s_i∈S_i$ is defined for all chance and decision nodes $i∈C∪D.$ We denote the set of paths as

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

We define a subpath of $𝐬$ with $A⊆C∪D$ as a subsequence

\[𝐬_A=(𝐬_{i}∣i∈A)∈𝐒_A.\]

We denote the set of subpaths as

\[𝐒_A=∏_{i∈A} S_i.\]

We define the number of paths as

\[|𝐒_A|=∏_{i∈A}|S_i|.\]

As mentioned above, each node $j∈N$ has an information set $I(j)$. A subpath, which is formed by the states of the nodes in the information set, is referred to as an information state $𝐬_{I(j)}$ of node $j$. The set of these subpaths is called the information states $𝐒_{I(j)}$ of node $j∈N.$

Also note that $𝐒=𝐒_{C∪D},$ and $𝐒_{i}=S_i$ and $𝐬_i=s_i$ where $i∈C∪D$ is an individual node.

Probabilities

Each chance node is associated with a set of discrete probability distributions over its states. Each of the probability distributions corresponds to one of the node's information states. Formally, for each chance node $j∈C$, we denote the probability of state $s_j$ given information state $𝐬_{I(j)}$ as

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

with

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

A chance state with a given information state is considered active if its probability is nonzero

\[ℙ(X_j=s_j∣X_{I(j)}=𝐬_{I(j)})>0.\]

Otherwise, it is inactive.

Decision Strategies

Each decision strategy models how the decision maker chooses a state $s_j∈S_j$ given an information state $𝐬_{I(j)}$ at decision node $j∈D.$ A decision node can be seen as a special type of chance node, such that the probability of the chosen state given an information state is fixed to one

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

By definition, the probabilities for other states are zero.

Formally, for each decision node $j∈D,$ a local decision strategy is a function that maps an information state $𝐬_{I(j)}$ to a state $s_j$

\[Z_j:𝐒_{I(j)}↦S_j.\]

A decision strategy contains one local decision strategy for each decision node

\[Z=\{Z_j∣j∈D\}.\]

The set of all decision strategies is denoted with $ℤ.$

Path Probability

The probability distributions at chance and decision nodes define the probability distribution over all paths $𝐬∈𝐒,$ which depends on the decision strategy $Z∈ℤ.$ We refer to it as the path probability

\[ℙ(X=𝐬∣Z) = ∏_{j∈C∪D} ℙ(X_j=𝐬_j∣X_{I(j)}=𝐬_{I(j)}).\]

We can decompose the path probability into two parts

\[ℙ(X=𝐬∣Z) = p(𝐬) q(𝐬∣Z).\]

The first part consists of the probability contributed by the chance nodes. We refer to it as the upper bound of path probability

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

The second part consists of the probability contributed by the decision nodes.

\[q(𝐬∣Z) = ∏_{j∈D} ℙ(X_j=𝐬_j∣X_{I(j)}=𝐬_{I(j)}).\]

Because the probabilities of decision nodes are defined as one or zero depending on the decision strategy, we can simplify the second part to an indicator function

\[q(𝐬∣Z)=\begin{cases} 1, & x(𝐬) = 1 \\ 0, & \text{otherwise} \end{cases}.\]

The binary variable $x(𝐬)$ indicates whether a decision stategy is compatible with the path $𝐬,$ that is, if each local decision strategy chooses a state on the path. Using the indicator function $I(.)$ whose value is 1 if the expression inside is true and 0 otherwise, we have

\[x(𝐬) = \prod_{j∈D} I(Z_j(𝐬_{I(j)})=𝐬_j).\]

Now the path probability equals the upper bound if the path is compatible with given decision strategy. Otherwise, the path probability is zero. Formally, we have

\[ℙ(𝐬∣X,Z)= \begin{cases} p(𝐬), & x(𝐬) = 1 \\ 0, & \text{otherwise} \end{cases}.\]

Consequences

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

\[Y_j:𝐒_{I(j)}↦ℂ,\]

where $ℂ$ is the set of real-valued consequences.

Path Utility

The utility function is a function that maps consequences to real-valued utility

\[U:ℂ^{|V|}↦ℝ.\]

The path utility is defined as the utility function acting on the consequences of value nodes given their information states

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

The default path utility is the sum of node utilities $U_j$

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

The utility function affects the objectives discussed on the Decision Model page. We can choose the utility function such that the path utility function either returns:

• a numerical value, which leads to a mixed-integer linear programming (MILP) formulation or
• a linear function with real and integer-valued variables, which leads to a mixed-integer quadratic programming (MIQP) formulation.

Different formulations require a solver capable of solving them.

Path Distribution

A path distribution is a pair

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

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

Other Properties

In this section, we define more properties for influence diagrams.

Discrete influence diagram refers to a countable state space. Otherwise, the influence diagram is continuous. We can discretize continuous influence diagrams using discrete bins.

Two nodes are sequential if there exists a directed path from one node to the other in the influence diagram. Otherwise, the nodes are parallel. Sequential nodes often model a time dimension.

Repeated subdiagram refers to a recurring pattern within an influence diagram. Often, influence diagrams do not have a unique structure, but they consist of a repeated pattern due to the underlying problem's properties.

Limited-memory influence diagram refers to an influence diagram where the no-forgetting assumption does not hold. In practice, this means that the decision maker does not necessarily remember all previous information. For example, the treatment decisions in the Pig Breeding example are made without full information about the treatment history.

Isolated subdiagrams refer to unconnected diagrams within an influence diagram. That is, there are no undirected connections between the diagrams. Therefore, one isolated subdiagram's decisions affect decisions on the other isolated subdiagrams only through the utility function.

A chance or decision node is redundant if it is a leaf node and not in any value node's information set. Formally, if $j∈C∪D$ is a leaf node and there does not exist a value node $i∈V$ such that $j∈I(i)$, then node $j$ is redundant.

References