Toward a Complete Criterion for Value of Information in Insoluble Decision Problems
Authors: Ryan Carey
Sanghack Lee
Robin J. Evans
Venue: Accepted by TMLR ()

Abstract: In a decision problem, observations are said to be material if they must be taken into account to perform optimally. Decision problems have an underlying (graphical) causal structure, which may sometimes be used to evaluate certain observations as immaterial. For soluble graphs — ones where important past observations are remembered — there is a complete graphical criterion; one that rules out materiality whenever this can be done on the basis of the graphical structure alone. In this work, we analyse a proposed criterion for insoluble graphs. In particular, we prove that some of the conditions used to prove immateriality are necessary; when they are not satisfied, materiality is possible. We discuss possible avenues and obstacles to proving necessity of the remaining conditions.

Published in Transactions on Machine Learning Research (12/2024)
Toward Complete Criterion for Value of Information in Insoluble Decision Problems
Ryan Carey Oxford University
ry.duff@gmail.comm com
Sanghack Lee
sanghack@smm..cc.k
Scoul National University
Robin Evans
ewans@stats..r..cs uk
Oxford University
Reviewed on OpenReview: https: // openreview. formm?? id- ORU=RVO5Jn
Abstract
In a decision problem, observations are said to be material if they must be taken into account to perform optimally. Decision problems have an underlying (graphical) causal structure, which may sometimes be used lo evaluate certain observations as immaterial. For soluble graphs - ones where important past observations are remembered - there is a complete graphical criterion; one that rules out materiality whenever this can done on the basis of the graphical structure alone. In this work, we analyse proposed criterion for insoluble graphs. In particular, prove that some of the conditions used to prove immateriality necessary; when they not satisfied, materiality is possible. We discuss possible avenues and obstacles to proving necessity of the remaining conditions.
1 Introduction
We can view any decision problem as having an underlying causal structure graph consisting of chance events, decisions and utility variables (or "outcomes"), and their causal relationships. Sometimes, it is possible to evaluate key aspects of a decision problem from its causal structure alone. For example, in Figure la and Figure 1b, we see two causal structures. each graph, there is an observation Z, which is a parent of the decision X, which affects the outcome Y. The difference that in Figure 1b, also directly influences Y, whereas in Figure la, does not.
To fully describe these decision problems must specify, for each non-decision variable, probability distribution. Each probability distribution must be conditional only on the outcomes of the directed causes (i.e. the parent variables), à condition known as Markov compatibility. In Figure 1b, a Markov compatible decision problem shown, where the variable is rewarded with Y if they state the outcome of Z (i.e. call the outcome of the coin flip), otherwise the reward is 0. In this sccnario, a greater reward can be attained the docision is allowed to be conditioned on Z, and Z said to be material. Specifically, if it is possible to observe the Bernoulli trial before selecting X, then the maximum expected utility is 0.5.
a Bernoulli trial (i.e. a coin flip), and the decision-maker
attain utility of surely, whereas if one cannot observe the Bernoulli trial,
For the causal structure shown in Figure la, however, there exists an optimal decision rule that ignores the value Z = entirely, in other words Z is immaterial; this holds true for any decision problem compatible with the graph. This evident because given any decision X æ, the observation Z independent of Y, and there is no need for the decision vary with Z. (This can be proved from the fact that is d-separated from Y given X.)

---

Published in Transactions on Machine Learning Research (12/2024)
There are several reasons that we may want to evaluate whether graph allows Z to be material. Firstly, for algorithmic efficiency - if an observed variable is immaterial, then the optimal policies are contained in small subset of all available policies, that we can search exponentially more quickly. (For example, in Figure la, there are four deterministic mappings from Z to X, but if we let X ignore Z, then there are just two possible choices, X = and X = =.)
Secondly, materiality can have consequences for the fairness of drciisonn-maiine procedure. Suppose that Z designates the gender of candidates available to recruiter, which are male (Z 1) female (Z 0) with equal probability, while X indicates whether that person is (X = 1) is not (X 0) recruited, and Y indicates whether that person is [Y=1) 1) or is not (Y = 0) hired. If is correlated with Z given X, then the applicant's gender is material for the recruiter, and to maximize the hiring probability, they will have to recruit applicants at different rates based on their gender. If the causal structure is that of Figure la, then materiality can be ruled out, meaning that unfair behaviour is not necessary for optimal performance, whercas the causal structure of Figure 1b can incentivize unfairness. Such an analysis can also be extended to counterfactual fairness (Kusner et al., 2017): in an arbitrary graph where Z is sensitive variable (such gender), counterfactual fairness can arise only when there is a path Z + + O X, where the observation O is material (Everitt et al., 2021).
Thirdly, materiality can have implications for AT safety - if represents a corrective instruction from a human overseer, and there exists no path 2 - ................................ + O + X where O is material, then there exist optimal policies that ignore this instruction (Everitt et al., 2021). Materiality is also relevant for evaluations of agents' intent (Halpern& & Kleiman-Weiner, 2018; Ward al., 2024b), and relatedly, their incentives to control parts of the environment (Everitt et al., 2021; Farquhar et al., 2022). For agent to intentionally manipulate variable Z to obtain outcome Y y, there must be path p X .... Z ..... Y where for each of its decisions X' lying on p, the parent O' along is material for X'. In general, a stronger criterion for ruling out materiality will allow us to rule out unfair or unsafe behaviour for wider range of event-euviromment interactions (Evcritt et al., 2021).
ε7 Eg ~ U(B)
Eg E2 U(B
Z 7 33
Z 7 E3
x
Y
x
X = 2 fr (pa.) = 1 = -]
x X'=X (pa
(a) Z is immaterial for X.
(b) Z is material for X.
(c) Z is material for X.
Figure 1: Three graphs, with decisions in red, and a real-valued outcome Y. We write UBB) for uniform distribution over B, i.e. Bernoulli distribution with p p= 0.5.
Any procedure for establishing immateriality based on the causal structure may be called a graphical crite- rion. For example, if a decision X is not an ancestor of the outcome Y, then all of the variables observed at X are immaterial. An ideal graphical criterion would be proved complete, in that it can establish immateriality whenever this is possible from the graphical structure alone. Clcarly, this criterion is not complete, because in Figure 1a, X is an ancestor of the outcome, but we still proved Z immaterial. So far, a graphical criterion from van Merwijk et al. (2022) has been proved complete, but only under some significant restrictions. The causal structure must be soluble, meaning that all of the important information observed from past decisions is remembered at later decision points. Also, no criteria has been proved complete for identifying immaterial decisions, i.e. past decisions that can be safely forgotten.
For insoluble graphs, there the criterion of Lee & Bareinboim (2020, Thm. 2), which can identify immaterial decisions and is (strictly) more potent in general. However, is not yet known whether this criterion is complete. In particular, it is not yet clear whether several of its conditions are necessary. For example, one
2

---

Published in Transactions on Machine Learning Research (12/2024)
case where all existing criteria are silent is the simple graph shown in Figure 1c we would like to know whether we can rule out X being a material observation for X'. We cannot use van Merwijk et al. (2022) because X is a decision, and because the graph is insoluble." Furthermore, we cannot establish immateriality using Lee & Bareinboim (2020, Thm. 2), because it violates a property that we term LB-aactorizaailityy which we will discuss in Section 3.4.²
By studying Figure 1e in a bespoke fashion, we find that there exists a decision problem with the given causal structure, where X is material for X'. As shown in Figure 1c, Z is Bernoulli variable, and Y is equal to 1 if Z X' and to 0 otherwise. If X is observed by X', then reward of E|Y] 1 can be achieved by the policy X' = X = Z. If X is not observed, the greatest achievable reward is lower, at E[[]] 0.5, implying materiality.
This raises a question: by generalizing this construction, can we prove that requirement of LB- LBB-fctoorizaaility is necessary to prove immateriality for wide class of graphs? This work will prove that this requirement is indeed necessary, meaning that materiality cannot be excluded for wide class of graphs including Figure lc.
whole is It remains an open question whether the criterion of Lee & Bareinboim (2020, Thm. 2) complete, in that its other conditions are necessary for establishing immateriality. In the case that it is complete, our work is step toward proving this. On the other hand, we also present some graphs where materiality is difficult to establish, that if the criterion is not complete - could bring us closer to a proof of incompleteness.
The structure of the paper is as follows. In Section 2, we will recap the formalism used by Lee & Bareinboim (2020) for modelling decision problems, based on structural causal models. In Section 3, will review existing procedures for proving that an observation can or cannot be material. In Section 4, we will establish our main result: that requirement I of LB- ff-aattorizability is necessary to establish immateriality. In Section 5, we present some analogous results for other requirements of LB-factorizabilityy that could serve as a building block for proving the necessity of those requirements. We then illustrate the problems that arise in trying to prove necessily of those further requirements, and outline some possible directions for further work. Finally, in Section 6, we conclude.
2 Setup
Throughout the paper, will define decision problems using structural causal models (Pearl, 2009, Chapter 7), following the formalism of Lee & Bareinboim (2020), although our results also apply equally to Bayesian networks and influence diagrams.
2.1 Structural causal models
A structural causal model (SCM) M is a tuple V, F), where U is a set of variables determined by factors outside the model, called erogenous following a joint distribution P(U), and V is set of endogenous variables whose values are determined by collection of functions F = [Jvivev such that V - (vaa(V),, Uv) where Pa(V) S VV (V) is a set of endogenous variables and Uy S U is a set of exogenous variables. The observational distribution P(v) is defined as En, llvev P(c|pay, Pv)) where uy is the assignment u restricted to variables Uy. Furthermore, do(X = x) represents the operation of fixing a set X a constant x regardless of their original mechanisms. Such intervention induces a submodel Mg, which is M with fx replaced by for X E X. Then, an interventional distribution P(u) oo do(x)) can be computed as the observational distribution in Ma- The induced graph of an SCM M is DAG g on only the endogenous variables V, where (i) X-+Y if X is an argument of fy; and (ii) X if Ux and Uy may be dependent, i.c. for any ux, uy, P(ux, uy) o P(ux) x P(uy).
I Formally, this is because W L and X' 1 UUW,, as per the definition of solubility that will review in Section
2 2Specifically, requirement of L.B.factrrieabiiity violated because Y is d-connected x given X
3

---

Published in Transactions on Machine Learning Research (12/2024)
We use the notation Pa(X), Ch(X), Ane(X) and Desc(X) to represent the parents, children, ancestors and descendants of a variable X, respectively, and take ancestors and descendants to include the node X itself. 3
We write V 1/2 to designate an edge whose direction may be V1 + 1/2 or Vi + V22 For a path V Ve, we will use the shorthand V1 --- Ve, and for a directed path V1 + ... - Ve, the shorthand V1 --+ V.. For a path p A - B --- C ---- D, we will describe the segment B --- C using the shorthand B C. We will use the shorthand VI.N for a sequence of variables Vi,... Vy indexed by I,...,N, VIN for a sequence of assignments, and PI.N for set of paths PI....PN: PN-
Some notations are used repeatedly when constructing causal models, such as tuples, bitstrings, indexing, and Iverson brackets. We will write a tuple as 2 == (r, v), and this may be indexed as z10] = x. A bitstring of length n, i.e. a tuple of n Booleans, may be written as IB;; and a uniform distribution over this space, as U (BB). We will denote a bitwise XOR operation by @ so that, for example, 01 o 11 = 10. Bitstrings may also be used for indexing, for example, the yth bit of z may be written as as xfy], and the leftmost bits are of higher-order so that, for example, 0100[01] = 1. Similarly, for random variables X, Y, we will write X[Y] for variable equal to z[y] when X and Y y. Finally, the Iverson bracket [P] is equal to 1 if P is true, and 0 otherwise.
2.2 Modelling decision problems
To turn an SCM into a decision problem, three further clements must be specified: a set of decision variables, set of policies that the agent may use to control those decision variables, and goal that the agent is trying to achieve.
A Mixed Policy Scope (Lee & Barcinboim, 2020) supplies the first two elements: identifying certain variables as decisions, and enumerating the contect variables or "observations" Cx on which each decision X is allowed to depend.
Definition 1 (Mixed Policy Scope (MPS)). Given DAG 9 on vertices V, mized policy scope S = (X, Cx)xex(s) consists of a set of decisions X(S) C V and a set of context variables Cx C V for each decision.
For a set of decisions X', we define their contexts as Cx = Uxxx Cx-
A policy consists of a probability distribution for each decision X, conditional on its contexis Cx-
Definition 2 (Mixed Policy). Given an SCM M and scope S = (X, Cx), a mised policy π (or a policy, for short) contains for each a decision rule Xx|Cx' where xx|Cx Ex x Acx + [0, 1] is a proper probability
mapping from the domain Xx of X to the domain Ncx of Cx.
We will say that such a policy π follows the scope S, written π ~ S. A mixed policy is said to be deterministic if every decision deterministic function of its contexts.
Given a mixed policy scope, we obtain a new causal strueture, described by scoped graph.
Definition (Scoped graph). The scoped gruph Gs is obtained from G by replacing, for each decision X X(S), all inbound edges to X with edges C+ X for every Ce Cx. We only consider scopes for which GS is acyclic.
In a scoped graph, we will always illustrate the docision variables as rod circles, as shown in Figure 1 (Lee & Bareinboim, 2020). The final element of decision problem - the agent's 's goal will be represented by real-valued variable Y. Throughout this paper, will assume that Y is neither decision, nor a context.
The expected utility Pn.S given policy π is simply the expected value of Y in the model Mr, where each fx is replaced with Xx, i.e. Px.s = MM [Y]. When the scope is obvious, we will simply write pr--
Note that Pa(X) is intentional reuse of the notation used describe the arguments of fx in the SCM definition, because the eudogenous arguments of fx and the parents of X in the induced graph are the same variables.
'Following Lee & Bareinboim (2020), we term this a "mixed policy" due its including mixed strategics. Note that game theory also has a distinction between "mixed" policies, where the decision rules share source of randomness, and "behavioural" policies, where they do not, and in this sense, the "mixed" policies of Lee & Bareinhoim (2020) are actually behavioural.
4

---

Published in Transactions on Machine Learning Research (12/2024)
This paper is concerned with materiality whether removing context variable from one decision will decrease the expected utility attainable by the best policy. We define materiality in terms of the value of information (Howard, 1990; Everitt et al., 2021).
Definition 4 (Value of Information). Given an SCM M and scope S, the marimum expected ulility (MEU) is Uss = maxq~8 M. The value of information (Vol) of context Z E Cx for decision X E X()) is p MS2 where SZ defined as (X', xxx))x ( Cx {(Z)).
The context. Z is material for X in SCM M if Z has strictly positive value of information for X, otherwise it is immaterial.
2.3 Graphical criteria for independence
Knowing when variables are independent an important step in identifying inmaterial contexts, as we will discuss in the next. section. Thus, we will make repeated use of d-separation, graphical criterion that establishes the independence of variables in graph.
Definition 5 (d-separation; Verma & Pearl, 1988). A path p is said to be d-separated by of nodes Z if and only if:
1. p contains collider X + W +- Y such that the middle node W is not in Z and no descendants of W are in Z, or
p contains chain x W + or fork X + W + where W in Z, or one or both of the endpoints of is Z.
A set is said d-separate X from Y, written (X Lg Y Z), if and only if Z d-separates every path from node in X to node in Y. Sets that not d-separated called d-connected, written X fg Y Z.
When the graph is clear from context, will write 1 in place of Lg. When sets X, W. Z satisfy X 1 W Z
they are conditionally independent: P(X,7 W Z) P(X P(W Z) (Verma & Pearl, 1988).
If we know that a deterministic mixed policy is being followed, then we may deduce further conditional independence relations. This is be- cause conditioning on variables V may determine some decision vari- ables, which are called "implied" (Lee & Bareinboim, 2020), "func- tionally determined" (Geiger & Pearl, 1990), making them conditionally independent of other variables in the graph
Definition 6 (Implied variables; Lee & Bareinboim, 2020). To obtain the implied variables Z for variables Z in G given a mixed policy scope S, begin with [2] + Z, then add to [Z] every decision X such that Cx C 1) until convergence.
Figure A graph where decisions Z, X jointly determine the outcome Y. A policy node Rx shown, which decides the decision rule at X.
For example, in Figure 2, we see that [X] (2,X), so d-separated from Y given [X]. This means that under deterministic mixed policy, and Y are statistically independent given X. This has implications for materiality. In particular, it means that the best deterministic mixed policy 7 == 2, X = does not need to observe Z at X. Morcover, the performance of the best deterministic mixed policy can never be surpassed by a stochastic policy (Lee & Bareinboim, 2020, Proposition 1), so Z is immaterial.
3 Literature review
Our review will begin with the origin and applications of the concept of materiality, then cover graphical criteria in single-decision, soluble, and general multi-decision settings.
5

---

Published in Transactions on Machine Learning Research (12/2024)
3.1 Graphical criteria for materiality, and their applications
"Value of information" was originally described separately from graphical models like the influence diagram (Howard, 1966). When influence diagrams were developed, however, knowing the value of information of different variables became a fundamental aspect of understanding an influence diagram (Shachter, 1986; Matheson, 1990; Howard Matheson, 2005). Finding that a variable has zero value of information is espocially important bocause narrows the search for an optimal policy. The property of having zero value of information has since been termed "immateriality" (Shachter, 2016).
Various past works have sought to establish the circumstances in which a variable could be proved immaterial. Sound criteria have been proposed by Fagiuoli & Zaffalon (1998); Lauritzen & Nilsson (2001); Shachter (2016). Furthermore, Fagiuoli & Zalfalon (1998) attempted to prove the criterion's completeness, although it was not successful (Everitt et al., 2021).
There are also criteria that establish whether a variable may be valuable to control (Fagiuoli & Zaffalon, 1998; Shachter & Heckerman, 2010). In particular, establishing immateriality can help with establishing zero value of control because it shows that there exists alternative influence diagram, where the same utility can be achieved but with fewer edges, making it easier to establish that some variables are unnecessary to control (Fagiuoli & Zaffalon, 1998). For example, in the influence diagram Z + X - Y, we know that Z is immaterial, and the graph may be separated into Z; X + Y, wherein Z affects nothing, and so is clearly of no value to control.
In recent years, influence diagrams have been applied to evaluating the salety of AT systems. To achieve this, incentive concepts have been developed that are related to the value of information and control, such as instrumental control incentives (Everitt et al., 2021), response incentives (Everitt et al., 2021), and notions of inlend (Halpern & Kleinan-Weiner, 2018). These concepts and their graphical criteria have been used to analyse agent interactions, especially in the context of A1, including matters of fairness (Ashurst et al., 2022), manipulation ( (Ward et al., 2024b), honesty (Ward et al., 2024a), and human control (Carey & Everitt, 2023). For these incentive concepts, proofs of the soundness and completeness of their graphical criteria directly extend the proofs pertaining to materiality (Everitt et al., 2021), and thus a complete criterion for materiality is a key step for this line of work.
3.2 Single-decision settings
In the single-decision setting, there is a sound and complete criterion for materiality: a scoped graph G(S), there exists an SCM where the context Z E Cx is material if and only if 2 1 Y Cx u [X} \ [2} and the outcome Y is descendant of X (Lee & Barcinboim, 2020; Everitt et al., 2021). The proofs of the soundness (the only if direction) and completeness (the if direction) are both relevant to the current paper.
The argument in the only if direction is that if X is not an ancestor of the outcome Y, then its policy is completely irrelevant to the expected utility, and so all of its contexts are immaterial, and if Z is conditionally independent of the outcome Y given the decision and other observations, then it may be safely ignored without changing the expected utility of the policy. These conditions imply immateriality in the multi- decision setting for precisely the same reasons.
The if direction is more important to us, because the result is extended by the present work. The if direction is proved by constructing decision problem where Z is material. By assumption, there is a directed path X --+ Y, called the control path, and path Z --- Y, active given Cx U(X} \ (2}, called the info path. The idea is to construct an SCM where the info path makes Z contain information about Y, and how X ought to influence Y, while the control path gives X a way to exert that influence.
The construction from Everitt et al. (2021) and Lee & Barcinboim (2020) has two cases. When the info path contains no colliders, the construction is shown in Figure 3a. In essence, the info path transmits random
6

---

Published in Transactions on Machine Learning Research (12/2024)
UU
UN
~ U
U1
UN-1
W1
WN
Z Z@U1
UN-1
(r(pay) |I x]
V ~ (B)
7
X = Z
Z - W1 @ WN
Sr 1 un
(a) The Everitt et al. (2021); Lee & Bareinboim (2020) scheme, with red info path that lacks colliders, and the control path shown with thick dark red arrow.
(b) The Everitt et al. (2021); Lee & Bareinhoim (2020) scheme, with red info path that contains colliders, and the control path shown in dark red.
Two decision problems where is material X. For readability, we marginalize out exogenous variables from the SCM, UB) can be understood shorthand for where ~ UR), and on.
Figure 3:
Z ~ (
Z ~ (()
Z
fy (pay) )= [2 [0]
+ +Iu' [0] = =2
fr(pay) = [= 1===] x']l
Z'
X
Z'
X
Z
X
Z'
Z
X
(Z', W')
W
W
= U'
U' ~ BB
U
U
(a) The Everitt et al. (2021) scheme is applied using just the red info path; Z is immaterial for X.
(b) The van Merwijk et al. (2022) scheme is applied, using the red and blue info paths; Z is material for X.
Figure 4: Two decision problems on a soluble graph.
value V = to Pay, and the decision has to match this value, i.c. X = VV, in order to obtain the maximum utility of Y 1. Without the context Z, the maximum expected utility is 0.5, proving materiality." 5
For the case where the info path does contains a collider, the construction shown in Figure 3b. Each fork U, in the info path, along with Z, generates random bit, while cach collider W; assigned the XOR (U--1 U:) of its two parents. By observing and the values WI.N, the agent has just enough information to recover uN. In particular, the policy that sets X equal to the XOR of a and WI.N, obtains X UN surely and achieves the MEU, E|y] = 1. Without the context Z, the MEU becomes 0.5, so Z is material.
3.3 Soluble multi-decision settings
A decision problem is said to be soluble (or to have "sufficient recall") if the decision decision-maker maker always remembers enough aspects of past decisions and observations to make the present decision optimally. Formally, this requires the graph to admit an ordering < = previous decision or context V E (X, Cx, x i}, we have V & Ane(Y) or V 1 Y (X,) U Cx,- For
over decisions such that for every X,, for every
3To be precise, the formalism of Lee & Barcinboim (2020) also allows the active path from Z include edges ++ Y, but deal with these cases, begin with the distribution that would for a path marginalize out L.
bidirected Y, then

---

Published in Transactions on Machine Learning Research (12/2024)
example, in Figure 4a, using the ordering X < X', the nodes Z,X are d-separated from Y by X' and its contexts { Z', WW), which implies solubility.
For those graphs that satisfy this condition (corresponding to solubility); there exists a sound and complete criterion for evaluating materiality. As in the single-decision setting, an observation Z is identified as immaterial if Z Y Cx U \ (Z) where Y E DescX. The only difference is that the multi-decision setting, we can remove Z as a context of X and then repeat the process (i.e. the edge Z + X is removed from the scoped graph Gs) to find more immaterial contexts, until all immaterial observations have been removed. Conversely, when every such context has been removed in this way, then all remaining contexts must be matcrial. For example, in the graph of Figure 4a, every decision is an ancestor of Y, and every context has an info path (the info paths include Z + Y, Z' + W" +- U" + Y, and W' + U" - Y), so, all contexts may be material in at least one decision problem with this causal structure, and in fact they are material in the SCM shown.
It is useful to understand how the completeness direction of this result is proved, i.e. how the presence of info paths is used to construct decision problem where Z is material (van Merwijk et al., 2022, Theorem 7). We can notice what obstacles arise by considering the graph from Figure 4. If we were to apply the single-decision construction of Everitt et al. (2021) to this graph, we would first identify the info path Z + Y and the control path X + Z' - X" YY The info path has no colliders, so we would construct a decision problem using the scheme from Figure 3a, and the result is shown in Figure 4a. The idea of this construction is that X should have to copy Z in order for the value z transmitted by the info path to match the value a' transmitted by the control path. Whatever action x is selected, however, the decision X' can assume the value 2, thereby achieving the MEU. The MEU is then achievable whether Z is context of X not, so Z is immaterial in this construction.
In order to render Z material, van Merwijk et al. (2022) instead adapts the construction from Figure 4a by incentivizing X' to pass along the value of Z'. This is done using the second info path Z' + W' + U - shown in Figure 4b. The term V/2 == [=]]=[0]] = x' ='[]]] is added to the reward, which equals 1 if X' presents one bit from U" along with its index. (Recall that x' [0] denotes the 9th bit of x' and so on.) Furthermore, W' is defined as W U'IZ', so that X' knows only the th bit of U", and since the index x' is one bit, U' is defined as two bits in length, i.c. U ~ U(? Finally, rather than requiring
x' as in Figure 4a, the term V1 := [= = x' o0]] is included, because an optimal policy in the new model will have z=[0] = =' = (rather than simply x' = 2, as in the previous model). In the resulting non-inters non-intervened model, the utility is clearly Y = 2, which is the MEU, and to achieve this utility, it is necessary that Y1 = Y22 = 1 with probability 1. To maximize y2, the decision X' must reproduce the only known digit from U", i.. x' = (a',u([=')) To maximize Vi, we must have Z- = X'(0] almost surely, and since X'[0] = X, this requires X = Z with probability 1. This can only be done if Z is a context of X, meaning that Z is material for X. A key idea of this approach Y, contains decisions other than X, then we need to incentivize the downstream decision to copy information along the control path, and this will be done by choosing values for variables lying on the info path for X' (the one shown in blue in Figure 4b); we will reuse this idea in the proofs of our main result.
is that if a control path for X, such as X + X' >
3.4 Multi-decision settings in full generality
For insoluble decision problems, the literature includes a graphical condition for establishing immateriality, but we do not yet know whether it is complete (in that materiality is possible whenever it is not satisfied). For this procedure, we would begin with graphical criteria from the single decision case.
a decision X is non-ancestor of Y, then its contexts are immaterial, ICCYYCC (C), then the context C is immaterial.
If either of these conditions describes the context Z that we are interested in, then we have proved it immaterial, and our job done. If neither of these conditions holds, then we can apply the more sophisticated criterion Loe & Bareinboim (2020, Lemma 1) and Lee & Bareinboim (2020, Theorem 2). If the assumptions of Lee & Bareinboim (2020, Lemma 1) hold for some target variables Z, target actions X', and latent
8

---

Published in Transactions on Machine Learning Research (12/2024)
variables U" then they admit factorization, which term "LB-factorizaaliity" after the authors' initials. Lee & Bareinboim (2020, Theorem 2) then contains some further assumptions; if these also hold, then the contexts Z are immaterial to the decisions X'. We begin with the definition of L.D-factorizabilityy
Definition 7. For scoped graph Gs, will say that target actions X', endogenous variables Z disjoint with X', contexts C' := Cx \ (X' U Z) and exogenous variables U are LB-factoriaable if there exists an ordering < over V == = X Z such that:
(Y X [[X
II. (C LX -c Zuc, U" [(X for every C E C' and
III. V2xx is disjoint with (e)c(X) and subsumes Pa(X) for every X X',
where x consists of new parent xx added to each variable X E X and W.v, for W C V", denotes the subset of W that is strictly prior to V in the ordering x,
For example, consider the graph Figure 2. In this case, Y Desc(X) and Z Y X, so the singlo-decision criteria cannot establish that Z is immaterial for X. However, by choosing Z [2]. X' [X}, and the ordering x= X), we have that:
the outcome Y is d-separated from л by [X], (since Z is a decision that lacks parents, we actually have [X] ())
II. the contexts C' are an empty set, so (II) is trivially true, and
III. V2x Z, and Z is disjoint with Desc(X) and Z 2 Pa(X)
so Z and X' are fb-ffactorizale.
In this paper, our focus exclusively on the assumptions of Lee & Barcinboim (2020, Lemma 1) rather than the additional conditions of Lee & Bareinboim (2020, Theorem 2), but for completeness sake, the latter is reproduced in Section A. We also establish in Section A that the assumptions of Lee & Bareinboim (2020, Theorem 2) are indeed satisfied in the graph Figure 2, mcaning that Z is immaterial for X, matching the ad hoc analysis of this graph in Section 2.
4
Main result
4.1 Theorem statement and proof overview
The goal of this paper is to prove that condition (I) of I.B-factorizaiiiity is necessary to establish immate- riality. More precisely, if condition (I) is unsatisfiable for all observations in the graph, then the graph is compatible with materiality for all observations.
might initially seem unnecessarily stringent to assume that this holds for all observations, rather than the context Zo for which we are trying to prove materiality, Recall from Figure 4b, however, that proofs of matcriality are recursive, in that prove that Z is material for X, we incentivized X to copy Z, and to do this, we had to incentivize X' to pass on the value of Z'. This required us to assume that other contexts and decisions (such Z' and X') have their own info paths and control paths, not just Z and X. So that we can assunee this, in our theorem below, condition (C) requires that (I) holds for all contexts. Conditions (A) and (B) are also necessary for a graph to be compatible with materiality, because their negation implies immateriality, as discussed in Section 3.2.
Theorem 8. If, in scoped graph Gs, for every X E X(S)
A. X Ancgs (Y), B. VC Cx (C Lgg YI(X)UXX (CH)), and
oTo he precise, each d-separation (A-B) holds the graph g", obtained from & by adding a parent xx for each decision
9

---

Published in Transactions on Machine Learning Research (12/2024)
C. for every contert Z E Cx in Is, (ax Lgs Y ((((S)) U \ (ZH)), where x is new parent of X,
then for every Xo E X(S) and Zo E Cx,, there erists on SCM where Zo is material for Xo-
In words, this means that if an outcome Y influencable (condition A) and each context provides information about Y given other contexts (condition B), and given everything determined by the contexts and decisions (condition C)2 then each context is material in at least one model compatible with the graph.
We will prove this result in three stages, across the next three sections.
In Section 4.2, we will prove that any scoped graph satisfying the conditions of Theorem 8 contains certain paths called "materiality paths", which begin al a context Zo and decision Xo-
In Section 4.3, we will use the materiality paths to define a model for this scoped graph, which we will call the materiality SCM.
In Section 4.4, we will prove that in the materiality SCM, Zo is material for Xo-
4.2 The materiality paths
To prove materiality, we will begin by selecting info paths and a control path, similar to what was described in Section 3.3 and illustrated Figure 4b. One difference, however, that we must choose paths that allow us prove the value of remembering a past decision. We will describe how to accommodate this difference in Section 4.2.1 then define the paths in Section 4.2.2.
4.2.1 Paths for the value of remembering a decision
Suppose that given the graph in Figure 5, we would like to establish that it is useful to remember the decision Zo. when making the decision Xo- Given an info path, the procedures of Everitt et al. (2021) and van Merwijk et al. (2022) will tell us how construct an SCM, in which we can compute whether Zo is material. The problem is that there are two candidate info paths: Zo Y and Zo + U +Y, and these procedures give
guidance which one to choose. So which one will lead us to construct SCM where Zo is material? Let us consider each info path in turn.
Using the info path Zo + Y, we obtain the model in Figure 5a. In this model, we have Y = if xo = 20: i.c. the decision X, is required to match the value of a past decision Figure 5a. Then, the MEU of 1 can be achieved with a deterministic policy such as Zo = Xo = 1, and Zo is immaterial for Xo. To understand this in terms of the paths involved, Why does the proof fail with this info path? It is because the the info path Zo + Y includes no parents of Zo, so Zo is implied by values outside the info path, and Zo + Y is rendcred inactive given [U]. This mcans that obscrving Zo can no longer provide useful information about how to maxinize Y.
Using the info path 2o + + we obtain the model in Figure 5b. In this model, Y = if xo u, i.e. the docision Xy must match the value of a random Bernoulli variable U. The value of U is directly observed only by Zo, and so in an optimal policy Xo must observe the decision zo; this is the case in the policy 20 = u, 2g = 20, and so Zo is material for Xy- The proof has succeeded because the info path Zn + U + includes a parent U of Zo, meaning that Zo no longer implied by variables outside the info path, and the path Zo + U + Y remains active given [Ø]. This choice of path helps to ensure that Zo provides useful information about Y.
In general, when an info path passes through a decision, such as Zo in the previous example, we want it to also pass through a non-decision parent of Zp. We will now see that condition (C) of Theorem implics that each decision has a non-decision parent. N that is not ((X(S) (S)USCC (X(())))))) (2)].
Lemma 9. If scoped graph
g(S) satisfies condition (C) of Theorem 8, then for every contert Z E Cx where Z, X X(S) are decisions, there erists non-decision N E Cz \ [(X(S) U Cx(sn(22) (7)]-
10

---

Published in Transactions on Machine Learning Research (12/2024)
fy (pay) ) [ zoll
fy fy
[u
(
= Zo
U(B)
= 2u
Zu
X
Y
U
Zo
Xo
Y
(a) Zo is immaterial for Xp-
(b) Zo is material for Xo
Figure 5: Two SCMs, with models constructed using different (red) info paths.
Intuitively, this is because condition (C) states that there is an active path from Z to Y, given a superset of [X(S) \ (2). If all of the parents of Z are decisions, then we would have Z E [X(() \ (Z), and every path would be blocked, and condition (C) could not be true.
Proof of Lemma 9. Assume that there is no such non-decision N, i.e. Cz S ((X(S) U Ux()N1())) \ (2)), and that πх L Y (S) U UX(SNz)) \ {2}], (by condition (C) of Theorem 8), and we will prove a contradiction. From Cz S [(X (S)UUX(S)) V (ZH], we deduce that & E [(x(S)CCx(s)) (23) (by the definition of (W]), and then there can be no active path from xx Y given [(X (X(())XX())x() (1))) M221 2 Cz U (Z), contradicting condition (C) of Theorem 8, and proving the result.
This tells us that for any decision Z there is an edge Z + N. Moreover, by condition (C) of the main result, we know that there is info path from N to Y. By concatenating the edge and the path, we obtain path from Z to Y, which we will prove is active given ((X U Cx(S))21) \ {Z}]. This is precisely what we want for our info path, first because it passes through a non-decision parent of the endpoint Z, (so the endpoint U will not be determined as it is in Figure 5a) and second, because this path is active given (S) U (x(S)12) \ {2}1, meaning that forks and chains are not decisions, and so they cannot be determined either.
Lemma 10. If a scoped graph G(S) satisfies conditions (B-C) of Theorem 8, then for every edge Z + X between decisions Z,X X E (SS), there crisls a path Z s N N.. (so N & ((X U CX(S)222)) ).
Y, active given UX(())XX))) (7)],
The proof that the segment N --- Y is active given [(X(S) U (S) [2}] rather than just ((X(S) U (x(S)(N)) \ [N}] requires some detail, so it is deferred to Section B.1.
4.2.2 Defining the materiality paths
In this subsection, we will describe how to select some paths to cxhibit that some context Zo is material for a decision Xo- In overview, this will begin with the selection of a directed control path passing through Zo -> Xo and terminating at Y. There are finitely many info paths, which emanate from the control paths and go to Y. Then finally, there are finitely many auxiliary paths, which go from colliders in the info paths to Y. We will refer to the control, info, and auxiliary paths collectively as the materiality paths, and they can all be seen in Figure 6.
The control path is the horizontal spine in Figure 6. The control path exists because Xo is an ancestor of Y by condition (A) of Thcorem 8, and Xo has a chance node ancestor A by Lemma 10 (because the parent Zo of X, either chance node, or it has a chance node parent.)
We then index the decisions on the control path as X Ximi....., Ximax and their parents along the control path as Zimm...... Zimax. where émin is either 0 (if Zo is chance node), -1 (if Zo X-).. (Note that where the control path has consecutive decisions, we will have Z, X.-1.) Then, an info path my is chosen for cach context Z, using Lemma 9 to ensure that it satisfies some desirable properties.
Rather than the info path m² per se, we will often be interested in the portion of it that is non-overlapping with the control path. So the intersection node T. will essentially be the point at which the info path departs from the control path, and the truncated info path m² will be the segment - of mi-
Then, in each truncated info path my, for each collider W we will define an auriliory path ragj = Wos Y.
11

---

Published in Transactions on Machine Learning Research (12/2024)
Vo.1
Uo,Jo
Wo,2
T0.2
Wo.Jo
1o,Jo
T0,0
d
A
To
Zo
X
Ti
Z1
X1
Tj
Z1
XJ
Y
W1,1
11.0
U1.J.
Figure 6: The set of paths proven to exist by Lemma are red, green and blue. In each case, the point of departure of the active path from the (black) directed path is designated by T;- In full generality, each path may begin either as Zi Ti t- (as red), or as Z,
(green, blue).
Lemma 11. Let G(S) be scoped graph that contains contect Zo E Cx, and satisfies the conditions of Theorem 8. Then, it contains the following:
control path: a directed path A --+ Zp - Xo -- --s Y, where A is a non-decision possibly equal to Zo, and contains no parents of Xo other than Zo.
We can write as A--s Zmmo + Ximm --+ ..... Zu - Xo --+ Zimos - Ximax --> Y,imin S imas
where each Zi is the parenl of X; along d (where A --4 Zimin and X;-1 --- Zi are allowed to have
length 0). Then, for each i, define the info path: m² Zi -k---Y. active given ((X(S) (x()))
Z:1, that if Z is a decision, begins as Z, t N (so N ((X(((((S) (((S)CC(L Cx(s)z 2,1.) Let T, be the node nearest Y in m4 Zi --- Y (and possibly equal to Z,) such that the segment 2; máh T; of m4 is identicul to the segment Ze 4-- T, of d. Then, let the truncated info path m.
be the segment T3 ni Y. Write my as in m. (We allow the possibilities that T; = W., so that m, begins as T, x-- U2a or that J, = 0 so that my is T₃ - Y. Then, for each i and S j S Ji, let the auciliary path be any directed path Tag W.. --4 from Wag to Y.
T4--+W., 1-- U
Wi, U12 U2.J; -++,,,+Y,, where J is the number of forks
The proof was described before the lemma statement, and is detailed in Section B.2.
4.3
The materiality SCM
We will now present construction that uses the materiality paths to define an SCM where Zo is material for Xg. This construction will differ from those of Sections 3.2 and 3.3, in ways that help to deal with insolubility, We will outline these differences in Section 4.3.1 then define the construction in Section 4.3.2.
4.3.1 Models for insoluble graphs
To how the past constructions of Everitt et al. (2021) and van Merwijk et al. (2022) need to be modified, it is instructive to consider some insoluble graphs that are allowed by Theorem 8, and examine how the past constructions fail to establish matcriality.
Consider, for example, the graph of Figure 7a. This is insoluble, because at the decision Xo, the past decision X' contains information about Y, i.e. X' V'L Y Zo, and it also satisfies the three conditions of Theorem 8.
In this graph, we can select the control path X, + Y and info path Zo + W1 U1 + Y. Then, the construction from Everitt et al. (2021) and van Merwijk et al. (2022) could be applied if only X'
12

---

Published in Transactions on Machine Learning Research (12/2024)
U3 ~ U (ea)
U1 ~ U(B)
U1 ~ U(B2)
Zo
Zo ~ U(B)
U1
Zo
Zo= ~ U(I)
U1
Uo
Up ~ U(B*)
Wi
Zo +U1
W1
--1 [2]]
W1
-U [U
WJ
Zo
Up.
W
X
W
W U,
Zo + W1
(Zo, X")
(Zo. W:J)
X
X
Xo
fr [r(pay) = [u xo]
Jr (pay) y)= = [= [x]]]
fv(pay) ) 110 com... w. u.]
(a) Zo is immaterial for Xo
(b) Zo is material for Xo
(c) Zo is material for Xo
Figure 7: Two SCMs (a-b), and a description of a family of SCMs, where each dashed line represents a path. The repeated exponent exp3 (k) is defined as & if n = O, and gexp2 (kk) otherwise.
non-decision variable. So treat X' as though was a non-decision, and we obtain the decision problem shown in Figure 7a. In this model, the outcome Y equal to 1 when Xo is equal U1. The idea of this construction is that since W1 Zo @ Ug. the MEU is achieved with the non-intervened policy Xo Zo e Wi, which would require Xo to depend on Zo. In this model, however, X' is decision, and there exists an alternative optimal policy, where X" = U1 and Xo = X', and Xo need not directly depend on Zo. proving that Zo is immaterial for Xo- Essentially, the single bit of X' suffices to transmit the value of U1, and so the information contained in Zo was not incrementally useful. So long as the decision problem allows X' to copy Ut. Zo will be immaterial.
A potential remedy is give U1 a larger domain than X', and this is the idea behind the modified construc- tion shown in Figure 7b. In this scheme, two random bits are generated at U1. The outcome is Y== if X1 supplies one bit from U1 along with its index. A random bit is sampled at Zo, and W1 presents the Znth bit from U1 while X1 has domain of just one bit. Then, similar to our previous discussion of Figure 4b, the only bit from Un that Xn can reliably know is the Zo"h bit. Hence the only way to achieve the MEU is for X' to inform Xo about the value of W1, and for Xo to equal Xo = (Zo, X'). Importantly, this can only be done if Xo observes Zo, meaning that Zo is material for Xo-
How might we generalize this construction to the case of Figure 7c, where the info path has multiple fork variables? Instead of just Zo and U1, now have J+1 fork variables Uo.; which sample bitstrings, each one 2n as long as its predecessor. Each bitstring is then used to index its successor to obtain one bit. Formally, the observation is Zu = Uo. and at each collider Wi, we have W; Uy(Ug-1]. If the decision Xo copies the values from Zo and Wi:, we will say that it is "consistent" " with uo.J- The outcome Y in this graph must be defined in terms of only Xy and U,, so it cannot verify whether X₂- = Uo..- What it can do, however, is check whether there exists any assignments Ua that, taken with U, would produce assignments Eg, Wi.J that Xo is consistent with. We term this latter property "compatibility".
Definition 12 (Consistency and compatibility). Let w = (Wp. "I,...,,y!. where wo E BA and Wn E B for n 2 1. Then, w is consistent with u = {uo,.... UJ us E Bexr)(()) (i.e,, w ~ u) if wo = uo and Wn, [un11] for n 2 1. Moreover, w is compatible with u, E Bexpi (R) (i.e. w ~ uy) if there exists any uo.... 4,-1 such that w is consistent with uo...., u..
For example, in Figure 7b, z1 is consistent with (z),un) (zo, wi [=o]). More leniently, we will say that I is compatible with (2a, un) if 21 produces any bit from u1. L.e. T1 = (Ro, un [2]b]} for any b. This means that either (0,0) or (1, is compatible with = 0 and i1 = 01, but only the former is consistent with 2g = 0 and in = 00.
un) if æ1 produces the 20" th bit from U1, ie 21
The idca of the construction is that if the docision xo is inconsistent with the fork assignments, then it will also sometimes be incompatible with Uy, and therefore will be suboptimal. For example, in Figure 7b, suppose that we have assignments 20 = 0 and 11 01 and decision x = (1, Then, given the assignments
13

---

Published in Transactions on Machine Learning Research (12/2024)
Mo = 0 and #1 = 00, will have assignments 2, 0 and w1 0, which will in turn cause the assignment = (1, 1) however, this is not consistent with 20 = 0 and 4n = (0, 0), so the utility will be y 0. We now prove that this is also true for the more general construction of Figure 7e: if with strictly positive probability, the assignment of Xy is inconsistent with uo:J, then there will exist an alternative assignment Up.5 = " that produces the same assignments to the observations of Xo, but where Xo is incompatible with u'y.
Lemma 13. Let w = (wo...., wa) and in = (wo....., ..)) be sequences with wo. up E B Wjs Vj E B for j 2 1, and let J' S J the smallest integer such that wy # wy. Let uo...., uy be a sequence where Uy uy[Mp-1] = w for 123 J'. Then, there erists some u us such that w is consistent with u0:-.., U,, bul to is incompalible with u.-
The proof is deferred to Section B.5.
We can then use this result to argue that Zo is material in Figure 7c. If Zu is observation of Xu, then we achieve the MEU of 1 in the non-intervened model, where vo is compatible with No:J, and y 1 surely. If instead Zo is removed as an observation, then Xo cannot copy it, because Zo is constructed to contain k bits, where k may be an arbitrarily large integer. It follows that In is sometimes inconsistent with Uy:J, and hence sometimes compatible with uJ (by Lemma 13), so we will have y = sometimes (by the definition of Y), making the MEU less than 1. This argument will be fully formalized in Section 4.4.
4.3.2 A decision problem for any graph containing the materiality paths
We will now define a construction for any graph containing the materiality paths described in Lemma 11.
In most respects, the construction is a slight evolution of previous examples. Where the truncated info path m, is a directed path, the construction will generalize Figure 3a, and the decision X, will be tasked with copying the value at an intersection node Tü. Where m, is not a directed path, the construction will generalize Figure 7c, and X; will be tasked with producing bitstring that is compatible with forks U...J.-
For this more general construction, we do, still need to fix some notation. The first issue is that the matcriality paths may overlap. To accommodate this possibility, we will define a random variable VP for each variable in a materiality path p, then to derive the overall materiality SCM, we will define V as a Cartesian product over each VP. The sole exception is the outcome variable Y, which will be defined by a sum over every YP. For any set of paths p, we define Vp VP.
A second issue is that variables will often depend on their parents along the same path somothing that can compactly describe as follows.
Definition 14 (Parents along paths). When vertex V has a unique parent V along p. Pa(Vr) VP, and for set of paths p', let Pa(VP') Xpep Pa(VP). For collider V in truncated info path m, T. Y. let the parent nearer T; along m, be (V), and the parent nearer Y be Pan(V).
For example, a non-outcome child V of A along the control path will be assigned V = Pa(V').
A third issue is that variables must sometimes depend on variables that do not lie in their paths, and this occurs in three cases:
in the truncated info path, the child of the intersection node must depend on all components TP: not just T,m
in the auxiliary path, the second node must copy the value of the collider from the info path W
when the intersection node is a collider that also the source node A of the control path, then it must depend on not just Pa(TPP), but also the exogenous variable E..
We define the following shorthand to deal with these three cases:
Definition 15 (Out-of-pate parent relations). For truncated info path m,, let:
T.:
if Pa(V""))= m and (V) = T.P.
if (V = Tym
Pa" (VTL) =
Pa(Vm.)
otherwise
(V
otherwise
14

---

Published in Transactions on Machine Learning Research (12/2024)
U(
U(Bexpooo (b))
Uo.1
U0 [U,1]]
Uo [0
Uo.Jo
W6,2
Wo,Jo
U(B
Ti
Z1
pa
(T))
A
To
Zo
Xo
T
Z1
X
T
Z
X1
Y
10 [A]
To
Zo
Xo
W1,1
Ti
U1.0
U(B2*
U1
U(Boxp?
((K))
(pay) = [pa (oo) com.w. Jo
+ +Ppa(YP comww. unJi +[a = ty
Figure The materiality SCM: a general SCM where To material for Xo-
W Pa(Vns)
if Pa(V W
For an auxiliary path rays let Pa PV*(V
otherwisc
For the intersection node let:
x Pa(PP)
is otherwise
Pa (TP')
PPa(TP))
Using this notation, we now define the materiality SCM as follows. Definition 16 (Materiality SCM). Given graph containing the materiality paths, we may define the following random variables.
In the control path, d: A - Y, let:
the source be Ad ga where EA U(B*), the positive integer l is the smallest such that 2* > (k: + c)be, the maximum number of variables that can be contexts of one decision is == maxxex(s)|CxI) and e is the maximum number of materiality paths passing through any vertex
the graph;
every non-endpoint V be pd Pa(V").
In each truncated info path that is directed, m, : T; -- Y, let:
the intersection node T have trivial domain;
each chain node be V Pa" (T="(mm.)
the outcome have the function fym: (pay) = [[pa(YP:) pap (Y
In each truncated info path that is not directed, --- Wi, W.,, Y, let:
each fork be - eWW ((B=))((++)))111)) where |pl the number of paths in p::
each chain node be yd Pa" (VV(V
15

---

Published in Transactions on Machine Learning Research (12/2024)
Vo.1
UI.E
U1.1
U1.E
To
Xo
T
PY
Y
Cam Xo
(o(Ti)
X1
PY
(a) The intersection node 'i chance node.
(b) The intersection node is decision. The of Xn are divided into C (its parent along the info path), and Cxp (the other parents).
Figure 9: The cases where the intersection node Ti is chance node, or a decision
each collider be W (V [Paj (Vm.)); }};
each intersection node be T. Pa(Vmm PPa (TP))] if the info path begins T; - otherwise it
has empty domain;
the outcome have the function fym: (pay) = [pa(Y is compatible with pa" (Y
In each auxiliary path rij Wis + 1/2 -- Y, let:
each chain node have V = Pa Pa" (v")))
each source Way have trivial domain.
SiSimax Ym; and non-outcome variables Then, let the materiality SCM have outcome variable Eimo Sismmas
V pd 1. Bimnn SiSimax) VP.
Note that this defines an SCM because each variable is a deterministic function of only its endogenous parents and exogenous variables.
In this non non-intervened model, we have y 1, surely.
Lemma 17. In the non-intervened model, the materiality SCM has Y = imaz ini + 1, surely.
The proof follows from the model definition, and is supplied in Scction B.4.
We also know that each utility term ym: is upper bounded at one, in order to obtain the MEU, each y must equal 1, almost surely. Lemma 18. policy N for the materiality SCM, has px (y <1)> 0 for any i, the MEU is not achieved.
Proof. We know that BT[ Eipg Sistun m (Definition 16), for all i, y < 1 surely. So, if Imax imi + 1, which underperforms the policy that is followed
pa (y < 1) > 0 for any i, then ET| in the non-intervened model (Lemma 17).
4.4 Proving materiality in the materiality SCM
We will now prove that in the materiality SCM, if Zu is removed from the contexts of Xb, then the perfor- mance for at least. one of the utility variables ym; is compromised, and so the MEU is not achieved. The proof divided into two cases, based on whether the child of Xo along the control path a non-decision (Soction 4.4.1) a decision (Soction 4.4.2).
16

---

Published in Transactions on Machine Learning Research (12/2024)
4.4.1 Case 1: child of Xo along d is non-decision.
We will now prove that the child of Xo along the control path is a non-decision, i.e, Xo is not the context Zi, then F] <1.
In this case, either Xo is the last decision in the control path, or otherwise there must exist an intersection node Ti, as shown in Figure 9a. If the former is true, then it is immediate that the value 2o is transmitted to Y along the control path, based on the model definition. As such, Yo can directly evaluate the decision Xo- For the latter case, we want an assurance that downstream decisions will pass along the value of X, as was the case in Figure 4b. Such an assurance is provided by the following lemma, which states that whenever an intersection node T; is a chance node (as Ti is) the value 4 is transmitted to Y by every optimal policy.
Lemma 19 (Chance intersection node requirement). If in the materiality SCM, where T2 is a chance node, a policy π has Pa (Pa(T?")) = P)(YP:)) < 1, then pM (ym,. <1) > 0.
First, we prove the case where m; is a directed path. In this case, m, copies the value the to Y, which y checks against the value pa(yP)) received via the control path. Maximizing ym, then requires them to be equal.
Proof of Lemma 19 when m, is directed path. We have fy (paym.) [[a(Y = pa(YP:)]] (Defini- tion 16). Also, Pa(Ymi)= = T. = Pa(TT) surely, where the first equality follows from Definition 16, while the second follows from Definition 16 and T; being a chance node. So, if pa (aclyii)=Pa((PPP < then p* (Y"m:1)) <1.
We now prove the case where m, is a directed path. In this case, if the assignment pa(YP:) transmitted along the control path differs from the value pa(T.")) that came in to the intersection node T;, then just as we established for Figure 7c, there will exist an assignment u1,1J, to the fork nodes in m, that gives an unchanged assignment to colliders v. but where pa(YP.) is incompatible with u.,
Proof of Lemma 19 when my is not directed path. Let index the forks and colliders of my T. V4,1 t-- U111 --+ W4,1 +-- ... Wa,J, 6-- Us,J, --+ Y. Choose any assignments pa(T.")) & pa(YP:) that occur with strictly positive probability. Then, there must also exist assignments Pa( Pa(Ymiriau)) pa(Y (ara)))) U...., = u1:J, and W.,1.. = W1:,, such that
pr ("'a(TT)) pa(Ypum ),(P, uIJ., wI.J.) > 0.
By Lemma 13, there also exists assignment U.,1., uh,,, such that pa(TP'), W1:J, is consistent with ano. and pa(Y?"), pa(Yr....)) is incompatible with n'y,- Now, consider the intervention do(U,,,,, = u Since Tr is a chance node, every collider in m, is a non-dccision, and is assigned the (unique) value consistent with pa(T."), ), uh.,.- Furthermore, pa(T."), WI.,, is consistent with pa(T?)), w(.J, so the intervention does not affect the assignments to these colliders. Moreover, from Definition 16, no variable outside of m, is affected by assignments within mi, except through the colliders. Therefore:
pd (TT(p(YP:) ), pa(Y Pa(Y = v/y, do(U,,1.1 = =v(,,)) > :: p. 0 (lo(U,,,.,, w(,):)) >
pa(rriuu) not compatible with v'y,)
:. (mmmm 0 U,.., = u/i..) > 0
(Un1 are unconfounded, so pM PV = u'(,,))= PM PM(V (VIU.... "Vi.,,=u'... =u'..))
:. :. (" = 0) >
(Pm (2(( > 0).
If m, is not a directed path, then we will require that the values pa (YT..:))) are passed down the auxiliary paths, not just the value pa(Y from the control path. Specifically, pa(Y")),, pa(Y must be consistent with pa(YP:), u.ndd, where u.u.J denotes the values of forks on the info path.
17

---

Published in Transactions on Machine Learning Research (12/2024)
Lemma 20 (Collider path requirement). If the materiality SCM has info path my that is not directed, and under the policy a there are assignments ) (PPiriiaa)) to parents of the oulcome, and my Uni. = to the forks of mi, with pT (pa(Y PPPPsa (.i...)) > 0 and where palY pu(YPu) is inconsistent with po(YP:), U s.I.d then P"(Y" < <1) > 0.
mh
The idea of the proof, similar to Lemma 19, is that whenever the bits transmitted along the auxiliary paths deviate from the values wi,1:;; of colliders in ma there exists an assignment u',1.,, to forks in my that will render the colliders, and hence the decision 2; unchanged, while making z; incompatible with uJ,, and thereby producing y < O. A detailed proof is in Section B.5.
Before we prove that Zo is material in this case, we require one more intermediate result: that Zo cannot be chosen deterministicallyy, if it is a decision. The idea will be that random information is generated at A, which each of the docisions, including Zo. is required to pass along the control path; we can prove this as a corollary of Lemma 19.
Lemma 21 (Initial truncated info path requirements). If in the materiality SCM does not satisfy: pR (Pa((dd) = A4) < 1. then the MEU is not achieved.
Proof. From Lemma 11, the control path d begins with chance node. So, the first decision X in d must have a chance node Zimin as its parent along d. Furthermore, the intersection node Timi must be an ancestor of Ziiiin along d, so it is also a chance node. So it follows from Lemma 19, that any policy π must PaPYP )) = if it attains the MEU. As Tim.. is in the control path, we have E Piuii (by Lemma 11) so T - Pa(Yd) is also required. Morcover, all of vertices in the segment A -- Timm of d are chance nodes, because Ximin was defined as the first decision in d, and Timin precedes it And, each chance variable Vd on the control path equals its parent Pa(V')) (by Definition 16), so A = imin: and thus Ad a.s. Pa(Yd) is required to attain the MEU.
satisly pT PTTTT (Trmmi
We can now combine our previous results to prove that it is impossible to achieve the MEU, Zo is not a context of Xo, in the case where Ti does not exist, or is a non-decision.
Lemma 22 (Required properties machievable if child is a non-decision). Let M be materiality SCM where the child of Xo along d is a non-decision. Then, the MEU for the scope S canmot be achieved by deterministic policy in the scope Sz (equal to S, encept that Zo is removed from Cx,).
The logic is that if child of Xo in the control path is a non-decision, then the value of Xo is copied all the way to Pa(Y') (Lemma 21). Furthermore, Z &.s. Pa(Y")) is necessary to achieve the MEU (Lemma 19). But the materiality SCM has been constructed that the non-Zo parents of Xo do not contain enough bits to transmit all of the information about Zg, so the MEU cannot be achieved. The proof is detailed in Section B.6.
4.4.2 Case 2: child of X, along d is a decision.
We will now prove that if, shown in Figure 9b, the child of Xo along d is a decision and the decision Zo is not available a context of Xo, then B[Yi] < 1. The overall argument will be that if Xo cannot observe Zo, then it cannot convey the value of U1,1 to the child X1, and so X1 will not be able to be consistent with uo:h+
Our first lemma will state that if a decision X,-1 does not distinguish U,,, and 222 is a bitstring wherein all of the digits are the same, then U²1 cannot influence Y, other contexts of T,, colliders Wi,,.,, or forks U22...- A couple of details of this lemma are worth remarking upon. First, it assumes that T, X,-1 something that is always true for = 1 in the case that Zı Xo- Second, it assumes that nr. is a deterministic decision rule, which will simplify the proofs without importantly weakening it, because every decision problem has a deterministic policy that performs as well as the best non-deterministic policy.
Lemma 23 (If next fork is repeated, then fork only influences intersection node). If. in the materiality SCM:
the intersection node T3 is the vertex X1-1,
18

---

Published in Transactions on Machine Learning Research (12/2024)
Tr; is deterministic decision rule where TT, (c (m (4,1) Tr. (m (Ti,
(/21)) for assignments
U4,1, u,,,"',1 to the first fork variable, and c (T;) to the conterts of Ti not on mi, and
W...., = Wi,1.J, and U1..J, = U1,2.J, are assignments to forks and colliders in my where each u4.j consists of just Wis repeated expl + 1psl - 1) times, then:
pa (mm((PPora) (TT")T.), Watso 4422. [do(ur,)) pM (pa(Y (T.) Wi.le 14,2.1 doo((,,)):
The proof follows from the definition of the materiality SCM, and it is detailed in Scction B.7.
We can now prove that if deterministic policy does not appropriately distinguish assignments to U4,, then the ith component of the utility will be suboptimal, i.e., [[ < 1.
Lemma 24 (Decision must distinguish fork values). If in the materiality SCM:
the intersection node T3 is the verter Xi-1, and is deterministic policy that for assignments u1,1, u/,1 to Us where us,1 M1.1#1/11 has TT. (c Th (T,), 11,1)= NT, (c "h: (T,)), 1) for every CT. (T.) =c my (T.),
(t)
then pT pTm < <1>>
The idea of the proof is that if 4ni and uf,1 differ, there will be some assignment pa(YP:) such that "i (PaP)))) and 1 [Pa(PP)) differ. When Pa(YP:) pa(YP:) and U,, M4,1. then Pa(Y will as- sume one value. But if we intervene uh,1, 41,2,4, then the value of Pa(Y*))) will be incorrect, making Pa.a).) inconsistent with Pa(YP:, Ui,..)) so the maximum expected utility is impossible to achieve. The details are deferred to Section B.8.
This allows us to prove that when the child of X, along d is a decision, the MEU cannot be achieved unless Zo context of Xo.
Lemma 25 (Required properties unachievable child is a decision). Let M be the materiality SCM for some scoped graph Gs, where imax 0 and Tr is decision. Then, there crists deternánistic policy in the scope So that achieves the MEU.
To prove that deterministic policy in Szo/Xx, can achieve the MEU (achievable with the scope S), we will show that if deterministic policy satisfies p= p=(Pa(Yd)) Ad) 1, required by Lemma 21, then the domain of Xo x C2." is smaller than the domain of CX2 so Equation (t) will be satisfied, and thus the MEU cannot be achieved. A detailed proof is presented in Section C.
We now combine Lemmas 22 and 25 to prove the main result.
Proof of Theorem 8. Any scoped graph G(S) that satisfies conditions (A-C) contains materiality paths for the context Zo of Xo (Lemmn 11), and has a materiality SCM (Definition 16) compatible with G(S). In this decision problem, whether the child of X, along is or is not a decision, the MEU cannot be achieved by a Zo (Temmas 22 and 25). And stochastic policies
deterministic policy unless X, is allowed to depend never surpass the best deterministic policy (Lec & Barcinboim, 2020, Proposition 1), such policy achieve the MEU, and therefore Zo is material for Xo-
5 Toward more general proof of materiality
So far, via Theorem 8, have established the necessity of condition (I) of L.--fatorizaailiity for immateri- ality. We now outline some steps toward evaluating the necessity of conditions (IIIIII) of L.B-fattorzzallitty as well as the further condition in (Lee & BBrriibbii, 2020, Thm. 2).
It trivial to satisfy either one of (II-III) in isolation. Condition (III) merely requires that we choose an ordering < such that the parents of cach docision X are prior to X, while the descendants come afterwards, and such an ordering clearly exists in any acyclic graph. Condition (II) can also be satisfied by placing all of the variables in C at the start of the ordering <.
19

---

Published in Transactions on Machine Learning Research (12/2024)
However, there does not always exist an ordering that satisfies (II-III) simultaneously. Indeed, whenever there does not, we will be able to prove the existence of some info paths and control paths. If we could use these paths to establish materiality, then we would have proved that (II-III) are necessary conditions. So far, however, we have only been able to carry out the first step - defining the paths - and difficulties have arisen in using those paths to define an SCM that exhibits materiality. In this section, we will outline what info paths and control paths can be proven to exist, and then outline the difficulties using them to prove materiality.
5.1 A lemma for proving the existence of paths
When the variables 2, X', C² are not faclorizable, we can prove the existence of info and control paths. Lemma 26 (System Exists General). Let 9s be a scoped graph that satisfies conditions (A,B) from Theo- rem 8. Z (Z), X' 2 Ch(Z), C' = Cx \ (X'UZ), Z), U = 0 are not LB-factorizable, then there erists pair of paths to some C' CYUY:
an info path m ----C. C², active given EXUU' and control path d X --9 C² where X E X'.
A proof is supplied in Section D.1. The intuition of this proof is that each of the conditions (I-III) implies a precedence relation between a pair of variables in V'UY. Each of these precedence relations can be used to build an "ordering graph" over V U. If the ordering graph is acyclic, then we can let < be any ordering that is topological on the graph, and then X', C", U are I.B-factorizable. Otherwise, we can use a cycle in the graph to prove the existence of an info path and a control path. By iterating over these cycles, we can obtain series of info paths and control paths that terminate at Y.
The resulting paths are in some cases quite useful for proving materiality. For instance, we can recover the pair of info and control paths used in Figure 4b. To prove that Z is material for X, we can start by choosing X' = (X,X', C' = {Z', W}, and U' = 0. Then, Lemma 26 implies the existence of an active path from Z to some Descx n', so we see that the first info path is the edge Y. Since Y is a descendant of X, we also have the first control path, X + Z' + X Y. We must then obtain some paths that exhibit why z' is itself useful for the decision X to know about, and to influence. To do this, we can reapply Lemma 26 using the sets X' = (X,X'), Z {Z'), O {Z, W}, and U' = 0. We then obtain the new info path Z' + W& + U + Y, and the new control path X" + Y. The SCM in Figure 4b uses these paths to prove Z is material for X.
5.2 A further challenge: non-collider contexts
In some graphs, it is not clear how to use the info and control paths from Lemma 26 to prove materiality, because non-collider nodes on the info path may be contexts. (In previous work, this possibility was excluded by the solubility assumption (van Merwijk et al., 2022, Lemma 28).) We will now highlight one case, in Figure 10, where it is iveatively clear how this challenge can be overcome, and one case, Figure 11, where it is unclear how to make progress.
In the graph of Figure 10, we would like to prove that Zu is material for Xp. Using Lemma 26, we can obtain the red and blue info paths as shown, and the corresponding control paths, shown in darker versions of the same colours. The usual idca of Definition 16, shown in Figure 10a, would be that X, must observe Zo in order to know which slice from V is presented at its parent Xi. In this model, X, would play two roles, one for the red info path, and one for the dark blue control path. As collider on the red info path, its role is to present the 7 bit from V. As the initial endpoint of the blue control path, its role is to copy the assignment of Zo- The problem, however, is that X, then does not need to observe Zu in order to reproduce its value, because this value is already observed at X1, and so Zo is not material.
To remedy this problem, we can construct an alternative SCM, where the value of Zo is "conccaled", i.c. it is removed from the other contexts, Cz. \ Zp. We now define X1 as V[Za] (i.e. we have removed Zo). leaving the decision X, with domain of only one bit. At C, we impose some random noise; that is C is
20

---

Published in Transactions on Machine Learning Research (12/2024)
not always perfect copy of Zo. The result is shown in Figure 10b. When this model is not intervened, an expected utility of [B[Y] = 10.99 is achieved, because the red term in Y always equals 10, while the blue term has an expectation of 0.99. (This is the MEU, because there is no way to improve the blue term to have expectation 1 without decrcasing the expectation of the red term by at least 0.05.) If instead Zu is removed as a context for Xg, then the expected utility can only be as high as [E[Y] = 10.95. To understand this, we restrict our attention to deterministic policies, and note that order for the red term to be better than a and the red term will have an expectation of 9.95, we must have X1 V[O] and Xo X1) and then the blue term will have an expectation of 0.5. In either case, performance is worse than 10.99, so Zo is material for Xo-
coin flip (with an expected value of 5), we would either need to have Xo (C)
U UB)
U(B2)
U(B)
U(22)
V
70
V
P 20) = 0.99 P(C=1- 2010) 00.01
X
C
(X1(0),
C
[20]
ViZol
(o (Zo)
(Zo, X1}
fy (pay) = [u[zo[0]] xo ro[l + [c[0] c[l]]
fy(pay) 10 [0]] ro[l]l + [c = zo [0]]
(u) A model with zero Vol.
(b) Zu material for Xo
Figure 10: Two allernative models that use the same two info paths, red and blue.
The problem is that concealing the value of Zo does not work for all graphs. To see this, let us add two decisions, X2 and X3. to the graph from Figure 10, to thereby obtain the graph in Figure 11. Let us retain the materiality SCM from Figure 10b, except that X2 and X3 copy the value from C' along to Y. One might expect that Zo should still be material, but it is not. Now, there is a policy that achieves the new MEU of 11 by superimposing the value of Zo on the assignments of decisions X2 and X3. In this policy n, F = v[zo], 2²2 = zu @ 2g, 23 = 22 O 20, and Fy = 22 @ x3 = 2u where Q represents the XOR function. Under л,, the rod term equals 10 surely, while the blue term equals 1 surely, i.e. the MEU is achieved, and π is a valid policy even if Zo is not context of Xo, meaning that Zo is not material for Xo-
In summary, whenever Z 3 Zo. X' 3 Xo, C", U are not LB-factorizable, then we can find some info and control paths for Zo and Xo, but then Xo can recover the value of Zo. making it possible to achieve the MEU even when Zo is removed as a context of Xg. In some graphs, we can devise an alternative SCM that conceals the value of Zo. But in others, a policy can superimpose the information from Zo on other decisions, such as X2 and X2 in Figure 11, so that Xn can recover the value of Zo, making Zo immaterial for X, once again.
Overall, in order to establish a complete criterion for materialily, we would need some new method to prevent the information from Zo from being superimposed on other decisions. So, in order for future work to achieve this goal, we predict that it will have to make further modifications to the construction from Definition 16.
6 Conclusion
In graphical models of decision-making, a key challenge is to ascertain which variables can be deemed immaterial based on the graphical structure alone. This problem is a long-standing one, a solution to which could allow influence diagrams be solved more efficiently, and aid in analyzing the safety and fairness of AI systems. A key condition for establishing immateriality is LB iB-factorizability We have found that if no context. can satisfy condition (T) of L.B-factorizability then any context is material in at least one decision
21

---

Published in Transactions on Machine Learning Research (12/2024)
~ UIB
Zo
~ ~U(
P 0.99
P 20) =0001
A1
X
V Vo00
A2
A3
X
X2
Y
(Zo, X1)
fr(pay) = [0[0[r][0]] - æo [1]] + [ - xo [0]]
Figure 11: A model with zero
problem that respects the graphical constraints. In the process of devising our proofs of materiality, we encountered and addressed several new kinds of problems:
if, as Figure 5, the variable Z; whose materiality we are trying to establish is a decision, then we must choose an info path so that the value of Z, cannot be determined by other contexts;
if, as in Figure 7, the info path begins with a variable Zo that is a context not just of the target decision Xo, but also some other decision X', then must construct the decision problem that
X' cannot copy Zo in its entirety;
if, as in Section 4.4.2, the control path contains consecutive decisions, then we give large domains to the source A, and all of the variables on the control path, so that this information can only possibly be copied by these decisions.
As a next step towards establishing a complete criterion for materiality, we then considered the more general setting where no context can jointly satisfy conditions (I-III) LB-factorizabilityy In this setting, we have identified info paths and control paths that appear useful for proofs of materiality, and we can apply an adjusted version of our construction to this case. However, in settings there ways for optimal performance to be achieved even when Zo is not context of Xo, and so have not yet found successful proof of materiality in this more general setting.
Thus, the challenge proving a complete critcrion for matcriality for insoluble graphs currently remains open.
Acknowledgements
Thanks to Min Woo Park and Tom Everitt for comments on draft versions of this manuscript. Sang- RS-2023-
hack Lee was supported by the ПITP ASS-2022-12220553/2222 and NRF 00222663/25%) grant funded by the Korcan government.
References
Carolyn Ashurst, Ryan Carey, Silvia. Chiappa, and Tom Everitt. Why fair labels yield unfair predictions: Graphical conditions for introduced unfairness. arXie preprinl ar arii:22202. 10816, 2022.
Ryan Carey and Tom Everitt. Human control: definitions and algorithms. In Uncertainly in Artificial Intelligence, pp. 271 281. PMLR, 2023.
Tom Everitt, Ryan Carey, Eric Langlois, Pedro A Ortega, and Shane Legg. perspective. In AAAT, 2021.
Agent incentives: A causal
22

---

Published in Transactions on Machine Learning Research (12/2024)
Enrico Fagiuoli and Marco Zaffalon. A note about redundancy in influence diagrams. International Journal of Approrimate Reasoning, 1998.
Sebastian Farquhar, Ryan Carey, and Tom Everitt. Path-specific objectives for safer agent incentives. AAAI, 2022.
Dan Geiger and Judea Pearl. On the Logic of Causal Models. Machine Intelligence and Pattern Recognition, 9:3 14, 1990.
Joseph Halpern and Max Kleiman-Weiner Towards formal definitions of blameworthiness, intention, and moral responsibility. In Proceedings of the AAAl conference on artificial intelligence, volume 32, 2018.
Ronald A Howard. Information value theory. IEEE Transactions on systems science and cybernetics, 2(1):
22-26, 1966.
Ronald A Howard. From influence to relevance to knowledge. Influence diagrams, belief nets and decision analysis, 1990.
Ronald A Howard and James E Matheson. Influence diagram retrospective. Decision Analysis, 2(3))144-147 2005.
Matt J. Kusner, Joshua R. Loftus, Chris Russell, and Ricardo Silva. Counterfactual Fairness. In NIPS, 2017.
Steffen L Lauritzen and Dennis Nilsson. Representing and solving decision problems with limited information. Management. Science, 12(3) 1235-1113112 2001.
Sanghack Lee and Elias Barcinboim. Characterizing optimal mixed policies: Where to intervene and what to observe. Advances in Neural Information Processing Systems, 33, 2020.
James E Matheson. Using influence diagrams to value information and control. In R. M. Oliver and J. Q- Smith (eds.), Influence Diagrams, Belief Nets, and Decision Analysis. Wiley and Sons, New York, 1990.
Judea Pearl. Causality: Models, Reasoning, and Inference. Cambridge University Press, edition, 2009.
ISBN 9780521895606.
Ross D Shachter. Evaluating influence diagrams. Operations research, 34(6):871 882, 1986.
Ross D Shachter. Decisions and Dependence in Influence Diagrams. In Proceedings of the Fighth International Conference Probabilistic Graphical Models, volume 52, pp. 462-473, 2016.
Ross Shachter and David Heckerman. Pearl Causality and the Value Control. In H. Geffner Dechter and J. Y. Halpern (eds.), Hewristics, Probability and Causality: Tribute to Judea Pearl, pp. 431-447. College Publications, 2010.
Chris van Merwijk, Ryan Carey, and Tom Everitt. A complete criterion for value of information in soluble influence diagrams. AAAI, 2022.
Thomas Verma and Judea. Pearl. Causal Networks: Semantics and Expressiveness. In Uncertoinly in Artificial Intelligence (UAI), pp. 69 78, Amsterdam, The Netherlands, 1988. North-Holland Publishing
Co.
Francis Ward, Francesca Toni, Francesco Belardinelli, and Tom Everitt. Honesty is the best policy: defining and miligating ai deception. Advances in Neurul Information Processing Systems, 36, 2024a.
Francis Rhys Ward, Matt MacDermott, Francesco Belardinelli, Francesca Toni, and Tom Everitt. The reasons that agents act: Intention and instrumental goals. AAMAS, 2024b.
23


Reviews:
[{"review_id": "DHQUh0YCt4", "reviewer": "Reviewer_oetD", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\n* The problem setting and its motivation are well explained.\n* Various concrete examples and diagrams are used to illustrate the issues and contributions.\n\nWeakness:\n* Related studies and references cited in the paper seem limited. \nThis study is positioned as a follow-up to (Lee & Bareinboim, 2020).\nThe only other comparisons mentioned are mainly (Everitt et al., 2021), (Farquhar et al., 2022), and (Merwijk et al., 2022).\nIf these are all the major relevant studies, the number of readers interested in this paper may be limited.\nIt was also surprising that while the problem setup seemed natural, previous studies were limited to these.\nIf the authors have any thoughts on why there is limited research on the problem setting (or similar ones) in this paper,\nI would like to see their explanation.\n* Many roughnesses and typos are found in the textual expression. \nFor example, p. 20 concludes with the following sentence, which I think is difficult to understand what exactly is being asserted.\n> It seems that new insights are needed to solve this superimposition problem, and that therefore that we will need new insights to establish a complete criterion for materiality in insoluble decision problems.\n\nOther issues of presentation are listed in [Minor comments].\n* It is difficult to interpret the claim of the main result (Theorem 8) well. In particular, since C in Theorem 8 is apparently different from that under the previous study, it would be better to explain how this can be interpreted.\n\n\n[Minor comment]\n* p.1, Abstract: may used to evaluate ... <- may be used to evaluate ... ? \n* p.1, Abstract: as immaterial For ... <- as immaterial. For ...\n* p.1, last sentence in the second paragraph in Introduction: The means <- This means\n* p.1, last sentence in the second paragraph in Introduction: $1 - 0.5 = 0.,$ <- $1 - 0.5 = 0.5,$\n* p.2, first sentence in the last paragraph: there the criterion <- there is the criterion\n* p.3, first sentence in the fourth paragraph: (2020, thm. 2) <- (2020, Thm. 2)\n* p.4, Definition 2: Symbols of the domain of $\\pi$ are not defined?\n* p.4, sentence just before Definition 3: Once a policy is selected <- Once a mixed policy scope is selected ?\n* p.5, last sentence: $Y$ ,and <- $Y$, and\n* p.7, second sentence of the second last sentence: in in Figure 4 Suppose <- in Figure 4. Suppose\n* p.8, second sentence: in this paper <- In this paper\n* p.18, second last paragraph: so it instead ...?\n* p.19, third paragraph in the last paragraph of Section 5.1: two definitions of $C'$", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper considers decision-making problems expressed by structural causal models.\nIn particular, it attempts to provide a characterization based on graph structure of variables that need to be observed for optimal decision making.\nThe characterization given in the previous study was limited to a special graph called soluble, whereas this study considers the case where this restriction is removed.\nThis paper shows that some of the conditions presented in existing studies are necessary conditions for this more general setting as well.\nIt also discusses the difficulty of identifying complete characterization through several specific examples.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "I would like to ask the authors for their views on the points listed under “Weakness” above.\nIn addition, the points listed in the “Minor comment” are not all that large, and I am concerned that there are many more points that need to be revised.", "broader_impact_concerns": "NA", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "8Kp9c58ydf", "reviewer": "Reviewer_eibw", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- The paper is well-organized. In Section 3, the authors clearly explains the proof ideas of important previous studies that the proof of this paper is based on. Although the proof of the main theorem is extremely complicated, this organization helps readers understand the main proof ideas gradually. The concrete examples with readable figures are also very helpful.\n- The direction of this paper is undoubtedly important. This paper aims at providing a necessary and sufficient condition for materiality. This is a fundamental research question in causal models and can have a great impact on various fields of machine learning (However, this paper provides only a partial result toward this goal).\n\nWeaknesses:\n- Although the organization is excellent, the writing quality of each sentence could be polished. As I write in Requested Changes, there are many small typos. Since the proof is complicated and requires readers to understand in detail, these small mistakes are confusing.\n- This paper provides only a sufficient condition. I cannot judge how this result is close to a complete characterization. I am not sure if only a sufficient condition is worth the effort of such a complicated proof.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper considers whether a target value can be improved by interventions to structured causal models (Pearl, 2009). The set of possible interventions is specified by mixed policy scopes, which consist of variables to be intervened (decision variables) and variables that each decision variable can be based on (context variables). This intervention model follows the setting of Lee & Bareinboim (2020).\n\nA goal of this research topic is to judge whether or not each context variable can improve the target value **only from the graph structure** of causal models. Precisely, given a context variable for some decision variable, the question is whether there exists a concrete probability distribution that aligns with the given causal graph in which an optimal decision based on the context variable is strictly better than an optimal decision that ignores the context variable. This property of the context variable is called \"materiality\" in this paper.\n\nIf there exists only one decision variable, materiality is known to be equivalent to a simple path-blocking property. On the other hand, if there exist multiple decision variables, a characterization of materiality is known only for a special class of graphs called \"soluble graphs.\" This paper proves a sufficient (but not necessary) condition for materiality in general graphs. The proof significantly extends an idea of control paths, which connect context variables and the target variable without touching decision variables, and info paths, which connect decision variables and the target variables. For any graph satisfying the proposed sufficient condition, the authors construct a probability distribution in which observing each context variable improves the target value.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Minor requested changes:\n- There are many small typos: \"may used to\" in the abstract, \"hte\" instead of \"the\", \"in in Figure 4\" , and many others. I recommend the authors to review the manuscript from beginning to end and fix them.\n- The notation $\\pi_X$ seems to be used in Definition 2 and Definition 7 for different meanings. It would be better to prevent this if it is possible.\n- What is the meaning of \"new parent\" in the statement of Theorem 8?\n- In 4.2.2, it is claimed that \"A --> Z_0 has length of either 0 or 1\" but actually not in Figure 6.\n- In 4.3.2, what is the difference between $V_p$ and $V^p$?\n- The sentence is incomplete with ending \"so it instead\" in page 18.", "broader_impact_concerns": "The contribution of this paper is theoretical, and there is no ethical concern.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "uNuJtEwLI5", "reviewer": "Reviewer_YwNK", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Strengths\n- The necessary conditions for the immateriality of insoluble graphs have been theoretically analyzed with a detailed proof. This result can be valuable to the community focused on structural causal analysis and decision problems.\n### Weaknesses\n- The clarity of the paper is lacking, and the overall presentation quality is not high. Many sentences are difficult to understand due to various issues, including grammatical errors and insufficient explanations. Even the abstract is hard to comprehend, as it is written in an unusual manner with several grammatical mistakes. Since clarity of narrative and the strength of arguments are among the most important acceptance criteria, these aspects need significant improvement.\n- The findings of this paper are quite specific. While I believe the paper holds some scientific value, considering another acceptance criterion—whether the findings will interest TMLR's audience—I feel that the scope is too narrow and specific. The content is difficult for a broad machine learning audience to understand, and the proof is highly technical. Therefore, a more specialized statistical journal might be a better fit for this paper. If the authors believe that their findings will appeal to a wider machine learning audience, this should be more clearly explained and emphasized in the paper.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper investigates insoluble decision problems, where soluble graphs are those that retain important past observations. The authors theoretically establish the necessary conditions for the immateriality of insoluble graphs.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "No", "audience_explanation": "", "requested_changes": "Please address the weaknesses mentioned above, particularly in terms of improving the overall presentation of the paper and providing a clearer motivation for the problem being studied.", "broader_impact_concerns": "I do not have any concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The tackled problem is relevant and the proposed approach is sound. However, as pointed out by some of the reviewers I think there are concerete concerns about the clarity of the writing which has been partially addressed in the revision. I suggest the authors to go through the comments from the reviewers and to address the main concern about the clarity of the writing of the manuscript.
Decision: Accept (poster)