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