Paths and Properties

Effective Paths

It is possible for some combinations of chance or decision states to be unrealizable. We refer to such subpaths as ineffective. For example, the above tree represents the generation of paths where subpaths $๐’_{\{1,2\}}^โ€ฒ=\{(2,2)\}$, $๐’_{\{1,2,3\}}^โ€ฒ=\{(1,1,2), (1,2,1)\}$ are ineffective.

Formally, the path $๐ฌ$ is ineffective if and only if $๐ฌ_Aโˆˆ๐’_A^โ€ฒ$ given ineffective subpaths $๐’_A^โ€ฒโŠ†๐’_A$ for nodes $AโŠ†CโˆชD.$ Then, effective paths is a subset of all paths without ineffective paths

\[๐’^โˆ—=\{๐ฌโˆˆ๐’โˆฃ๐ฌ_{A}โˆ‰๐’_{A}^โ€ฒ\}โŠ†๐’.\]

The Decision Model size depends on the number of effective paths, rather than the number of paths or size of the influence diagram directly. If effective paths is empty, the influence diagram has no solutions.

Active Paths

If the upper bound of path probability is zero, its probability is zero, and it does not affect the solution. Therefore, we can only consider paths with a positive upper bound of path probability. We refer to these paths as active paths. Formally, we define an active path as a path $๐ฌ$ if all of its chance states are active

\[\begin{aligned} X(๐ฌ)&โ†”(p(๐ฌ)>0)\\ &โ†” โ‹€_{jโˆˆC} (โ„™(X_j=๐ฌ_jโˆฃX_{I(j)}=๐ฌ_{I(j)})>0). \end{aligned}\]

Otherwise, it is an inactive path. We denote the set of active paths as

\[๐’(X)=\{๐ฌโˆˆ๐’ โˆฃ X(๐ฌ)\}.\]

The number of active paths is

\[|๐’(X)|โ‰ค|๐’|.\]

Effective paths are related to active paths, such that, for all $jโˆˆC,$ we have ineffective subpaths

\[๐’_{I(j)โˆชj}^โ€ฒ=\{๐ฌ_{I(j)โˆชj}โˆˆ๐’_{I(j)โˆชj} โˆฃ โ„™(X_j=๐ฌ_jโˆฃX_{I(j)}=๐ฌ_{I(j)})=0\}.\]

Generally, we have

\[๐’^โˆ— โŠ† ๐’(X).\]

If there are no other ineffective subpaths, we have

\[๐’^โˆ— = ๐’(X).\]

Compatible Paths

Each decision strategy $Zโˆˆโ„ค$ chooses a set of paths from all paths, referred to as compatible paths. Formally, we denote the set of compatible paths as

\[๐’(Z)=\{๐ฌโˆˆ๐’ โˆฃ Z(๐ฌ)\}.\]

Since each local decision strategy $Z_jโˆˆZ$ can choose only one of its states, the number of compatible paths is

\[|๐’(Z)|=|๐’|/|๐’_D|=|๐’_C|.\]

The compatible paths of all distinct pairs of decision strategies are disjoint. Formally, for all $Z,Z^โ€ฒโˆˆโ„ค$ where $Zโ‰ Z^โ€ฒ$, we have $Z(๐ฌ)โˆงZ^โ€ฒ(๐ฌ)โ†”โŠฅ,$ which gives as

\[๐’(Z)โˆฉ๐’(Z^โ€ฒ)=\{๐ฌโˆˆ๐’โˆฃZ(๐ฌ)โˆงZ^โ€ฒ(๐ฌ)\}=โˆ….\]

Symmetry

We define the set of active and compatible paths as

\[๐’(X)โˆฉ๐’(Z)=\{๐ฌโˆˆ๐’โˆฃX(๐ฌ)โˆงZ(๐ฌ)\}.\]

An influence diagram is symmetric if the number of active and compatible paths is a constant. Formally, if for all $Z,Z^โ€ฒโˆˆโ„ค,$ where $Zโ‰ Z^โ€ฒ,$ we have

\[|๐’(X)โˆฉ๐’(Z)|=|๐’(X)โˆฉ๐’(Z^โ€ฒ)|.\]

For example, if all paths are active $X(๐ฌ)โ†”โŠค,$ we have $|๐’(X)โˆฉ๐’(Z)|=|๐’(Z)|,$ which is a constant. Otherwise, the influence diagram is asymmetric. The figures below demonstrate symmetric and asymmetric influence diagrams.

Example 1

Consider the influence diagram with two nodes. The first is a decision node with two states, and the second is a chance node with three states.

Example 2

If there are no inactive chance states, all paths are possible. That is, for all $sโˆˆS,$ we have $p(s)>0.$ In this case, the influence diagram is symmetric.

However, if there are inactive chance states, such as $โ„™(s_2=2โˆฃs_1=2)=0$, we can remove $(2,2)$ from the paths, visualized by a dashed shape. Therefore, there is a varying number of possible paths depending on whether the decision-maker chooses state $s_1=1$ or $s_1=2$ in the first node, and the influence diagram is asymmetric.

Example 3

Let us add one chance node with two states to the influence diagram.

Now, given inactive chance states such that we remove the dashed paths, we have a symmetric influence diagram. Both decisions will have an equal number of possible paths. However, there are only eight possible paths instead of twelve if there were no inactive chance states.

Other Properties

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

Discrete influence diagram refers to 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 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 an upper bound limits the size of the information set for decision nodes. That is, $I(j)โ‰คm$ for all $jโˆˆD$ where the limit $m$ is less than $|CโˆชD|.$ Smaller limits of $m$ are desirable because they reduce the decision model size, as discussed in the Computational Complexity page.

Isolated subdiagrams refer to an influence diagram that consists of multiple unconnected diagrams. 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.

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).$