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