# 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:

**Chance nodes**$C⊆\{1,...,n\}$ (circles) represent uncertain events associated with random variables.**Decision nodes**$D⊆\{1,...,n\}$ (squares) correspond to decisions among discrete alternatives.**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

- 1Salo, A., Andelmin, J., & Oliveira, F. (2019). Decision Programming for Multi-Stage Optimization under Uncertainty, 1–35. Retrieved from http://arxiv.org/abs/1910.09196
- 2Howard, R. A., & Matheson, J. E. (2005). Influence diagrams. Decision Analysis, 2(3), 127-143. https://doi.org/10.1287/deca.1050.0020
- 3Shachter, R. D. (1986). Evaluating influence diagrams. Operations research, 34(6), 871-882. https://doi.org/10.1287/opre.34.6.871