Efficiently Finding Conditional Instruments for Causal Inference

1 Introduction

When studying a system that cannot be manipulated, we can only attempt to infer its cause-effect relationships from observational data. Conclusions drawn from observational studies are confounded when the putative cause and effect variables share common unobserved causes. This threat to causal inference is sometimes called the endogeneity problem [Antonakis et al., 2010]. In practice, the endogeneity problem is often addressed by making the parametric assumptions needed to justify a linear regression model. Under these assumptions, it is possible to remove confounding by using an instrumental variable (instrument, IV) [Angrist et al., 1996; Imbens, 2014a].

For instance, suppose our system under study can be described by the set of structural equations depicted in Fig. 1A, then (assuming all arrows describe linear functions and all variables have variance 1) we have Cov(X, Y ) = γ + λ1λ2, which differs from the causal effect γ. Yet, given that Cov(Y,Z) = βγ and Cov(X,Z) = β, we can estimate the causal effect as Cov(Y,Z)/Cov(X,Z). This approach is called the IV method, which is valid under two conditions called exogeneity (Z shares no causes with and is not caused by Y nor U) and exclusion restriction (Z only affects Y through X). Both conditions hold in Fig. 1A. The conditions are untestable 1 and have to be justified from domain knowledge. However, the IV method can sometimes also be applied if exogeneity does not hold. For instance, Z is not exogenous in Fig. 1B, but by conditioning on W we get Cov(Y, Z | W)/Cov(X, Z | W) = γ. In such cases, we call Z a conditional instrument, and we say that W instrumentalizes Z.

This begs the more general question: When, and how, can a variable be instrumentalized using a covariate set W? A graphical criterion exists to answer this question when a causal diagram (directed acyclic graph, DAG) is given [Pearl, 2009], but it requires exponential time to find W. Indeed, we show here that this is an NP-hard problem. Nevertheless, we prove that the following related question can be answered constructively in polynomial time: Given a DAG, does any (perhaps conditional) IV exist? In other words, finding a conditional IV is easier than instrumentalizing a given variable. This surprising result implies that we can always efficiently find a conditional IV in a DAG if one exists.

Our paper starts with a brief outline of our notation and graphical formalisms. We divide our results into a conceptual and a computational part: Section 3 introduces a new threelevel hierarchy of increasingly general IV definitions, which forms the basis for our results. Section 4 presents algorithms and hardness proofs.

1 More precisely, instrumentality is testable to some extent if all variables are discrete [Pearl, 2009]. However, most practical methods assume X to be normally distributed and therefore continuous, in which case we cannot test instrumentality [Bonet, 2001].

2 Background

We denote sets in bold upper case (S), and abbreviate singleton sets as S = {S}. Graphs are written calligraphically (G), and variables in upper case (X). We consider graphs G = (V, E) with nodes (variables) V and directed (A → B) edges E. We assume that the set V is partitioned disjointly into a set of latent variables (that are not measured) and a set Mof observed (measured) variables.

Nodes linked by an edge are adjacent. A path of length n is a node sequence V1, . . . , Vn+1, in which no Vi occurs more than once, such that there exists an edge sequence E1,E2, . . . ,En for which every edge Ei connects Vi, Vi+1. Then V1 is called the start node and Vn+1 the end node of the path. We use the kinship terms child, parent, ancestor and descendant to describe node relationships in graphs in the same way as in [Pearl, 2009]; in this convention, every node is an ancestor (but not a parent) and a descendant (but not a child) of itself. For a node set Y we denote by An(Y) the set of all ancestors of nodes in Y. Analogously, the descendant set De(Y) is the set of all descendants of any node in Y. Given a graph G and a node set Y ⊆ V, the ancestor graph GAn(Y) is the subgraph of G consisting only of the nodes in An(Y) and all edges between them.

A path from a node X to Y is called causal or directed if it only contains directed edges pointing away from X. A graph is a DAG if it does not contain a directed path from a node to itself of length > 1. A node V on a path π is called a collider if two arrowheads of π meet at V , e.g. if π contains U → V ← Q. There can be no collider if π is shorter than 2. Two nodes Z, Y are called d-connected by a set W if there is a path π between them on which every collider is an ancestor of W and every non-collider is not in W. Then π is called a d-connecting or active path. If Z, Y are not d-connected by W, we say that W d-separates them or blocks all paths between them. We use the notation (Z⊥⊥Y | W)G to indicate this separation, analogously (Z ⧸ ⊥⊥ Y | W)G if Z, Y are d-connected by W. If Z, Y are d-connected (d-separated) by the empty set, we simply say they are d-connected (dseparated). For a path π, we denote by π[X ∼ Z] the subpath of π consisting of the edges between X and Z.

Given a directed graph G, the moral graph Gm [Lauritzen et al., 1990] is the undirected graph obtained by transforming G as follows: (1) For all pairs of edges of the form A → B, C → B, if A and C are not adjacent in G, add an undirected edge A - C to G. (2) Substitute every directed edge A → B by an undirected edge A - B.

3 AHierarchy of Conditional Instruments

Because IVs rely on causal assumptions, it is natural to base IV definitions on causal models. Directed acyclic graphs (DAGs) are simple causal models consisting of nodes representing variables and edges representing causal relationships. In this paper, we focus on the acyclic case in which reciprocal causation is not allowed. We assume that a DAG G = (V, E) with measured variables M ⊆ V is given. Also we assume that G contains an edge X → Y (the effect to be estimated), and we denote by Gc the graph obtained by removing said edge from G.

As mentioned above, exogeneity and exclusion restriction are statistically untestable - arguably, they cannot even be expressed in statistical language [Pearl, 2009]. Conversely, requirements that can be formulated in statistical language have the advantage of being testable. We make this distinction explicit by expressing testable requirements in statistical language (labeled with ∗ ), and untestable ones 2 in graphical language. The standard IV definition then reads as follows:

Definition 3.1 (IV). Z is an instrumental variable relative to X → Y , if

• ∗ (a) Z correlates with X,
• (b) Z is d-separated from Y in Gc.

Note that (a) implies the existence of a path π from Z to X that is d-connected. Our definition is thus stricter than the one given by [Pearl, 2009], in which (a) only requires the existence of π. However, for actual estimation of causal effects e.g. by two-stage regression, Z needs to be correlated with X, so our definition does not miss any relevant cases.

Definition 3.2 (Conditional Instrument [Pearl, 2009]). Z is said to be a conditional instrument relative to X → Y , if there exists a set W ⊆ M such that

• ∗ (a) Z correlates with X conditioned on W,
• (b) Wd-separates Z and Y in Gc,
• (c) W consists of non-descendants of Y .

For instance, Z is a conditional instrument in Fig. 1B using W = W. Again, condition (a) is statistically testable, and it implies the existence of a path π from Z to X that is d-connected byW. Conditions (a) and (b) are direct generalizations of the same conditions in the standard IV definition. Restriction (c) is necessary because conditioning on descendants of Y would bias estimation by the reversal paradox.

The idea of applying instruments together with conditioning variables predates its graphical definition. Take the seminal work of Angrist on the labor market impact of voluntary military service [Angrist, 1998; Angrist and Pischke, 2008]: During the "Vietnam draft lottery", randomly chosen men were called to serve in the war. As not every drafted person enlisted, this is a classical example of a randomized trial with imperfect compliance: The IV Z in this case is the draft, and the independent variable X is enlistment. Several dependent variables Y could be studied with this setup. However, because different numbers of men were drafted for each birth cohort, the IV was only exogenous conditioned on the year of birth (this would be our W in Definition 3.2). A DAG describing this scenario could look like this:

In this typical example, we condition on a set of covariates to render a variable exogenous. However, Definition 3.2 also allows for quite different scenarios that no longer fit the usual IV setting. For example, in the DAG

2 By this we mean "untestable from observed data". In principle we could test some of these requirements experimentally.

Z1 is a canonical IV. But Definition 3.2 also allows Z2 as an IV after conditioning on W: even though Z1 and X are initially independent, they (may) become correlated after conditioning. Whilst this is technically fine, starting from a variable that is uncorrelated with X and then essentially exploiting the reversal paradox might lend less credibility to such an analysis. In practice, good candidate IVs are often found when circumstances create a scenario akin to (imperfect) randomization, like in the Vietnam lottery example. We would then use conditioning to remove any residual endogeneity from the instrument, not to create spurious correlations. Natural covariates would be the common causes of Z, X and Y (or proxies thereof). With this motivation in mind, we define the following "restricted" version of a conditional IV.

Definition 3.3 (Ancestral Instrument). Variable Z is said to be an ancestral instrument relative to X → Y , if there exists a set W ⊆ M such that

∗ (a) Z correlates with X conditional onW,

• (b) Wd-separates Z and Y in Gc,
• (c) W consists of ancestors of Y or Z or both which are non-descendants of Y .

From this definition, it is obvious that ancestral IVs are special case of conditional IVs. Also, each standard IV is an ancestral IV (usingW= ∅). There are, however, conditional IVs that are not ancestral (e.g. Z2 in the above DAG), and this might seem to imply that ancestral IVs are less "powerful" than generic conditional ones. Importantly and perhaps surprisingly, the following theorem shows that this is not the case.

Theorem 3.4. For a given DAG G and variables X and Y , a conditional IV Z relative to X → Y exists if and only if an ancestral IV Z ′ relative to X → Y exists.

Proof. Let Z be a conditional IV relative to X → Y , such that the path π from X to Z has the minimum number of colliders. Let W be a minimal set of non-descendants of Y opening the path π and separating Y and Z in Gc. If π has no colliders then after removing nodes from W which are neither ancestors of Y nor of Z the set still d-separates Y and Z [Lauritzen et al., 1990] and does not block π. Thus, Z is an ancestral instrument.

Assume π has at least one collider, say C. Let W ∈ W be the first descendant of C in Gc. Note that W can coincide with C. Then all paths τ between Y and W that are active given W\W in Gc have the form τ = τ0 ← W, where τ0 starts with Y , and at least one such path exists: Otherwise, if no open path between Y and W exists, W is a conditional instrument relative to X → Y whose sequence π[X ∼ C] → . . . → W givenW\W in Gc has fewer colliders than π. If the sequence does not visit a node twice, it is an active path; Otherwise, if a node, say D, is visited on the sequence twice, we can remove all nodes between the farthest occurrences of D resulting in an active path π[X ∼ D] → . . . → W. If path τ ends with →, i.e. τ = τ0 →W and no node occurs twice in the sequence

τ0 → W ← . . . ← π[C ∼ Z] then it is a path between Y and Z in Gc which is open given W. If a node, say D, occurs twice in the sequence, we remove all nodes between the farthest occurrences of D obtaining a shorter sequence with a single occurrence of D. In the shorter sequence, every collider is open given W and no non-collider is blocked by W. This fact is obvious for any node V ̸= D. To see that it is true also for D, we consider two cases. If in the shorter sequence node D is a non-collider, then at least one of its occurrences in the original sequence was a non-blocked non-collider. Thus, W does not block D in the shorter sequence either. If D becomes a collider but in the original sequence both occurrences were non-colliders, then in the original sequence the subsequence between both occurrences has the form → D → . . . ← D ←. This means that a descendant of D is inW.

If one of these first descendants W ∈ W is not an ancestor of Y then there exists a path τ of the form τ1 → V ← . . . ← W, for some subpath τ1 starting in Y that is active givenW\W in Gc. Node V has a descendant inW\W.

Since W is minimal no node W ∈ W that does not open the path between X and Z can be removed without opening a path π′ between Y and Z in Gc. Since such a path π′ has to contain a collider, W is an ancestor of this collider and a node W ′ ∈W that is opening the collider.

So, every node in W is either an ancestor of Y or Z, or is an ancestor of some other node in W. Since Gc does not contain cycles, every node inW is an ancestor of Y or Z.

The result that we lose nothing by restricting ourselves to ancestral IVs has an interesting connection to a similar result for covariate adjustment: If it is possible to identify a causal effect by adjustment, then it is always possible to do so by only adjusting for ancestors of the variables of interest [van der Zander et al., 2014].

The rest of the paper will show that ancestral instruments are algorithmically appealing: Unlike non-ancestral instruments, they can be found efficiently in a given DAG.

4 Finding Conditional Instruments

In this section we are concerned with the following problem: Given a DAG G and variables X, Y, can we find a variable Z and a set W ⊆ M that renders Z into a conditional instrument with respect to X → Y ? If this is possible, we say that Z can be instrumentalized using W. If many such W exist, we give a preference to "simple" sets - e.g., we prefer to instrumentalize using the empty set if possible. Our main workhorse to achieve this is the notion of a nearest separator, which we introduce now.

4.1 Nearest Separators

Let G = (V,E) be a graph and let M ⊆ V denote the measured nodes and let Y and Z be nodes in V. We say that Y and Z are separable in G if there exists W ⊆ M such that (Z⊥⊥Y | W)G. For given nodes Y and Z in V we call a subset W ⊆ M a nearest separator according to (Y,Z) if and only if (i) (Z⊥⊥Y | W)G and (ii) for all X ∈ An(Y ∪ Z) \ {Y, Z} and any path π in the moral graph (GAn(Y ∪Z))m connecting X and Z, if there exists W′ ⊆ M

such that (Z⊥⊥Y | W′ )G andW′ does not block π thenW does not block π either. For an example nearest separator see Fig. 2. The following algorithm computes such separators.

function NEAREST-SEPARATOR(G, Y, Z) Let M be the set of measured variables in G Construct the moralized graph M = (GAn(Y ∪Z))m W := ∅ while ∃ π = Y, V1, . . . , Vk, Z - a path from Y to Z inMs.t. k ≥ 1, π is not blocked byW, and {V1, . . . , Vk} ∩M ̸= ∅ do W := W ∪ {first measurable node Vi of π} if (Z⊥⊥Y |W) then returnWelse return ⊥

Lemma 4.1. AlgorithmNEAREST-SEPARATOR finds a nearest separator W ⊆ An(Y ∪ Z) if Y and Z are separable in G; otherwise it returns ⊥. Moreover, if Y and Z can be separated in G by a set that does not contain a descendant of Y , thenW ⊆ An(Y ∪Z)\De(Y ). The runtime of the algorithm is O(nm), where n = |V| and m = |E|.

Proof. The algorithm finds W satisfying (Z⊥⊥Y | W)G if such a set exists, because in this case it exists in the moral graph of ancestors [Lauritzen et al., 1990] and in an undirected graph a separating set can be found greedily.

This W contains only ancestors of Z and Y , so if W contains a descendant V of Y then V is an ancestor of Z. Hence there is a causal path from Y to V and a causal path from V to Z. Thus, there exists a causal path from Y to Z that can only be blocked by a descendant of Y , and every separating set must contain a descendant of Y . This proves the condition that the algorithm returns a set of non-descendants of Y if such a set exists.

Next, we show that the set W returned by the algorithm is a nearest separator according to (Y,Z) in G. So, let X be an arbitrary node in An(Y ∪ Z) other than Y and Z and let π be a path in the moral graph (GAn(Y∪Z))m connecting X and Z such that π is blocked by W. Assume there exists a set W′ ⊆ M which separates Y and Z in G but does not block the path π in the moral graph. Then π is blocked by a node W ∈ W\W′ which has to block a path π′ from Y to Z in the moral graph. This follows from the construction of the algorithm. The subpath of π′ between Y and W is not blocked by W′ , because the algorithm only chooses W, if no node closer to Y can block the path π′ . Hence every path fromW to Z in (GAn(Y ∪Z))m is blocked byW′ . Particularly, a subpath of π between W and Z is blocked by W′ , too. But this contradicts the assumption that W′ does not block π.

The runtime is O(nm) since a path in the moralized graph can be found in O(m) steps and at most O(n) nodes are needed to block all paths. The times needed to construct the moralized graph (O(n)) and to check the separation at the end (O(m)) do not change the asymptotic runtime.

The following property of nearest separators computed by the algorithm above will turn out to be useful.

Corollary 4.2. Let X, Y,Z be different variables in V and let W ̸= ⊥ be a set returned by NEAREST-SEPARATOR for (Gc, Y,Z). If X ∈ W, then variable Z is not an ancestral instrument relative to X → Y in G.

4.2 Ancestral Instruments

Having introduced the concept of nearest separators and having shown how to find them, we are now ready to present an algorithm to instrumentalize ancestral IVs.

function ANCESTRAL-INSTRUMENT(G, X, Y, Z) Gc := G with edge X → Y removed W := NEAREST-SEPARATOR(Gc, Y, Z) if (W = ⊥) ∨ (W ∩ De(Y ) ̸= ∅) ∨ (X ∈ W) then return ⊥ if (Z ⧸ ⊥⊥ X | W) in Gc then return W else return ⊥

Theorem 4.3. For given X, Y and Z in a DAG G algorithm ANCESTRAL-INSTRUMENT returns a set of variables W that satisfies the properties of ancestral conditional instruments relative to X → Y , if such a set exists; Otherwise it returns ⊥. The running time of the algorithm is O(nm).

Proof. Let A=M∩An(Y,Z)\De(Y ). We prove first that if the algorithm returns a set W ̸= ⊥, it has found W satisfying the conditions of Definition 3.3.

From Lemma 4.1 we know that NEAREST-SEPARATOR returns a nearest separator W according to (Y,Z) and that W ⊆ M∩ An(Y,Z). Due to the test for descendants of Y we have that W ⊆ A. From Corollary 4.2 we know that Z cannot be an ancestral instrument if X ∈ W. Finally, a set W is returned if it does not separate X and Z in Gc.

Next, assume there exists a set W0 ⊆ A, such that (Y⊥⊥Z | W0)Gc and a path π0 between X and Z which is open in Gc givenW0. We show that the algorithm finds a set W satisfying the conditions of ancestral instruments.

From the assumption and due to Lemma 4.1, we get that NEAREST-SEPARATOR returns a set W ⊆ A which is a nearest separator according to (Y,Z). If π0 has colliders, then all of them are ancestors of nodes in W0 that, recall, is a subset of An(Y,Z). So, π0 has the form X ← . . . ← Z, or X ← . . . ← V → π1, or X → π2 such that V and all nodes on π1 and π2 are ancestors of Y or Z. Paths V → π1 and X → π2 correspond to paths in the moralized graph M = (Gc,An(Y,Z))m, which are not blocked by W0 and thus not blocked by W in M. Relying on the properties of the moralized graph, we can prove that there exist paths V → π′1 or X → π′2 to Z in Gc that are not blocked by W and V /∈ W due to Corollary 4.2. The paths X ← . . . ← Z and X ← . . . ← V are not blocked by W either, since if the nodes belong to the moral graph, they are not blocked due to Lemma 4.1, otherwise W cannot block them since it only contains nodes of the moral graph. Similarly V /∈ W, or there would be a path between Y and Z that is not blocked by W0. Thus, replacing π1, π2 by π′1 , π′2 , resp., in π0 leads to a path π′0 that is not blocked by W and the condition (Z ⧸ ⊥⊥ X | W)Gc is true. The runtime is dominated by NEAREST-SEPARATOR.

It is easy to see that if Z is d-separated from Y in Gc, i.e. if (Z⊥⊥Y | ∅)Gc , then for given Gc, Y , and Z, algorithm NEAREST-SEPARATOR, returnsW= ∅. Thus, we get:

Corollary 4.4. For given X, Y and Z in a DAG G algorithm ANCESTRAL-INSTRUMENT returns the empty set W = ∅ if and only if Z is an instrumental variable relative to X → Y .

Further, we can use algorithm ANCESTRAL-INSTRUMENT to find a conditional instrumental variable relative to X → Y : we search exhaustively in M\ (X ∪ De(Y )) for a variable Z for which the algorithm returns W ̸= ⊥. The soundness of the algorithm and its time complexity O(n2m) follows from Theorem 4.3. The completeness is a consequence of Theorem 3.4. We obtain the following result.

Corollary 4.5. There exists an algorithm which, given X and Y , returns a node Z and a node set W in time O(n2m) such that W instrumentalizes Z, if such W and Z exist. Otherwise, it returns ⊥.

This corollary is complete for effect identification using conditional IVs in the same sense as the do-calculus is complete for causal effect identification in general [Huang and Valtorta, 2006; Shpitser and Pearl, 2006]: if it is possible to estimate a causal effect in a DAG using a conditional IV, then we can find such an IV using our algorithm.

4.3 Instrumentalization is NP-hard in general

We have now solved the problem posed in the previous section: find a variable Z and a set W such that W instrumentalizes Z. Now it is natural to wonder about a slightly different problem: given Z, find a set W that instrumentalizes Z. We refer to this as the instrumentalization problem. Intuitively, this new problem might seem to be easier than finding an IV because Z is already fixed. Perhaps surprisingly, the opposite turns out to be true: Instrumentalization is computationally harder than finding an IV.

Theorem 4.6. Determining if, for given X, Y, Z ∈ V, node Z is a conditional instrument relative to X → Y is an NPcomplete problem.

Proof. Obviously, the conditions of Definition 3.2 can be verified in polynomial time after guessing W ⊆ M. Thus, the problem is in NP. To prove the NP-hardness we show a reduction from the 3SAT problem, which is the canonical complete problem for NP [Garey and Johnson, 1979].

Assume ϕ = ∧mj=1 Cj is an instance of 3SAT, which is a Boolean formula in conjunctive normal form over n variables x1, . . . , xn where each clause Cj is limited to exactly three literals from x1, x1, . . . , xn, xn. We construct the DAG G = (V, E) for ϕ as follows.

For every clause Cj we define two nodes Cj and C ′j in V. Next, let oi, resp. oi, be the number of occurrences of positive literal xi, resp. negative literal xi, in ϕ. For each literal xi we define oi nodes V 1 i , . . . , V oi i in V, resp., for xi we define nodes V 1i , . . . , V oi i . Additionally, for every xi two nodes V 0 i , V -1 i are defined and for every xi the node V 0i is included in V. We complete the construction of V by adding the sets of nodes Pi, Fi,Ni, for all 1 ≤ i ≤ n and nodes X, Z, Y, Y ′ , Y ′′ . Thus,

We define the edges of G such that C ′ i ,Ci form the path X → C ′1 → C1 ← C ′2 → C2 ← ... ← C ′m → Cm ← Z between X and Z (see the top of Fig. 3), and the nodes Pi, Fi,Ni form the n paths Y ′ → Pi ← Fi → Ni ← Y ′′ between Y ′ and Y ′′ (see the bottom of Fig. 3). The complete set of edges E is defined as follows:

The set M of observed nodes is defined as

G can be constructed in polynomial time with respect to the length of the instance formula ϕ. The construction ensures that sets W that instrumentalizes Z w.r.t. X, Y bijectively map to satisfying assignments as follows:

Our construction ensures the validity of this mapping in the following manner. First, the only possible open path from X to Z is the path via the Ci,C′ i nodes; if W opens any other path, then it also opens a path from Z to Y . Second, to connect Z and X, set W needs to contain at least one of V j i , V ki for i ≥ 1. But it is not possible to pick both V j i and V ki for any i ≥ 1, j, k without opening a path from Z to Y . This ensures that no variable is assigned both "true" and "false". If a path has been found that is d-connected by W, then it therefore has to contain an assignment for at least one variable in every clause, and this assignment fulfills said clause. Therefore, we altogether obtain a satisfying assignment. If no such assignment exists, then it is also not possible simultaneously to d-connect Z and X and d-separate Z and Y in the graph.

5 Discussion

We proposed a three-level hierarchy that links traditional IVs [Angrist et al., 1996] to conditional IVs [Pearl, 2009]. For the first two stages, classic and ancestral instruments, we gave efficient algorithms for finding IVs and for instrumentalizing given variables. At the same time, we showed that instrumentalization is in general not efficiently solvable unless P=NP. Yet, whenever a conditional IV exists, an ancestral IV also exists. In this sense, our solution is complete - it covers all cases where a causal effect can be identified using the conditional IV method. To our knowledge, no attempt has been made so far to find conditional IVs efficiently or to prove the hardness of this problem, and perhaps due to these algorithmic issues, the existing software that we know of is limited to finding unconditional IVs [Kyono, 2010].

We focused here on estimation of causal effects of the form X → Y , disregarding scenarios where the effect of X on Y is mediated by other observed variables. However, our results easily generalize to IVs with respect to the total effect. Details will appear in an extended version of this paper. On the other hand, IVs are also often used to disentangle reciprocal causation in cyclic models such as typical supply-and-demand systems [Angrist and Pischke, 2008], and that important case remains to be addressed in future research.

From a computational complexity perspective, the result that instrumentalization is hard whereas finding a conditional IV is easy is rather intriguing. This can be explained by noting that the solution space of the IV problem decomposes into some instances that are easy to find (ancestral IVs) and others that are hard to find (non-ancestral IVs like the ones used in our reduction). Our hardness proof heavily uses long paths on which every observed variable is a collider. In DAGs with only observed variables (Markovian DAGs), such long collider paths are impossible. Thus, the question whether non-ancestral IVs are easier to find in Markovian DAGs remains open. However, this question is not of immediate practical relevance since in Markovian DAGs, we can identify causal effects using hierarchical regression or using adjustment, which have superior statistical properties.

We hope our findings will benefit both users of DAGs and users of standard IV methods, for partly different reasons. With DAGs we have the do-calculus at our disposal, which always finds a formula to estimate a causal effect if one exists [Huang and Valtorta, 2006; Shpitser and Pearl, 2006]. However, these formulas can grow large, which complicates estimation [VanderWeele, 2009; Glynn and Kashin, 2013]. IV methods are statistically well-understood, and can identify causal effects in many settings where standard approaches like covariate adjustment fail, e.g., when an unobserved confounder affects X and Y . Yet, IV methods are rarely used so far in fields where DAGs are popular, like Epidemiology [Greenland, 2000]. Phrasing generalized IV methods in the DAG framework and providing efficient algorithms for IV construction may make them more palatable for DAG users, and embracing IV estimation procedures for causal effects might benefit those fields.

Econometrics is perhaps the field where IV methods are most commonly used [Imbens, 2014a]. Econometricians have thus far largely refrained from using graphical causal models [Pearl, 2013; Imbens, 2014b], and might not be comfortable with Pearl's fully generalized IV definition that includes IVs which are uncorrelated with X. Therefore, we hope that interested Econometricians might find some merit in our notion of ancestral IVs, which reflects the combined use of IVs and covariates for adjustment. In this context, it is interesting to note that the linearity requirement of the IV method does not necessarily apply to the covariates: an estimation approach has been developed into which the covariates can enter non-parametrically [Kasy, 2009].

In summary, we have presented a hierarchy of generalized IV definitions and gave efficient algorithms to find generalized IVs for all levels of this hierarchy. We hope our results will help DAG users to adopt the IV method, and users of the IV method to adopt DAGs. Our algorithms are implemented in the open-source software DAGitty [Textor et al., 2011].