comment

# A Complete Criterion for Value of Information in Soluble Influence Diagrams

Chris van Merwijk*,1 Ryan Carey*,1 Tom Everitt2

###### Abstract

Influence diagrams have recently been used to analyse the safety and fairness
properties of AI systems. A key building block for this analysis is a
graphical criterion for value of information (VoI). This paper establishes the
first complete graphical criterion for VoI in influence diagrams with multiple
decisions. Along the way, we establish two important techniques for proving
properties of multi-decision influence diagrams: ID homomorphisms are
structure-preserving transformations of influence diagrams, while a Tree of
Systems is a collection of paths that captures how information and control can
flow in an influence diagram.

##  1 Introduction

One approach to analysing the safety and fairness of AI systems is to
represent them using variants of Bayesian networks (Everitt et al. 2019;
Kusner et al. 2017). Influence diagrams (IDs) can be viewed an extension of
Bayesian networks for representing agents (Howard et al. 2005; Everitt et al.
2021a). This graphical perspective offers a concise view of key relationships,
that abstracts away from much of the internal complexity of modern-day AI
systems.

Once a decision problem is represented graphically, key aspects can be
summarised. One well-studied concept is the _value of information_ (VoI)
(Howard 1966), which describes how much more utility an agent is able to
obtain if it can observe a variable in its environment, compared with if it
cannot. Other summary concepts includes “materiality”, “value of control”,
“response incentives”.

These concepts have been used to analyse the redirectability (Everitt et al.
2021b; Holtman 2020) of AI systems, fairness (Everitt et al. 2021a; Ashurst et
al. 2022), ambitiousness (Cohen, Vellambi, and Hutter 2020), and the safety of
reward learning systems (Armstrong et al. 2020; Everitt et al. 2019; Langlois
and Everitt 2021; Evans and Kasirzadeh 2021; Farquhar, Carey, and Everitt
2022). Typically, this analysis involves applying _graphical criteria_ , that
indicate which properties can or cannot occur in a given diagram, based on the
graph structure alone. Graphical criteria are useful because they enable
qualitative judgements even when the precise functional relationships between
variables are unknown or unspecified.

For the single-decision case, complete criteria have been established for all
four of the aforementioned concepts (Everitt et al. 2021a). However, many AI
applications such as reinforcement learning involve an agent making multiple
decisions. For the multi-decision case, multiple criteria for VoI have been
proposed (Nielsen and Jensen 1999; Shachter 1998; Nilsson and Lauritzen 2000),
but none proven complete.

$X$$D$$V$$X^{\prime}$$D^{\prime}$$Q^{\prime}$$U$chance nodedecision
nodeutility node Figure 1:  Does $X$ has positive value of information for
$D$?

This means that for some graphs, it is not known whether a node can have
positive VoI. For example, in Fig. 1, it is not known whether it can be
valuable for $D$ to observe $X$. Specifically, the edge $X\to D$ does not meet
the criterion of _nonrequisiteness_ used by Nilsson and Lauritzen (2000), so
we cannot rule out that it contains valuable information. However, the
procedure that is used to prove completeness in the single-decision setting
(Everitt et al. 2021a) does not establish positive VoI.

We prove that the graphical criterion of Nilsson and Lauritzen (2000) is
complete, in that any environmental variable not guaranteed to have zero VoI
by their criterion must have positive VoI in some compatible ID. In the course
of the proof, we develop several tools for reasoning about soluble IDs. In
summary, our main contributions are:

  * •

ID homomorphisms. These allow us to transform an ID into another with similar
properties, that may be more easily analysed (Section 4).

  * •

Trees of systems. A system is a set of paths that make information valuable to
a decision. A tree of systems describes how those paths traverse other
decisions (Section 5.3).

  * •

A complete VoI criterion. We prove the criterion in Section 5. In Section 6 we
explain why this criterion may be useful, how it may be used in an AI safety
application, and share an open source implementation.

##  2 Setup

color=blue!30]Ryan: Or “ all of the results transfer to a regular influence
diagram setting. footnote: the only difference is that if edges do not match
the direction of causation, then a node may be deemed valuable to control,
when controlling it is not in-fact useful (everitt2021, Appendix A) ”

Limited memory influence diagrams (also called LIMIDs) are graphical models
containing decision and utility nodes, used to model decision-making problems
(Howard 1966; Nilsson and Lauritzen 2000).

######  Definition 1 (Limited memory influence diagram graph; Nilsson and
Lauritzen 2000).

A _(limited memory) ID graph_ is a directed acyclic graph
${\mathcal{G}}\\!=\\!({\bm{V}},E)$ where the vertex set ${\bm{V}}$ is
partitioned into _chance-_ (${\bm{X}}$), _decision-_ (${\bm{D}}$), and
_utility nodes_ (${\bm{U}}$). Utility nodes lack children.

Since all of the influence diagram graphs in this paper have limited memory,
we will consistently refer to them simply as _influence diagram_ (ID) graphs.
We denote the parents, descendants,color=green!30]Chris: And ancestors? and
family of a node $V\in{\bm{V}}$ as $\mathrm{\mathbf{Pa}}(V),\textbf{Desc}(V)$,
and $\mathrm{\mathbf{{Fa}}}(V)=\mathrm{\mathbf{Pa}}(V)\cup\\{V\\}$. For
$Y\in{\bm{V}}$, color=green!30]Chris: Remove ”For $Y\in{\bm{V}}$,”? we denote
an edge by $V\to Y$, and a directed path by $V\dashrightarrow Y$.

To specify the precise statistical relationships, rather than just their
structure, we will use a model that attaches probability distributions to the
variables in an ID graph.

######  Definition 2.

An _influence diagram_ (ID) is a tuple
${\mathcal{M}}=({\mathcal{G}},\mathrm{dom},P)$ where ${\mathcal{G}}$ is an ID
graph, $\mathrm{dom}(X)$ is a finite domain for each node $X$ in
${\mathcal{G}}$ that is real-valued for utility nodes, and
$P(X|\mathrm{\mathbf{Pa}}(X))$ is a conditional probability distribution (CPD)
for each chance and utility node $X$ in ${\mathcal{G}}$. We will say that
${\mathcal{M}}$ is _compatible with_ ${\mathcal{G}}$, or simply that
${\mathcal{M}}$ is an ID _on_ ${\mathcal{G}}$.

The decision-making task is to maximize the sum of expected utilities by
selecting a CPD $\pi^{D}(D|\mathrm{\mathbf{Pa}}(D))$, called a _decision rule_
, for each decision $D\in{\bm{D}}$. A _policy_
${\pi}=\\{\pi^{D}\\}_{D\in{\bm{D}}}$ consists of one decision rule for each
decision. Once the policy is specified, this induces joint probability
distribution $P^{\mathcal{M}}_{\pi}$ over all the variables. We denote
expectations by ${\mathbb{E}}^{\mathcal{M}}_{\pi}$ and omit the superscript
when clear from context. A policy ${\pi}$ is called _optimal_ if it maximises
${\mathbb{E}}_{{\pi}}[\mathcal{U}]$, where
$\mathcal{U}\coloneqq\sum_{U\in{\bm{U}}}{U}$. Throughout this paper, we use
subscripts for policies, and superscripts for indexing. A lowercase
$v\in\mathrm{dom}(V)$ denotes an outcome of $V$.

Some past work has assumed “no-forgetting”, meaning that every decision $d$ is
allowed to depend on the value $v$ of any past decision $D^{\prime}$ or its
observations $\mathrm{\mathbf{Pa}}(D^{\prime})$, even when that variable
$V\in\mathrm{\mathbf{{Fa}}}(D^{\prime})$ is not a parent of the current
decision ($V\not\in\mathrm{\mathbf{Pa}}(D)$) (Shachter 1986). In contrast, we
follow the more flexible convention of limited memory IDs (Nilsson and
Lauritzen 2000), by explicitly indicating whether a decision $d$ can depend on
the value of an observation or decision $v$ by the presence (or absence) of an
edge $V\to D$, just as we would do with any variable that is not associated
with a past decision.

Within the space of limited memory IDs, this paper focuses on _soluble_ IDs
(Nilsson and Lauritzen 2000), also known as IDs with “sufficient recall”
(Milch and Koller 2008). The solubility assumption requires that it is always
possible to choose an optimal decision rule without knowing what decision
rules were followed by past decisions. The formal definition uses
$d$-separation.

######  Definition 3 (d-separation; Verma and Pearl (1988)).

A path $p$ is _blocked_ by a set of nodes ${\bm{Z}}$ if $p$ contains a
collider $X\to W\leftarrow Y$, such that neither $W$ nor any of its
descendants are in ${\bm{Z}}$, or $p$ contains a chain $X\to W\to Y$ or fork
$X\leftarrow W\to Y$ where $W$ is in ${\bm{Z}}$. If $p$ is not blocked, then
it is _active_. For disjoint sets ${\bm{X}}$, ${\bm{Y}}$, ${\bm{Z}}$, the set
${\bm{Z}}$ is said to _d-separate_ ${\bm{X}}$ from ${\bm{Y}}$,
${({\bm{X}}\perp{\bm{Y}}\mid{\bm{Z}})}$ if ${\bm{Z}}$ blocks every path from a
node in ${\bm{X}}$ to a node in ${\bm{Y}}$. Sets that are not d-separated are
called _d-connected_.

######  Definition 4 (Solubility; Nilsson and Lauritzen (2000)).

For an ID graph ${\mathcal{G}}$ let the _mapping extension_
${\mathcal{G}}^{\prime}$ be a modified version of ${\mathcal{G}}$ where a
chance node parent $\Pi^{i}$ is added to each decision $D^{i}$. Then
${\mathcal{G}}$ is _soluble_ if there exists an ordering $D^{1},\dots,D^{n}$
over the decisions, such that in the mapping extension
${\mathcal{G}}^{\prime}$, for all $i$:

${\Pi}^{<i}\perp{\bm{U}}(D^{i})\mid\mathrm{\mathbf{{Fa}}}(D^{i})$

where ${\Pi}^{<i}:=\\{\Pi^{j}\mid j<i\\}$ and
${\bm{U}}(D^{i}):={\bm{U}}\cap\textbf{Desc}(D^{i})$.

We will subsequently only consider ID graphs that are soluble. Solubility is
entailed by the popular more restrictive “no forgetting” assumption, where the
decision-maker remembers previous decisions and observations (Shachter 1986,
2016): in no forgetting, the family $\mathrm{\mathbf{{Fa}}}(D^{i})$ includes
$\mathrm{\mathbf{{Fa}}}(D^{j})$ for $j<i$, so every policy node $\Pi^{j}$ is
$d$-separated from
${\bm{V}}\setminus\mathrm{\mathbf{{Fa}}}(D^{j})\supseteq{\bm{U}}\cap\textbf{Desc}^{D^{j}}$.
However, solubility is more general, for example Fig. 1 is soluble, even
though past decisions are forgotten.

##  3 Value of Information

The VoI of a variable color=blue!30]Ryan: Add “is a widely studied property
that [cite cite]”? indicates how much the attainable expected utility
increases when a variable is observed compared to when it is not:

######  Definition 5 (Value of Information; Howard (1966)).

For an ID ${\mathcal{M}}$ and $X\\!\not\in\textbf{Desc}_{D}$,
color=blue!30]Ryan: I added a bit about it being a nondescendant. let
${\mathcal{M}}_{X\\!\not\\!\to\\!D}$ and ${\mathcal{M}}_{X\\!\to\\!D}$ be
${\mathcal{M}}$ modified by respectively removing and adding the edge
$X\\!\to\\!D$. Then, the _value of information_ of $X$ for $D$ is:

$\max_{\pi}{\mathbb{E}}^{{\mathcal{M}}_{X\to
D}}_{\pi}[\mathcal{U}]-\max_{\pi}{\mathbb{E}}^{{\mathcal{M}}_{X\not\to
D}}_{\pi}[\mathcal{U}].$

This is closely related to the concept of _materiality_ ; an observation
$X\in\mathrm{\mathbf{Pa}}(D)$ is called material if its VoI is positive.

The graphical criterion for VoI that we will use iteratively removes
information links that cannot contain useful information, based on a condition
called _nonrequisiteness_. If
$X\perp{\bm{U}}(D^{i})\mid\mathrm{\mathbf{{Fa}}}(D^{i})\setminus\\{X\\}$, then
both $X$ and the information link $X\to D^{i}$ are called _nonrequisite_ ,
otherwise, they are _requisite_. Intuitively, nonrequisite links contain no
information about influencable utility nodes, so the attainable expected
utility is not decreased by their removal. Removing one nonrequisite
observation link can make a previously requisite information link
nonrequisite, so the criterion involves iterative removal of nonrequisite
links. The criterion was first proposed by Nilsson and Lauritzen (2000), who
also proved that it is sound. Formally, it is captured by what we calll a
$d$-reduction:

######  Definition 6 ($d$-reduction).

The ID graph ${\mathcal{G}}^{\prime}$ is a _$d$ -reduction_ of ${\mathcal{G}}$
if ${\mathcal{G}}^{\prime}$ can be obtained from ${\mathcal{G}}$ via a
sequence
${\mathcal{G}}={\mathcal{G}}^{1},...,{\mathcal{G}}^{k}={\mathcal{G}}^{\prime}$
where each ${\mathcal{G}}^{i},i>1$ differs from its predecessor
${\mathcal{G}}^{i-1}$ by the removal of one nonrequisite information link. A
$d$-reduction is called _minimal_ if it lacks any nonrequisite information
links.

For any ID graph ${\mathcal{G}}$, there is only one minimal $d$-reduction
(Nilsson and Lauritzen 2000), i.e. the minimal $d$ reduction is independent of
the order in which edges are removed. We can therefore denote _the minimal
$d$-reduction_ of ${\mathcal{G}}$ as ${\mathcal{G}}^{*}$. Thus, Nilsson and
Lauritzen (2000, Theorem 3) states that _if_ an ID graph ${\mathcal{G}}$
contains $X\to D$ but ${\mathcal{G}}^{*}$ does not, then $X$ has zero VoI in
every ID compatible with ${\mathcal{G}}$. Our completeness result replaces
this with an _if and only if_ statement.

######  Theorem 7 (VoI Criterion).

Let ${\mathcal{G}}$ be a soluble ID graph containing an edge $X\to D$ from
chance node $X\in{\bm{X}}$ to decision $D\in{\bm{D}}$. There exists an ID
${\mathcal{M}}$ compatible with ${\mathcal{G}}$ such that $X$ has strictly
positive VoI for $D$ if and only if the minimal $d$-reduction contains $X\to
D$.

The VoI criterion is posed in terms of a graph ${\mathcal{G}}$ that contains
$X\to D$. To analyse a graph that does not, one can simply add the edge $X\to
D$ then apply the same criterion as long as the new ID graph is soluble
(Shachter 2016). color=blue!30]Ryan: Is this the correct shachter cite?

The proof will be given in Section 5, with details in Appendices C and D. We
note that this excludes the case of remembering a past decision
$X\in{\bm{D}}$, because Nilsson’s criterion is incomplete for this case. For
example, the simple ID graph with the edges $D\to D^{\prime}\to U$ and $D\to
U$, $D$ satisfies the graphical criterion of being requisite for $D^{\prime}$,
but $D^{\prime}$ has zero VoI because it is possible for the decision $D$ to
be deterministically assigned some optimal value. This means that there is no
need for $D^{\prime}$ to observe $D$.

##  4 ID Homomorphisms

To make the analysis easier, we will often want to transform an original ID
graph into a more structured one. Before describing the structure we will be
aiming for, we consider the general question of when a modified ID graph
retains important properties of the original. To this end, we will define the
concept of an _ID homomorphism_ , which we then use to define a class of
property-preserving ID transformations. (Proofs are supplied in Appendix B.)

color=blue!30]Ryan: Should be able to condense the bullets from 8 lines to 5

######  Definition 8 (ID homomorphism).

For ID graphs ${\mathcal{G}}\\!\\!=\\!({\bm{V}}\\!,E)$ and
${\mathcal{G}}^{\prime}\\!\\!=\\!({\bm{V}}^{\prime}\\!,E^{\prime})$, a map
$h\colon\\!{\bm{V}}^{\prime}\\!\\!\to\\!{\bm{V}}\\!$ is an _ID homomorphism_
from ${\mathcal{G}}^{\prime}$ to ${\mathcal{G}}$ iff:

  1. (a)

(Preserves node types) $h$ maps each chance-, decision-, or utility-node to a
node of the same type;

  2. (b)

(Preserves links) For every $A\to B$ in ${\mathcal{G}}^{\prime}$ either
$h(A)\to h(B)$ is in ${\mathcal{G}}$, or $h(A)=h(B)$;

  3. (c)

(Covers all information links) If $h(N)\to h(D)$ is in ${\mathcal{G}}$ for
$D\in{\bm{D}}$, then $N\to D$ is in ${\mathcal{G}}^{\prime}$; and

  4. (d)

(Combines only linked decisions) If $h(D_{1})\\!=\\!h(D_{2})$ for decisions
$D^{1}\neq D^{2}$ in ${\mathcal{G}}^{\prime}$ then ${\mathcal{G}}^{\prime}$
contains $D^{1}\\!\\!\to\\!D^{2}$ or $D^{2}\\!\to\\!D^{1}$.

$Y$$D$$U$${\mathcal{G}}$original$D$$U$${\mathcal{G}}^{\prime}$remove
$Y$$D$$D^{\prime}$$U$${\mathcal{G}}^{\prime\prime}$duplicate
$D$$D$$D^{\prime}$$U$${\mathcal{G}}^{\prime\prime\prime}$remove an edge Figure
2: A sequence of homorphic transformations showing how ${\mathcal{G}}$ can be
homorphically transformed into ${\mathcal{G}}^{\prime\prime\prime}$ by
composition of Lemmas 13 and 14. In the first step from ${\mathcal{G}}$ to
${\mathcal{G}}^{\prime}$, $Y$ is removed; in the step from
${\mathcal{G}}^{\prime}$ to ${\mathcal{G}}^{\prime\prime}$ a decision is
duplicated; and in the final step from ${\mathcal{G}}^{\prime\prime}$ to
${\mathcal{G}}^{\prime\prime\prime}$, a link is removed. Since the mapping at
each step (blue, green, and orange respectively) meets the definition of an ID
homomorphism, ${\mathcal{G}}^{\prime\prime\prime}$ must be an ID homorphism of
${\mathcal{G}}$ (Lemma 15).

An ID homomorphism is analogous to the notion of graph homomorphism from graph
theory, which essentially requires that edges are preserved along the map. An
ID homomorphism additionally requires that decisions in the two graphs have
equivalent parents (c), and that split decisions are connected (d). This
requirement maintains a direct correspondence between policies on the two
graphs, so that, as we will see, ID homomorphisms preserve VoI. Examples of ID
homorphisms are given in Fig. 2.

color=blue!30]Ryan: Cite graph homomorphisms? color=green!30]Chris: we could
add a citation to graph theory, Diestel, 2017. Though it’s also just a “well
known concept” and has a wikipedia page. color=blue!30]Ryan: This is where we
should have remarks about the intuition of this definition. But I don’t
understand what is being said about adding edges from each node to itself.

The following three lemmas establish properties that are preserved under ID
homorphisms.

######  Lemma 9 (Preserves Solubility).

Let ${\mathcal{G}}=({\bm{V}},E)$ and
${\mathcal{G}}^{\prime}=({\bm{V}}^{\prime},E^{\prime})$ be ID graphs. If
${\mathcal{G}}$ is soluble, and there exists a homomorphism
$h\colon{\bm{V}}^{\prime}\to{\bm{V}}$, then ${\mathcal{G}}^{\prime}$ is also
soluble.

color=blue!30]Ryan: Probably we should uniformise to either
${\mathcal{G}}^{\prime}/{\mathcal{M}}^{\prime}$ or
$\bar{\mathcal{G}}\bar{\mathcal{M}}$ throughout this section

Given a homomorphism $h$ from ${\mathcal{G}}^{\prime}$ to ${\mathcal{G}}$, we
can define a notion of equivalence between IDs (and policies) on each graph.
Roughly, two IDs are equivalent if the domain of every node is a cartesian
product of the domains of the nodes in its pre-image (or the sum, in the case
of a utility node). Formally:

######  Definition 10 (Equivalence).

${\mathcal{M}}_{\pi}$ on ${\mathcal{G}}$ and
${\mathcal{M}}^{\prime}_{\pi^{\prime}}$ on ${\mathcal{G}}_{\pi^{\prime}}$ are
_equivalent_ if each non-utility node $N$ in ${\mathcal{G}}$ has
$\mathrm{dom}(N):=\bigtimes_{N^{i}\in h^{-1}(N)}\mathrm{dom}(N^{i})$, and
$P^{\mathcal{M}}_{\pi}(N\\!=\\!(n^{1},...,n^{k}))=P^{{\mathcal{M}}^{\prime}}_{\pi^{\prime}}(N^{1}\\!=\\!n^{1},...,N^{k}\\!=\\!n^{k})$,
and each utility node has
$P^{\mathcal{M}}_{\pi}(U\\!=\\!u)=P^{{\mathcal{M}}^{\prime}}_{\pi^{\prime}}(\sum_{U^{i}\in
h^{-1}(U)}U^{i}\\!=\\!u)$.

######  Lemma 11 (Equivalence).

If there is an ID homomorphism $h$ from ${\mathcal{G}}^{\prime}$ to
${\mathcal{G}}$, then for any policy $\pi^{\prime}$ in any ID
${\mathcal{M}}^{\prime}$ on ${\mathcal{G}}^{\prime}$ there is a policy $\pi$
in a ID ${\mathcal{M}}$ on ${\mathcal{G}}$ such that ${\mathcal{M}}_{\pi}$ and
${\mathcal{M}}^{\prime}_{\pi^{\prime}}$ are equivalent. color=red!30]Tom: what
does it mean for two probability distributions to be equivalent?

color=blue!30]Ryan: Changed from $\tilde{M}$ to $M^{\prime}$ here. May need to
make corresponding change to proof in appendix

In this case, we will call ${\mathcal{M}}$ and $\pi$ the _ID and policy
transported along the homomorphism $h$_. In the appendix, we show that this
correspondence between policies on ${\mathcal{M}}^{\prime}$ and
${\mathcal{M}}$ is a bijection. color=blue!30]Ryan: The one-sentence
explanation above isn’t very explanatory. color=green!30]Chris: I just removed
it Intuitively, if there is an ID homomorphism
${\mathcal{G}}^{\prime}\to{\mathcal{G}}$, this means we have a particular way
to fit an ID on ${\mathcal{G}}^{\prime}$ into ${\mathcal{G}}$, while
preserving the information that the decisions can access. The basis of this
proof is that properties (c,d) of ID homomorphisms (Definition 8) require
decisions to have precisely the same information in $\cal M$ as in $\cal
M^{\prime}$.

color=blue!30]Ryan: “interpreted as” feels a bit too informal to me.

For our proof of Theorem 7, we will require that VoI is preserved under
homomorphism.

######  Lemma 12 (Preserves VoI).

Let $h\colon\\!{\mathcal{G}}^{\prime}\\!\\!\to\\!{\mathcal{G}}$ be an ID
homomorphism. If $X^{\prime}$ has positive VoI for $D^{\prime}$ in an ID
${\mathcal{M}}^{\prime}$ on ${\mathcal{G}}^{\prime}$, then $X\\!=\\!h(X)$ has
positive VoI for $D\\!=\\!h(D^{\prime})$ in the transported ID
${\mathcal{M}}\\!=\\!h({\mathcal{M}}^{\prime})$.

color=blue!30]Ryan: I thought materiality is defined with respect to just a
model, so I’ve changed this statement. I think the proof should remain
similar, and use transported model + policy?

The proof builds heavily on there being a precise correspondence between
policies on $\cal M$ and on $\cal M^{\prime}$. Since these two IDs are
equivalent (Lemma 11), if obtaining certain information in $\cal M^{\prime}$
has value, so does obtaining that information in $\cal M$. The formal details
are left to Appendix B.

We next present two transformation rulescolor=green!30]Chris: rudimentary
calculus is kind of a weird phrasing with which to modify any ID graph, which
are illustrated in Fig. 2. The first transformation obtains a new graph
${\mathcal{G}}^{\prime}$ by deleting or duplicating nodes, while preserving
all links. Under this transformation, the function that maps a node in
${\mathcal{G}}^{\prime}$ to its ‘originating node’ in ${\mathcal{G}}$ is an ID
homomorphism:

######  Lemma 13 (Deletion & Link-Preserving Copying).

Let ${\mathcal{G}}\\!\\!=\\!\\!({\bm{V}},E)$ be an ID graph and
${\mathcal{G}}^{\prime}\\!=\\!(\bigcup_{N\in{\bm{V}}}\mathrm{Copies}(N),E^{\prime})$
an ID graph where $\mathrm{Copies}$ maps nodes in ${\mathcal{G}}$ to disjoint
sets in ${\mathcal{G}}^{\prime}$, and where $E^{\prime}$ is a minimal set of
edges such that for any edge $A\to B$ in $E$ and $A^{i}\in\mathrm{Copies}(A)$
and $B^{i}\in\mathrm{Copies}(B)$ there is an edge $A^{i}\to B^{i}$, and if
$A^{i},A^{j}\in\mathrm{Copies}(A)$ are non-utility nodes then either $A^{i}\to
A^{j}$ or $A^{i}\leftarrow A^{j}$. Then the function $h$ that maps each
$V\in\mathrm{Copies}(N)$ to $N$ is an ID homomorphism.

color=blue!30]Ryan: I’ve simplified/shortened this a bit further. Feel free to
revert any changes is preferred.

Edges that are not information links can also be removed, while having a
homomorphism back to the original:

######  Lemma 14 (Link Pruning).

Let ${\mathcal{G}}=({\bm{V}},E)$ and
${\mathcal{G}}^{\prime}=({\bm{V}},E^{\prime})$ be ID graphs, where
$E^{\prime}\subseteq E$ and where for each decision node $D$ in ${\bm{V}}$,
every incoming edge $N\to D$ in $E$ is in $E^{\prime}$. Then the identity
function $h(N)=N$ on ${\bm{V}}$ is a homomorphism from
${\mathcal{G}}^{\prime}$ to ${\mathcal{G}}$.

Finally, we can chain together a sequence of such graph transformation steps,
and still maintain a homomorphism to the original. The justification for this
is that a composition of ID homomorphisms is again an ID homomorphism:

######  Lemma 15 (Composition).

If $h\colon{\mathcal{G}}^{\prime}\to{\mathcal{G}}$ and
$h^{\prime}\colon{\mathcal{G}}^{\prime\prime}\to{\mathcal{G}}^{\prime}$ are ID
homomorphisms then the composition $h\circ
h^{\prime}\colon{\mathcal{G}}^{\prime\prime}\to{\mathcal{G}}$ is an ID
homomorphism.

##  5 Completeness of the VoI Criterion

We will now prove that the _value of information_ (VoI) criterion of Nilsson
and Lauritzen (2000) is complete for chance nodes (details are deferred to
Appendices C and D).

###  5.1 Parameterising one system

To prove that the criterion from Theorem 7 is complete we must show that for
any graph where $X\to D$ is in the minimal d-reduction, $X$ has positive VoI
for $D$. For example, consider the graph in Fig. 3, which is its own
d-reduction, and contains $X\to D$. In this graph, we can choose for $X$ to be
Bernoulli distributed, for $D$ to have the boolean domain $\\{0,1\\}$, and for
$U$ to be equal to $1$ if and only if $X$ and $D$ match. Clearly, the policy
$d=x$ will obtain $\mathbb{E}[U]=1$. In contrast, if $X$ were not observed (no
link $X\to D)$, then no policy could achieve expected utility more than $0.5$;
so the VoI of $X$ in this ID is $0.5$.

$X$$x\sim\text{Bern}(0.5)$$D$$d\in\\{0,1\\}$$U$$u=\delta_{d=x}$ Figure 3:  The
observation $X$ has positive VoI for $D$.

A general procedure for parameterising any single-decision ID graph meeting
the Theorem 7 criterion to exhibit positive VoI has been established by
Everitt et al. (2021a) and Lee and Bareinboim (2020). This procedure consists
of two steps: first, establish the existence of some paths, then choose CPDs
for the nodes on those paths. We call the paths found in the first step a
system, which will be a building block for our analysis of IDs with multiple
decisions. A fully-general illustration of a system is shown in Fig. 4.
color=blue!30]Ryan: Maybe move some of these definitions down to wherever
they’re used.

######  Definition 16 (System).

A _system_ $s$ in an ID graph ${\mathcal{G}}$ is a tuple
$(\mathrm{control}^{s},\mathrm{info}^{s},\mathrm{obs}^{s})$ where:

  * •

The _control path_ , $\mathrm{control}^{s}$, is a directed path
$D^{s}\dashrightarrow U^{s}$ where $D^{s}\in\bm{D}$ and $U^{s}\in\bm{U}$,

  * •

The _info path_ , $\mathrm{info}^{s}$, is a path
$\mathrm{\mathbf{Pa}}(D^{s})\ni X^{s}\;\hbox{- - -}\;U^{s}$, active given
$\mathrm{\mathbf{{Fa}}}(D^{s})\setminus\\{X^{s}\\}$,

  * •

$\mathrm{obs}^{s}$ maps each collider $C^{i}$ in $\mathrm{info}^{s}$ to an
_obs path_ , a _minimal-length_ directed path
$C^{i}\\!\\!\dashrightarrow\\!D^{s}$.

color=blue!30]Ryan: Tweaked the formatting of this definition, old version
below

We denote the _information link of_ $s$, $X^{s}\\!\to\\!D^{s}$, by
$\mathrm{infolink}^{s}$ and the union of nodes in _all_ paths of $s$ by
${\bm{V}}^{s}$.

color=blue!30]Ryan: TODO: set nodes to be circular, except for labels, which
are rectangular

$F^{1}$$f^{1}\sim\text{Bern}(0.5)$$C^{1}$$c^{i}\\!\\!=\\!f^{i}\\!\oplus\\!f^{i+1}$$\ldots$$C^{n}$$Q^{s}$$q^{s}\sim\text{Bern}(0.5)$$O^{1}$$o^{i}=c^{i}$$O^{n}$$X^{s}$$x^{s}\\!\\!=\\!\\!f^{1}$$D^{s}$$d^{s}\in\\{0,1\\}$$U^{s}$$u^{s}=\delta_{q^{s}=d^{s}}$pathedge$\mathrm{info}^{s}$$\mathrm{obs}^{s}$$\mathrm{infolink}^{s}$$\mathrm{control}^{s}$
Figure 4:  A system, annotated with a parameterization that has positive VoI
in the single-decision case. Dashed arrows can zero or more nodes.

color=blue!30]Ryan: Probably should try to make the text larger in this figure
if spare space

The existence of these paths follow from the graphical criterion of Theorem 7.
In particular, since $X\\!\to\\!D$ is in the minimal d-reduction of
${\mathcal{G}}$, there must exist a path from $X$ to some utility node
$U\in{\bm{U}}\cap\textbf{Desc}^{D^{s}}\\!$, active given
$\mathrm{\mathbf{{Fa}}}(D^{s})\\!\setminus\\!\\{X^{s}\\}$ (the “info path” in
Definition 16).

The second step is to choose CPDs for the nodes ${\bm{V}}^{s}$ in the system
$s$, as also illustrated in Fig. 4. The idea is to require the decision
$D^{s}$ to match the value of $Q^{s}$, by letting the utility $U^{s}$ equal
$1$ if and only if its parents along the control and information paths are
equal. If $X^{s}$ is observed, the decision $D^{s}=X^{s}\oplus O^{1}...\oplus
O^{n}=Q^{s}$ yields $\mathbb{E}[U^{s}]=1$, where $\oplus$ denotes _exclusive
or_ (XOR). Otherwise, the observations $O^{1},...,O^{n}$ are insufficient to
decrypt $Q^{s}$, giving $\mathbb{E}[U^{s}]<1$. So $X^{s}$ has positive VoI.
The intuitive idea is that $U^{s}$ tests whether $D^{s}$ knows $Q^{s}$, based
on the value $d^{s}$ transmitted along $\mathrm{control}^{s}$.
color=green!30]Chris: Above is a bit hard to follow I think.

###  5.2 Parameterising two systems

$X$$x\sim\text{Bern}(0.5)$$D$$d=0$$V$$v=d$$Q^{\prime}$$X^{\prime}$$x^{\prime}=v$$D^{\prime}$$d^{\prime}=x$$U$$U=\delta_{d^{\prime}=x}$

(a)  The variable $X$ has zero VoI for $D$.

$X$$x\sim\text{Bern}(0.5)$$D$$d=x$$V$$v=d$$Q^{\prime}$$q^{\prime}\sim\text{Bern}(0.5)^{2}$$X^{\prime}$$x^{\prime}=(v,q^{\prime}[v])$$D^{\prime}$$d^{\prime}=x^{\prime}$$U$$U=\delta_{d^{\prime}[2]=q^{\prime}[d^{\prime}[1]]}$$+\delta_{d^{\prime}[1]=x}$
(b)  The variable $X$ has positive VoI for $D$.

Figure 5: In (a), a parameterisation of nodes in a single (red) system fails
to exhibit that $X$ has positive VoI for $D$, whereas in (b), positive VoI is
exhibited by parameterising two (red and blue) systems.

When we have two decisions, however, it becomes insufficient to parameterise
just one system. For example, suppose that we try to apply the same scheme as
in the previous subsection to the graph of Fig. 5(a). Then, we would generate
a random bit at $X$ and stipulate that the utility is $U=1$ if the parents $X$
and $D^{\prime}$ on the red paths are equal. One might hope that this would
give $D$ an incentive to observe $X$, so that $d=x$ is copied through
$D^{\prime}$ to obtain $\mathbb{E}[U]=1$. And that is indeed one way to obtain
optimal expected utility. However, the presence of a second decision
$D^{\prime}$ means that maximal utility of $U=1$ may also be obtained using
the policy $d=0,d^{\prime}=x$, which does not require $X$ to be observed by
$D$.

To achieve positive VoI, it is necessary to parameterise two systems as shown
in Fig. 5(b). We first parameterise the second (blue) system to ensure that
$x^{\prime}$ is transmitted to $U$, and then parameterise the initial (red)
system.

To check that $X$ has positive VoI for $D$, we now solve the combined model.
Due to the solubility assumption, we know that the optimal decision rule at
$D^{\prime}$ does not depend on the decision rule taken at $D$. So let us
consider $D^{\prime}$ first. $D^{\prime}$ chooses a pair $(i,j)$ where $i$ is
interpreted as an index of the bits generated at $Q^{\prime}$, and $j$ is
interpreted as a claim about the $i\textsuperscript{th}$ bit of $Q^{\prime}$.
The first term of the utility $U$ is equal to $1$ if and only if the “claim”
made by $D^{\prime}$ is correct, i.e. if the $i\textsuperscript{th}$ bit
generated by $Q^{\prime}$ really is $j$. $X^{\prime}$ contains (only) the
$v\textsuperscript{th}$ digit of $Q^{\prime}$. Hence $D^{\prime}$ can only
ensure its “claim” is correct if it chooses
$d^{\prime}=x^{\prime}=(v,q^{\prime}[v])$, where $q^{\prime}[v]$ denotes the
$v\textsuperscript{th}$ bit of $q^{\prime}$. Having figured out the optimal
policy for $D^{\prime}$, we next turn our attention to $D$. Intuitively, the
task of $D$ is to match $X$, as in Fig. 3. The parameterization encodes this
task, by letting $D$ determine $V$, which in turn influences which bit of
$Q^{\prime}$ is revealed to $D^{\prime}$. This allows $U$ to check the output
of $D$ via the index outputted by $D^{\prime}$, and thereby check whether $D$
matched $X$. This means the second term of $U$ is 1 if and only if $D=X$ so
$d=x$ the optimal policy for $D$, with expected utility $\mathbb{E}[U]=2$.

In contrast, if $X$ were unobserved by $D$, then it would no-longer be
possible to achieve a perfect score on both terms of $U$, so
$\mathbb{E}[U]<2$. This shows that $X$ has positive VoI for $D$.

###  5.3 A tree of systems

In order to generalise this approach to arbitrary number of decisions, we need
a structure that specifies a system for each decision, and indicates what
downstream decisions that system may depend on. These relationships may be
represented by a tree.

######  Definition 17 (Tree of systems).

A _tree of systems_ on an ID graph ${\mathcal{G}}$ is a tuple
$T=({\mathcal{S}},\mathrm{pred})$ where:

  * •

${\mathcal{S}}=(s^{0},...,s^{k})$ is a list of systems (which may include
duplicates).

  * •

$\mathrm{pred}$ maps each $s^{i}$ to a pair $(s^{j},p)$, where
$s^{j}\in({\mathcal{S}}\setminus\\{s^{i}\\})$ is a system, $p$ is one of the
paths of $s^{j}$ (info, control, or obs), and $\mathrm{infolink}^{s^{i}}$ is
in the path $p$, except there is a unique “root system” $s^{\mathrm{root}}$
that is mapped to $(s^{\mathrm{root}},``\mathrm{None}")$.

Moreover, a _full tree of systems_ is one where for each information link
$X^{\prime}\to D^{\prime}$ in each path $p$ in each system $s$, there is
precisely one system $s^{\prime}$ whose information link equals $X^{\prime}\to
D^{\prime}$ and with $\mathrm{pred}(s^{\prime})=(s,p)$.

The idea of a tree of systems is that if a decision $D^{s^{\prime}}$ lies on a
path in the system $s$ of some decision $D^{s}$, then $s$ is a predecessor of
$s^{\prime}$. We will use this tree to parameterise the ID graph, and then we
will also use it to supply an ordering over the decisions (from leaf to root)
in which the model can be solved by backward induction. color=blue!30]Ryan:
Added some explanation here.

$X^{s}$$D^{s}$$Y$$X^{\prime}$$D^{\prime}$$U$$Q^{\prime}$ (a) $Y$ and $U$ occur
in both $s$ (red) and in $s^{\prime}$ (blue)

$X^{s}$$D^{s}$$Y$$X^{\prime}$$D^{\prime}$$U$$Y^{\prime}$$U^{\prime}$$Q^{\prime}$
(b) Copying $Y$ and $U$ ensures position-in-tree-uniqueness

$X^{s}$$D^{s}$$Y$$X^{\prime}$$D^{\prime}$$U$$O$$Y^{\prime}$$U^{\prime}$$Q^{\prime}$
(c) Making a copy $O$ of $X^{\prime}$, ensures no-backdoor-infopaths.

$X^{s}$$D^{s}$$Y$$X^{\prime}$$D^{\prime}$$U$$O$$Y^{\prime}$$U^{\prime}$$Q^{\prime}$
(d) Finally, links are removed, ensuring no-redundant-links

Figure 6: color=green!30]Chris: Obtaining a normal form tree via homomorphic
graph transformations: An ID graph (a) is homomorphically transformed via
graphs (b) and (c) into a graph (d) whose tree is in normal form.

In order to generalise the approach taken to parameterising two systems, we
need to reason about the systems independently, in reverse order. If the
systems overlap, however, this makes it harder to reason about them
independently. Thus it is useful to define a notion of systems called _normal
form_ that are well-behaved.

######  Definition 18 (Normal form tree).

A tree $T$ on ${\mathcal{G}}$ is in _normal form_ if all of the following
hold:

  1. (a)

(position-in-tree-uniqueness) A node $N$ in $T$ can only be in multiple paths
$p^{1},...,p^{k}$ of systems in the tree, if splitting $N$ into
$\\{N,N^{\prime}\\}$ via Lemma 13 and obtaining $T^{\prime}$ from $T$ by
replacing $N$ with $N^{\prime}$ in one of those paths would make $T^{\prime}$
no longer a tree of systems.

  2. (b)

(no-backdoor-infopaths) Every system $s$ in $T$ has an info path that starts
with an outgoing link from $X^{s}$.

  3. (c)

(no-redundant-links) If $N\to N^{\prime}$ is an edge to a non-decision
$N^{\prime}$, where one of $N$ and $N^{\prime}$ is in a path in a system of
$T$, not including the nodes of the root information link, then $N\to
N^{\prime}$ is in a path of a system of $T$.

inline, color=blue!30]Ryan: We should define front-door or just say “starting
with a tail”

An arbitrarily chosen tree will not generally be in normal form. For example,
Fig. 6(a) contains two systems (a red root system for $X^{s}\to D^{s}$ and a
blue child system for $X^{\prime}\to D^{\prime}$) that constitute a tree, but
this tree fails all three requirements for being in normal form. However, by a
series of homomorphic transformations, it is possible to obtain a new graph
with a tree of systems that is in normal form (as in Fig. 6(d)).

######  Lemma 19 (Normal Form Existence).

Let ${\mathcal{G}}$ be a soluble ID graph whose minimal $d$-reduction
${\mathcal{G}}^{*}$ contains $X\to D$. Then there is a normal form tree
$T^{\prime}$ on a soluble ID graph ${\mathcal{G}}^{\prime}$, with a
homomorphism $h$ from ${\mathcal{G}}^{\prime}$ to ${\mathcal{G}}$ where the
information link $X^{\prime}\to D^{\prime}$ of the root system of
$T^{\prime}$, has $h(X^{\prime})=X$, $h(D^{\prime})=D$, and every node in
${\mathcal{G}}$ is also in ${\mathcal{G}}^{\prime}$ but the only nodes in
${\mathcal{G}}$ that are in $T^{\prime}$ are $X$ and $D$.

color=blue!30]Ryan: Is it actually meaningful for nodes in ${\mathcal{G}}$ to
be in $T^{\prime}$, or do we need to talk about applying $h^{-1}$ to them
first? color=blue!30]Ryan: Need to state that
${\mathcal{G}}^{3}={\mathcal{G}}^{\prime},T^{3}=T^{\prime},h^{\prime}=h^{0\leftarrow
3}$ in the proof. color=blue!30]Ryan: Maybe remark at this point that it’s
interesting that we can homomorphically modify the tree to obtain one that
behaves differently, describing how this relates to the unidirectionality of
the homomorphism property? / Address the apparent contradiction that
homomorphisms preserved the properties of a tree, but that we can analyse them
differently.

Essentially, the procedure for obtaining a normal form tree proceeds in four
steps:

  1. 1.

Construct a tree of systems on $X\to D$: First, pick any system for $X\to D$.
Then, pick any system for every other information link $X^{\prime}\to
D^{\prime}$ in the existing system. Iterate until every link in the tree has a
system.

  2. 2.

Make a copy (lemma 12) of each node for each position (basically, each path)
that node has in the tree. This ensures position-in-tree-uniqueness.

  3. 3.

For systems whose infopath starts with an incoming link $X\leftarrow Y$, copy
$X$ (lemma 12), to obtain $X\to O\leftarrow Y$. This ensures no-backdoor-
infopaths.

  4. 4.

Prune the graph (using lemma 13), by removing any (non-information) links
outside the tree of systems. This ensures no-redundant-links.

For example, in Figs. 6(a), 6(b), 6(c) and 6(d), three transformations are
performed, each of which makes the tree meet one additional requirement,
ultimately yielding a normal form tree (Fig. 6(d)) with a homomorphism to the
original.

###  5.4 Proving positive VoI given a normal form tree

The reason for using normal form trees is that they enable each system to be
parameterized and solved independently. In particular, we know that the
optimal policy for one system involves reproducing information from ancestor
nodes such as $Q^{s}$. As optimal policies can be found with backwards
induction in soluble graphs, our approach involves finding optimal policies in
reverse order. It will therefore suffice to prove that non-descendant systems
cannot provide information about ancestor nodes within the system. For
example, in Fig. 6(a), when solving for $\pi^{D^{\prime}}$, we would like to
know that $D^{s}$ cannot provide information about $Q^{\prime}$.

######  Lemma 20 (Subtree Independence).

Let $s$ be a system in a normal form tree $\mathcal{T}$ on a soluble ID graph
${\mathcal{G}}$. Let
$\mathrm{\mathbf{Pa}}^{-s}=\mathrm{\mathbf{Pa}}(D^{s})\setminus{\bm{V}}^{s}$
be $D^{s}$’s out-of-system parents,
$\mathrm{\mathbf{Pa}}^{s}={\mathrm{\mathbf{Pa}}(D^{s})\cap{\bm{V}}^{s}}$ be
the within-system parents of $D^{s}$, $\bf{{ObsDesc}}^{s}$ be the observation
nodes in descendant systems of $s$, and let
$\bf{Back}^{s}={\bm{V}}^{s}\cup(\textbf{Anc}(D^{s})\setminus\mathrm{\mathbf{{Fa}}}(D^{s}))$.
Then
$\bf{Back}^{s}\perp\mathrm{\mathbf{Pa}}^{-s}\setminus\bf{{ObsDesc}}^{s}\mid\mathrm{\mathbf{Pa}}^{s}\cup\bf{{ObsDesc}}^{s}$.

For example, Fig. 6(d), has a normal form tree, which implies the assurance
that $X^{\prime}$ cannot use information from the red system to tell it about
$Q^{\prime}$; formally, $Q^{\prime}\perp(Y\cup X^{s})\mid X^{\prime}$. Given
that each decision $D^{s}$ in the tree cannot use information from ancestor
systems, we can then prove that $D^{s}$ cannot know enough about $X^{s}$ and
$Q^{s}$ to perform optimally, without observing $X^{s}$. More formally:

######  Lemma 21 (VoI Given Normal Form Tree).

Let ${\mathcal{G}}$ be a soluble ID graph with a normal form tree with root
info link $X\to D$. Then there exists an ID compatible with ${\mathcal{G}}$
for which $X$ has positive VoI for $D$.

The formal proof is given in Section D.3. Informally, in order to show that
the decision of each system is forced to behave as intended despite there now
being a tree of systems full of other decisions, we use Lemma 20 to show that
the utility that a decision obtains in system $s$ only depends on the
information it obtains from within system $s$. This rules out that ancestor
decisions can observe and pass along relevant information via a path outside
the system. Moreover, we know by the solubility assumption that the optimal
decision rule at a later decision cannot depend on the decision rule followed
by earlier decisions. The argument then proceeds by backward induction. The
final decision $D^{s^{n}}$ must copy the value of $X^{s_{n}}$. Given that it
does so, the penultimate decision $D^{s^{n-1}}$ must do the same. And so on,
until we find that $D$ must copy $X$, and cannot do so in any way other than
by observing it, meaning that $X$ has positive VoI for $D$.
color=green!30]Chris: I think these explanatory paragraphs can be better.
color=blue!30]Ryan: Is this accurate & better?

Finally, we can prove our main result, that there exists an ID on
${\mathcal{G}}$ where $X$ has positive VoI.

###### Proof of Theorem 7 (completeness direction).

We know that the d-reduction ${\mathcal{G}}^{*}$ of ${\mathcal{G}}$ contains
$X\to D$. By Lemma 19, there exists an ID graph ${\mathcal{G}}^{\prime}$ with
normal form tree rooted at a link $X^{\prime}\to D^{\prime}$, with an ID
homomorphism from ${\mathcal{G}}^{\prime}$ to ${\mathcal{G}}$ that has
$h(X^{\prime})=X$ and $h(D^{\prime})=D$. By Lemma 21, since
${\mathcal{G}}^{\prime}$ has a normal form tree rooted at $X^{\prime}\to
D^{\prime}$, there exists an ID on ${\mathcal{G}}^{\prime}$ in which
$X^{\prime}$ has positive VoI for $D^{\prime}$. By Lemma 12, the presence of
the ID homomorphism $h$ from ${\mathcal{G}}^{\prime}$ to ${\mathcal{G}}$ means
that there also exists an ID ${\mathcal{M}}$ on ${\mathcal{G}}$ such that
$h(X^{\prime})=X$ has positive VoI for $h(D^{\prime})=D$, showing the result.
∎

##  6 Applications & Implementation

color=blue!30]Ryan: Change the figure to all-superscripts? color=blue!30]Ryan:
Cite frameworks paper. color=blue!30]Ryan: Illustrate nodes with +VoC?

Graphical criteria can help with modeling agents’ incentives in a wide range
of settings including (factored) Partially Observed Markov Decision Processes
(POMDPs) and Modified-action Markov Decision Processes (Langlois and Everitt
2021). For concreteness, we show how our contributions can aid in analysing a
supervision POMDP (Milli et al. 2017). In a supervision POMDP, an AI interacts
with its environment, given suggested actions from a human player. We will
assume that the human’s policy has already been selected, in order to focus on
the incentives of the AI system.

$R_{1}$$S_{1}$$A_{1}$$R_{2}$$S_{2}$$A_{2}$$R_{3}$$S_{3}$$A^{\mathrm{H}}_{1}$$A^{\mathrm{H}}_{2}$$\Theta^{H}$
Figure 7: A supervision POMDP with the human considered part of the
environment; we show 3 timesteps and 2 actions.

Given the graph in Fig. 7, we can apply the VoI criterion to each $A^{H}_{i}$,
the sole parent of $A^{i}$. The minimal d-reduction is identical to the
original graph, so since $A^{H}_{i}\\!\not\perp\\!R^{i+1}\\!\mid\\!\emptyset$,
the observation $A^{H}_{i}$ can have positive VoI. This formalises the claim
of Milli et al. (2017) that in a supervision POMDP, the agent “can learn about
reward through [the human’s] orders”. We can say the same about Cooperative
Inverse Reinforcement Learning (CIRL). CIRL differs from supervision POMDPs
only in that each human action $A^{H}_{i}$ directly affects the state
$S_{i+1}$. If ${\mathcal{G}}$ is modified by adding edges $A^{H}_{i}\to
S_{i+1}$, and the VoI criterion is applied at $A^{H}_{i}$ once again, we find
that $A^{H}_{i}$ may have positive VoI for $A^{i}$, thereby formalising the
claim that the robot is “incentivised to learn” (Hadfield-Menell et al. 2016,
Remark 1).

To facilitate convenient use of the graphical criterion, we have implemented
it in the open source ID library _pycid_ (Fox et al. 2021), whereas the
previous implementation was limited to single-decision IDs.111Code is
available at www.github.com/causalincentives/pycid.

##  7 Related Work

##### Value of information

The concept of value of information dates back to the earliest papers on
influence diagrams (Howard 1966; Matheson 1968). For a review of recent
advances, see Borgonovo and Plischke (2016).

Previous results have shown how to identify observations with zero VoI or
equivalent properties in various settings. In the no forgetting setting,
Fagiuoli and Zaffalon (1998) and Nielsen and Jensen (1999) identified
“structurally redundant” and “required nodes” respectively. In soluble IDs,
Nilsson and Lauritzen (2000) proved that optimal decisions need not rely on
nonrequisite nodes. Completeness proofs in a setting of one decision have been
discovered for VoI and its analogues by Zhang, Kumor, and Bareinboim (2020);
Lee and Bareinboim (2020); Everitt et al. (2021a). Finally, in insoluble IDs,
Lee and Bareinboim (2020) proved that certain nodes are “redundant under
optimality”. Of these works, only Nielsen and Jensen (1999) attempts a
completeness result for the multi-decision setting. However, as pointed out by
Everitt et al. (2021a), it falls short in two respects: Firstly, the criterion
$X\not\perp{\bm{U}}^{D}\mid\mathrm{\mathbf{Pa}}(D)$ is proposed, which differs
from nonrequisiteness in the conditioning set. Secondly, and more importantly,
the proof is incomplete because it assumes that positive VoI follows from
d-connectedness.

##### Submodel-trees

Trees of systems are loosely related to the “submodel-trees” of Lee,
Marinescu, and Dechter (2021). In both cases, the tree encodes an ordering in
which the ID can be solved, so the edges in a tree of systems are analogous to
those in a submodel-tree. The nodes, however, (i.e. systems and submodels)
differ. Whereas a submodel-tree aids with solving IDs, a tree of systems helps
with parameterising an ID graph. As a result, a submodel contains all nodes
relevant for $D$, whereas a system consists just one set of
info-/control-/obs-paths. Relatedly, in a submodel, downstream decisions may
be solved and replaced with a value node, whereas in a tree of systems, they
are not.

##  8 Discussion and Conclusion

This paper has described techniques for analyzing soluble influence diagrams.
In particular, we introduced ID homomorphisms, a method for transforming ID
graphs while preserving key properties, and showed how these can be used to
establish equivalent ID graphs with conveniently parameterizable “trees of
systems”. These techniques enabled us to derive the first completeness result
for a graphical criterion for value of information in the multi-decision
setting.

Given the promise of reinforcement learning methods, it is essential that we
obtain a formal understanding of how multi-decision behavior is shaped. The
graphical perspective taken in this paper has both advantages and
disadvantages. On the one hand, some properties cannot be distinguished from a
graphical perspective alone. On the other hand, it means our results are
applicable even when the precise relationships are unspecified or unknown.
There are a range of ways that this work could be beneficial. For example,
analogous results for the single-decision setting have contributed to safety
and fairness analyses (Armstrong et al. 2020; Cohen, Vellambi, and Hutter
2020; Everitt et al. 2021b, 2019; Langlois and Everitt 2021; Everitt et al.
2021a).

Future work could include applying the tools developed in this paper to other
incentive concepts such as value of control (Shachter 1986), instrumental
control incentives, and response incentives (Everitt et al. 2021a), to further
analyse the value of remembering past decisions (Shachter 2016; Lee and
Bareinboim 2020), and to generalize the analysis to multi-agent influence
diagrams (Hammond et al. 2021; Koller and Milch 2003).

## Acknowledgments

This work was supported in-part by the Leverhulme Centre for the Future of
Intelligence, Leverhulme Trust, under Grant RC2015-067.

## References

  * Armstrong et al. (2020) Armstrong, S.; Orseau, L.; Leike, J.; and Legg, S. 2020.  Pitfalls in learning a reward function online.  In _International Joint Conference on Artificial Intelligence (IJCAI)_.
  * Ashurst et al. (2022) Ashurst, C.; Carey, R.; Chiappa, S.; and Everitt, T. 2022.  Why Fair Labels Can Yield Unfair Predictions: Graphical Conditions for Introduced Unfairness.  In _AAAI_.
  * Borgonovo and Plischke (2016) Borgonovo, E.; and Plischke, E. 2016.  Sensitivity analysis: a review of recent advances.  _European Journal of Operational Research_.
  * Cohen, Vellambi, and Hutter (2020) Cohen, M. K.; Vellambi, B. N.; and Hutter, M. 2020.  Asymptotically Unambitious Artificial General Intelligence.  In _AAAI Conference on Artificial Intelligence_.
  * Evans and Kasirzadeh (2021) Evans, C.; and Kasirzadeh, A. 2021.  User Tampering in Reinforcement Learning Recommender Systems.  In _FAccTRec Workshop on Responsible Recommendation_.
  * Everitt et al. (2021a) Everitt, T.; Carey, R.; Langlois, E.; Ortega, P. A.; and Legg, S. 2021a.  Agent Incentives: A Causal Perspective.  In _AAAI_.
  * Everitt et al. (2021b) Everitt, T.; Hutter, M.; Kumar, R.; and Krakovna, V. 2021b.  Reward Tampering Problems and Solutions in Reinforcement Learning: A Causal Influence Diagram Perspective.  _Synthese_.
  * Everitt et al. (2019) Everitt, T.; Kumar, R.; Krakovna, V.; and Legg, S. 2019.  Modeling AGI Safety Frameworks with Causal Influence Diagrams.  In _IJCAI Workshop on AI Safety_.
  * Fagiuoli and Zaffalon (1998) Fagiuoli, E.; and Zaffalon, M. 1998.  A note about redundancy in influence diagrams.  _International Journal of Approximate Reasoning_.
  * Farquhar, Carey, and Everitt (2022) Farquhar, S.; Carey, R.; and Everitt, T. 2022.  Path-Specific Objectives for Safer Agent Incentives.  In _AAAI_.
  * Fox et al. (2021) Fox, J.; Everitt, T.; Carey, R.; Langlois, E.; Abate, A.; and Wooldridge, M. 2021\.  PyCID: A Python Library for Causal Influence Diagrams.  In _Scientific Computing with Python Conference (SciPy)_.
  * Hadfield-Menell et al. (2016) Hadfield-Menell, D.; Dragan, A.; Abbeel, P.; and Russell, S. J. 2016.  Cooperative Inverse Reinforcement Learning.  In _Advances in Neural Information Processing Systems (Neurips)_.
  * Hammond et al. (2021) Hammond, L.; Fox, J.; Everitt, T.; Abate, A.; and Wooldridge, M. 2021.  Equilibrium Refinements for Multi-Agent Influence Diagrams: Theory and Practice.  In _International Conference on Autonomous Agents and Multiagent Systems (AAMAS)_.
  * Holtman (2020) Holtman, K. 2020.  AGI Agent Safety by Iteratively Improving the Utility Function.  _International Conference on Artificial General Intelligence_.
  * Howard (1966) Howard, R. A. 1966.  Information Value Theory.  _IEEE Transactions on Systems Science and Cybernetics_.
  * Howard et al. (2005) Howard, R. A.; Matheson, J. E.; Howard, R. A.; and Matheson, J. E. 2005.  Influence Diagram Retrospective.  _Decision Analysis_.
  * Koller and Milch (2003) Koller, D.; and Milch, B. 2003.  Multi-agent influence diagrams for representing and solving games.  _Games and Economic Behavior_.
  * Kusner et al. (2017) Kusner, M. J.; Loftus, J. R.; Russell, C.; and Silva, R. 2017.  Counterfactual Fairness.  In _Advances in Neural Information Processing Systems (Neurips)_.
  * Langlois and Everitt (2021) Langlois, E.; and Everitt, T. 2021.  How RL Agents Behave when their Actions are Modified.  In _AAAI_.
  * Lee, Marinescu, and Dechter (2021) Lee, J.; Marinescu, R.; and Dechter, R. 2021.  Submodel Decomposition Bounds for Influence Diagrams.  In _AAAI_.
  * Lee and Bareinboim (2020) Lee, S.; and Bareinboim, E. 2020.  Characterizing optimal mixed policies: Where to intervene and what to observe.  _Advances in Neural Information Processing Systems (Neurips)_.
  * Matheson (1968) Matheson, J. E. 1968.  The economic value of analysis and computation.  _IEEE Transactions on Systems Science and Cybernetics_.
  * Milch and Koller (2008) Milch, B.; and Koller, D. 2008.  Ignorable Information in Multi-Agent Scenarios.  Technical report, Massachusetts Insitute of Technology (MIT).
  * Milli et al. (2017) Milli, S.; Hadfield-Menell, D.; Dragan, A.; and Russell, S. J. 2017.  Should robots be obedient?  In _International Joint Conference on Artificial Intelligence (IJCAI)_.
  * Nielsen and Jensen (1999) Nielsen, T. D.; and Jensen, F. V. 1999.  Welldefined decision scenarios.  In _Uncertainty in Artificial Intelligence (UAI)_.
  * Nilsson and Lauritzen (2000) Nilsson, D.; and Lauritzen, S. L. 2000.  Evaluating influence diagrams using LIMIDs.  _Uncertainty in Artificial Intelligence (UAI)_.
  * Shachter (1986) Shachter, R. D. 1986.  Evaluating influence diagrams.  _Operations research_.
  * Shachter (1998) Shachter, R. D. 1998.  Bayes-Ball: The Rational Pastime (for Determining Irrelevance and Requisite Information in Belief Networks and Influence Diagrams).  _Uncertainty in Artificial Intelligence (UAI)_.
  * Shachter (2016) Shachter, R. D. 2016.  Decisions and Dependence in Influence Diagrams.  In _Proceedings of the Eighth International Conference on Probabilistic Graphical Models_.
  * Verma and Pearl (1988) Verma, T.; and Pearl, J. 1988.  Causal Networks: Semantics and Expressiveness.  In _Uncertainty in Artificial Intelligence (UAI)_.
  * Zhang, Kumor, and Bareinboim (2020) Zhang, J.; Kumor, D.; and Bareinboim, E. 2020.  Causal imitation learning with unobserved confounders.  _Advances in Neural Information Processing Systems (Neurips)_.

##  Appendix A Background for the proofs

We review two properties of IDs — and all Bayesian networks — that we will use
throughout our proofs.

######  Lemma 22 (Active paths between ancestors contain only ancestors).

A path from an ancestor of node $N$ to another ancestor of $N$, that is active
conditional on only ancestors of $N$, contains only ancestors of $N$.

###### Proof.

Let $p\colon A\;\hbox{- - -}\;B$ be any active path where $A$ and $B$ are
ancestors of $N$ and let the colliders on $p$ be ${\bm{O}}$. Since $p$ is
active, any collider $O\in{\bm{O}}$ on $p$ is an ancestor of the conditioned
set, and is therefore an ancestor of $N$. For any chain or fork node $V$,
choose one of its outgoing edges along $p$ and follow $p$ until the next
collider or endpoint (${\bm{O}}$, $A$, or $B$). This path is directed, so $V$
is an ancestor of $O$, $A$, or $B$, and hence $M$. ∎

The standard definition of a walk is a sequence of consecutive edges. Unless a
node has an edge to itself, a walk is not alowed to visit the same node twice
in a row. Instead, we define a notion of a walk such that it is always allowed
to repeat the same node previously visited.

######  Definition 23 (Walk with node repetition).

A _walk with node repetition_ from $N^{1}$ to $N^{n}$ in a graph
$({\bm{V}},{E})$ is a sequence of nodes $N^{1},...,N^{n}$ such that for any
$i\in\\{1,...,n-1\\}$, either there is a link $N^{i}\to N^{i+1}$ or
$N^{i}\leftarrow N^{i+1}$ in ${E}$, or $N^{i}=N^{i+1}$.

We say that a node $N$ in a walk with node repetitions $p$ is a
collider/fork/chain node in a walk with node repetitions $w$ if it is a
collider/fork/chain node in the walk (without node repetitions) $w^{\prime}$
obtained by removing any nodes that are equal to their predecessor.

######  Lemma 24 (“Active” walk with node repetitions implies active path).

If there is a walk with node repetition from node $A$ to node $B$, such that
all fork and chain nodes are not in a set ${\bm{Z}}$, and all collider nodes
have a descendant in ${\bm{Z}}$, then there is a path between $A$ and $B$ that
is active given ${\bm{Z}}$.

###### Proof.

Assume there is a walk with node repetition $w\colon A\;\hbox{- - -}\;B$ such
that every collider in $w$ has a descendant in ${\bm{Z}}$ and every non-
collider in $w$ is not in ${\bm{Z}}$. Then let $p$ be the path obtained from
$w$ by replacing every segment $N\;\hbox{- - -}\;N$ with the node $N$.
Clearly, $p$ is a path, so we will proceed to show that it is active given
${\bm{Z}}$, by showing that it is active at each of its nodes.

Assume that $N$ is a collider in $p$. Then, $N$ was obtained from a segment in
$w$, $Y_{1}\to N\;\hbox{- - -}\;N\leftarrow Y_{2}$ where $N\;\hbox{- - -}\;N$
has length zero or greater. For this segment to be active in $w$, the first
collider in $N\;\hbox{- - -}\;N$ must have a descendant in ${\bm{Z}}$, and
thus so does $N$, and it is active in $p$. Assume instead that $N$ is a non-
collider. Then, $N$ was obtained from a segment in $w$, $Y_{1}\to N\;\hbox{- -
-}\;N\to Y_{2}$, $Y_{1}\leftarrow N\;\hbox{- - -}\;N\leftarrow Y_{2}$, or
$Y_{1}\leftarrow N\;\hbox{- - -}\;N\to Y_{2}$. In any case, for this segment
to be active in $w$, $N\not\in{\bm{Z}}$, so it is active in $p$, proving the
result. ∎

$O$$D_{1}$$D_{2}$$U$$\Pi_{1}$$\Pi_{2}$ (a) Insoluble ID graph

$O$$D_{1}$$D_{2}$$U$$\Pi_{1}$$\Pi_{2}$ (b) ID graph with perfect recall

$O_{2}$$D_{1}$$S$$O_{1}$$D_{2}$$U_{2}$$U_{1}$$\Pi_{1}$$\Pi_{2}$ (c) Soluble ID
graph

Figure 8: Multi-decision IDs.

For our analysis, we consider soluble ID graphs. This condition includes
graphs with perfect recall Fig. 8(b) but also includes some others, shown in
Fig. 8(c).

##  Appendix B ID homomorphisms

###  B.1 Properties preserved given an ID homomorphism

We now prove two properties that are preserved by any ID homomorphism:222An ID
homomorphism is analogous to the notion of graph homomorphism from graph
theory, which essentially requires that edges are preserved along the map. In
fact, if we would consider every node in an ID graph as a decision and as
having an edge to itself, then any ID homomorphism is also a graph
homomorphism when considering the two ID graphs as ordinary graphs (ignoring
node types). solubility, and VoI.

See 9

###### Proof.

Since ${\mathcal{G}}$ is soluble, there is a total ordering of decisions $<$
such that for all $D^{1}<D^{2}$, $\Pi^{D}\perp
U(D^{2})\mid\mathrm{\mathbf{{Fa}}}(D^{2})$. To show that
${\mathcal{G}}^{\prime}$ is also soluble, we use $<$ to construct an ordering
on the decisions of ${\mathcal{G}}^{\prime}$ that has the same property. We
define $<^{\prime}$ for decisions in ${\mathcal{G}}^{\prime}$: as
$D^{1}<^{\prime}D^{2}$ when:

  * •

$h(D^{1})\neq h(D^{2})$ and $h(D^{1})<h({D^{2}})$; or

  * •

$h(D^{2})=h(D^{2})$ and ${\mathcal{G}}^{\prime}$ contains $D^{1}\to D^{2}$.

This is a total order since whenever $h(D^{1})\neq h(D^{2})$ then either
$h(D^{1})<h(D^{2})$ or $h(D^{1})>h(D^{2})$ by the total order on
${\mathcal{G}}$, and whenever $h(D^{1})=h(D^{2})$ then
${\mathcal{G}}^{\prime}$ contains $D^{1}\to D^{2}$ or $D^{1}\leftarrow D^{2}$
by (Combines only linked decisions).

Now we show that for any two decisions $D^{1},D^{2}$ in
${\mathcal{G}}^{\prime}$, with $D^{1}<^{\prime}D^{2}$, that any path
$p\colon\Pi^{D^{1}}\to D^{1}\;\hbox{- - -}\;U$ for some
$U\in\textbf{Desc}(D^{2})$ cannot be active given
$\mathrm{\mathbf{{Fa}}}(D^{2})$. Consider two cases:

Case (1) : Assume $h(D^{2})\\!=\\!h(D^{1})$. Then $D^{1}\\!<\\!D^{2}$ so
${\mathcal{G}}^{\prime}$ contains $D^{1}\to D^{2}$ by definition of
$<^{\prime}$, and so any path $p\colon\Pi^{D^{1}}\to D^{1}\;\hbox{- - -}\;U$
that starts with the link $\Pi^{D^{1}}\to D^{1}\to Y$ is blocked at $D^{1}$
given $\mathrm{\mathbf{Pa}}({D^{2}})$. Any path that begins as $\Pi^{D^{1}}\to
D^{1}\leftarrow Y$ is blocked at the non-collider $Y$: the presence of
$D^{1}\leftarrow Y$ implies that ${\mathcal{G}}$ contains $h(D^{1})\leftarrow
h(Y)$ (Preserves links), so that ${\mathcal{G}}^{\prime}$ contains
$D^{2}\leftarrow Y$ (Covers all infolinks), and
$Y\in\mathrm{\mathbf{Pa}}(D^{2})$.

Case (2) : Assume $h(D^{2})\neq h(D^{1})$. We will prove the contrapositive:
if $\Pi^{D^{1}}\not\perp U(D^{2})\mid\mathrm{\mathbf{{Fa}}}(D^{2})$ in
${\mathcal{G}}^{\prime}$ then $\Pi^{h(D^{1})}\not\perp
U(h(D^{2}))\mid\mathrm{\mathbf{{Fa}}}(h(D^{2}))$ in ${\mathcal{G}}$ where
$h(D^{1})<h(D^{2})$. If $p\colon\Pi^{D^{1}}\to D^{1}\;\hbox{- - -}\;U(D^{2})$
is active given $\mathrm{\mathbf{{Fa}}}(D^{2})$, then consider the walk with
node repetition $w\colon\Pi^{h(D^{1})}\to h(D^{1})\;\hbox{- -
-}\;h(U(D^{\prime}))$ consisting of $f(V)$ for each node $V$ in $p$. We know
that each $V$ in $p$ is a (chain/fork/collider) if and only if $h(V)$ is a
(chain/fork/collider) in $w$, since if there is a link $N\to V$ or
$N\leftarrow V$ then there must be a link $h(N)\to h(V)$ or $h(N)\leftarrow
h(V)$ respectively by the (Preserves links) assumption of ID homomorphisms.
And that each node $V$ contains a descendant in
$\mathrm{\mathbf{{Fa}}}(D^{2})$ if and only if $h(V)$ contains a descendant in
$\mathrm{\mathbf{{Fa}}}(h(D^{2}))$. So every collider in $w$ has a descendant
in $\mathrm{\mathbf{{Fa}}}(h(D^{2}))$ while every non-collider does not. This
implies that $\Pi^{h(D^{1})}\not\perp
U(h(D^{2}))\mid\mathrm{\mathbf{{Fa}}}(h(D^{2}))$ by Lemma 24, and we know that
$h(D^{1})<h(D^{2})$ by the definition of $<^{\prime}$ so the result follows. ∎

We can now define how a homomorphism allows us to define a procedure for
transporting IDs between the two graphs, such that corresponding IDs and
policies lead to equivalent outcomes.

See 11

###### Proof.

We define the _ported ID_ ${\mathcal{M}}=({\mathcal{G}},\mathrm{dom},P)$ as
follows: Each non-utility node $N$ in ${\mathcal{G}}$ has
$\mathrm{dom}(N)=\prod_{N^{i}\in h^{-1}(N)}\mathrm{dom}(N^{i})$, and each
utility node $U$ in ${\mathcal{G}}$ has $\mathrm{dom}(U)=\mathbb{R}$. Each
non-decision node $N$ has as $P^{N}(n|\mathrm{\mathbf{pa}})$ the joint
conditional distribution of each
$\tilde{P}^{N^{i}}(n^{i}|\mathrm{\mathbf{pa}}^{i})$. We define the _ported
policy_ $\pi$ so that each decision $D$ has as
$\pi^{D}(d|\mathrm{\mathbf{pa}})$ the joint conditional distribution of each
$\pi^{D^{i}}(d^{i}|\mathrm{\mathbf{pa}})$. These in fact factor over
${\mathcal{G}}$ by property (b) of ID homomorphisms.

We show the result by induction on the graph of nodes $N^{i}$ in
${\mathcal{G}}^{4}$. Let $N=h(N^{i})$.

base step : Assume $N^{i}$ has no parents in ${\mathcal{G}}^{4}$. Then
$P(N\\!=\\!(n^{1},...,n^{k}))=P^{N}((n^{1},...,n^{k}))=\prod_{i=1}^{k}\tilde{P}^{N^{i}}(n^{i}|n^{1},...,n^{i-1})=\tilde{P}(N^{1}\\!=\\!n^{1},...,N^{k}=n^{k})$.

inductive step : Assume that for all parents $Y^{i}$ of $N^{i}$, letting
$Y=h(Y^{i})$, we have that
$P(Y\\!=\\!(y^{1},...,y^{k}))=\tilde{P}(Y^{1}\\!=\\!y^{1},...,Y^{k}=y^{k})$.
Then

$\displaystyle P(N\\!=\\!(n^{1},...,n^{k}))$
$\displaystyle=\sum_{y^{1},...,y^{k}}P(Y\\!=\\!(y^{1},...,y^{k}))\cdot
P^{N}((n^{1},...,n^{k})|y^{1},...,y^{k})\quad\quad$
$\displaystyle=\sum_{y^{1},...,y^{k}}\tilde{P}(Y^{1}\\!=\\!y^{1},...,Y^{k}\\!=\\!y^{k}))\cdot\prod_{i=1}^{k}\tilde{P}^{N^{i}}(n^{i}|n^{1},...,n^{i-1},y^{1},...,y^{k})\quad\quad$
$\displaystyle=\tilde{P}(N^{1}\\!=\\!n^{1},...,N^{k}=n^{k})\quad$

Which shows the result. ∎

We will write the “transported ID” and policy from Lemma 11 as $h(M)$ and
$h(\pi)$. This means that we also treat a homomorphism $h$ as a function
between IDs and policies. In fact, in order to show that ID homomorphisms
preserve VoI , we show that on policies, $h$ is a bijection, which relies on
the properties (c) and (d) of ID homomorphisms, and is the primary reason why
(c,d) are included:

######  Lemma 25.

Any ID homomorphism $h$ is a bijection from (optimal) policies on
$\tilde{\mathcal{M}}$ to (optimal) policies on
${\mathcal{M}}=h(\tilde{\mathcal{M}})$.

###### Proof.

We define an inverse for the map as follows: Take a policy $\pi_{D}$ on $M$.
This gives a joint distribution $\tilde{\pi}^{D^{i}}=(\pi^{D})^{i}$ over
$\mathrm{dom}(D^{i})$ for $D^{i}\in\mathcal{D}=h^{-1}(D)$. Moreover, for any
$X^{j}\in\mathrm{\mathbf{Pa}}(D)$ and for any $X^{j,k}\in h^{-1}(X^{j})$, each
decision $D^{i}$ has $X^{j,k}\in\mathrm{\mathbf{Pa}}(D^{i})$ by (Covers all
infolinks), and since these decisions $D^{i}$ form a complete graph (each
$D^{i}$ is linked to each $D^{j}$) by condition (Combines only linked
decisions), this distribution $\tilde{\pi}^{D^{i}}$ also factors over
$\tilde{\mathcal{G}}$ and hence is a policy $\tilde{M}$. But this is precisely
the definition of $\pi^{D}$ being the transported policy of
$\tilde{\pi}^{\mathcal{D}}$, so that $\pi^{D}\mapsto\pi^{\mathcal{D}}$ is
indeed the desired inverse. The optimal version of this lemma then follows
from Lemma 11. ∎

See 12

###### Proof.

Let $\mathcal{X}$ be the set of nodes $X^{j}$ in ${\mathcal{G}}^{\prime}$ such
that $h(X^{j})=X$, and $\mathcal{D}$ the set of nodes $D^{j}$ such that
$h(D^{j})=D$.

Firstly, note that $h$ is also a homomorphism from
${\mathcal{G}}^{\prime}_{\mathcal{X}\to\mathcal{D}}$ to ${\mathcal{G}}_{X\to
D}$ and from ${\mathcal{G}}^{\prime}_{\mathcal{X}\not\to\mathcal{D}}$ to
${\mathcal{G}}_{X\not\to D}$ (since in both cases, there is still an edge
$X^{i}\to D^{i}$ iff there is an edge $X\to D$). Hence, for any policy
$\pi^{\prime}$ on $M^{\prime}$ and letting $\pi=h(\pi^{\prime})$ be the
corresponding policy on $M$, apply Lemma 11 twice to conclude that
${\mathbb{E}}^{M_{X\to
D}}_{\pi}(\mathcal{U})={\mathbb{E}}^{M^{\prime}_{\mathcal{X}\to\mathcal{D}}}_{\pi^{\prime}}(\mathcal{U})$
and ${\mathbb{E}}^{M^{\prime}_{X\not\to
D}}_{\pi^{\prime}}(\mathcal{U})={\mathbb{E}}^{M_{\mathcal{X}\not\to\mathcal{D}}}_{\pi}(\mathcal{U})$.

Since the map that maps a policy on $M^{\prime}$ to the corresponding policy
on $M$ (see Lemma 11) is a bijection by Lemma 25, this implies that
$\max_{\pi}{\mathbb{E}}^{M_{X\to
D}}_{\pi}(\mathcal{U})=\max_{\pi^{\prime}}{\mathbb{E}}^{M^{\prime}_{\mathcal{X}\to\mathcal{D}}}_{\pi^{\prime}}(\mathcal{U})$
and $\max_{\pi}{\mathbb{E}}^{M_{X\not\to
D}}_{\pi}(\mathcal{U})=\max_{\pi^{\prime}}{\mathbb{E}}^{M^{\prime}_{\mathcal{X}\not\to\mathcal{D}}}_{\pi^{\prime}}(\mathcal{U})$.
These imply:

$\displaystyle\max\limits_{\pi}{\mathbb{E}}^{M_{X\to D}}_{\pi}(\mathcal{U})$
$\displaystyle=\max\limits_{\pi^{\prime}}{\mathbb{E}}^{M^{\prime}_{\mathcal{X}\to\mathcal{D}}}_{\pi^{\prime}}(\mathcal{U})\quad\quad$
$\displaystyle:\text{by the argument above}$
$\displaystyle\geq\max\limits_{\pi^{\prime}}{\mathbb{E}}^{M^{\prime}_{X^{i}\to
D^{i}}}_{\pi^{\prime}}(\mathcal{U})\quad\quad$ $\displaystyle:\text{more
infolinks cannot decrease max utility}$
$\displaystyle>\max\limits_{\pi^{\prime}}{\mathbb{E}}^{M^{\prime}_{X^{i}\not\to
D^{i}}}_{\pi^{\prime}}(\mathcal{U})\quad$ $\displaystyle:\text{by assumption:
$X^{i}$ is material for $D^{i}$}$
$\displaystyle\geq\max\limits_{\pi^{\prime}}{\mathbb{E}}^{M^{\prime}_{\mathcal{X}\not\to\mathcal{D}}}_{\pi^{\prime}}(\mathcal{U})\quad$
$\displaystyle:\text{more infolinks cannot decrease max utility}$
$\displaystyle=\max\limits_{\pi}{\mathbb{E}}^{M_{X\not\to
D}}_{\pi}(\mathcal{U})\quad$ $\displaystyle:\text{by the argument above}$

which shows the result. ∎

###  B.2 Transformations that ensure a homomorphism

See 15

###### Proof.

We show that each of the four properties is preserved under composition:

(a) If $h$ and $h’$ preserve node types, then clearly so does $h\circ
h^{\prime}$.

(b) If ${\mathcal{G}}^{\prime\prime}$ contains $A\to B$ then by (b) for
$h^{\prime}$, ${\mathcal{G}}^{\prime}$ contains $h’(A)\to h^{\prime}(B)$ or
$h^{\prime}(A)=h^{\prime}(B)$. In either case, (b) for $h$ implies that
${\mathcal{G}}$ contains $h\circ h^{\prime}(A)\to h\circ h^{\prime}(B)$ or
$h\circ h^{\prime}(A)=h\circ h^{\prime}(B)$.

(c) If ${\mathcal{G}}$ contains $h\circ h^{\prime}(N)\to h\circ
h^{\prime}(D)$, then by (c) for $h$, ${\mathcal{G}}^{\prime}$ contains
$h’(N)\to h^{\prime}(D)$ and by the same argument ${\mathcal{G}}$ contains
$N\to D$.

(d) Assume $h\circ h^{\prime}(D^{1})=h\circ h^{\prime}(D^{2})$ and
$D^{1}\\!\neq\\!D^{2}$ in ${\mathcal{G}}^{\prime\prime}$. Then if
$h’(D^{1})\\!=\\!h^{\prime}(D^{2})$, by (d) for $h^{\prime}$,
${\mathcal{G}}^{\prime\prime}$ contains $D^{1}\\!\to\\!D^{2}$ or
$D^{2}\\!\to\\!D^{1}$ showing the result. If $h’(D^{1})\neq h^{\prime}(D^{2})$
then by (d) for $h$, ${\mathcal{G}}^{\prime}$ contains $h’(D^{1})\to
h^{\prime}(D^{2})$ or $h’(D^{2})\to h^{\prime}(D^{1})$, and hence by (c) for
$h^{\prime}$, ${\mathcal{G}}^{\prime\prime}$ contains $D^{1}\to D^{2}$ or
$D^{2}\to D^{1}$. ∎

See 13 color=blue!30]Ryan: I’ve simplified/shortened this a bit further. Feel
free to revert any changes is preferred.

###### Proof.

ID homomorphism condition (a) follows by definition. (b) follows from the
definition of $E^{\prime}$. (c,d) follow since they hold for all nodes $N$ by
definition, including the decisions. ∎

See 14

###### Proof.

The homomorphism properties follow: (a) by definition. (b) from
$E^{\prime}\\!\subseteq\\!E$, (c) from every $N\\!\to\\!D\in{\bm{D}}$ being in
$E$, (d) from $h$ being the identity map so every $D^{1}\\!\neq\\!D^{2}$ has
$h(D^{1})\\!\neq\\!h(D^{2})$. ∎

##  Appendix C Systems and trees of systems in an ID graph

###  C.1 Systems

Before detailing the properties of systems, we first recap the elements of a
system. We call $D^{s}$, $U^{s}$, $X^{s}$, and $\mathrm{infolink}^{s}\colon
X^{s}\to D^{s}$ the _decision node_ , _utility node_ , _info node_ , and
_infolink_ of $s$, respectively, and refer to $\mathrm{control}^{s}$,
$\mathrm{info}^{s}$ and $\mathrm{obs}^{s}(C)$ for each collider $C$ in
$\mathrm{info}^{s}$ as the _paths of $s$_.

######  Definition 26 (Elements of a system).

For a system $s$:

  * •

An _obs node_ $O$ of $s$ is the penultimate node of each obs path
$\mathrm{obs}^{s}(C)$.333For “observation node”. But note that though $D^{i}$
does “observe” $X^{i}$, it is not an obsnode, since it is not the penultimate
node of an $\mathrm{obs}^{s}(C)$, but is the first node of
$\mathrm{info}^{s}$.

  * •

The _question node_ $Q^{s}$, if $\mathrm{info}^{s}$ contains at least one fork
node, is the closest-to-$U^{s}$ fork node on $\mathrm{info}^{s}$.444This
implies that the segment of the info path from $Q^{s}$ to $U^{s}$ is a
directed path $Q^{s}\dashrightarrow U^{s}$, since there are no fork nodes on
that path, and it must begin and end with an arrow towards $U^{s}$.

  * •

The _back section_ , if $\mathrm{info}^{s}$ contains a fork, is the set of
nodes in $X^{s}\;\hbox{- - -}\;Q^{s}$ in $\mathrm{info}^{s}$ (including
$X^{s}$ and $Q^{s}$) and in each $\mathrm{obs}(C^{i})$, except for $D^{s}$.
Otherwise, the back section is empty.

  * •

The _front section_ consists of the nodes in any path in $s$ that are not in
the back section.

######  Definition 27 (Within-system links and paths).

A link $A\to B$ that is in $\mathrm{info}^{s}$, $\mathrm{control}^{s}$, or any
$\mathrm{obs}^{s}(C^{i})$, or the link $X^{s}\to D^{s}$ for some system $s$ is
called a _within-system- $s$_ or _within-system link_. A _within-system path_
is a path that contains only within-system links.

We will now prove a number of fundamental properties of systems.

######  Lemma 28 (Basic properties of a system in a soluble ID graph).

Any system $s$ in a soluble ID graph has the properties:

  1. (a)

(No infolinks in the back-section) The back section of $s$ can only contain a
decision $D^{\prime}\in{\bm{D}}$ if $D^{\prime}=X^{s}$, and the infopath
$\mathrm{info}^{s}$ is front-door. Moreover then $D^{\prime}$ is not in any
$\mathrm{obs}^{s}(C^{i})$. color=green!30]Chris: Above can be phrased more
neatly. but not a priority.

  2. (b)

(Infolinks in $s$ are descendants of $D^{s}$) An information link $N\to
D^{\prime}$ for $D^{\prime}\neq D^{s}$ can only be contained in a path in
system $s$ if the control path $\mathrm{control}^{s}$ contains a parent of
$D^{\prime}$, so that $D^{\prime}\in\textbf{Desc}(D^{s})$.

  3. (c)

(Parents of ancestor decisions are parents of $D^{s}$) A node $N$ in system
$s$ can only be a parent of an ancestor decision $D^{\prime}$ of $D^{s}$ if
$N$ is also a parent of $D^{s}$.555Note that in a normal form tree (see
below), this link $N\to D^{\prime}$ is an out-of-tree link

###### Proof.

We prove each property in succession:

(a) (No infolinks in the back section) We will prove what restrictions are
implies by considering sequentially the cases where $D^{\prime}$ is in either
the infopath, or in the observation path. To begin with, let us state what we
know in both cases: $D^{\prime}$ must be an ancestor of $D^{s}$. As such,
$D^{\prime}<D^{s}$ in any topological ordering, so solubility requires that
$D^{\prime}\perp U^{s}\mid\mathrm{\mathbf{{Fa}}}(D^{s})$.

If $D^{\prime}\in\mathrm{info}^{s}$, then the path $p\colon\Pi^{\prime}\to
D^{\prime}\mathrel{\mathop{\;\hbox{- - -}\;}\limits^{\vbox
to1.50694pt{\kern-2.0pt\hbox{$\scriptstyle\mathrm{info}^{s}$}\vss}}}U^{s}$ may
be formed from by truncating the infopath $\mathrm{info}^{s}$. By solubility,
$p$ must be blocked given $\mathrm{\mathbf{{Fa}}}(D^{s})$. We know, however,
that $\mathrm{info}\colon X^{s}\mathrel{\mathop{\;\hbox{- -
-}\;}\limits^{\vbox
to1.50694pt{\kern-2.0pt\hbox{$\scriptstyle\mathrm{info}^{s}$}\vss}}}U^{s}$ is
active given $\mathrm{\mathbf{{Fa}}}({D^{s}})\setminus\\{X^{s}\\}$. If
$D^{\prime}\neq X^{s}$ then $p$ does not contain $X^{s}$, and so it is is
active given $\mathrm{\mathbf{{Fa}}}({D^{s}})$, violating solubility.
Moreover, if $D^{\prime}=X^{s}$ and $\mathrm{info}$ is a backdoor path, then
$p$ will have a collider at $D^{\prime}$, and solubility is violated once
again. So $\mathrm{info}^{s}$ can only contain a decision $D^{\prime}$ if
$D^{\prime}=X^{s}$ and $\mathrm{info}^{s}$ is frontdoor.

Now we will prove that $D^{\prime}\not\in\mathrm{obs}(C)$, by contradiction.
Suppose that $D^{\prime}\in\mathrm{obs}(C)$. Then, consider the path
$q\colon\Pi^{\prime}\to
D^{\prime}\mathrel{\mathop{\dashleftarrow}\limits^{\vbox
to1.50694pt{\kern-2.0pt\hbox{$\scriptstyle\mathrm{obs}^{s}(C)$}\vss}}}C\mathrel{\mathop{\;\hbox{-
- -}\;}\limits^{\vbox
to1.50694pt{\kern-2.0pt\hbox{$\scriptstyle\mathrm{info}^{s}$}\vss}}}U^{s}$,
constructed by truncating the observation path and infopath. By assumption,
the path $C\mathrel{\mathop{\dashrightarrow}\limits^{\vbox
to1.50694pt{\kern-2.0pt\hbox{$\scriptstyle\mathrm{obs}^{s}(C)$}\vss}}}Y\to D$
is minimal-length, so no node $W\neq Y$ on the path can be a parent of
$D^{s}$, and so $D^{s}\mathrel{\mathop{\dashleftarrow}\limits^{\vbox
to1.50694pt{\kern-2.0pt\hbox{$\scriptstyle\mathrm{obs}^{s}(C)$}\vss}}}C$ is
active given $\mathrm{\mathbf{{Fa}}}(D^{s})$. The segment
$C\mathrel{\mathop{\;\hbox{- - -}\;}\limits^{\vbox
to1.50694pt{\kern-2.0pt\hbox{$\scriptstyle\mathrm{info}^{s}$}\vss}}}U^{s}$ is
active given $\mathrm{\mathbf{{Fa}}}(D^{s})\setminus\\{X^{s}\\}$. Since
$\mathrm{info}^{s}$ is a path, the segment $C\mathrel{\mathop{\;\hbox{- -
-}\;}\limits^{\vbox
to1.50694pt{\kern-2.0pt\hbox{$\scriptstyle\mathrm{info}^{s}$}\vss}}}U^{s}$
cannot contain $X^{s}$, and thus is active given
$\mathrm{\mathbf{{Fa}}}(D^{s})$. So the path $q$ is active given
$\mathrm{\mathbf{{Fa}}}(D^{s})$, violating solubility.

Together, these two cases prove the result.

(b) (Infolinks in $s$ are descendants of $D^{s}$) We know from sublemma (a)
that the back section cannot contain any link $N\to D^{\prime}$. So
$D^{\prime}$ must lie in the front-section of $s$: either in
$Q^{s}\mathrel{\mathop{\;\hbox{- - -}\;}\limits^{\vbox
to1.50694pt{\kern-2.0pt\hbox{$\scriptstyle\mathrm{info}^{s}$}\vss}}}U^{s}$, or
in $\mathrm{control}^{s}$. In either case, we have
$U^{s}\in\textbf{Desc}(D^{s})$ and $U^{s}\in\textbf{Desc}(D^{\prime})$. So in
order for the ID graph to be soluble, we must have either
$\Pi^{D^{\prime}}\perp U^{s}\mid\mathrm{\mathbf{{Fa}}}(D^{s})$ or
$\Pi^{D^{s}}\perp U^{s}\mid\mathrm{\mathbf{{Fa}}}(D^{\prime})$.

We can show that the first case $\Pi^{D^{\prime}}\perp
U^{s}\mid\mathrm{\mathbf{{Fa}}}(D^{s})$ cannot hold. If $D^{\prime}$ is in
$\mathrm{control}^{s}$, note that $\mathrm{control}^{s}$ consists of only
descendants of $D^{s}$. If $D^{\prime}$ is in
$q:Q^{s}\mathrel{\mathop{\;\hbox{- - -}\;}\limits^{\vbox
to1.50694pt{\kern-2.0pt\hbox{$\scriptstyle\mathrm{info}^{s}$}\vss}}}U^{s}$
then note that $q$ is assumed to be active given
$\mathrm{\mathbf{{Fa}}}(D^{s})\setminus\\{X^{s}\\}$, and cannot contain
$X^{s}$. In either case, $\Pi^{D^{\prime}}\not\perp
U^{s}\mid\mathrm{\mathbf{{Fa}}}(D^{s})$. Hence we must have $\Pi^{D^{s}}\perp
U^{s}\mid\mathrm{\mathbf{{Fa}}}(D^{\prime})$, from which it follows that every
directed path from $D^{s}$ to $U^{s}$ (including $\mathrm{control}^{s}$) must
contain a parent of $D^{\prime}$.

(c) (Parents of ancestor decisions are parents of $D^{s}$) Assume $N$ is a
parent of $D^{\prime}$ in a path of $s$. It cannot be in
$\mathrm{control}^{s}$, because then $D^{\prime}$ would be a descendant of
$D^{s}$. So $N$ must be in $\mathrm{info}^{s}$ or one of
$\mathrm{obs}^{s}(C)$. If $N$ is in $\mathrm{info}^{s}$, consider the path
$p\colon\Pi^{D’}\to D’\leftarrow N\mathrel{\mathop{\;\hbox{- -
-}\;}\limits^{\vbox
to1.50694pt{\kern-2.0pt\hbox{$\scriptstyle\mathrm{info}^{s}$}\vss}}}U^{s}$. We
know $\mathrm{info}^{s}$ is active given
$\mathrm{\mathbf{{Fa}}}({D^{s}})\setminus\\{X^{s}\\}$. Hence if
$N\notin\mathrm{\mathbf{Pa}}(D^{s})$, then $p$ is active given
$\mathrm{\mathbf{Pa}}({D^{s}})$ and since it doesn’t contain $D^{s}$ also
active given $\mathrm{\mathbf{{Fa}}}(D^{s})$, violating solubility. Hence
$N\in\mathrm{\mathbf{Pa}}(D^{s})$.

Similarly, if $N$ is in $\mathrm{obs}^{s}(C)$, then consider the path
$q\colon\Pi^{D^{\prime}}\to D^{\prime}\leftarrow
N\mathrel{\mathop{\dashleftarrow}\limits^{\vbox
to1.50694pt{\kern-2.0pt\hbox{$\scriptstyle\mathrm{obs}^{s}(C)$}\vss}}}C\mathrel{\mathop{\;\hbox{-
- -}\;}\limits^{\vbox
to1.50694pt{\kern-2.0pt\hbox{$\scriptstyle\mathrm{info}^{s}$}\vss}}}U^{s}$.
Hence if $N\notin\mathrm{\mathbf{Pa}}(D^{s})$, then since
$\mathrm{obs}^{s}(C)$ is minimal-length, it holds that
$N\mathrel{\mathop{\dashleftarrow}\limits^{\vbox
to1.50694pt{\kern-2.0pt\hbox{$\scriptstyle\mathrm{obs}^{s}(C)$}\vss}}}C$ is
active given $\mathrm{\mathbf{{Fa}}}(D^{s})$, as in the proof of (a).
Moreover, the segment $C\mathrel{\mathop{\;\hbox{- - -}\;}\limits^{\vbox
to1.50694pt{\kern-2.0pt\hbox{$\scriptstyle\mathrm{info}^{s}$}\vss}}}U^{s}$ is
active given $\mathrm{\mathbf{{Fa}}}(D^{s})\setminus\\{X^{s}\\}$ by
assumption, and hence given $\mathrm{\mathbf{{Fa}}}(D^{s})$. Since
$D^{\prime}\in\textbf{Anc}(D^{s})$, $q$ is active given
$\mathrm{\mathbf{{Fa}}}(D^{s})$, again violating solubility. Hence again
$N\in\mathrm{\mathbf{Pa}}(D^{s})$. ∎

###  C.2 Trees of systems

First, let us recap the definition of a tree of systems.

See 17 We define the _predecessor system_ and _predecessor path_ of system
$s^{i}$ as
$({\mathrm{predsys}}(s^{i}),{\mathrm{predpath}}(s^{i})):=\mathrm{pred}(s^{i})$.
Moreover, we will sometimes say “An ID graph with tree” to refer to an ID
graph, together with a tree on that ID graph.

######  Terminology.

If $s^{i}={\mathrm{predsys}}(s^{j})$ then we say that $s^{j}$ is a child
system of $s^{i}$. We will similarly apply the standard terminology of trees
and graphs: Ancestor system, descendant system.

######  Lemma 29 (A tree of systems has a tree structure).

Given a tree of systems $T=({\mathcal{S}},\mathrm{pred})$, the pair
$({\mathcal{S}},{\mathrm{predsys}})$ is a tree structure, i.e. it satisfies:

  * •

There is a unique node $s^{\mathrm{root}}$ that has
${\mathrm{predsys}}(s^{\mathrm{root}})=s^{\mathrm{root}}$; and

  * •

For any node $s$, there is some number $n\in\mathbb{N}$ such that
${\mathrm{predsys}}^{n}(s)=s^{\mathrm{root}}$.

###### Proof.

The first condition is satisfied directly by definition of
$s^{\mathrm{root}}$. For the second condition, we only need to show that for
any $s^{i}$, there is a sequence of systems $(s^{1},...,s^{n})$ such that
$s^{1}=s^{\mathrm{root}}$ and $s^{n}=s^{i}$, and
${\mathrm{predsys}}(s^{j})=s^{j-1}$ for all $1<j\leq n$. Assume by
contradiction that there is a system that doesn’t satisfy this, and let
${\mathcal{S}}^{*}$ be the set of all such systems. Then since the restrition
of ${\mathrm{predsys}}$ to ${\mathcal{S}}^{*}$ has no fixed points
($s^{\mathrm{root}}$ is the only fixed point and is not in ${\mathcal{S}}^{*}$
by definition), it must have some sequence $(\tilde{s}^{1},...,\tilde{s}^{k})$
with ${\mathrm{predsys}}(\tilde{s}^{1})=\tilde{s}^{k}$ and
${\mathrm{predsys}}(\tilde{s}^{j})=\tilde{s}^{j-1}$ for all $1<j\leq k$ (i.e.
a cycle). But this would imply that there is at least one pair of systems
$(\tilde{s}^{k},\tilde{s}^{m})$ with
${\mathrm{predsys}}(\tilde{s}^{k})=\tilde{s}^{m}$ but where
$D^{\tilde{s}^{k}}$ is a later decision than $D^{\tilde{s}^{m}}$,
contradicting Lemma 28(b). ∎

######  Lemma 30 (Basic properties of a tree in a soluble ID).

Let $T$ be a tree on a soluble ID graph. Then:

  1. (a)

(Decisions in descendant systems are descendants) If $s^{\prime}$ is a
descendant system of $s$, then $D^{s^{\prime}}$ is a descendant node of
$D^{s}$.

  2. (b)

(Info links to ancestor decisions only from obsnodes) Let $s^{\prime}$ be a
descendant system of $s$. If there is a link from a node $V$ in any path in
$s^{\prime}$ to any node in ${\bm{D}}\cap\textbf{Anc}(D^{s})$ (including
$D^{s}$), then either: i) $V$ is an obsnode in $s^{\prime}$, or ii)
$V=X^{s^{\prime}}=X^{s}$.

###### Proof.

We prove each property in succession:

Sublemma (a) : (Decisions in descendant systems are descendants) If
$s^{\prime}$ is a child system of $s$, then $D^{s^{\prime}}$ is a descendant
of $D^{s}$ by Lemma 28(b) (since it cannot lie in the back section by Lemma
28(a)). By induction the result follows: If any system $s^{\prime}$ with child
system $s^{\prime\prime}$ is a descendant system of $s$, then
$D^{s^{\prime\prime}}\in\textbf{Desc}(D^{s^{\prime}})$, and by the induction
assumption we know $D^{s^{\prime}}\in\textbf{Desc}(D^{s})$, so that
$D^{s^{\prime\prime}}\in\textbf{Desc}(D^{s})$.

Sublemma (b) : (Only info links from obsnodes to ancestor decisions) Since
$\mathrm{info}^{s}$ is active, and each $\mathrm{obs}^{s}(C)$ is a minimal
length path, the only parents of $D^{s^{\prime}}$ within system $s^{\prime}$
(i.e. the only nodes in
$\mathrm{\mathbf{Pa}}(D^{s^{\prime}})\cap{\bm{V}}^{s^{\prime}}$) are
$X^{s^{\prime}}$ and the obsnodes of $s^{\prime}$. Therefore, by Lemma 28(c)
and using Sublemma (a) that $D^{s}$ is an ancestor of $D^{s^{\prime}}$ (since
$s$ is an ancestor of $s^{\prime}$), these are the only nodes in $s’$ that can
be parents of $D^{s}$ or of ancestor decisions of $D^{s}$.

To show the result we show that $X^{s^{\prime}}$ cannot be such a parent when
$X^{s^{\prime}}\neq X^{s}$: Let $s^{*}$ be the closest-to-$s^{\prime}$
ancestor of $s^{\prime}$ in the tree such that $X^{s*}\neq X^{s^{\prime}}$.
Assume such $s^{*}$ exists and either equals $s$ or is a descendant of $s$
since otherwise $X^{s}$ would equal $X^{s^{\prime}}$, which would show the
result. We know that $X^{s^{\prime}}$ is in the system $s^{*}$, since it is
the closest-to-$s^{\prime}$ system such that $X^{s*}\neq X^{s^{\prime}}$, so
that there is a child system of $s^{*}$ whose info node equals
$X^{s^{\prime}}$ and hence must be part of an info-link in $s^{*}$. Hence
$X^{s^{\prime}}$ cannot be a parent of $D^{s^{*}}$ since the only parents
within a system of that system’s decision other than its info node are its
obsnodes, but $X^{s^{\prime}}$ cannot be one of the obsnodes since then
$D^{s^{\prime}}$ would have to be in the back section, which would violate
Lemma 28(a). But we assumed $s^{*}$ is a descendant system of $s$, and hence
$D^{s^{*}}$ is a descendant decision of $D^{s}$ (by Sublemma (a)), which
implies that $D^{s}$ and its ancestor decisions also don’t have
$X^{s^{\prime}}$ as a parent (due to the result shown in the previous
paragraph). ∎

###  C.3 Normal form trees of systems

In this section, we will prove that in a _normal form tree_ , a system can
only get information from its own parents, and obsnodes of descendant systems.

See 18

We will also use the components of the definition of normal form tree
separately.

######  Lemma 31 (Concrete properties of position-in-tree-uniqueness).

A tree $T$ satisfied position-in-tree-uniqueness if and only if every node $N$
that is in some path of some system in $T$ lies in precisely one path $p$ of
one system $s$, with four exceptions:

  * •

If $N$ is a collider node in path $p=\mathrm{info}^{s}$ then it is also the
first node in $\mathrm{obs}^{s}(N)$.

  * •

If $N=U^{s}$ then it lies in both $\mathrm{info}^{s}$ and
$\mathrm{control}^{s}$.

  * •

If $N$ is in an infolink $X^{s^{\prime}}\to D^{s^{\prime}}$ (with
$s^{\prime}\neq s$) on path $p$, then $N$ is also in
$\mathrm{info}^{s^{\prime}}$ (if $N=X^{s^{\prime}}$), or also in
$\mathrm{control}^{s^{\prime}}$ and in $\mathrm{obs}^{s^{\prime}}(C^{i})$ for
each collider $C^{i}$ in $\mathrm{info}^{s^{\prime}}$ (if $N=D^{s^{\prime}}$).
In both cases $N$ may also be the info node for exactly one of its child
systems $s^{1}$, of exactly one child system $s^{2}$ of $s^{1}$, and so on.
Formally, $N=X^{s^{1}}=...=X^{s^{n}}$ where each $s^{i}$ is a child system of
$s^{i-1}$.

###### Proof.

First we show that if a tree $T$ satisfies position-in-tree-uniqueness, then
the result is true. Assume that a tree $T$ does not satisfy the required
property, i.e. there is at least one node $N$ that is in multiple paths, but
without satisfying one of the exceptions. Then by Lemma 37 a different tree
$T^{\prime}$ can be obtained by applying graph transformation 1 (Definition
36), where $N$ is replaced with different nodes in those paths.

Now we show the other direction. Assume that the property holds. Assume $N$ is
part of two paths $p^{1}$ and $p^{2}$. Then one of the three exceptions must
apply. If the first exception applies, then $N$ is a collider, and
$p^{1}=\mathrm{info}^{s}$ and $p^{2}=\mathrm{obs}^{s}(N)$, so that replacing
$N$ with two separate nodes on $p^{1}$ and $p^{2}$ would make that the obspath
of $N$ no longer starts with a collider on $\mathrm{info}^{s}$. If the second
one applies, then replacing $N=U^{s}$ with two nodes would mean that the
control and info path no longer end at the same utility node. If the third
case applies and $N=X^{s^{\prime}}$ of a descendant system $s^{\prime}$ of
$s$, then $p^{1},p^{2}$ equal $\mathrm{info}^{s^{\prime}}$ and
${\mathrm{predpath}}^{s^{\prime}}$. Replacing $N$ with two nodes on the two
paths would break the required property on $\mathrm{pred}$ for $T$ to be a
tree. If the third case applies and $N=D^{s^{\prime}}$, then $p^{1},p^{2}$
equal two of: $\mathrm{control}^{s^{\prime}}$,
${\mathrm{predpath}}^{s^{\prime}}$ or one of $\mathrm{obs}^{s^{\prime}}$. If
one of them equals ${\mathrm{predpath}}^{s^{\prime}}$, then replacing $N$ with
two nodes would again break the required property on $\mathrm{pred}$ for $T$
to be a tree. Otherwise, it would mean that at least one of the
$\mathrm{obs}^{s^{\prime}}$ no longer ends at $D^{s^{\prime}}$, so that
$s^{\prime}$ would no longer be a system. ∎

######  Definition 32 (Base system and path of a node; chain of systems).

If $T$ is a normal form tree of systems, then we refer to the system $s$ and
the path $p$ from Lemma 31 (including in the exceptions) respectively as the
_base system_ and _base path_ of node $N$.

Note that this implies that a utility node $U^{s}$ has no base path. We refer
to the sequence of systems of which a node $N$ is the info node (in the third
exception) as the _chain of systems_ of $N$ (which is possibly empty).

######  Definition 33.

A within-tree-$T$ path for a normal form tree $T$ on an ID graph is a path
that contains only within-system links for the systems in $T$.

Note that we define the notion of within-tree path only for normal form trees,
since it is not sensible for trees that don’t satisfy position-in-tree-
uniqueness: If a node $N$ occurs in two unrelated systems, then a sequence of
within-tree links may jump between nodes in the tree that are not linked.

###  C.4 Properties of normal form trees of systems

In this subsection, we will prove Lemma 20 — that the only information that
$D^{s}$ receives that is relevant within system $s$ is information that it
receives from its parents and obsnodes of descendant systems. To reach this
result, we first need to state some more fundamental properties of normal form
trees.

######  Lemma 34 (Properties of soluble ID graphs with trees that have
position-in-tree-uniqueness).

Any soluble ID graph ${\mathcal{G}}$ with a tree that has position-in-tree-
uniqueness has the following properties.

  1. (a)

(A within-tree path corresponds to a walk with node repetition in the tree of
systems) For any within-tree path $p\colon N^{1}\;\hbox{- - -}\;N^{n}$, there
is a walk with node repetition in the tree of systems
$p_{\mathrm{systems}}\colon s^{1}\;\hbox{- - -}\;s^{m}$, with $m\geq n$,
together with a walk with node repetitions $p_{\mathrm{walk}}\colon
V^{1}\;\hbox{- - -}\;V^{m}$ in ${\mathcal{G}}$ such that each $V^{i}$ is in
some path in system $s^{i}$ and if we remove from $p_{\mathrm{walk}}$ every
node that equals its predecessor we obtain $p$.666Hence in particular, there
can only be a within-tree path between a node $N^{1}$ in system $s$ and node
$N^{n}$ in system $s^{\prime}$ if there is a path between $s$ and $s’$ in the
tree of systems.

  2. (b)

(Within-tree links between systems only via $X^{s}$, $D^{s}$) If
$N-N^{\prime}$ is a within-tree link, where $N$ and $N^{\prime}$ are in nodes
in paths of systems $s$ and $s^{\prime}$ respectively, and $s\neq s^{\prime}$,
then $N-N^{\prime}$ must contain $X^{s}$ or $D^{s}$.

###### Proof.

We prove each sublemma in succession:

Sublemma (a) : (Within-tree paths correspond to walks with node repetition in
the tree of systems). We construct this walk with node repetition
$p_{\mathrm{systems}}$ recursively as follows, by iterating from $N^{1}$ to
$N^{n}$, using the fact that each link in $p$ is within-system for some system
(see definition of within-tree paths). For the base case, let $s^{1}$ equal
any of the systems that $N^{1}$ is a node in. Let $s^{k+1}$ and $V^{k+1}$ be
defined mutually based on $s^{k}$ and $V^{k}$: If the node $N’$ that is next
to $V^{k}$ on $p$ is also in system $s^{k}$, then let $s^{k+1}=s^{k}$ and let
$V^{k+1}=N’$, in which case the desired result follows that $s^{k}=s^{k+1}$
and that $V^{k}-V^{k+1}$ is a link in $p$. If it is not also in system
$s^{k}$, then by definition of within-tree path, $N’$ and $V^{k}$ are both in
some system $s’\neq s^{k}$, where $s’$ is part of the chain of systems of
$V^{k}$. Then let $s^{k+1}$ be the next system from $s^{k}$ in that chain, and
let $V^{k+1}=V^{k}$, from which the desired result follows that there is a
link $s^{k}-s^{k+1}$ and $V^{k+1}=V^{k}$. Together with the base case this
shows the result by induction.

Sublemma (b) : (Within-tree links between systems only via $X^{s}$, $D^{s}$).
Take any link $A-B$ with $A$ a part of $s$ and $B$ a part of some other system
$s’$. Then we must either have that $A$ is in both $s$ and in
${\mathrm{predsys}}(s)$, or that $B$ is in both $s$ and
${\mathrm{predsys}}(s)$. Whichever it is, by the position-in-tree-uniqueness
assumption, this can only be if that node equals $X^{s}$ or $D^{s}$, since any
node that is in multiple systems $s’$ must equal either $X^{s^{\prime}}$ or
$D^{s^{\prime}}$ for all systems $s^{\prime}$ except its base system. ∎

We now show graphically that in an ID graph with normal form tree a decision
$D^{s}$ cannot get relevant information about system $s$ from any paths via
nodes outside system $s$ and descendant systems. This will imply the
following:

See 20 color=blue!30]Ryan: graph knowledge lemma numbered as 43 here, but as
20 in the main paper

inline, color=green!30]Chris: I should try to simplify the proof below
further.

###### Proof.

Take any path from a node in $\bf{Back}^{s}$ to a node in
$\mathrm{\mathbf{Pa}}^{-s}\setminus\bf{{ObsDesc}}^{s}$. We will show that it
is inactive given $\mathrm{\mathbf{Pa}}^{s}\cup\bf{{ObsDesc}}^{s}$.

We first assume that the path starts from a node in the back section, so that
it is an ancestor of $D^{s}$. First note that since the decision of $s$ and
those of its descendant systems cannot be ancestors of $D^{s}$ (Lemma 30(a)),
this implies that if the path contains any of these it is necessarily inactive
given $\mathrm{\mathbf{Pa}}^{s}\cup\bf{{ObsDesc}}^{s}$, since active paths
between ancestors given ancestors contain only ancestors (Lemma 22).

So assume that the path does not contain the decision of $s$ (i.e. $D^{s}$)
nor those of its descendant systems. We will consider the initial within-tree
segment of the path.

By Lemma 34(a), this initial within-tree path corresponds to a walk with node
repetition in the tree of systems, and since the latter has a tree structure
by construction, this initial within-tree path either has to exit system $s$
via a node in its predecessor system, or stay within $s$ itself and its
descendant systems. The former can only happen via one of the links via
$X^{s}$ and $D^{s}$ by Lemma 34(b).

We first show that in this case, the path is blocked given
$\mathrm{\mathbf{Pa}}^{s}\cup\bf{{ObsDesc}}^{s}$. We already assumed that the
path doesn’t contain $D^{s}$, so assume that the link contains $X^{s}$. Since
$\mathrm{info}^{s}$ is front-door by the appropriateness assumption of normal
form tree, $X^{s}$ blocks the path, since
$X^{s}\in\mathrm{\mathbf{Pa}}^{s}\cup\bf{{ObsDesc}}^{s}$.

So we now assume that the initial within-tree segment does not exit into the
predecessor of $s$, and hence is contained within system $s$ and its
descendant systems. Consider the first link of the path that is out-of-tree.
At the start of this proof we assumed that the path doesn’t contain the
decisions $D^{s}$, nor $D^{s^{\prime}}$ of any of its ancestors $s^{\prime}$.
Hence by Lemma 28(a), the only decision that the initial within-tree segment
could contain is $X^{s}$ if that is a decision, but we just assumed that the
path doesn’t contain this.

So we assume now that the initial within-tree segment doesn’t contain any
decisions, so that the first out-of-tree link would have to be of the form
$N\to D$ for some decision $D$ (by the no redundant links assumption of normal
form trees, and using the fact that $N$ is inside the tree). $N$ can be either
in system $s$ or in a descendant system, and can be either an observation node
or some other node. Consider two exhaustive cases:

  1. (a)

Assume $N$ is neither an obsnode in $s$ nor in a descendant system $s’$. Then
$D$ cannot be an ancestor of $D^{s}$, since the only info links from nodes in
$s$ or its descendant systems to $D^{s}$ or to ancestor decisions are from
obsnodes by Lemma 30(b), and hence the path cannot be active (active paths
between ancestors given ancestors contain only ancestors by Lemma 22).

  2. (b)

Assume $N$ is an observation node of $s$ or of some descendant system of $s$.
Then $N$ blocks the path, since it is in
$\mathrm{\mathbf{Pa}}^{s}\cup\bf{{ObsDesc}}^{s}$.

This shows the result. ∎

###  C.5 Obtaining a (homomorphically) transformed ID graph with a normal form
tree

We will prove that if an infolink is in the minimal $d$-reduction, then there
exists a transformed ID graph with a normal form tree and homomorphism to the
original. We will show that a series of three homomorphic transformations
yields a graph ${\mathcal{G}}^{3}$ with tree $T^{3}$ is in normal form, and
root infolink corresponding to that of $T$. Since each transformation is
homomorphic, their composition is a homomorphism from ${\mathcal{G}}^{3}$ to
${\mathcal{G}}$. The transformations are:

  * •

First, we _obtain a full tree_ on ${\mathcal{G}}$.

  * •

_Transformation 1_ obtains $({\mathcal{G}}^{1},T^{1})$, where $T^{1}$ has
property (a). This splits nodes other than $X^{s}$ and $D^{s}$, to ensure that
they do not appear in multiple positions in the tree.

  * •

_Transformation 2_ obtains $({\mathcal{G}}^{2},T^{2})$, where $T^{2}$ has the
properties (a, b). This is done by modifying any backdoor infopath to be
front-door.

  * •

_Transformation 3_ obtains $({\mathcal{G}}^{3},T^{3})$, where $T^{3}$ has the
properties (a, b, c). This consists of removing edges other than the within-
tree links.

We will not use the intermediate graphs ${\mathcal{G}}^{1},{\mathcal{G}}^{2}$,
except to define ${\mathcal{G}}^{3}$.

#### Obtain a full tree on ${\mathcal{G}}$

We will construct an arbitrary full tree using only infolinks in the minimal
$d$-reduction.

######  Lemma 35 (Existence of full tree).

Let ${\mathcal{G}}$ be a soluble ID graph whose minimal $d$-reduction
${\mathcal{G}}^{*}$ contains the link $X\to D$. Then there exists a full tree
of systems $T$ on ${\mathcal{G}}^{*}$ with root system on $X\to D$.

###### Proof.

We construct a tree iteratively. Since $X\to D$ is in ${\mathcal{G}}^{*}$,
there exists a directed path $p$ from $X$ to some $U\in\textbf{Desc}(D)$
active given $\mathrm{\mathbf{{Fa}}}(D^{i})\setminus\\{X\\}$. Let the infopath
be any such $p$, let the control path be any directed path from $D$ to $U$ and
let the obspaths be the shortest directed paths to $D$ from each collider in
$p$. Then, choose any infolink $X^{\prime}\to D^{\prime}$ in a path $q$ of any
system $s$ that lacks an associated system. Since $X^{\prime}\to D^{\prime}$
is in ${\mathcal{G}}^{*}$, we can choose paths in the same fashion and repeat
this procedure until every infolink that is traversed has its own system. This
process halts, because a path in a system $s$ (whose decision is $D^{s}$) can
only contain an infolink $X^{\prime}\to D^{\prime}$ if
$D^{\prime}\in\textbf{Desc}(D^{s})$. This is because: i)
$\mathrm{control}^{s}$ is directed, ii) $\mathrm{info}^{s}$ only contains
infolinks in $\textbf{Desc}(D^{s})$ (Lemma 28(b)), and iii) $\mathrm{obs}^{s}$
cannot contain any infolinks. So a full tree has been constructed. ∎

#### Transformation 1 (split): ensuring position-in-tree-uniqueness

For Transformation 1, a node $N$ is copied into a different node (of unchanged
type) for each position that $N$ occupies in the tree. More precisely, we
replace each node $N$ that is in path $p$ in system $s$, with the new node
$\mathrm{New}(N,s,p)$. This function is defined such that each node
$\mathrm{New}(N,s,p)$ has a unique position in the tree, which basically means
that it is only a part of path $p$ in system $s$, except that we need to make
sure that certain nodes are in multiple paths (e.g. a collider node $C$ in a
path $\mathrm{info}^{s}$ must be in both $\mathrm{info}^{s}$ and in
$\mathrm{obs}^{s}(C)$). We don’t delete the original occurrences of each node
$N$, so that the original graph is a subgraph of the transformed graph.

color=blue!30]Ryan: Seems we should be able to remove the name $Nsplit$ and
just substitute in New()

######  Definition 36 (Graph transformation 1).

Let $T^{0}=({\mathcal{S}}^{0},\mathrm{pred}^{0})$ be a tree on an ID graph
${\mathcal{G}}^{0}=({\bm{V}}^{0},E^{0})$. Then define
$\mathrm{transf}^{1}({\mathcal{G}}^{0},T^{0})=({\mathcal{G}}^{1},T^{1})$ where
${\mathcal{G}}^{1}=({\bm{V}}^{1},E^{1})$, together with homomorphism
$h^{0\leftarrow 1}\colon{\bm{V}}^{1}\to{\bm{V}}^{0}$ as

  * •

Obtain any ${\mathcal{G}}^{1}$ and $h^{0\leftarrow 1}$ from Lemma 13, by
adding for each node $N$ a set of copies

$\mathrm{Copies}(N)=\\{N_{\mathrm{split}}\mid\textnormal{$\exists
s\in{\mathcal{S}}^{0},\exists$ path $p\in s$ such that $N\in p$, and
$N_{\mathrm{split}}=\mathrm{New}(N,s,p)$ }\\},$

where by tree recursion on $T^{0}$ (which has tree structure: Lemma 29) we
define $\mathrm{New}(N,s,p)$

$=\begin{cases}\mathrm{New}(N,{\mathrm{predsys}}(s),{\mathrm{predpath}}(s))&\textnormal{if
$s\neq\mathrm{root}(T^{0})$ and $N\in\\{X^{s},D^{s}\\}$}\\\
(N,s,\\{\mathrm{info}^{s},\mathrm{control}^{s}\\})&\textnormal{if
$N=U^{s}$}\\\ (N,s,\mathrm{info}^{s})&\textnormal{if
$p=\mathrm{obs}^{s}(N)$}\\\ N&\textnormal{if $s=\mathrm{root}(T^{0})$ and
$N\in\\{X^{s},D^{s}$\\}}\\\ (N,s,p)\quad&\textnormal{otherwise }\end{cases}.$

  * •

$T^{1}$ is the tree $({\mathcal{S}}^{1},\mathrm{pred}^{1})$, where the system
$s_{\mathrm{split}}^{i}\in{\mathcal{S}}^{1}$ is defined as the system
$(\mathrm{split}(s^{i},\mathrm{info}^{T,s^{i}}),\mathrm{split}(s,\mathrm{control}^{T,s^{i}}),\mathrm{split}(s,\mathrm{obs}^{T,s}))$
for $s^{i}\in{\mathcal{S}}^{T}$, where
$\mathrm{split}(s^{i},p)^{j}=\mathrm{New}(p^{j},s^{i},p),$ and where $p^{j}$
denotes the $j$’th node of a path $p$. (this indeed gives a path, since there
is an edge between $\mathrm{split}(s^{i},p)^{j}=\mathrm{New}(p^{j},s^{i},p)$
and $\mathrm{split}(s^{i},p)^{j+1}=\mathrm{New}(p^{j+1},s^{i},p)$ because
there is an edge between $p^{j}$ and $p^{j+1}$ and by definition of $E^{1}$
using $p^{j}\neq p^{j+1}$). Moreover $\mathrm{pred}^{1}$ is the same as
$\mathrm{pred}^{0}$ except that each $s$ in $T^{0}$ is replaced with its
transformed $s_{\mathrm{split}}$.

######  Lemma 37 (Transformation 1 preserves tree).

Let $({\mathcal{G}}^{1},T^{1})=\mathrm{transf}^{1}({\mathcal{G}}^{0},T^{0})$.
If $T^{0}$ is a tree of systems on ${\mathcal{G}}^{0}$ with root link $X\to
D$, then $T^{1}$ is a tree of systems on ${\mathcal{G}}^{1}$ with root link
$X^{\prime}\to D^{\prime}$ with $h^{0\leftarrow 1}(X^{\prime})=X$ and
$h^{0\leftarrow 1}(D^{\prime})=D$.

###### Proof.

First we show that $T^{1}$ satisfies the three conditions of a tree of
systems: (1) We will show below that each indexed element of
${\mathcal{S}}^{1}$ is indeed a system. (2) since
$\mathrm{pred}^{0}=\mathrm{pred}^{1}$, and since $T^{0}$ is a tree of systems,
the required condition on $\mathrm{pred}^{1}$ is satisfied. (3) We show that
each system’s infolink is an infolink on its predecessor path: The nodes
$X^{s_{\mathrm{split}}}$ and $D^{s_{\mathrm{split}}}$ in ${\mathcal{G}}^{1}$
equal $\mathrm{New}(X^{s},s,\mathrm{info}^{s})$ and
$\mathrm{New}(D^{s},s,\mathrm{control}^{s})$ for $X^{s}$ and $D^{s}$ in
${\mathcal{G}}^{0}$. By definition of $\mathrm{New}(N,s,p)$, this is indeed an
infolink on ${\mathrm{predpath}}(s)$.

It remains to be shown that $s_{\mathrm{split}}$ indeed is a system for each
$s\in{\mathcal{S}}^{0}$:

Step (1) : We show that $\mathrm{control}^{s_{\mathrm{split}}}$ is a directed
path to a utility node. $\mathrm{control}^{s_{\mathrm{split}}}$ is a path from
$\mathrm{New}(D^{s},{s},\mathrm{control}^{s})$ to
$\mathrm{New}(U^{s},{s},\mathrm{control}^{s})$ and by definition of $E^{1}$
this is indeed a directed path (since $\mathrm{control}^{s}$ is directed in
$T$);

Step (2) : We show that $\mathrm{info}^{s_{\mathrm{split}}}$ is an active path
to the same utility node. Firstly, $\mathrm{info}^{s_{\mathrm{split}}}$ is a
path from $\mathrm{New}(X^{s},{s},\mathrm{info}^{s})$ to
$\mathrm{New}(U^{s},{s},\mathrm{info}^{s})$, and since
$\mathrm{New}(U^{s},{s},\mathrm{info}^{s})=\mathrm{New}(U^{s},{s},\mathrm{control}^{s})$
by definition of $\mathrm{New}$ for utility nodes, therefore the control and
info path indeed end at the same utility node. Secondly, it follows easily
from the definition of $E^{1}$, that a node
$\mathrm{New}(N,s,\mathrm{info}^{s})$ blocks the path if and only if $N$
blocks $\mathrm{info}^{s}$, and the latter is active by assumption, so that
$\mathrm{info}^{s_{\mathrm{split}}}$ is active as well;

Step (3) : Finally, we show that the $\mathrm{obs}^{s_{\mathrm{split}}}$ are
minimal length paths from collider nodes on
$\mathrm{info}^{s_{\mathrm{split}}}$ to $D^{s_{\mathrm{split}}}$. Firstly,
$\mathrm{obs}^{s_{\mathrm{split}}}(\mathrm{New}(C,s,\mathrm{info}^{s}))$ is a
path from $\mathrm{New}(C,s,\mathrm{obs}^{s}(C))$ to
$\mathrm{New}(D^{s},s,\mathrm{obs}^{s}(C))$. By definition of $L$, the former
equals $(C,(s,\mathrm{info}^{s}))$ and the latter equals
$\mathrm{New}(D^{s},{\mathrm{predsys}}(s),{\mathrm{predpath}}(s))$ if
$s\neq\mathrm{root}(T)$ and $(D^{s},(s,\mathrm{control}^{s}))$ if
$s=\mathrm{root}(T)$, which in both cases equals
$\mathrm{New}(D^{s},s,\mathrm{control}^{s})=D^{s_{\mathrm{split}}}$, so that
this is indeed a valid obspath. To show that it’s minimal length, assume by
contradiction that there is a shorter path and denote its $j$’th node by
$(N^{j},(s^{j},p^{j}))$, so that there are links
$(N^{j},s^{j},p^{j})\to(N^{j+1},s^{j+1},p^{j+1})$. Then by definition of
$E^{1}$, ${\mathcal{G}}^{0}$ contains an edge $N^{j}\to N^{j+1}$, and hence
this path in ${\mathcal{G}}^{0}$ must also be shorter than
$\mathrm{obs}^{s}(C)$, contradicting the assumption that $s$ is a system.

This shows that $T^{1}$ is a tree of systems. Finally, The root infolink of
$T^{1}$ is $X\to D$ by definition of $\mathrm{New}$, and $h^{0\leftarrow
1}(X)=X$ and $h^{0\leftarrow 1}(D)=D$, so it is mapped to the root info link
of $T$. ∎

######  Lemma 38 (Transformation 1 ensures position-in-tree-uniqueness).

Let $({\mathcal{G}}^{0},T^{0})$ be any soluble ID graph with complete tree.
Then $({\mathcal{G}}^{1},T^{1})=\mathrm{transf}^{1}({\mathcal{G}}^{0},T^{0})$
is an ID graph with complete tree that satisfies (a) position-in-tree-
uniqueness.

###### Proof.

We first show that the split preserves fullness, then that it ensures
position-in-tree-uniqueness.

(i) (full tree). color=green!30]Chris: my sense is this subproof can be
simplified, it seems very long for what it’s doing. Basically it’s a ”by
definition” kind of proof. We show that if ${T^{0}}$ is a full tree, then so
is $T^{1}$: Let $(X,s^{*,1},p^{*,1})\to(D,s^{*,2},p^{*,2})$ be an infolink in
${\mathcal{G}}^{1}$ on the path $p_{\mathrm{split}}$ in system
$s_{\mathrm{split}}$. We need to show that there is a system
$s_{\mathrm{split}}^{\prime}$ such that
$X^{s_{\mathrm{split}}^{\prime}}=(X,s^{*,1},p^{*,1})$ and
$D^{s_{\mathrm{split}}^{\prime}}=(D,s^{*,2},p^{*,2})$.

Note that this link in $p_{\mathrm{split}}$ implies that there is a
corresponding link in the original path $p$. By the definition of $T^{1}$, the
split path $p_{\mathrm{split}}$ was constructed from the original path $p$
(that has the same path type in system $s$ as $p_{\mathrm{split}}$ does in
$s_{\mathrm{split}}$) where if $(X,s^{*,1},p^{*,1})$ is the $i$’th node on
$p_{\mathrm{split}}$, it corresponds to the $i$’th node on $p$ by
$(X,s^{*,1},p^{*,1})=p_{\mathrm{split}}^{i}=\mathrm{New}(p^{i},s,p)$ and
similarly
$(D,s^{*,2},p^{*,2})=p_{\mathrm{split}}^{i+1}=\mathrm{New}(p^{i+1},s,p)$.
Hence $X=p^{i}$ and $D=p^{i+1}$, so that $X\to D$ is also an infolink on $p$
in $s$ in ${T^{0}}$. And since by assumption ${T^{0}}$ is full, there is a
system $s^{\prime}$ with $\mathrm{pred}^{0}(s^{\prime})=(s,p)$ such that
$X^{s^{\prime}}\to D^{s^{\prime}}$ equals $X\to D$. This implies also that the
desired system in $T^{1}$ exists: Since by definition $\mathrm{pred}^{1}$ is
equivalent to $\mathrm{pred}^{0}$ it implies that
$\mathrm{pred}^{1}(s_{\mathrm{split}}^{\prime})=(s_{\mathrm{split}},p_{\mathrm{split}})$,
and by construction of $s_{\mathrm{split}}$, $X^{s_{\mathrm{split}}^{\prime}}$
and $D^{s_{\mathrm{split}}^{\prime}}$ equal
$\mathrm{New}(X^{s^{\prime}},s^{\prime},\mathrm{info}^{s^{\prime}})=\mathrm{New}(X,s^{\prime},\mathrm{info}^{s^{\prime}})$
and
$\mathrm{New}(D^{s^{\prime}},s^{\prime},\mathrm{control}^{s^{\prime}})=\mathrm{New}(D,s^{\prime},\mathrm{control}^{s^{\prime}})$
respectively, which by definition of $\mathrm{New}(X,s,p)$ implies that they
equal $\mathrm{New}(X,s,p)$ and $\mathrm{New}(D,s,p)$ respectively, showing
the result.

(ii) (position-in-tree-uniqueness). Any node $N_{\mathrm{split}}$ in the tree
either equals one of $X,D$, or is a node of the form
$N_{\mathrm{split}}=(N,(s^{*},p^{*}))$. In the former case, let
$s^{*}=\mathrm{root}(T^{1})$ and let $p^{*}=\mathrm{info}^{\mathrm{root}}$ if
the node equals $X$ and $p^{*}=\mathrm{control}^{\mathrm{root}}$ if it equals
$D$. We will show that $s_{\mathrm{split}}^{*}$ and $p_{\mathrm{split}}^{*}$
are the node’s base system and base path respectively, by taking any path
$p_{\mathrm{split}}$ in any system $s_{\mathrm{split}}$ such that the node is
on $p_{\mathrm{split}}$, and showing that for the original path $p$ and system
$s$, either $p=p^{*}$ and $s=s^{*}$ or that one of the exceptions applies.

We will show this by induction on the tree: Assume that it holds for any
$p_{\mathrm{split}}^{\prime}$ in system $s_{\mathrm{split}}^{\prime}$ that is
an ancestor system of $s_{\mathrm{split}}$. Note that if
$N_{\mathrm{split}}=(N,(s^{*},p^{*}))$ is on path $p_{\mathrm{split}}$ in
system $s_{\mathrm{split}}$, then $N_{\mathrm{split}}=\mathrm{New}(N,s,p)$, so
consider two cases of the definition of $\mathrm{New}(N,s,p)$ separately:

Case (1) : (Assume $s\neq\mathrm{root}(T^{0})$ and $N\in\\{X^{s},D^{s}\\}$.)
Then
$N_{\mathrm{split}}=(N,s^{*},p^{*})=\mathrm{New}(N,s,p)=\mathrm{New}(N,{\mathrm{predsys}}(s),{\mathrm{predpath}}(s))$,
and we will use the induction assumption on
${\mathrm{predsys}}(s_{\mathrm{split}}),{\mathrm{predpath}}(s_{\mathrm{split}})$:
We know that $(N,s^{*},p^{*})$ lies on
${\mathrm{predpath}}(s_{\mathrm{split}})$ (since $T^{1}$ is a tree), and by
the induction assumption, either
${\mathrm{predsys}}(s_{\mathrm{split}})=s_{\mathrm{split}}^{*}$ and
${\mathrm{predpath}}(s_{\mathrm{split}})=p_{\mathrm{split}}^{*}$ (in which
case the third or fourth exception applies to $s_{\mathrm{split}}$ and
$p_{\mathrm{split}}$, showing the result), or one of the exceptions applies.
Since $X^{s}$ and $D^{s}$ aren’t utility nodes, and can’t be colliders on the
info path of ${\mathrm{predsys}}(s)$ (Lemma 28(a)), and ${\mathrm{predpath}}$
always is either an info or control path, only the third exception can apply
to ${\mathrm{predsys}}(s_{\mathrm{split}})$ and
${\mathrm{predpath}}(s_{\mathrm{split}})$, i.e. $(N,s^{*},p^{*})$ is the info
or decision node of ${\mathrm{predsys}}(s_{\mathrm{split}})$, where the latter
is a child system of $s_{\mathrm{split}}^{*}$ or it is the info node of an
unbroken chain of descendant systems of $s_{\mathrm{split}}^{*}$. In both
cases, $N$ cannot equal $D^{s}$, since the decision node of a system
(${\mathrm{predsys}}(s_{\mathrm{split}})$ in this case) is neither the
decision of an info link on its info path nor on its control path and hence
cannot equal the decision node of one of its child systems
($s_{\mathrm{split}}$ in this case), and hence $(N,s^{*},p^{*})$ must be the
info node of $s_{\mathrm{split}}$ and an unbroken chain of predecessor systems
between $s_{\mathrm{split}}$ and $s_{\mathrm{split}}^{*}$, so that it
satisfies the third exception.

Case (2) : (Assume $s=\mathrm{root}(T^{0})$ or $X\notin\\{X^{s},D^{s}\\}$.)
Then if $s=\mathrm{root}(T^{0})$ and $N\in\\{X^{s},D^{s}\\}$, then
$N_{\mathrm{split}}=N$, and the result follows easily (where
$p_{\mathrm{split}}$ may be an obs path in which case the final exception
applies). So assume otherwise, so that
$N_{\mathrm{split}}=(N,s^{*},p^{*})=\mathrm{New}(N,s,p)$, where $s^{*}=s$, and
we can easily match each of the cases of $\mathrm{New}(N,s,p)$ to the
exceptions, showing the result. ∎

#### Transformation 2 (split): ensuring no backdoor info-paths

In the second transformation, we turn any backdoor-info paths into frontdoor
infopaths.

######  Definition 39 (Transformation 2).

Let ${\mathcal{G}}^{1}=({\bm{V}}^{1},E^{1})$ be an ID graph with tree
$T^{1}=({\mathcal{S}}^{1},\mathrm{pred}^{1})$. Then
$\mathrm{transf}^{2}({\mathcal{G}}^{1},T^{1})=({\mathcal{G}}^{2},T^{2})$,
where ${\mathcal{G}}^{2}=({\bm{V}}^{2},E^{2})$ and $h^{1\leftarrow
2}\colon{\bm{V}}^{2}\to{\bm{V}}^{1}$ are defined as follows:

  * •

Obtain any ${\mathcal{G}}^{2}$ and $h^{1\leftarrow 2}$ from Lemma 13, by
adding for each node $N$ a set of copies

$\mathrm{Copies}(N)=\begin{cases}\\{(N,``\mathrm{copy}",s)\\}&\textnormal{if
$N=X^{s}$ for some backdoor-info system $s$ in ${T^{1}}$}\\\
\emptyset\quad&\textnormal{otherwise }\end{cases}$

  * •

$T^{2}$ is the tree $({\mathcal{S}}^{2},\mathrm{pred}^{2})$, where each system
$s_{\mathrm{split}}\in{\mathcal{S}}^{2}$ is obtained from $s$ by replacing the
first link $X^{s}\leftarrow N$ in $\mathrm{info}^{s}$ with the links
$X^{s}\to(X^{s},``\mathrm{copy}")\leftarrow N$, and extending
$\mathrm{obs}^{s}$ with $\mathrm{obs}^{s}((X^{s},``\mathrm{copy}"))$ to be the
path consisting of the single link $(X^{s},``\mathrm{copy}",s)\to D^{s}$.
Moreover $\mathrm{pred}^{2}$ is the same as $\mathrm{pred}^{1}$ except that
each $s$ in $T^{1}$ is replaced with its transformed $s_{\mathrm{split}}$.

######  Lemma 40 (Transformation 2 preserves tree).

Let $({\mathcal{G}}^{2},T^{2})=\mathrm{transf}^{2}({\mathcal{G}}^{1},T^{1})$.
If $T^{1}$ is a tree of systems on ${\mathcal{G}}^{1}$ with root link $X\to
D$, then $T^{2}$ is a tree of systems on ${\mathcal{G}}^{2}$ with root link
$X^{\prime}\to D^{\prime}$ with $h^{1\leftarrow 2}(X^{\prime})=X$ and
$h^{1\leftarrow 2}(D^{\prime})=D$.

###### Proof.

First we show that $T^{2}$ satisfies the three conditions of a tree of
systems: (1) We will show below that each indexed element of
${\mathcal{S}}^{2}$ is indeed a system. (2) since $\mathrm{pred}^{1}$ is
equivalent to $\mathrm{pred}^{2}$, and since ${T^{1}}$ is a tree of systems,
the required conditions on $\mathrm{pred}^{2}$ are satisfied. (3) For any
system $s$, $X^{s_{\mathrm{split}}}=X^{s}$ and $D^{s_{\mathrm{split}}}=D^{s}$
(i.e. they are unchanged under the split), and the front-section of
${\mathrm{predsys}}(s_{\mathrm{split}})$ is identical to that of
${\mathrm{predsys}}(s)$, and since infolinks can only be in the front section
(by Lemma 28(a)), so that the fact that ${T^{1}}$ is a tree of systems and
hence has $X^{s}\to D^{s}$ as an infolink on ${\mathrm{predpath}}(s)$, this
implies that $X^{s_{\mathrm{split}}}\to D^{s_{\mathrm{split}}}$ is an infolink
on ${\mathrm{predpath}}(s_{\mathrm{split}})$.

It remains to be shown that $s_{\mathrm{split}}\in{\mathcal{S}}^{2}$ indeed is
a system for each $s\in{\mathcal{S}}^{1}$:

Step (1) : $\mathrm{control}^{s_{\mathrm{split}}}$ is a directed path to a
utility node. $\mathrm{control}^{s_{\mathrm{split}}}$ is identical to
$\mathrm{control}^{s}$.

Step (2) : $\mathrm{info}^{s_{\mathrm{split}}}$ is an active path to the same
utility node. Since $\mathrm{info}^{s}$ is active given
$\mathrm{\mathbf{Pa}}(D^{s})$ by assumption, and
$\mathrm{info}^{s_{\mathrm{split}}}$ is identical to $\mathrm{info}^{s}$
except that if $\mathrm{info}^{s}$ is backdoor from $X^{s}$ then the first
link $X^{s}\leftarrow N$ is replaced by
$X^{s}\to(X^{s},``\mathrm{copy}")\leftarrow N$, hence by definition of
$E^{2}$, a node on $\mathrm{info}^{s_{\mathrm{split}}}$ is a parent of
$D^{s_{\mathrm{split}}}$ in ${\mathcal{G}}^{2}$ iff it is a parent of $D^{s}$
in ${\mathcal{G}}^{1}$ or if it equals $(X^{s},``\mathrm{copy}")$. Therefore,
$(X^{s},``\mathrm{copy}")$ doesn’t block because it’s a collider, and the
other nodes don’t block $\mathrm{info}^{s_{\mathrm{split}}}$ because by
assumption they didn’t block $\mathrm{info}^{s}$.

Step (3) : Finally, $\mathrm{obs}^{s_{\mathrm{split}}}$ are minimal length
paths from collider nodes on $\mathrm{info}^{s_{\mathrm{split}}}$ to
$D^{s_{\mathrm{split}}}$: For
$\mathrm{obs}^{s}_{\mathrm{split}}((X^{s},``\mathrm{copy}"))$, it is a single
link to $D^{s}$ and hence trivially minimal-length, so consider the other
colliders $C$ which are also on $\mathrm{info}^{s}$. Firstly, each
$\mathrm{obs}^{s_{\mathrm{split}}}(C)$ is identical to $\mathrm{obs}^{s}(C)$.
Secondly, the split doesn’t introduce shorter-length such paths, since any
path from $C$ to $D^{s_{\mathrm{split}}}$ via some newly added
$(X,``\mathrm{copy}")$ would correspond to a path via $X^{s}$ in
${\mathcal{G}}^{1}$ that is at least as short, using the fact that this ID
transformation is homomorphic and hence doesn’t introduce extra edges.

This shows that $T^{2}$ is a tree of systems. Finally, we show that the root
infolinks are equivalent: The if $s^{i}$ is the root system of ${T^{1}}$ then
$s_{\mathrm{split}}^{i}$ is the root system of $T^{2}$, and since the infolink
of each system in $T^{2}$ equals that of the corresponding system in ${T^{1}}$
by definition, we have $h^{1\leftarrow
2}(X^{s_{\mathrm{split}}^{\mathrm{root}}})=X^{s^{\mathrm{root}}}$ and
$h^{1\leftarrow
2}(D^{s_{\mathrm{split}}^{\mathrm{root}}})=D^{s^{\mathrm{root}}}$, showing the
result. ∎

######  Lemma 41 (Transformation 2 ensures appropriateness).

Let $({\mathcal{G}}^{1},T^{1})$ be any soluble ID graph with complete tree
satisfying property (a) position-in-tree-uniqueness. Then
$({\mathcal{G}}^{2},T^{2})=\mathrm{transf}^{2}({\mathcal{G}}^{1},T^{1})$ is an
ID graph with complete tree satisfying (a) and also (b) appropriateness.

###### Proof.

We first show that the split preserves fullness, position-in-tree-uniqueness
and no overlapping $X^{s}$, $Q^{\mathrm{pred}}$, then we show that it ensures
appropriateness:

(i) (full tree). We show that if ${T^{1}}$ is a full tree, so is $T^{2}$: For
any link $X\to D$ on a path in a system $s_{\mathrm{split}}$, that infolink
was also on the same path in system $s_{\mathrm{split}}$, since
$s_{\mathrm{split}}$ is identical to $s$ except for the first link on
$\mathrm{info}^{s_{\mathrm{split}}}$ but that link is in the back section and
hence cannot contain $X$ or $D$ by Lemma 28(a). Hence there is a system
$s^{\prime}$ in ${T^{1}}$ with $X\to D$ as its infolink. Hence since by
Definition 39 the infolink of $s_{\mathrm{split}}^{\prime}$ is the same as
that of $s^{\prime}$, there is a system in $T^{2}$ that has $X\to D$ as its
infolink, namely $s_{\mathrm{split}}^{\prime}$.

(ii) (a-position-in-tree-uniqueness). We show that if ${T^{1}}$ satisfies
position-in-tree-uniqueness, then so does $T^{2}$. We state the argument
informally: The nodes in $T^{2}$ are identical to those in ${T^{1}}$, except
for sometimes a split of $X^{s}$. In that case, $(X^{s},``\mathrm{copy}")$ is
a new node that only appears in system $s_{\mathrm{split}}$. Moreover, any
other nodes are precisely in system $s_{\mathrm{split}}$ if they were in
system $s$, so since the node satisfied the required property in ${T^{1}}$, it
also does so in $T^{2}$.

(iii) (b-no-backdoor-infopaths) Take any system
$s_{\mathrm{split}}\in{\mathcal{S}}^{2}$. If $s$ is frontdoor info, then
$s_{\mathrm{split}}$ is identical, so is also frontdoor info. If $s$ is
backdoor-info, then $s_{\mathrm{split}}$ is modified to be frontdoor-info. ∎

#### Transformation 3 (pruning): ensuring no-redundant-links

######  Definition 42 (Transformation 3).

Let ${\mathcal{G}}^{2}\\!=\\!({\bm{V}}^{2},E^{2})$ be an ID graph with tree
$T^{2}$. Then
$\mathrm{transf}^{3}({\mathcal{G}}^{2},T^{2})=({\mathcal{G}}^{3},T^{3})$ where
${\mathcal{G}}^{3}=({\bm{V}}^{3},E^{3})$ and the identity homomorphism
$h^{2\leftarrow 3}$ are obtained from ${\mathcal{G}}^{2}$ using Lemma 14 by
removing all Definition 18(c) (no-redundant-links) links are removed (which
are all into non-decision nodes), and where $T^{3}=T^{2}$.

######  Lemma 43 (Transformation 3 is homomorphic).

$h^{2\leftarrow 3}$ from Definition 42 is an ID homomorphism from
${\mathcal{G}}^{3}$ to ${\mathcal{G}}^{2}$.

######  Lemma 44 (Transformation 3 preserves tree).

Let $({\mathcal{G}}^{3},T^{3})=\mathrm{transf}^{3}({\mathcal{G}}^{2},T^{2})$.
If $T^{2}$ is a tree of systems on ${\mathcal{G}}^{2}$ with root link $X\to
D$, then $T^{3}$ is a tree of systems on ${\mathcal{G}}^{3}$ with root link
$X^{\prime}\to D^{\prime}$ with $h^{2\leftarrow 3}(X^{\prime})=X$ and
$h^{2\leftarrow 3}(D^{\prime})=D$.

###### Proof.

The tree $T^{3}$ is rooted at $X\to D$ such that $h^{2\leftarrow 3}(X)\to
h^{2\leftarrow 3}(D)$ because it is unchanged from $T^{2}$. $T^{3}$ is a tree
of systems because it is unchanged from $T^{2}$, while ${\mathcal{G}}^{3}$
retains every edge in any path of every system of $T^{2}$ — only redundant
links Definition 18(c) (no-redundant-links) are removed. ∎

######  Lemma 45 (Transformation 3 preserves (a,b) and ensures (c)).

Let $({\mathcal{G}}^{2},T^{2})$ be any soluble ID graph with complete tree
satisfying properties (a,b) of normal form trees. Then
$({\mathcal{G}}^{3},T^{3})=\mathrm{transf}^{3}({\mathcal{G}}^{2},T^{2})$ is an
ID graph with complete tree satisfying (a-c).

###### Proof.

The tree $T^{3}$ on ID graph ${\mathcal{G}}^{3}$ satisfies (b) because
$T^{3}\\!=\\!T^{2}$ and $T^{2}$ satisfies (b). It satisfies (a) because
$T^{3}\\!=\\!T^{2}$ and ${\mathcal{G}}^{3}$ has the same set of nodes, and a
subset of the edges of ${\mathcal{G}}^{2}$. color=blue!30]Ryan: Explain this.
It satisfies (c) by definition. ∎

#### Composing the transformations to obtain an ID graph with normal form tree

We will now perform these three transformations in order to obtain a normal
form tree.

See 19

###### Proof.

Given that the minimal $d$-reduction ${\mathcal{G}}^{*}$ of ${\mathcal{G}}$
contains $X\to D$, we can first pick an arbitrary full tree from Lemma 35 to
obtain a tree $T^{0}$ satisfying (a) position-in-tree-uniqueness.

Then, let
$({\mathcal{G}}^{\prime},T^{\prime})\\!=({\mathcal{G}}^{3},T^{3})=\\!\mathrm{transf}^{3}\circ\mathrm{transf}^{2}\circ\mathrm{transf}^{1}({\mathcal{G}}^{0},T^{0})$
and let $h=\\!h^{0\leftarrow 1}\circ h^{1\leftarrow 2}\circ h^{2\leftarrow 3}$
using Definition 36, Definition 39 and Definition 42. We show that these have
each of the desired properties.

Firstly, $T^{\prime}$ is normal form: Each transformation results in a tree
with one more property of normal form trees, and preserves the properties of
the previous transformations (Lemma 38, Lemma 41, Lemma 45).

Secondly, $h$ is a homomorphism from ${\mathcal{G}}^{\prime}$ to
${\mathcal{G}}^{0}$ since ID homomorphism is preserved under composition
(Lemma 15).

Thirdly, ${\mathcal{G}}^{\prime}$ is soluble since that is preserved under ID
homomorphisms (Lemma 9).

Fourthly, each transformation outputs a tree $T^{i}$ where $h^{(i-1)\leftarrow
i}$ maps nodes in the root infolink to nodes of infolink of $T^{i-1}$ (Lemma
37, Lemma 40 Lemma 44), so the composition has $h(X^{\prime})=X^{0}$ and
$h(D^{\prime})=D^{0}$.

Finally, Transformation 1 results in an ID graph with tree where the nodes in
the tree that are also in the original ID graph ${\mathcal{G}}^{0}$ are
precisely $X$ and $D$. And transformations 2-4 only remove and add nodes that
are not in ${\mathcal{G}}^{0}$, so the property also holds for $G^{\prime}$
and $T^{\prime}$, showing the result. ∎

##  Appendix D Value of Information criterion completeness

In Appendix C we have shown that if an infolink $X\to D$ is present in the
minimal $d$-reduction of a soluble ID graph ${\mathcal{G}}$, then we can
choose a graph and tree ${\mathcal{G}}^{3},T^{3}$ so that ${\mathcal{G}}^{3}$
is homomorphic to ${\mathcal{G}}$, and $T^{3}$ is in normal form. In this
section, we will prove that we can use $T^{3}$ to parameterise
${\mathcal{G}}^{3}$ so that optimal performance can only be achieved by a
policy that has $\pi^{D}(\mathrm{\mathbf{pa}})=f(x)$ for a specific $f$ given
every $\mathrm{\mathbf{pa}}\in\mathrm{dom}(\mathrm{\mathbf{Pa}}(D))$ with
$P(\mathrm{\mathbf{pa}})>0$.

###  D.1 Constructing an ID on nodes in a normal form tree

We will define an ID for only the nodes in the tree, excluding the root info
link, assuming that there is already an ID (possibly trivial) defined for all
the other nodes (including those in the root infolink). This result is more
general than is needed to prove positive VoI (wherein we will chose a trivial
ID) but this is done in order to help with generalizing to the
$\mathrm{Taskify}$ construction in the next section.

######  Definition 46 (Parameterization of a normal form tree).

Let ${\mathcal{G}}^{3}$ be a soluble ID graph together with a normal form tree
of systems $T^{3}$ with root info-link $X\to D$. Let ${\mathcal{G}}^{0}$ be
the subgraph consisting of $X,D$, and all nodes in ${\mathcal{G}}^{3}$ that
are not in $T^{3}$. Let $M^{0}=({\mathcal{G}}^{0},\mathrm{dom}^{0},P)$ be an
ID on on ${\mathcal{G}}^{0}$, and let $\pi_{\mathrm{Task}}^{D}$ (which we call
_the task for $D$_) be a deterministic decision rule for $D$ that depends only
on $X$. Then we define the ID $M^{3}=({\mathcal{G}}^{3},\mathrm{dom},P)$,
which are defined as follows:

  * •

For each node $N$ in ${\mathcal{G}}^{0}$ except $D$, let
$\mathrm{dom}(N)=\mathrm{dom}^{0}(N)$, and let
$\mathrm{dom}(D)=\mathrm{dom}_{\mathrm{base}}(D)\times\mathbb{B}$, where
$\mathrm{dom}_{\mathrm{base}}(D)=\mathrm{dom}^{0}(D)$. For any other chance or
decision node $N$, we define the domain of a node by recursion on the tree
$T^{3}$. Let $s$ be the base system of $N$.777This uses the assumption that
$T^{3}$ is normal form, and hence satisfies Definition 18(a) (position-in-
tree-uniqueness), and using the properties that this implies by Lemma 31
Assume that the domains of the info node and decision node $X^{s},D^{s}$ of
$N$’s base system $s$ are already defined.888This is well-founded recursion,
and for the base case of $s=\mathrm{root}^{T}$, the domains of $X^{s}=X$ and
$D^{s}=D$ were already defined above. Then, if $s$ is of the non-directed-info
case then

$\mathrm{dom}_{\mathrm{base}}(N)=\begin{cases}\mathbb{B}&\textnormal{if $N$ is
on $\mathrm{obs}^{s}(C^{1})$, incl. $C^{1}$, the first obspath of $s$}\\\
\mathrm{dom}{(X^{s})}&\textnormal{if $N$ is in between $X^{s}\dashrightarrow
C^{1}$ on $\mathrm{info}^{s}$ }\\\
\mathbb{B}^{|\mathrm{dom}_{\mathrm{base}}{(D^{s})}|}&\textnormal{if $N$ in any
other part of $\mathrm{info}^{s}$, or any other $\mathrm{obs}^{s}$}\\\
\mathrm{dom}(D^{s})&\textnormal{if $N$ in $\mathrm{control}^{s}$}\end{cases},$

and if it is of the directed-info case then
$\mathrm{dom}_{\mathrm{base}}(N)=\mathrm{dom}(X^{s})$. Based on this:

$\mathrm{dom}(N)=\begin{cases}\mathrm{dom}_{\mathrm{base}}(N)\times\mathbb{B}&\textnormal{if
$N=D^{s^{\prime}}$ for a non-directed-info descendant $s^{\prime}$}\\\
\mathrm{dom}_{\mathrm{base}}(N)\quad&\textnormal{otherwise }\end{cases}.$

color=blue!30]Ryan: Relatedly, can we just refer to dom-base with $dom(Q^{s})$
or something, or do we need this term? color=green!30]Chris: We might be able
to get rid of it, but I’m not immediately sure how.

color=blue!30]Ryan: It seems like the domains are implied by the functions and
domains of the parents in all cases other than forks, and the root systems so
can we just define the functions directly? color=green!30]Chris: We maybe
should consider this, but it’s probably not a priority. It maybe has some
downsides in terms of understandability, but my guess is it’d be better if it
can be done clearly and rigorously. Probably the main problem is that decision
nodes need domains too.

  * •

For each chance node $N$ in ${\mathcal{G}}^{0}$ (including
$X=X^{s^{\mathrm{root}}}$), let $P_{M^{3}}^{N}=P^{N}_{M^{0}}$. For any other
chance node $N$, let $s$ be the base system of $N$ and $p$ the base path of
$N$,999This uses the assumption that $T^{3}$ is normal form, and thus
satisfies (c) position-in-tree-uniqueness and let
$\pi_{\mathrm{Task}}^{D^{s}}$ be the task of the decision of system $s$,
defined for $s=\mathrm{root}$ as the task $\pi_{\mathrm{Task}}^{D}$ given
above, and as the identity operation _$\mathrm{id}^{p}$_ for every other
system. Then, writing $\pi_{\mathrm{Task}}^{D^{s}}(x)$ to refer to $d$ s.t.
$\pi_{\mathrm{Task}}^{D^{s}}(d|x)=1$, we let $P^{N}(n|\mathrm{\mathbf{pa}})=1$
iff $n=f^{N}(\mathrm{\mathbf{pa}})$, where

$f^{N}=\begin{cases}{\mathrm{id}}^{p}&\textnormal{if $\to N\to$ or $\leftarrow
N\leftarrow$ in $p$}\\\
N^{2}[\pi_{\mathrm{Task}}^{D^{s}}(N^{1})]&\textnormal{if $N^{1}\to N\leftarrow
N^{3}$ is the first collider on $\mathrm{info}^{s}$}\\\
{\mathrm{XOR}}^{p}&\textnormal{if $\to N\leftarrow$ is a collider on $p$ other
than the first}\\\ \mathrm{random}^{p}&\textnormal{if $\leftarrow N\to$ in
$p$}\end{cases}$

where $\mathrm{id}^{p}$ copies the output of the
$\mathrm{dom}_{\mathrm{base}}$ part of the previous node on $p$,