Paths

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.

In Decision Programming, one can declare certain subpaths to be ineffective using the fixed path and forbidden paths sets.

Fixed Path

Fixed path refers to a subpath which must be realized. If the fixed path is $s_Y = S_Y^f$ for all nodes $YโŠ†CโˆชD$, then the effective paths in the model are

\[๐’^โˆ—=\{๐ฌโˆˆ๐’โˆฃs_{Y} = S_{Y}^f \forall \ Y \}.\]

Forbidden Paths

Forbidden paths are a way to declare ineffective subpaths. If $๐ฌ_Xโˆˆ๐’_X^โ€ฒ$ are forbidden subpaths for nodes $XโŠ†CโˆชD$, then the effective paths in the model are

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

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 consider only the 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=s_jโˆฃX_{I(j)}=๐ฌ_{I(j)})=0\}.\]

Generally, the effective paths is a subset of the active paths, that is

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

If there are no other ineffective subpaths, we have

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

Notice that, the number of active paths affects the size of the Decision Model because it depends on the number of effective paths.

Compatible Paths

Each decision strategy $Zโˆˆโ„ค$ determines a set of compatible paths. We use the shorthand $Z(s) โ†” (q(๐ฌ \mid Z) = 1)$, where q is as defined in Path Probability. Formally, we denote the set of compatible paths as

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

Since each local decision strategy $Z_jโˆˆZ$ is deterministic, it can choose only one state $s_j$ for each information state $๐ฌ_{I(j)}$. Thus, 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^โ€ฒ)=\{๐ฌโˆˆ๐’โˆฃZ(๐ฌ)โˆงZ^โ€ฒ(๐ฌ)\}=โˆ….\]

Locally Compatible Paths

Locally compatible paths refers to a subset of paths that include the subpath $(๐ฌ_{I(j)}, s_j)$ and thus, represent the local decision strategy $Z_j(๐ฌ_{I(j)}) = s_j$ for decision node $j \in D$. Formally, the locally compatible paths for node $j \in D$, state $s_j \in S_j$ and information state $๐ฌ_{I(j)} \in ๐’_{I(j)}$ includes the paths

\[๐’_{s_j \mid s_{I(j)}} = \{ ๐ฌ \in ๐’ \mid (๐ฌ_{I(j)}, s_j) โŠ‚ ๐ฌ\}.\]

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, 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.

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.

Example 2

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.