Fast Proxy Experiment Design for Causal Effect Identification

Authors: sepehr  elahi
sina  akbari
jalal  etesami
negar  kiyavash
patrick  thiran
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-14 17:50:20

Abstract: Identifying causal effects is a key problem of interest across many disciplines. The two long-standing approaches to estimate causal effects are observational and experimental (randomized) studies. Observational studies can suffer from unmeasured confounding, which may render the causal effects unidentifiable. On the other hand, direct experiments on the target variable may be too costly or even infeasible to conduct. A middle ground between these two approaches is to estimate the causal effect of interest through proxy experiments, which are  conducted on variables with a lower cost to intervene on compared to the main target. In an earlier work, we studied this setting and demonstrated that the problem of designing the optimal (minimum-cost) experiment for  causal effect identification is NP-complete and provided a naive algorithm that may require solving exponentially many NP-hard problems as a sub-routine in the worst case. In this work, we provide a few reformulations of the problem that allow for designing significantly more efficient algorithms to solve it as witnessed by our extensive simulations. Additionally, we study the closely-related problem of designing experiments that enable us to identify a given effect through valid adjustments sets.

Main paper: 
 problem formulation: 
 We begin by reviewing relevant graphical definitions. An acyclic directed mixed graph (ADMG) is a graph with directed (→) and bidirected (↔) edges such that the directed edges form no cycles [Richardson, 2003] . We denote an ADMG G by a tuple G = ⟨V, -→ E , ← → E ⟩, where V , -→ E , and ← → E represent the set of vertices, directed edges, and bidirected edges, respectively. Note that -→ E is a set of ordered pairs of vertices in V , whereas ← → E is a set of unordered pairs of vertices.Vertices of G represent variables of the system under consideration, while the edges represent causal relations between them. We use the terms 'variable' and 'vertex' interchangeably. When (y, x) ∈ -→ E , we say y is a parent of x and x is a child of y. The set of parents of X ⊆ V denoted by Pa(X) = {y : (y, x) ∈ -→ E for some x ∈ X} \ X. We denote byG[W ], the induced subgraph of G over vertices W ⊆ V . A subset S of V is said to form a district in G if S is a maximal set such that any pair of vertices x, y ∈ S are connected through a bidirected path x ↔ • • • ↔ y in G[S]. In other words, G[S] is a connected component through its bidirected edges. We say x ∈ V is an ancestor of S ⊆ V if there is a directed path x → • • • → s for some s ∈ S.We denote the set of ancestors of S in the subgraph G[W ] by Anc W (S). Note that S ⊆ Anc W (S). When W = V , we drop the subscript for ease of notation.Let X, Y ⊆ V be two disjoint sets of variables. The probability distribution of Y under a (possibly hypothetical) intervention on X setting its value to x is often represented as either P(Y (x) ), using Rubin's potential outcomes model [Rubin, 1974] , or P(Y | do(X = x)) using Pearl's do operator [Pearl, 2009] . We will adopt the shorthand P x (Y ) to denote this interventional distribution3 .Definition 1 (Identifiability). An interventional distribution P x (Y ) is identifiable given an ADMG G and the intervention set family I = {I 1 , . . . , I t }, with I i ⊆ V , over the variables corresponding to G, if P x (Y ) is uniquely computable as a functional of the members of {P I (•) : I ∈ I}.Remark 1. It is common in the literature to define identifiability with respect to observational data only (i.e., when I = {I 1 = ∅}). Our definition above follows what is known as the 'general identifiability' from Lee et al. [2020a] .We will now formally define a hedge, which, as we will see shortly after, is central to deciding the identifiability of an interventional distribution given the data at hand. Definition 2 (Hedge). Let S ⊆ V be a district in G[S]. We say W ⊋ S forms a hedge for S if (i) W is a district in G[W ], and (ii) every vertex w ∈ W is an ancestor of S in G[W ] (i.e., W = Anc W (S)). We denote by H G (S) the set of hedges formed for S in G.For example, in Fig. 2 (b), S has two hedges given by H G (S) = {S ∪ {v 3 , v 1 }, S ∪ {v 3 , v 1 , v 2 }}. Definition 3 (Hedge hull Akbari et al., 2022) . Let S be a district in ADMG G. Also let H G (S) be the set of all hedges formed for S in G. The union of all hedges in H G (S), denoted by H G (S) = W ∈H G (S) W, is said to be the hedge hull of S in G.For instance, in Fig. 2 (d), the hedge hull of S 1 = {s 1 } is H G (S 1 ) = {s 1 , s 2 , v 1 , v 2 , v 3 , v 4 , v 5 } and the hedge hull of S 2 = {s 2 } is H G (S 2 ) = {s 2 , v 3 }.When a set S consists of more than one district, we simply define the hedge hull of S as the union of the hedge hulls of each district of S. The hedge hull of a set can be found through a series of at most |V | depth-first-searches. In the latter example, the hedge hull ofS = {s 1 , s 2 } is H G (S) = {s 1 , s 2 , v 1 , v 2 , v 3 , v 4 , v 5 }.For the sake of completeness, we have included the algorithm for finding a hedge hull in Appendix B.1.The following proposition from Lee et al. [2020a] and Kivva et al. [2022] establishes the graphical criterion for deciding the identifiability of a causal effect given a set family of interventions. Proposition 1. Let G be an ADMG over the vertices V . Also let X, Y ⊆ V be disjoint sets of variables. Define S = Anc V \X (Y ), and let S = {S 1 , . . . , S r } be the (unique) set of districts in G[S]. The interventional distribution P x (Y ) is identifiable given G and the intervention set family I = {I 1 , . . . , I t }, if and only if for every S ℓ ∈ S, there exists an intervention setI k ∈ I such that (i) I k ∩ S ℓ = ∅, and (ii) there is no hedge formed for S ℓ in G[V \ I k ].Note that there is no hedge formed for S ℓ in G[V \ I k ] if and only if I k hits every hedge of S ℓ (i.e., for any hedge W ∈ H G (S ℓ ), I k ∩ W ̸ = ∅). For ease of presentation, we will use I k id -→ S ℓ to denote that I k ∩ S ℓ = ∅ and I k hits every hedge formed for S ℓ . For example, given the graph in Fig. 2(d ) and with S = {S 1 , S 2 }, an intervention set family that hits every hedge is I = {{s 2 }, {v 3 }}.Minimum-cost intervention for causal effect identification (MCID) problem. Let C : V → R ≥0 ∪{+∞} be a known function 4 indicating the cost of intervening on each vertex v ∈ V . An infinite cost is assigned to variables where an intervention is not feasible. Given G and disjoint sets X, Y ⊆ V , our objective is to find a set family I * with minimum cost such that P x (Y ) is identifiable given I * ; that is, for every district S ℓ of S, there exists I k such that I k id -→ S ℓ . Since every I ∈ I is a subset of V , the space of such set families is the power set of the power set of V .To formalize the MCID problem, we first write the cost of a set family I as C(I) := I∈I v∈I C(v), where with a slight abuse of notation, we denoted the cost of I by C(I).The MCID problem then can be formalized as follows.EQUATIONwhere S = {S 1 , . . . , S r } is the set of districts of S = Anc V \X (Y ), and 2 2 V represents the power set of the power set of V . In the special case where S comprises a single district, the MCID problem can be presented in a simpler way. Proposition 2 (Akbari et al., 2022) . If S = Anc V \X (Y ) comprises a single district S = {S 1 = S}, then the optimization in (1) is equivalent to the following optimization:I * ∈ argmin I∈2 V \S C(I) s.t. ∀ W ∈ H G (S) : I ∩ W ̸ = ∅. (2)That is, the problem reduces to finding the minimum-cost set that 'hits' every hedge formed for S.Recall example Example 1, we were interested in finding the least costly proxy experiment to identify the effect of v 2 and v 3 on y. By Proposition 2, this problem is equivalent to finding an intervention set with the least cost (i.e., a set of proxy experiments) that hits every hedge of S = {y, w} in the transformed graph (Fig. 2 (b)). If C(v 1 ) < C(v 3 ), then the optimal solution would be I * = {v 1 }.In the remainder of the paper, we consider the problem of identification of P X (Y ) for a given pair (X, Y ), and with S defined as S = Anc V \X (Y ), unless otherwise stated. We will first consider the case where S comprises a single district, and then generalize our findings to multiple districts.3 Reformulations of the min-cost intervention problemIn the previous section, we delineated the MCID problem as a discrete optimization problem. This problem, cast as Eq. ( 1), necessitates search within a doubly exponential space, which is computationally intractable. Algorithm 2 of [Akbari et al., 2022] is an algorithm that conducts this search and eventually finds the optimal solution. However, even when S comprises a single district, this algorithm requires, in the worst case, exponentially many calls to a subroutine which solves the NP-complete minimum hitting set problem on exponentially many input sets, hence resulting in a doubly exponential complexity. More specifically, our previous algorithm described in Akbari et al. [2022] attempts to find a set of minimal hedges, where minimal indicates a hedge that contains no other hedges, and solves the minimum hitting set problem on them. However, there can be exponentially many minimal hedges, as shown for example in Fig. 2(c ). Letting m = n/2, then any set that contains one vertex from each level (i.e., directed distance from S) is a minimal hedge, of which there are O(2 n/2 ).Furthermore, the computational complexity of Algorithm 2 of Akbari et al. [2022] grows superexponentially in the number of districts of S. This is due to the necessity of exhaustively enumerating every possible partitioning of these districts and executing their algorithm once for each partitioning.In this section, we reformulate the MCID problem as a weighted partially maximum satisfiability (WPMAX-SAT) problem [Fu and Malik, 2006] , as well as an integer linear programming (ILP) problem. We focus on the WPMAX-SAT and ILP reformulations due to their computational efficiency and practical applicability, but we provide alternative reformulations as a submodular maximization problem and a reinforcement learning problem in Appendix D for completeness. The advantage of the WPMAX-SAT and ILP formulations is two-fold: (i) compared to Algorithm 2 of [Akbari et al., 2022] , we state the problem as a single instance of another problem for which a range of well-studied solvers exist, and (ii) these formulations allow us to propose algorithms with computational complexity that is quadratic in the number of districts of S. We will see how these advantages translate to drastic performance gains in Section 5. 
min-cost intervention as a wpmax-sat problem: 
 We begin with constructing a 3-SAT formula F that is satisfiable if and only if the given query P X (Y ) is identifiable. To this end, we define m + 2 variables {x i,j } m+1 j=0 for each vertex v i ∈ V , where m = |H G (S) \ S| is the cardinality of the hedge hull of S, excluding S. Intuitively, x i,j is going to indicate whether or not vertex v i is reachable from S after j iterations of alternating depth-first-searches on directed and bidirected edges. This is in line with the workings of Algorithm 2 for finding the hedge hull of S. In particular, if a vertex v i is reachable after m + 1 iterations, that is, x i,m+1 = 1, then v i is a member of the hedge hull of S. The query of interest is identifiable if and only if H G (S) = S, that is, the hedge hull of S contains no other vertices. Therefore, we ensure that the formula F is satisfiable if and only if x i,m+1 = 0 for every v i / ∈ S. The formal procedure for constructing this formula is as follows.SAT Construction Procedure. Suppose a causal ADMG G = ⟨V, - → E , ← → E ⟩ and a set S ⊂ V are given, where S is a district in G. Suppose H G (S) = {v 1 , . . . , v n } is the hedge hull of S in G,where without loss of generality, S = {v m+1 , . . . v n }, and {v 1 , . . . v m } ∩ S = ∅. We will construct a corresponding boolean expression in conjunctive normal form (CNF) using variables {x i,j } for i ∈ {1, . . . , m} and j ∈ {0, . . . , m + 1}. For ease of presentation, we also define x i,j = 1 for all i ∈ {m + 1, . . . , n}, j ∈ {0, . . . , m + 1}. The construction is carried out in m + 2 steps, where in each step, we conjoin new clauses to the previous formula using 'and'. The procedure is as follows:• For odd j ∈ {1, . . . , m+1}, for each directed edge (v i , v ℓ ) ∈ -→ E , add (¬x i,j-1 ∨ x i,j ∨¬x ℓ,j ) to F .• For even j ∈ {1, . . . , m+1}, for each bidirected edge {v i , v ℓ } ∈ ← → E , add both clauses (¬x i,j-1 ∨ x i,j ∨ ¬x ℓ,j ) and (¬x ℓ,j-1 ∨ x ℓ,j ∨ ¬x i,j ) to F .• Finally, at step m + 2, add clauses ¬x i,m+1 to the expression F for every i ∈ {1, . . . , m}. As an example, consider the graph of Figure 3 with n = 3 vertices. The hedge hull of S = {v 3 } is {v 1 , v 2 , v 3 }, and m = |{v 1 , v 2 }| = 2. Following the SAT construction procedure outlined above, the construction is carried out in m + 2 = 4 steps. Our SAT expression will consist of 8 variables, x i,j for i ∈ {1, 2} -corresponding to v 1 and v 2 -and j ∈ {0, 1, 2, 3} -corresponding to the four steps of construction. Below, we explain each step.At step 1, we add the clauses (¬x 1,0 ∨ x 1,1 ∨ ¬x 2,1 ) and (¬x 2,0 ∨ x 2,1 ∨ ¬x 3,1 ), corresponding to the edges v 1 → v 2 and v 2 → v 3 , respectively. Note that by convention, x 3,1 = 1, hence the second clause reduces to (¬x 2,0 ∨ x 2,1 ). At step 2, for the edge v 1 ↔ v 2 , we add the clauses (¬x 1,1 ∨x 1,2 ∨¬x 2,2 ) and (¬x 2,1 ∨x 2,2 ∨¬x 1,2 ). Similarly for the edge v 1 ↔ v 3 , we add the clauses (¬x 1,1 ∨ x 1,2 ∨ ¬x 3,2 ) and (¬x 3,1 ∨ x 3,2 ∨ ¬x 1,2 ). Since by convention, x 3,1 = x 3,2 = 1, the latter two clauses reduce to (¬x 1,1 ∨ x 1,2 ) and 1, respectively. At step 3, we add the clauses (¬x 1,2 ∨ x 1,3 ∨ ¬x 2,3 ) and (¬x 2,2 ∨ x 2,3 ∨ ¬x 3,3 ), corresponding to the edges v 1 → v 2 and v 2 → v 3 , respectively. Again x 3,3 = 1, and the latter clause reduces to (¬x 2,2 ∨ x 2,3 ). At step 4, the clauses ¬x 1,3 and ¬x 2,3 are added.Finally, combining all the clauses together, the SAT expression is given by(¬x 1,0 ∨ x 1,1 ∨ ¬x 2,1 ) ∧ (¬x 2,0 ∨ x 2,1 ) ∧ (¬x 1,1 ∨ x 1,2 ∨ ¬x 2,2 ) ∧ (¬x 2,1 ∨ x 2,2 ∨ ¬x 1,2 ) ∧ (¬x 1,1 ∨ x 1,2 ) ∧ (¬x 1,2 ∨ x 1,3 ∨ ¬x 2,3 ) ∧ (¬x 2,2 ∨ x 2,3 ) ∧ ¬x 1,3 ∧ ¬x 2,3 .Theorem 1. The 3-SAT formula F constructed by the procedure above given G and S has a satisfying solution {x * i,j } where x * i,0 = 0 for i ∈ I ⊆ {1, . . . , m} and x * i,0 = 1 for i ∈ {1, . . . , m}\I if and only if I intersects every hedge formed for S in G; i.e., I is a feasible solution to the optimization in Eq. (2).The proofs of all our results appear in Appendix C. The first corollary of Theorem 1 is that the SAT formula is always satisfiable, for instance by setting x * i,0 = 0 for every i ∈ {1, . . . , m}. The second (and more important) corollary is that the optimal solution to Eq. (2) corresponds to the satisfying assignment for the SAT formula F that minimizesEQUATIONThis suggests that the problem in Eq. ( 2) can be reformulated as a weighted partial MAX-SAT (WPMAX-SAT) problem. WPMAX-SAT is a generalization of the MAX-SAT problem, where the clauses are partitioned into hard and soft clauses, and each soft clause is assigned a weight. The goal is to maximize the aggregate weight of the satisfied soft clauses while satisfying all of the hard ones.To construct the WPMAX-SAT instance, we simply define all clauses in F as hard constraints, and add a soft clause x i,0 with weight C(v i ) for every i ∈ {1, . . . , m}. The former ensures that the assignment corresponds to a feasible solution of Eq. ( 2), while the latter ensures that the objective in Eq. ( 3) is minimized -which, consequently, minimizes the cost of the corresponding intervention.Multiple districts. The formulation above was presented for the case where S is a single district.In the more general case where S has multiple districts, we can extend our formulation to solve the general problem of Eq. ( 1) instead. To this end, we will use the following lemma. Lemma 1. Let S = {S 1 , . . . , S r } be the set of districts of S, where S = Anc V \X (Y ). There exists an intervention set family I * of size |S| = r that is optimal for identifying P X (Y ).Based on Lemma 1, we can assume w.l.o.g. that the optimizer of Eq. ( 1) contains exactly r intervention sets I 1 , . . . , I r . We will modify the SAT construction procedure described in the previous section to allow for multiple districts as follows. For any district S ℓ , we will construct r copies of the SAT expression, one corresponding to each intervention set I k , k ∈ {1, . . . , r}. Each copy is built on new sets of variables indexed by (k, ℓ), except the variables with index j = 0, which are common across districts. We introduce variables {z k,ℓ } r k,ℓ=1 , which will serve as indicators for whether I k hits all the hedges formed for S ℓ . We relax every clause corresponding to the k-th copy by conjoining a ¬z k,ℓ literal with an 'or.' Intuitively, this is because it suffices to hit the hedges formed for S ℓ with some I k . Additionally, we add the clauses (z 1,ℓ ∨ • • • ∨ z r,ℓ ) for any ℓ ∈ {1, . . . , r} to ensure that for every district, there is at least one intervention set that hits every hedge. This modified procedure, detailed in Algorithm 3, appears in Appendix B.2. The following result generalizes Theorem 1.Theorem 2. Suppose G, a set of its vertices S with districts S = {S 1 , . . . , S r }, and an intervention set family 2 I = {I 1 , . . . , I r } are given. Define m ℓ = |H G (S ℓ ) \ S ℓ |, i.e., the cardinality of the hedge hull of S ℓ excluding S ℓ itself. The SAT formula F constructed by Algorithm 3 has a satisfying solution {x * i,0,k }∪{x * i,j,k,ℓ }∪{z * k,ℓ } where for every ℓ ∈ {1, . . . , r}, there exists k ∈ {1, . . . , r} such that (i) z * k,ℓ = 1, (ii) x * i,0,k = 0 for every i ∈ I k , and (iii) x * i,0,k = 1 for every i ∈ {1, . . . , m ℓ } \ I k , if and only if I is a feasible solution to optimization of Eq. (1).Constructing the corresponding WPMAX-SAT instance follows the same steps as the case for a single district, except that the soft clauses are of the form (x i,0,k ∨ ¬z k,ℓ ) with weight C(v i ) for every i ∈ {1, . . . , m ℓ } and k ∈ {1, . . . , r}.Remark 2. The SAT construction of Algorithm 3 is advantageous because its complexity grows quadratically with the number of districts of S in the worst case. This is because the inner-loop of the SAT construction algorithm (line 8 of Algorithm 3) is executed r 2 many times. In contrast, the runtime of the algorithm of Akbari et al. [2022] , when S consists of multiple districts, is super-exponential in the number of districts, because they need to execute their single-district algorithm at least as many times as the number of partitions of the set {1, . . . , r}.Min-cost intervention as an ILP problem. The WPMAX-SAT formulation of Section 3.1 paves the way for a straightforward formulation of an integer linear program (ILP) for the MCID problem. ILP allows for straightforward integration of various constraints and objectives, enabling flexible modeling of potential extra constraints. Moreover, there exist efficient and scalable solvers for ILP [Gearhart et al., 2013 , Gurobi Optimization, LLC, 2023] . To construct the ILP instance for the MCID problem, it suffices to represent every clause in the boolean expression F of Algorithm 3 as a linear inequality. For example, clauses of the form(¬a ∨ b ∨ ¬c) is rewritten as (1 -a) + b + (1 -c) ≥ 1.The soft constraints may be rewritten as a sum to maximize over, given by Eq. ( 3). 
minimum-cost intervention design for adjustment criterion: 
 A special case of identifying interventional distributions is identification through adjusting for confounders. A set Z ⊆ V is a valid adjustment set for P X (Y ) if P X (Y ) is identified asEQUATIONwhere the expectation w.r.t. P(Z). Adjustment sets have received extensive attention in the literature because of the straightforward form of the identification formula (Eq. 4) and the intuitive interpretation: Z is the set of confounders that we need to adjust for to identify the effect of interest. The simple form of Eq. ( 4) has the added desirable property that its sample efficiency and asymptotic behavior are easy to analyze [Witte et al., 2020 , Rotnitzky and Smucler, 2020 , Henckel et al., 2022] . A complete graphical criterion for adjustment sets was given by Shpitser et al. [2010] . As an example, when all parents of X (i.e., Pa(X)) are observable, they form a valid adjustment set. However, in the presence of unmeasured confounding, no valid adjustment sets may exist. Below, we generalize the notion of adjustment sets to the interventional setting.Definition 4 (Generalized adjustment). We say Z ⊆ V is a generalized adjustment set for P X (Y ) under interventionI if P X (Y ) is identified as P X (Y ) = E P I [P I (Y | X, Z)], where P I (•) represents the distribution after intervening on I ⊆V and the expectation is w.r.t. P I (Z).Note that unlike the classic adjustment, the generalized adjustment is always feasible -a trivial generalized adjustment can be formed by choosing I = X and Z = ∅.Equipped with Definition 4, we can define a problem closely linked to Eq. ( 2), but with a (possibly) narrower set of solutions, which can be defined as follows: find the minimum-cost intervention I such that a generalized adjustment exists for P X (Y ) under I:I * = argmin I∈2 V C(I) s.t. ∃ Z ⊆ V : P X (Y ) = E P I [P I (Y | X, Z)].(5)Observation. The existence of a valid (generalized) adjustment set ensures the identifiability of P X (Y ). As such, any feasible solution to the optimization above is also a feasible solution to Eq. ( 2). Eq. ( 5) is not only a problem that deserves attention in its own right, but also serves as a proxy for our initial problem (Eq. 2).To proceed, we need the following definitions. Given anADMG G = ⟨V, - → E , ← → E ⟩, let G d = ⟨V d , - → E d, ∅⟩ be the ADMG resulting from replacing every bidirected edge e = {x, y} ∈ ← → E by a vertex e and two directed edges (e, x), (e, y). In particular,V d = V ∪ ← → E , and - → E d = - → E ∪ {(e, x) : e ∈ ← → E , x ∈ e}. Note that G d is a directed acyclic graph (DAG). The moralized graph of G, denoted by G m , is the undirected graph constructed by moralizing G d as follows: The set of vertices of G m is V d . Each pair of vertices x, y ∈ V d are connected by an (undirected) edge if either (i) (x, y) ∈ - → E d , or (ii) ∃z ∈ V d such that {(x, z), (y, z)} ⊆ - → E d .Throughout this section, we assume without loss of generality that X is minimal in the following sense: there exists no proper subset X 1 ⊊ X such that P X (Y ) = P X1 (Y ) everywhere5 . Otherwise, we apply the third rule of do calculus [Pearl, 2009] as many times as possible to make X minimal. We also assume w.l.o.g. that V = Anc(X ∪ Y ) as other vertices are irrelevant for our purposes [Lee et al., 2020b ]. We will utilize the following graphical criterion for generalized adjustment.Lemma 2. Let X, Y be two disjoint sets of vertices in G such that X is minimal as defined above.Set Z ⊆ V is a generalized adjustment set for P X (Y ) under intervention I if (i) Z ⊆ Anc(S), and (ii) Z is a vertex cut6 between S and Pa(S) in (G IPa(S) ) m , where S = Anc V \X (Y ), and G IPa(S) is the ADMG resulting from omitting all edges incoming to I and all edges outgoing of Pa(S).Based on the graphical criterion of Lemma 2, we present the following polynomial-time7 algorithm for finding an intervention set that allows for identification of the query of interest in the form of a (generalized) adjustment. This algorithm will find the intervention set I and the corresponding generalized adjustment set Z simultaneously. We begin by making X minimal in the sense of applicability of rule 3 of do calculus. Then we omit all edges going out of Pa(S), and construct the graph (G Pa(S)) d = ⟨V d , - → E d, ∅⟩ as defined above -by replacing bidirected edges with vertices representing unobserved confounding. Finally, we construct an (undirected) vertex cut networkG vc = ⟨V vc , E vc ⟩ as follows. Each vertex v ∈ V d is represented by two connected vertices v 1 , v 2 in G vc . If v ∈ V , then v 1has a cost of zero, and v 2 has cost C(v). Otherwise, both v 1 and v 2 have infinite costs. Intuitively, choosing v 1 will correspond to including v in the adjustment set, whereas choosing v 2 in the cut would imply intervention on v. We connect v 2 to all vertices corresponding to Pa(v) with index 1, i.e., {w1 : (w, v) ∈ - → E d }.This serves two purposes: (i) if v 2 is included in the cut (corresponding to an intervention on v), all connections between v and its parents are broken, and (ii) when v 2 is not included in the cut (corresponding to no intervention on v), v 2 connects the parents of v to each other, completing the necessary moralization process. We solve for the minimum vertex cut between vertices with index 1 corresponding to S and Pa(S). Algorithm 1 summarizes this approach. In the solution set J, the vertices with index 2 represent the vertices where an intervention is required, while those with index 1 represent the generalized adjustment set under this intervention.Theorem 3. Let (I, Z) be the output returned by Algorithm 1 for the query P X (Y ). Then, -Z is a generalized adjustment set for P X (Y ) under intervention I.-I is the minimum-cost intervention for which there exists a generalized adjustment set based on the graphical criterion of Lemma 2.1: procedure MINCOSTGENADJUSTMENT(X, Y, G = ⟨V, - → E , ← → E ⟩, {C(v) : v ∈ V }) 2: while ∃x ∈ X s.t. x is m-sep from Y given X \ {x} in G X do ▷ Make X minimal 3: X ← X \ {x} 4: S ← Anc V \X (Y ) 5: - → E ← - → E \ {(x, s) : x ∈ Pa(S)} ▷ G Pa(S)6:V d ← V ∪ ← → E , - → E d ← - → E ∪ {(e, v) : e ∈ ← → E , v ∈ e} ▷ Construct (G Pa(S) ) d 7: V vc ← ∪ v∈V d {v 1 , v 2 }, E vc ← {v 1 , v 2 } : v ∈ V d ∪ {w 1 , v 2 } : (w, v) ∈ - → E d 8:Construct a minimum vertex cut instance on the network G vc = ⟨V vc , E vc ⟩, with costs 0 for any v 1 where v ∈ V , C(v) for any v 2 where v ∈ V , and ∞ for any other vertex 9:J ← the minimum vertex cut between {x 1 : x ∈ Pa(S)} and {s 1 : s ∈ S} 10: Remark 3. Algorithm 1 enforces identification based on (generalized) adjustment for P X (Y ). As discussed above, this algorithm can be utilized as a heuristic approach to solve the MCID problem in (2). In this case, one can run the algorithm on the hedge hull of S rather than the whole graph. We prove in Appendix C that the cost of this approach is always at most as high as heuristic algorithm 1 of Akbari et al. [2022] , and is often in practice lower, as verified by our experiments.I ← {v : v 2 ∈ J}, Z ← {v : v 1 ∈ J} 11: return (I, Z)The worst-case time complexity of Algorithm 1 is cubic in the number of variables. The two main computational bottlenecks are (i) the preprocessing in lines 2-3, which involves up to |V | rounds of m-separation tests (performed via depth-first search), resulting in a complexity ofO |V | |V | + | - → E | + | ← → E |, and (ii) the minimum-cut instance in line 9, solved using a max-flow algorithm with |V vc | ∼ O(|V | + | ← → E |) and |E vc | ∼ O(|V | + | - → E | + | ← → E |) many vertices and edges, respectively.Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?Answer: [Yes] Justification: We will release our code as a toolbox on GitHub, providing access for researchers and practitioners. The link will be available upon publication of the paper. 
experiments: 
 In this section, we present numerical experiments that showcase the empirical performance and time efficiency of our proposed exact and heuristic algorithms. A comprehensive set of synthetic and real-world experiments analyzing the impact of various problem parameters on the performance of these algorithms, along with the complete implementation details, is provided in Appendix A. We first compare the time efficiency of our exact algorithms: WPMAX-SAT and ILP, with the exact algorithm of Akbari et al. [2022] . Then, we present results pertaining to performance of our heuristic algorithm. All experiments, coded in Python, were conducted on a machine equipped two Intel Xeon E5-2680 v3 CPUs, 256GB of RAM, and running Ubuntu 20.04.3 LTS. Results on exact algorithms. We compare the performance of the WPMAX-SAT formulation, the ILP formulation, and Algorithm 2 of Akbari et al. [2022] , called Minimal Hedge Solver (MHS) from hereon. We used the RC2 algorithm [Ignatiev et al., 2019] , and the Gurobi solver [Gurobi Optimization, LLC, 2023] , to solve the WPMAX-SAT problem, and the ILP, respectively. We ran each algorithm for solving the MCID problem on 100 randomly generated Erdos-Renyi [Erdos and Renyi, 1960] ADMG graphs with directed and bidirected edge probabilities ranging from 0.01 to 1.00, in increments of 0.01. We performed two sets of simulations: for single-district and multiple-district settings, respectively. In the single-district case, we varied n, the number of vertices, from 20 to 100, while in the multiple-district case, we fixed n = 20 and varied the number of districts from 1 to 9.We plot the average time taken to solve each graph versus the number of vertices (single-district) in Fig. 4 (a) and versus the number of districts (n = 20) in Fig. 4(b) . The error bands in our figures represent 99% confidence intervals. Focusing on the single-district plot, we observe that both of our algorithms are faster than MHS of Akbari et al. [2022] for all graph sizes. More specifically, ILP is on average one to two orders of magnitude faster than MHS, while SAT is on average four to five orders of magnitude faster. All three algorithms exhibit exponential growth in time complexity with the number of vertices, which is expected as the problem is NP-hard, but SAT grows at a much slower rate than the other two algorithms. This is likely due to RC2's ability of exploiting the structure of the SAT problem to reduce the search space efficiently. In the multiple-district case, we observe that the time complexity of both SAT and ILP grows polynomially with the number of districts, while the time complexity of MHS grows exponentially. This is consistent with theory, as MHS iterates over all partitions of the set of districts, which grows exponentially with the number of districts.Results on inexact algorithms. We compared Algorithm 1, our proposed heuristic, with the two best performing heuristic algorithms in Akbari et al. [2022] , H 1 and H 2 . We ran each algorithm on 500 randomly generated Erdos-Renyi ADMG graphs with directed and bidirected edge probabilities in {0.1, 0.5}, with n ranging from 10 to 200. We randomly sampled the cost of each vertex from a discrete uniform distribution on [1, n]. In Fig. 5 , we plot the normalized cost of each algorithm, computed by dividing the cost of the algorithm by the cost of the optimal solution, provided by WPMAX-SAT. Observe that Algorithm 1 consistently outperforms H 1 and H 2 for all graph sizes.Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material?Answer: [Yes] Justification: We will release our code as a toolbox on GitHub, providing access for researchers and practitioners. The link will be available upon publication of the paper.Guidelines:• The answer NA means that paper does not include experiments requiring code. • Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted. 
conclusion: 
 We introduced novel formulations and efficient algorithms for the MCID problem, demonstrating significant improvements over existing methods. Our extensive experiments showed that the WPMAX-SAT reformulation, particularly when using a high-performance solver like RC2, excels in both speed and effectiveness. In contrast, the ILP reformulation offers a more interpretable approach, especially valuable for incorporating additional constraints such as domain expert knowledge. Moreover, our work on designing minimum-cost experiments for obtaining valid adjustment sets demonstrates both practical and theoretical advancements. We highlighted the superior performance of our proposed methods through extensive numerical experiments. We envision designing efficient approximation algorithms for MCID as future work.Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?Answer: [Yes] Justification: We specify the experimental details both in the text and also in the code.Guidelines:• The answer NA means that the paper does not include experiments.• The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them. • The full details can be provided either with the code, in appendix, or as supplemental material. 
experiment statistical significance: 
 Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?Answer: [Yes] Justification: The plotted results are displayed with 99% CI on each figure reporting experimental results.Guidelines:• The answer NA means that the paper does not include experiments.• The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper. • The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions). • The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.) • The assumptions made should be given (e.g., Normally distributed errors).• It should be clear whether the error bar is the standard deviation or the standard error of the mean. • It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified. • For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates). • If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text. 
experiments compute resources: 
 Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?Answer: [Yes] Justification: The computing resources used to produce the numerical results are provided at the beginning of Section 5Guidelines:• The answer NA means that the paper does not include experiments.• The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage. • The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute. • The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper). 
code of ethics: 
 Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines?Answer: [Yes] Justification: The research conducted in this paper respects the NeurIPS Code of Ethics.Guidelines:• The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 
broader impacts: 
 Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?Answer: [NA] Justification:Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact. • Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.• The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA] Justification: The paper poses no such risks.Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters. • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?Answer: [Yes] Justification: We cited all the original papers that produced the (code of the) various algorithms and packages used in the paper Guidelines:• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided. • If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. • For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. 
: 
 The average runtime of our approach compared with the state-of-the-art (S.O.T.A) from Akbari et al. [2022] .Identifying causal effects is a central problem of interest across many fields, ranging from epidemiology all the way to economics and social sciences. While conducting randomized (controlled) trials provides a framework to analyze and estimate the causal effects of interest, such experiments are often impractical due to various limitations, including financial, logistical, and ethical constraints. Even when they are practical, gathering sufficient data to draw statistically significant conclusions is often challenging due to the high costs.Costs can arise in multiple forms: financial costs (e.g., implementing costly interventions), time resources (e.g., upgrading infrastructure), and other logistical constraints such as human resources. Moreover, certain experiments might be unethical or outright unfeasible, such as exposing patients to harmful treatments, and hence have infinite cost.v 1 v 3 w v 2 y (a) v 1 v 3 v 2 S (b) v 1 z 1 v 2 z 2 . . . . . . v m z m S (c) s 1 s 2 v 3 v 1 v 2 v 5 X 4 (d)Observational data, which is usually more abundant and accessible, offers an alternative avenue. However, observational studies bring a new challenge: the causal effect may not be identifiable due to unmeasured confounding, making it impossible to draw inferences from the observed data [Pearl, 2009, Hernán and Robins, 2006] . A middle ground between observational and experimental approaches is to fuse data from both types of studies [Bareinboim and Pearl, 2016, Athey et al., 2020] . For example, cities might introduce low-emission zones as a proxy experiment before banning diesel vehicles [Dey et al., 2018] , or governments might impose regional sugary drink taxes to estimate the effects of nationwide policies Redondo et al. [2018] . Several works have studied the achievability of identification from ensembles of observational and experimental data [Bareinboim and Pearl, 2012 , Lee et al., 2020a , Kivva et al., 2022 , Jamshidi et al., 2024] . Our previous work [Akbari et al., 2022] was the first to investigate the problem of designing proxy experiments to identify a causal effect that is not identifiable from observational data alone.To illustrate the need for proxy experiments, consider the following drug-drug interaction example, based on the example in Lee et al. [2020a] .Example 1. (Complex Drug Interactions and Cardiovascular Risk) Consider a simplified example involving the interaction between a new antihypertensive therapy (v 1 ), anti-diabetic medications (v 2 ), renal function modulators (v 3 ), and their effects on blood pressure (w) and cardiovascular disease (y). Blood pressure and cardiovascular health are closely linked. The antihypertensive therapy v 1 directly influences the need for renal function modulators v 3 , and v 3 in turn directly affects blood pressure w. Additionally, anti-diabetic medications v 2 reduce the risk of cardiovascular disease y by controlling blood sugar levels, while blood pressure w directly impacts y. Unmeasured factors confound these relationships: shared health conditions can influence the prescription of both v 1 and v 3 ; lifestyle factors affect both v 1 and w; and common conditions like metabolic syndrome can impact both v 1 and v 2 . Fig. 2 (a) illustrates the resulting causal graph, whose directed edges represent direct causal effects, and bidirected edges indicate unmeasured confounders. Suppose we are interested in estimating the intervention effects of v 2 and v 3 on y, which are not identifiable from observational data alone. Moreover, we cannot directly intervene on these variables because v 2 and v 3 are essential for managing immediate, life-threatening conditions. Instead, we can intervene on v 1 , which is a feasible and safer approach due to the broader range of treatment options and more manageable risks associated with adjusting antihypertensive therapy. As we shall see, intervention on v 1 suffices for identifying the effects of v 2 and v 3 on y.Selecting the optimal set of proxy experiments is not straightforward in general. In particular, in [Akbari et al., 2022] we proved that the problem of finding the minimum-cost intervention set to identify a given causal effect, hereon called the MCID problem, is NP-complete and provided a naive algorithm that requires solving exponentially many instances of the minimum hitting set problem in the worst case. As the minimum hitting set problem is NP-complete itself, our earlier algorithm in [Akbari et al., 2022] can become computationally intractable even for graphs with a modest number of vertices. Moreover, this algorithm was tailored to a specific class of causal effects in which the effect of interest is a functional of an interventional distribution where the intervention is made on every variable except one district of the causal graph2 . For a general causal effect, the complexity of this algorithm includes an additional (super-)exponential multiplicative factor, where the exponent is the number of districts.In this work, we revisit the MCID problem and develop tractable algorithms by reformulating the problem as instances of well-known problems, such as the weighted maximum satisfiability and integer linear programming problems. Furthermore, we analyze the problem of designing minimum cost interventions to obtain a valid adjustment set for a query. This problem not only merits attention in its own right, but also serves as a proxy for MCID. Our contributions are as follows:• We formulate the MCID problem in terms of a partially weighted maximum satisfiability, integer linear programming, submodular function maximization, and reinforcement learning problem.While our main focus is on the former two reformulations, we state the others in Appendix D.• We propose new, and in practice, much faster (up to six orders of magnitude) algorithms for solving the problem optimally using our reformulations. Moreover, the computational complexity of our proposed algorithms scales quadratically in the number of districts, a significant improvement over the super-exponential growth exhibited by existing algorithms -see Remark 2.• We formulate and study the problem of designing minimum-cost experiments for identifying a given effect through finding a valid adjustments set. Besides the practical advantages of valid adjustment, including ease of interpretability and tractable sample complexity, this approach enables us to design a polynomial-time heuristic algorithm for the MCID problem that outperforms the heuristic algorithms provided in Akbari et al. [2022] .• We present new numerical experiments that demonstrate the exceptional speed of our exact algorithms when compared to the current state-of-the-art, along with our heuristic algorithm showcasing superior performance over previous heuristic approaches. 
 
 Appendix: We conduct experiments using 17 real-world networks from the Bayesian Network Repository8 . This repository encompasses networks from diverse domains such as biology, engineering, medicine, and social science. In our experiments, each network from the repository is utilized as the DAG on the known variables. We assign a random cost to each variable, sampled uniformly at random from [1, n]. We then introduce hidden variables by randomly sampling bidirected edges with probabilities of 0.01, 0.1, and 0.3, resulting in 50 ADMGs per network. For each ADMG, we select S to be a singleton consisting of the last node in the causal order. This choice ensures that any other node would not reduce the network's size by ignoring some vertices and edges, as outgoing edges from S are irrelevant for the MCID problem.Subsequently, we implemented the exact algorithms: minimal hedge solver (Algorithm 2 of Akbari et al. [2022] ), ILP, and WPMAX-SAT. We also tested the heuristic algorithms H 1 and H 2 from Akbari et al. [2022] , alongside Algorithm 1 from this work.In Figure 6 , we present a semi-log bar chart of the average time taken for each exact algorithm to solve an instance of a graph for each network. Notably, our approaches, ILP and SAT, consistently outperform MHS by an average factor of over 100, and by more than 1000 times on the largest network, link. Additionally, SAT demonstrates superior performance in all but two networks, andes and diabetes.In Figure 7 , we provide a semi-log plot of the normalized cost of the heuristics H 1 and H 2 from Akbari et al., 2022, and our Algorithm 1, averaged across each network. It is evident that Algorithm 1 significantly outperforms H 1 , often by one to two orders of magnitude. Although H 2 performs better due to its focus on performing cuts on nodes over directed edges (which are fewer), its cost remains higher than that of Algorithm 1. Overall, the results align with our findings from synthetic simulations in the main text. Our WPMAX-SAT and ILP formulations surpass the previous stateof-the-art approach of Akbari et al. [2022] , with WPMAX-SAT being the fastest. Furthermore, our polynomial-time Algorithm 1 consistently outperforms the heuristics of Akbari et al. [2022] . We extended the simulations in Section 5 for up to n = 500 vertices, and the results are presented in Fig. 8 . We observe that even at n = 500, WPMAX-SAT takes around the same time as Algorithm 2 of Akbari et al. [2022] does to solve n = 40 (230 s for both). Moreover, we can clearly see the exponential growth in time complexity, as expected, especially for n > 400.We run experiments on varying the probabilities of directed and bidirected edges in the graph. We fix the number of vertices at n = 20 and vary the probabilities of directed and bidirected edges from 0.001 to 1.00 in increments of 0.001. The results are presented in Fig. 9 . We run experiments with n = 20 and costs sampled from a Poisson distributions with mean parameter ranging from 1 to 100. The results are presented in Fig. 10 . Interestingly, there appears to be no clear trend in the time complexity of the algorithms with respect to the mean parameter of the Poisson distribution. This suggests that the time complexity of the algorithms is not significantly affected by the cost of the vertices. A.6 Investigating the effects of directed and bidirected edge probabilities on the performance of the heuristic algorithmsWe run experiments on varying the probabilities of directed and bidirected edges in the graph. We vary n from n = 10 to n = 200 and the probabilities of directed and bidirected edges in {0.1, 0.5}.The results are presented in Fig. 11 . We see that our proposed heuristic algorithm consistently outperforms the heuristic algorithms of Akbari et al. [2022] for all graph sizes and edge probabilities.We include the algorithm for finding the hedge hull for the sake of completeness. This algorithm is adopted from Akbari et al. [2022] .Algorithm 2 Pruning algorithm1: procedure PRUNE(G = ⟨V, - → E , ← → E ⟩, S) 2: H ← Anc V (S) 3:while True do 4:H ′ ← {v ∈ H : v has a bidirected path to S in G[H]} 5: if H ′ = H then 6: return H 7: H ← Anc H ′ (S) 8: if H = H ′ then 9:return HThe procedure for constructing the SAT formula when S comprises multiple districts was postponed to this section due to space limitations. This procedure is detailed below.Algorithm 3 SAT construction 1: procedure CONSTRUCTSAT(X, Y, G = ⟨V, - → E , ← → E ⟩) 2: S ← Anc V \X (Y ) 3: S ← districts of S in G[S] 4: r ← |S| 5: F ← 1 6:for ℓ ∈ {1, . . . r} do ▷ iterate over districts of S 7:m ← |H G (S ℓ ) \ S ℓ | ▷ # iterations 8:for k ∈ {1, . . . , r} do ▷ iterate over expressions 9:F ← F ∧ (x i,0,k ∨ ¬z k,ℓ ) for every i s.t. v i ∈ S ℓ 10: F ← F ∧ (x i,j,k,ℓ ∨ ¬z k,ℓ) for every i s.t. v i ∈ S ℓ and every j ∈ {1, . . . , m + 1} 11:for (v i , v p ) ∈ - → E do ▷ iteration j = 1 12: F ← F ∧ (¬x i,0,k ∨ x i,1,k,ℓ ∨ ¬x p,1,k,ℓ ∨ ¬z k,ℓ ) 13:for j ∈ {2, . . . , m + 1} do 14:if j is odd then 15:for (v i , v p ) ∈ - → E do 16: F ← F ∧ (¬x i,j-1,k,ℓ ∨ x i,j,k,ℓ ∨ ¬x p,j,k,ℓ ∨ ¬z k,ℓ ) 17: else 18: for {v i , v p } ∈ ← → E do 19: F ← F ∧ (¬x i,j-1,k,ℓ ∨ x i,j,k,ℓ ∨ ¬x p,j,k,ℓ ∨ ¬z k,ℓ ) 20: F ← F ∧ (¬x p,j-1,k,ℓ ∨ x p,j,k,ℓ ∨ ¬x i,j,k,ℓ ∨ ¬z k,ℓ ) 21: F ← F ∧ (¬x i,m+1,k,ℓ ∨ ¬z k,ℓ ) for every v i / ∈ S ℓ 22: F ← F ∧ (z 1,ℓ ∨ • • • ∨ z r,ℓ ) 23:return FC.1 Results of Section 3Theorem 1. The 3-SAT formula F constructed by the procedure above given G and S has a satisfying solution {x * i,j } where x * i,0 = 0 for i ∈ I ⊆ {1, . . . , m} and x * i,0 = 1 for i ∈ {1, . . . , m}\I if and only if I intersects every hedge formed for S in G; i.e., I is a feasible solution to the optimization in Eq. (2).Proof. Proof of 'if:' Suppose I hits every hedge formed for S. We construct a satisfying solution for the SAT formula as follows. We begin with x i,0 :x * i,0 = 0; if i ∈ I 1; o.w.For every j ∈ {1, . . . , m + 1}, define H j = {i : x i,j-1 = 1}. Then x * i,j for j ∈ {1, . . . , m + 1} is chosen recursively as below.• Odd j: x * i,j = 1 if i ∈ H j and v i has a directed path to S in G[H j ], and x * i,j = 0 otherwise.• Even j: x * i,j = 1 if i ∈ H j and v i has a bidirected path to S in G[H j ], and x * i,j = 0 otherwise.Next, we prove that {x * i,j } as defined above satisfies F . We consider the three types of clauses in F separately:• For odd j ∈ {1, . . . , m + 1}, the clause (¬x i,j-1 ∨ x i,j ∨ ¬x ℓ,j ) corresponds to the directed edge(v i , v ℓ ) ∈ - → E : if either x * i,j-1 = 0 or x * ℓ,j = 0, then this clause is trivially satisfied. So suppose x * i,j-1 = 1, and x * ℓ,j = 1, which implies by construction that x * ℓ,j-1 = 1. Therefore, i, ℓ ∈ H j . Further, since x * ℓ,j = 1, v ℓ has a directed path to S in G[H j ]. Then v i has a directed path to S in G[H j ] because of the edge (v i , v ℓ ) ∈ - → E. By the construction above, x * i,j = 1, which satisfies the clause.• For even j ∈ {1, . . . , m + 1}, the clause (¬x i,j-1 ∨ x i,j ∨ ¬x ℓ,j ) corresponds to the bidirected edge {v i , v ℓ } ∈ ← → E : if either x * i,j-1 = 0 or x * ℓ,j = 0, then this clause is trivially satisfied. So suppose x * i,j-1 = 1, and x * ℓ,j = 1, which implies by construction that x * ℓ,j-1 = 1. Therefore, i, ℓ ∈ H j . Further, since x * ℓ,j = 1, v ℓ has a bidirected path to S in G[H j ]. Then v i has a bidirected path to S in G[H j ] because of the edge {v i , v ℓ } ∈ ← → E . By the construction above, x * i,j = 1, which satisfies the clause.• The clauses ¬x i,m+1 : First note that by construction, if for some j ∈ {1, . . . , m + 1},x * i,j-1 = 0, then x * i,j = x * i,j+1 = • • • = x * i,m = 0. That is, {x * i,j } m j=0is a non-increasing binary-valued sequence for every i. Therefore, for every i ∈ {1, . . . , m}, there exists at most one j such that x * i,j-1 > x * i,j . We consider two cases separately:-There are exactly m many j ∈ {1, . . . , m + 1} for which there exists at least one i such that x * i,j-1 > x * i,j . In this case, for every i ∈ {1, . . . , m}, there exists exactly one j ∈ {1, . . . , m + 1} such that x * i,j-1 > x * i,j . Then for every i, there exists j such that x * i,j = 0, and following the argument above, x * i,m+1 = 0. Hence, the clauses ¬x i,m+1 are all satisfied. -There are strictly less than m many j ∈ {1, . . . , m + 1} for which there exists at least one i such that x * i,j-1 > x * i,j . Then there exist j, j ′ ∈ {1, . . . , m + 1} such that for every i ∈ {1, . . . , m}, x * i,j-1 = x * i,j and x * i,j ′ -1 = x * x,j ′ . Assume without loss of generality that j ′ < j and therefore, j > 1. If x * i,j = 0 for every i, then by similar arguments as the previous case, x * i,m+1 = 0 and the clauses ¬x i,m are satisfied. So suppose for the sake of contradiction that there exists a non-empty set H j = {i : x * i,j-1 = 1} ̸ = ∅. Note that H j+1 := {i : x * i,j = 1} = H j , since x * i,j-1 = x * i,j for every i. Moreover, I ∩ H j = ∅ since x * i,0 = 0 for every i ∈ I and {x * i,k } k is non-increasing. Assume without loss of generality that j is odd. The proof is identical in case j is even. By definition, the set of vertices H j+1 = H j have a directed path to S in G[H j ]. Moreover, the set of vertices H j are those vertices in H j-1 that have a bidirected path to S in G[H j-1 ] (here we used j > 1 for H j-1 to be well-defined.) That is, H j is the connected component of S in G[H j-1 ]. The latter implies that every vertex in H j has a bidirected path to S in G[H j ]. We proved that H j is a hedge formed for S, and H j ∩ I = ∅. This contradicts with I intersecting with every hedge formed for S.Proof of 'only if:' Suppose {x * i,j } is a satisfying solution, where x * i,0 = 1 for every i / ∈ I. To prove I intersects every hedge formed for S, it suffices to show that there is no hedge formed for S in G[V \ I]. Assume, for the sake of contradiction, that this is not the case. That is, there exists a hedge H ⊆ V \ I formed for S in G. Suppose for some j ∈ {1, . . . , m + 1}, it holds that x * i,j-1 = 1 for every v i ∈ H. We show that x * i,j = 1 for every v i ∈ H. We consider the following two cases separately:• Even j: for arbitrary v i , v ℓ ∈ H such that {v i , v ℓ } ∈← → E , consider the clauses (¬x i,j-1 ∨ x i,j ∨ ¬x ℓ,j ) and (¬x ℓ,j-1 ∨ x ℓ,j ∨ ¬x i,j ) that are in F by construction for even j. Sincex * i,j-1 = x * ℓ,j-1 = 1, the expression (x * i,j ∨ ¬x * ℓ,j ) ∧ (x * ℓ,j ∨ ¬x * i,j) is satisfied; i.e., it evaluates to 'true.' The latter expression is equivalent to(x * i,j ∧ x * ℓ,j ) ∨ (¬x * i,j ∧ ¬x * ℓ,j), which implies that x * i,j = x * ℓ,j . Note that i, ℓ were chosen arbitrarily. This implies that x * i,j is equal for every i, since H is a connected component through bidirected edges by definition of a hedge. Finally, since by construction, x i,j = 1 for every v i ∈ S ⊆ H, that equal value is 1. Therefore, x * i,j = 1 for every i such that v i ∈ H.• Odd j: the proof is analogous to the case where j is even. For arbitraryv i , v ℓ ∈ H such that (v i , v ℓ ) ∈ - → E , consider the clause (¬x i,j-1 ∨ x i,j ∨ ¬x ℓ,j ). Since x * i,j-1 = 1, the expression (x * i,j ∨ ¬x * ℓ,j) is satisfied; i.e., it evaluates to 'true.' The latter implies that if x * ℓ,j = 1 and v i has a directed edge to v j , then x * i,j = 1. Using the same argument recursively, if x * ℓ,j = 1 and v i has a directed 'path' to v j in G[H], then x * i,j = 1. By construction, x * ℓ,j = 1 for every v ℓ ∈ S, and by definition of a hedge, every vertex v i ∈ H has a directed path to S. As a result, x * i,j = 1 for every v i ∈ H.Since for every v i ∈ H, x * i,0 = 1, using the arguments above, by induction, x * i,m+1 = 1 for every v i ∈ H. However, this contradicts the fact that {x * i,j } satisfies F , since F includes the clauses ¬x i,m+1 for every i.Lemma 1. Let S = {S 1 , . . . , S r } be the set of districts of S, where S = Anc V \X (Y ). There exists an intervention set family I * of size |S| = r that is optimal for identifying P X (Y ).Proof. Let I be an optimizer of Eq. (1). By Proposition 1, for every S i ∈ S, there exists I j ∈ I that hits every hedge formed for S i . The set of such I j s is a subset of at most size r of I, which implies that |I| ≤ r since I is optimal. If |I| = r, the claim is trivial. If |I| < r, then simply add (r -|I|) empty intervention sets to I to form an intervention set family I * with the same cost which is an optimal solution to Eq. ( 1).Theorem 2. Suppose G, a set of its vertices S with districts S = {S 1 , . . . , S r }, and an intervention set family 2 I = {I 1 , . . . , I r } are given. Define m ℓ = |H G (S ℓ ) \ S ℓ |, i.e., the cardinality of the hedge hull of S ℓ excluding S ℓ itself. The SAT formula F constructed by Algorithm 3 has a satisfying solution {x * i,0,k }∪{x * i,j,k,ℓ }∪{z * k,ℓ } where for every ℓ ∈ {1, . . . , r}, there exists k ∈ {1, . . . , r} such that (i) z * k,ℓ = 1, (ii) x * i,0,k = 0 for every i ∈ I k , and (iii) x * i,0,k = 1 for every i ∈ {1, . . . , m ℓ } \ I k , if and only if I is a feasible solution to optimization of Eq. (1).Proof. The proof is identical to that of Theorem 1 with necessary adaptations.Proof of 'if:' Suppose I is a solution to Eq. (1). From Proposition 1, for every S ℓ ∈ S, there exists k such that I k hits every hedge formed for S ℓ . Assign z * k,ℓ = 1 and z k ′ ,ℓ = 0 for every other k ′ ̸ = k, thereby satisfying every clause that includes ¬z k ′ ,ℓ , k ′ ̸ = k. So it suffices to assign values to other variables so that clauses including ¬z k,ℓ . Since z k,ℓ = 1, these clauses reduce to (¬x i,j-1,k,ℓ ∨ x i,j,k,ℓ ∨ ¬x p,j,k,ℓ ) (see lines 16, 19, or 20.) These clauses are exactly in the form of 3-SAT clauses as in the single-district case procedure. An assignment exactly parallel to the proof of Theorem 1 satisfies these clauses.Proof of 'only if:' Suppose {x * i,0,k } ∪ {x * i,j,k,ℓ } is a satisfying solution, where for some k, ℓ ∈ {1, . . . , r}, it holds that z * k,ℓ = 1 and x * i,0,k = 1 for every i / ∈ I k . We show that I k hits every hedge formed for S ℓ . Since such a k exists for every S ℓ , we will conclude that I is feasible for Eq. ( 1) by Proposition 1. Finally, to show that I k hits every hedge formed for S ℓ , note that satisfiability of all clauses containing the literal ¬z * k,ℓ reduces to the satisfiability of (¬x i,j-1,k,ℓ ∨ x i,j,k,ℓ ∨ ¬x p,j,k,ℓ ) (see lines 16, 19, or 20) , and the same arguments as in the proof of Theorem 1 apply.Lemma 2. Let X, Y be two disjoint sets of vertices in G such that X is minimal as defined above. Set Z ⊆ V is a generalized adjustment set for P X (Y ) under intervention I if (i) Z ⊆ Anc(S), and (ii) Z is a vertex cut9 between S and Pa(S) in (G IPa(S) ) m , where S = Anc V \X (Y ), and G IPa(S) is the ADMG resulting from omitting all edges incoming to I and all edges outgoing of Pa(S).Proof. Define S = Anc V \X (Y ). First, we show that Pa(S) ⊆ X. Assume the contrary, i.e., there is a vertex w ∈ Pa(S) \ X. Clearly w has a directed path to S (a direct edge) that does not go through X. This implies that w ∈ Anc V \X (S), and since by definition, S = Anc V \X (Y ), w ∈ Anc V \X (Y ) = S. However, the latter contradicts with w ∈ Pa(S). Second, we note that from the third rule of do calculus [Pearl, 2009] , P W (S) = P Pa(S) (S) for any W ⊇ Pa(S). Combining the two arguments, we have the following:EQUATIONTo proceed, we will use the following proposition.Proposition 3 (Lauritzen et al., 1990) . Let S, R, and Z be disjoint subsets of vertices in a directed acyclic graph G.Then Z d-separates S from R if and only if Z is a vertex cut between S and R in (G[Anc(S ∪ R ∪ Z)]) m .Choose R = Pa(S) in the proposition above. Since Z ⊆ Anc(S), we have that Anc(S ∪ R ∪ Z) = Anc(S). From condition (ii) in the lemma, Z is a vertex cut between S and R in (G IPa(S) ) m , which implies it is also a vertex cut in (G IPa(S) [Anc(S)]) m , as every path in the latter graph exists in (G IPa(S) ) m . Using the proposition above, Z d-separates S and Pa(S) in G IPa(S) . This is to say, Z blocks all non-causal paths from Pa(S) to S in G I , and it clearly has no elements that are descendants of Pa(S). Therefore, Z satisfies the adjustment criterion of Shpitser et al. [2010] w.r.t. P Pa(S) (S) in G I . That is, the following holds:P I∪Pa(S) (S) = E P I [P I (S | Pa(S), Z)],where the expectation is w.r.t. P I (Z). Choosing W = I ∪ Pa(S) in Eq. ( 6), we getP X (S) = E P I [P I (S | Pa(S), Z)].Marginalizing S \ Y out in both sides of the equation above, we haveP X (Y ) = E P I [P I (Y | Pa(S), Z)].The last step of the proof is to show that Pa(S) = X. We already showed that Pa(S) ⊆ X. For the other direction, we will use the minimality of X. Suppose to the contrary that x ∈ X \ Pa(S). We first show that every causal path from x to Y goes through X \ {x}. Suppose not. Then take a causal path x, s 1 , . . . , s m , y be a causal path from x to y ∈ Y . Note that s 1 has a causal path to Y that does not go through X. By definition, s 1 ∈ S, which implies x ∈ Pa(S), which is a contradiction. Therefore, every causal path from x to Y goes through X \ {x}, and consequently, there is no causal path from x to Y in G X . Clearly there is no backdoor path either. Every other path has a collider on it, and therefore is blocked by X \ {x} -note that none of these can be colliders in G X . Therefore, {x} is d-separated from Y given X \ {x} in G X , which contradicts the minimality of X w.r.t. the third rule of do calculus. This shows X ⊆ Pa(S), completing the proof.Theorem 3. Let (I, Z) be the output returned by Algorithm 1 for the query P X (Y ). Then, -Z is a generalized adjustment set for P X (Y ) under intervention I.-I is the minimum-cost intervention for which there exists a generalized adjustment set based on the graphical criterion of Lemma 2.Proof. For the first part, using Lemma 2, it suffices to show that Z is a vertex cut between S and Pa(S) in (G IPa(S) ) m . Suppose not. That is, there exists a path from S to Pa(S) in (G IPa(S) ) m that does not pass through any member of Z. Let P = s, v 1 , . . . , v l , x represent this path, where s ∈ S and x ∈ Pa(S). We construct a corresponding path P ′ in G vc as follows. The first vertex on P ′ is s 1 , which corresponds to the first vertex on P , s. We then walk along P and add a path to P ′ corresponding to each edge we traverse on P as follows. Consider this edge to be {v, w} -for instance, the first edge would be {s, v 1 }. By definition of (G IPa(S) ) m , for every pair of adjacent vertices v, w on the path P , one of the following holds:(i) v → w in (G IPa(S) ) d , (ii) v ← w in (G IPa(S)) d , or (iii) v and w have a common child t in (G IPa(S) ) d . In case (i), we add v 1 , w 2 , w 1 . In case (ii), we add v 2 , w 1 . Finally, in case (iii), we add v 1 , t 2 , w 1 to P ′ . We continue this procedure until we traverse all edges on P . The last vertex on P ′ is x 2 , as x has no children in (G IPa(S) ) d . Finally we add x 1 to this path, as x 2 and x 1 are always connected by construction. Note that by construction of P ′ , any vertex that appears with index 2 has a parent in v → w in (G IPa(S) ) d , and therefore is not a member of I. Hence, {v 2 : v ∈ I} does not intersect with P ′ . Further, {v 1 : v ∈ Z} does not intersect with P ′ either, as none of the vertices appearing on P ′ correspond to Z. This is to say that J = {v 2 : v ∈ I} ∪ {v 1 : v ∈ Z}, which is the solution obtained by Algorithm 1 in line 10, does not cut the path P ′ . This contradicts with J being a vertex cut.For the second part, let (I ′ , Z ′ ) be so that Z ′ is a vertex cut between S and Pa(S) in (G I ′ Pa(S) ) m , andI ′ induces a lower cost than I; that is, C(I ′ ) < C(I). Define J ′ = {v 2 : v ∈ I ′ } ∪ {v 1 : v ∈ Z ′ }.Clearly, the cost of J ′ is equal to C(I ′ ), which is lower than the cost of minimum vertex cut found in line 10 of Algorithm 1. It suffices to show that J ′ is also a vertex cut between {x 1 : x ∈ Pa(S)} and {s 1 : s ∈ S} in G vc to arrive at a contradiction. Suppose not; that is, there is a path P = s 1 , . . . , x 1 on G vc that J ′ = {v 2 : v ∈ I ′ } ∪ {v 1 : v ∈ Z ′ } does not intersect. None of the vertices with index 2 on P belong to I ′ , and none of the vertices with index 1 belong to Z ′ . Analogous to the first part, we construct a corresponding path P ′ -this time in (G I ′ Pa(S) ) m . The starting vertex on P ′ is s, which corresponds to s 1 , the initial vertex on P . Let us imagine a cursor on s 1 . We then sequentially build P ′ by traversing P as follows. We always look at sequences starting with v 1 (where the cursor is located): when the sequence is of the form v 1 , w 2 , w 1 or v 1 , v 2 , w 1 , we add w to P ′ , and move the cursor to w 1 ; however, when the sequence is of the form v 1 , w 2 , r 1 , we add r 1 to P ′ and move the cursor to r 1 . By construction of G vc , no other sequence is possible -note that there are no edges between v 1 and w 1 or v 2 and w 2 where v and w are distinct. Since none of the vertices with index 2 on P belong to I, in the first case, the corresponding edge v ← w or v → w is present in (G I ′ Pa(S) ) d and consequently, the edge {v, w} is present in (G I ′ Pa(S) ) m ; and in the latter case, both edges v → w and w ← r are present in (G I ′ Pa(S) ) d and consequently, the edge {v, r} is present in (G I ′ Pa(S) ) m . P ′ is therefore a path between S and Pa(S) in (G I ′ Pa(S) ) m . Notice that by construction, only those vertices appear on P ′ that their corresponding vertex with index 1 appears on P -the cursor always stays on vertices with index 1. As argued above, none of such vertices belong to Z ′ , which means Z ′ does not intersect with P ′ which is a path from S to Pa(S) in (G I ′ Pa(S) ) m . This contradicts with Z ′ being a vertex cut.Proof. Since the algorithms are run in the hedge hull of S, assume without loss of generality that V = H G (S), i.e., V is the hedge hull of S. From Theorem 3, Algorithm 1 finds the optimal (minimum-cost) intervention I such that there exists a set Z ⊆ V that is a vertex cut between S and Pa(S) in (G IPa(S) ) m . To prove that the cost of the solution returned by Algorithm 1 is always smaller than or equal to that of heuristic algorithm 1 of Akbari et al. [2022] , it suffices to show that the solution of their algorithm is a feasible point for the statement above. That is, denoting the output of heuristic algorithm 1 of Akbari et al. [2022] by I 1 , we will show that there exist sets Z 1 ⊆ V such that it is a vertex cut between S and Pa(S) in (G I1Pa(S) ) m .Heuristic algorithm 1: This algorithm returns an intervention set I 1 such that there is no bidirected path from Pa(S) to S in G I1 . We claim Z 1 = V \ Pa(S) \ S satisfies the criterion above. To prove this, consider an arbitrary path P between S and Pa(S) in (G I1Pa(S) ) m . If there is an observed vertex v ∈ V on P , this vertex is included in Z 1 and separates the path. So it suffices to show that there is no path P between S and Pa(S) in (G I1Pa(S) ) m where all the intermediate vertices on P correspond to unobserved confounders. Suppose there is. That is, P = x, u 1 , . . . , u m , s, where x ∈ Pa(S) and {u i } m i=1 are unobserved. Since u i is not connected to u j in (G I1Pa(S) ) d , it must be the case that any u i and u i+1 have a common child v i,j in (G I1Pa(S) ) d . This is to say, there is a pathx ← u 1 → v 1,2 ← u 2 → • • • → v m-1,m ← u m → s in (G I1Pa(S)) d , which corresponds to the bidirected path x, v 1,2 , . . . , v m-1,m , s in G I1 . This contradicts with the fact that there is no bidirected path between Pa(S) and S in G I1 .Lemma 3. For any district S ⊆ V , the function f S : 2 V \S → Z ≤0 is submodular.Proof. Take two distinct vertices {x, y} ∈ V \ S and an arbitrary setI ⊂ V \ S \ {x, y}. It suffices to show that f S (I ∪ {x, y}) -f S (I ∪ {y}) ≤ f S (I ∪ {x}) -f S (I).By definition, the right hand side is the number of hedges H ⊆ V \ I formed for S such that x / ∈ H. Similarly, the left hand side counts the number of hedges H ⊆ V \ (I ∪ {y}) formed for S such that x / ∈ H. The inequality holds because the set of hedges counted by the left hand side is a subset of that on the right hand side.Proposition 4. The combinatorial optimization of Eq. (2) is equivalent to the following unconstrained submodular optimization problem.EQUATION)Proof. The submodularity of the objective function follows from Lemma 3. To show the equivalence of the two optimization problems, we show that a maximizer I * of Eq. ( 7) (i) hits every hedge formed for S, and (ii) has the optimal cost among such sets.Proof of '(i):' Note that f S (I) = 0 if and only if there are no hedges formed for S in G[V \ I * ], or equivalently, I hits every hedge formed for S. So it suffices to show that f S (I * ) = 0 for every maximizer I * of Eq. ( 7). To this end, first note thatf S (V \ S) - v∈V \S C(v) 1 + v∈V \S C(v) = 0 -1 + 1 1 + v∈V \S C(v) > -1, which implies that f S (I * ) - v∈I * C(v) 1 + v∈V \S C(v) > -1.On the other hand, clearlyv∈I * C(v)1+ v∈V \S C(v) ≥ 0, which combined with the inequality above implies f S (I * ) > -1. Since f S (I * ) ∈ Z ≤0 , it is only possible that f S (I * ) = 0.Proof of '(ii):' We showed that f S (I * ) = 0. So I * maximizes v∈I C(v) C(v) among all those I such that f S (I) = 0. Since the denominator is a constant, this is equivalent to minimizing C(I) = v∈I C(v) among all those I that hit all the hedges formed for S, which matches the optimization of Eq. ( 2).1+ v∈V \SIn this Section, we reformulate the minimum-cost intervention design as a submodular optimization problem. Submodular functions exhibit a property akin to diminishing returns: the incremental gain from adding an element to a set decreases as the set grows [Nemhauser et al., 1978] .Definition 5. A function f : 2 V → R is submodular if for all A ⊆ B ⊆ V and v ∈ V \ B, we have that f (A ∪ {v}) -f (A) ≥ f (B ∪ {v}) -f (B).Given an ADMG G = ⟨V, -→ E , ← → E ⟩ a district S in G, and an arbitrary set I ⊆ V \ S, we define f S (I) as the negative count of hedges formed for S in G[V \ I]. Lemma 3. For any district S ⊆ V , the function f S : 2 V \S → Z ≤0 is submodular.Note that g S : 2 V \S → R, where g S (I) := f S (I) + α v∈I C(v), and α is an arbitrary constant, is also submodular as the second component is a modular function (similar definition as in 5 only with equality instead of inequality.). Proposition 4. The combinatorial optimization of Eq. ( 2) is equivalent to the following unconstrained submodular optimization problem.EQUATIONWe model the MCID problem given a graph G = (V, E) and S ⊂ V , as a Markov decision process (MDP), where a vertex is removed in each step t until there are no hedges left. The goal is to minimize the cost of the removed vertices (i.e., intervention set). Naturally, the action space is the set of vertices, V and the state space is the set of all subsets of V . More precisely, let s t and a t denote the state and the action of the MDP at iteration t, respectively. Then, s t is the hedge hull for S from the remaining vertices at time t, and action a t is the vertex that will be removed from V t in that iteration. Consequently, the state transition due to action a t is s t+1 = H hull (V t \ {a t }). The immediate reward of selecting action a t at state s t will be the negative of the cost of removing (i.e., intervening on) a t , given by r(s t , a t ) = -C(a t ).The MDP terminates when there are no hedges left and the hedge hull of the remaining vertices is empty (i.e., s t = ∅). The goal is to find a policy π that maximizes sum of the rewards until the termination of the MDP. Formally, the goal is to solveargmax π T t=1 r(s t , a t ) ,where s 1 = V and T is the time step at which the MDP terminates (i.e., s T = ∅).1. Claims Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? Answer: [Yes] Justification: The abstract summarizes the problem and contributions of the paper. The contributions are listed at the end of Section 4, after a couple of paragraphs explaining the problem with an illustrative example and positioning the contributions with respect to the state of the art.• All the theorems, formulas, and proofs in the paper should be numbered and crossreferenced. • All assumptions should be clearly stated or referenced in the statement of any theorems.• The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch to provide intuition. • Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material. • Theorems and Lemmas that the proof relies upon should be properly referenced.• The answer NA means that the paper does not include experiments.• If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not. • If the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable. • Depending on the contribution, reproducibility can be accomplished in various ways.For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed. • While NeurIPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. (d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility.In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.See Section 2 the definition of a district.This interventional distribution is often mistakenly referred to as the causal effect of X on Y . However, a causal effect, such as an average treatment effect or a quantile treatment effect, is usually a specific functional of this probability distribution for different values of x.Although it only makes sense to assign non-negative costs to interventions, adopting non-negative costs is without loss of generality. If certain intervention costs are negative, one can shift all the costs equally so that the most negative cost becomes zero. This constant shift would not affect the minimization problem in any way.This is to say, the third rule of do calculus does not apply to PX (Y ).This corresponds to Z blocking all the backdoor paths between Pa(S) and S, in the modified graph G I .The computational bottleneck of the algorithm is an instance of minimum vertex cut problem, which can be solved using any off-the-shelf max-flow algorithm.bnlearn.com/bnrepositoryThis corresponds to Z blocking all the backdoor paths between Pa(S) and S, in the modified graph G I . 


Decision: Reviewer Zgff reduced their score to a 2 from a 4 after rebuttal. Based on the discussion, it is clear they have taken this as a retaliation because the authors posted a comment since the authors answered the questions in great detail. Posting comments before reviewer engagement is not forbidden by the NeurIPS policies. I agree with the authors that this is very unprofessional/policing behavior by the reviewer, rather than evaluating the scientific merit of the work.  

Because of this, I am treating Reviewer Zgff's score as a 4 instead of the updated 2. This brings the average to a 5, making this a borderline paper. 

With this, overall no reviewer has a strong opinion about this paper in its current form. Two reviewers acknowledge the validity of the contributions; although admittedly one with low confidence. The critical reviewer #tZFY, who is also an expert, provided very detailed feedback. There were initial concerns around inconsistent use of some previously well-known concepts, and some around clarity. Most of these seem to have been cleared out by the rebuttal although the reviewer seems to be hesitant to increase their score without seeing a revised version with changes implemented. There seem to be no major concerns by any of the reviewers currently.

Reviews: review: paper_summary: paper_summary: The problem of finding a lower cost intervention to identify causal effects has been shown to be NP-complete.
This paper provides many new reformulations to the problem in terms of a partially weighted maximum satisfiability (in the main paper), integer linear programming (in supplementary), submodular function maximization (in supplementary), and reinforcement learning (in supplementary) that allow designing algorithms that are significantly more efficient.
The new proposed algorithms were shown to have a superior performance through extensive numerical experiments.
strength_weakness: strength_weakness: * The primary weakness of this paper lies in its presentation and clarity. I believe it would greatly benefit from another round of revision and restructuring by the authors to enhance its clarity and organization (see section questions), making it more accessible to readers who are not familiar with the topic.

* The limitations were not clearly addressed (see section limitations).

* In the introduction, the authors stated their intention to introduce several reformulations; however, only one reformulation was presented in the main paper.
questions: questions: * Could you provide a definition of cost? Alternatively, can you offer a concrete example of what the cost might be?

* I believe the paper could be made smoother by consistently using notation. For instance, in almost all definitions, S is used for districts, but in the introduction of notations, S is used as a random set and W as a district. Please consider using S exclusively for districts. This would simplify the reading of the paper.

* lines 133 and 136 and fig 2(d): can you give an intuition of why S2 and X3 hits every hedge for S1 and S2? Maybe consider given the manipulated graph after intervention and discuss how the hedges disappear. Same remark for fig 2(b) the lines  lines 152 and 155.

* Example 1 seems to be not compatible with the text between lines 152 and 155. In the example you consider the effect of X1 and X3 on Y and you say that intervening on X2 suffices for identification; in  lines 152 and 155, you consider the effect of X2 and X3 on Y.

* Perhaps providing a brief overview of the other reformulations introduced in the supplementary material in the main paper could give readers a glimpse into the broader scope of the study. Alternatively, focusing solely on one reformulation in the main paper and leaving the others for future work might streamline the presentation.

* There is a typo in "causal effects win which the effect of ..."
limitations: limitations: Limitations were not clearly addressed in the paper, although some limitations are implicitly pointed out in the complexities and conditions under which the results hold true. It would be beneficial to explicitly discuss these limitations. Additionally, it would be valuable to explore whether there are specific limitations associated with the new reformulations of the problem compared to the initial formulation.
paper_summary: paper_summary: In this paper, the authors consider how to introduce interventional data based on observational data to make causal effect identifiability with the minimal cost. A high-dependent method is proposed by Akbari et al. [2022], which needs a very large computational cost. In this paper, by converting the problem to weighted partially maximum satisfiability problem, the computational cost is largely reduced. The authors prove that addressing the weighted partially maximum satisfiability problem equals to find to min-cost intervention target by Theorem 1 and Theorem 2. In light of the ease to calculation by adjustment criterion, the authors also establish the relevant results for adjustment criterion.
strength_weakness: strength_weakness: I do not find evident weaknesses.
questions: questions: Could the authors provide more clues about the reason that the SAT-based method performs better than the existing method?
limitations: limitations: No.
paper_summary: paper_summary: This paper contributes to connecting the MCID problem—finding the minimum-cost interventions to identify a given causal effect, which has been proven to be NP-Complete—with four well-known problems, such as weighted maximum satisfiability and integer linear programming. These reformulations allow the original MCID problem to be solved by existing advanced solvers associated with the corresponding problems, reducing its computational complexity. The numerical experiments conducted demonstrate the improvements brought by the proposed methods.
strength_weakness: strength_weakness: 1. This paper provides four types of reformulations of the MCID problem. It would be better to add a discussion section about which reformulation users should choose for their specific problem and the reasoning behind the recommendation.
2. Can the authors analyze the time complexity of the proposed heuristic algorithm?  Besides, a thorough analysis of the time complexity in experiment part would provide a deeper understanding of the algorithm's performance, particularly in terms of its behavior in worst-case and average-case conditions.
3. In lines 230-231, The inclusion of $\neg z_{k,l}$ in the SAT construction seems intuitive, but can the authors provide a more detailed explanation of its rationale? Specifically, it would be beneficial to understand how $\neg z_{k,l}$ functions within the overall logic of the problem.
4. The experimental results are solely based on synthetic data. It would be beneficial to evaluate the proposed method using real-world datasets, if possible, which would provide a more comprehensive validation of the method's effectiveness in practical applications.
5. The writing of this paper mostly focus on the theoretical results, and may be difficult to be understood by the readers, especially for the example 1, a more straightforward example may be helpful for the paper presentation.
questions: questions: See weaknesses.
limitations: limitations: 1. More details about the baselines and datasets should be provided in the manuscript. This includes a thorough description of the baseline algorithms used for comparison and the characteristics of the datasets employed in the experiments.
2. The methodology part of this paper, especially Section 3.1, might hinder readers who are not familiar with SAT from fully understanding this kind of reformulation. It would be helpful to include a more detailed and intuitive explanation of the SAT concepts and their application in this context in the appendix.
paper_summary: paper_summary: This paper provide a computationally efficient algorithm for finding the sets of variables $\mathbf{Z}_1,\cdots,\mathbf{Z}_m$ that achieve the minimum intervention cost, allowing for $P(\mathbf{y} \mid \operatorname{do}(\mathbf{x}))$ to be identifiable from $\{P(\mathbf{V} \mid \operatorname{do}(\mathbf{Z}_i)): i=1,\cdots,m\}$.
strength_weakness: strength_weakness: __1. Misleading and wrong statements__

This paper contains some statements that could mislead readers. First, there is a sentence that doesn’t acknowledge the previous works properly.

> A middle ground between the two extremes of observational and experimental approaches was introduced by Akbari et al. [2022]
> 

The middle ground, which uses the fusion of observational and experimental data to identify the causal effect, is introduced by [Bareinboim and Pearl (2012)](https://arxiv.org/pdf/1210.4842), not Akbari et al., 2022. This sentence could mislead readers by ignoring existing works on the middle ground.

Second, this paper incorrectly defines some existing notions in theories of causal effect identification or gives new names to already existing concepts. 

- For example, a “district” is a *maximal* set of vertices connected by bidirected edges [[Richardson et al., 2023](https://arxiv.org/abs/1701.06686) or [Shpitser et al., 2014](https://web.archive.org/web/20181102234555id_/https://www.jstage.jst.go.jp/article/bhmk/41/1/41_3/_pdf)]. Therefore, given a (sub-)graph $\mathcal{G}(T)$ and a set of vertices $S$, there is only one district containing $S$ in $\mathcal{G}(T)$. However, this paper wrongly defines “district” without invoking *maximality.*
- Another example is “hedge hull.” Acknowledging the original definition of the district, the hedge hull is just a hedge defined by [Shpitser et al., 2008](https://jmlr.org/papers/volume9/shpitser08a/shpitser08a.pdf) and [Shpitser al el., 2012](https://arxiv.org/pdf/1202.3763), which is an ancestor of $S$ and a district at the same time. I don’t see why the authors redefine the original “hedge” as “hedge hull.” It only raises confusion in comprehending the paper.

Third, some of statements are not sound. Specifically, the following sentence in line 133-134 seems to be incorrect.

> Note that there is no hedge formed for $S_{\ell}$ in $\mathcal{G}[V \setminus \mathcal{I}_k]$ if and only if \mathcal{I}_k hits every hedge of $S_{\ell}$ (i.e.,for any hedge $W \in H_{\mathcal{G}}(S_{\ell})$,$\mathcal{I}_k \cap W \ neq \emptyset$).
>

For example, 

* Consider the case where $S_{\ell}$ is identifiable in $\mathcal{G}$. Then, there must be no hedge formed for $S_{\ell}$ in $\mathcal{G}$. However, the condition where $\mathcal{I}_k$ and $W$ is non-overlapped is violated. 

* Another case is when $S_{\ell}$ itself is a hedge. Then, with $\mathcal{I}_k = \emptyset$, the sentence doesn't hold. 

Also, The following sentence is false: 

> The query of interest is identifiable if and only if HG (S) = S, that is, the hedge hull of S contains no other vertices.
> 

Consider the graph $\mathcal{G} = ( W → R → X → Z → Y, W ↔ X, W↔Z, X↔Y )$. Here, $S = \operatorname{Anc}_{V \setminus X}(Y) = (Z,Y)$, but the hedge hull found from Algorithm 2 is $(X,Z,Y)$. However, the causal effect P(Y | do(X)) is identifiable from $\mathcal{G}$. 

---

__2. Weak presentation__ 

First, the paper weakly exemplifies the SAT Construction Procedure. Without providing detailed examples of how 3-SAT can be constructed using the graphs in Figure 1, it's hard to understand how the problem is reformulated using 3-SAT.

Second, many important results are omitted (e.g., a detailed example for 3-SAT construction and IP formulation) and presented in the supplementary document (e.g., Algorithms 2 and 3). Specifically, it's impossible to comprehend this paper without reading Section B. Given that reading the supplementary document is not mandatory for reviewers and readers, I encourage the authors to reorganize the paper to make it more comprehensible.


---

__3. Lack of analysis \& misleading contribution__ 

To my knowledge, the exact solution for integer programming is NP-hard, and only heuristic methods are available for efficiently solving the problem. A natural question is the gap between the exact solution and these approximated solutions.

Also, the authors need to be more cautious in presenting their contribution. The fast experiment design was achieved by heuristically solving the problem, and the exact solution remains NP-hard. However, the paper is presented as if the NP-hard problem has been solved just by reformulating the problem.

---

__4.Minor comments__

1. The following sentence is not parsable. Is “win” a typo? 

> Moreover, Akbari et al. [2022]’s algorithm was tailored to a specific class of causal effects win which the effect of interest is a functional of an interventional distribution where the intervention is made on every variable except one district of the causal graph
>
questions: questions: 1. In line 109, is the condition S \subsetneq W is necessary?
limitations: limitations: 1. This paper still solves the heuristic solution, instead of the exact solution. The exact solution of the problem still remains NP-hard.

Comments: title: Summary of Fig. 3(a) as a table
Response
Limitations and minor comments
Modified example
comment: ### The average time taken in seconds to solve one instance of the MCID problem for our SAT approach and the minimal hedge solver (MHS) of Akbari et al., 2022. The speedup factor refers to MHS time divided by SAT time.
|   $n$ | SAT time               | MHS time              | Speedup factor                 |
|:----|:-----------------------|:-----------------------|:----------------------|
|  20 | $2.90 \times 10^{-3}$ | $1.08 \times 10^{-1}$ | $3.72 \times 10^{1}$ |
|  31 | $1.33 \times 10^{-2}$ | $1.79 \times 10^{1}$  | $1.34 \times 10^{3}$ |
|  42 | $3.93 \times 10^{-2}$ | $1.05 \times 10^{3}$  | $2.68 \times 10^{4}$ |
|  53 | $8.59 \times 10^{-2}$ | $6.65 \times 10^{4}$  | $7.75 \times 10^{5}$ |
|  58 | $1.15 \times 10^{-1}$ | $3.93 \times 10^{5}$  | $3.42 \times 10^{6}$ |
|  61 | $1.36 \times 10^{-1}$ |         - |     - |
|  77 | $2.95 \times 10^{-1}$ |         - |     - |
|  86 | $4.26 \times 10^{-1}$ |         - |     - |
|  94 | $5.70 \times 10^{-1}$ |         - |     - |
| 100 | $7.01 \times 10^{-1}$ |         - |     - |
Thank you for taking the time to read our rebuttal and engage in the discussion. Please find our responses to your comments and questions below.

## W2
Our claims, including the results we reference from other works, such as Proposition 1, are valid under our own definitions. However, it would not be difficult to use the original definitions. For example, while we did not impose maximality when defining a district, we refer to $\\{S_i\\}_{i=1}^{r}$ as the ‘maximal districts’ of $\mathcal{G}[S]$ in Proposition 1, Lemma 1, and Theorem 2, aligning with the original definition. The decision not to impose maximality in our definitions was made for simplicity, as there are sections of the paper where we discuss connected components that are not necessarily ‘maximal’, such as the set $S$ itself. Based on your suggestion, we will use standard terms for non-maximal components, but please note that our claims remain valid with this renaming.

## 1,000 to 100,000,000 speed up
Based on the results that generated Fig. 3(a), posted below for your convenience, starting with $n$ as small as 30, we observe a speedup ratio of 1,000, which increases to 1,000,000 by $n=58$. Although we were unable to run MHS for $n$ greater than 60, we can extrapolate that for $n$ as low as 70, the speedup factor would reach at least 100,000,000. 

## Worst-case complexity
We discuss the reason behind this speed up to some extent in lines 162-173 and Remark 3 (lines 244-248). Specifically, the method of Akbari et al., 2022 has a two-step procedure:
1) Discover a new (minimal) hedge.
2) Solve a weighted minimum hitting set problem (WMHS) on the already discovered hedges.
3) Repeat steps 1 and 2 until the solution to the WMHS instance results in identification.

We present an example in Figure 2\(c), where the number of minimal hedges is exponential in $n$. Since the WMHS problem itself is NP-hard, their approach requires running an exponential number of instances of an NP-hard problem. In comparison, our method reduces the MCID problem to a single instance of WPMAX-SAT, which has a worst-case time complexity of one WMHS problem, rather than exponentially many of them. This is why we can solve the same problem several orders of magnitude faster than the method of Akbari et al., 2022.

It is noteworthy that the size of an instance of the WMHS problem they solve (i.e., the number of sets to hit) can be exponential in $n$, whereas the size of the WPMAX-SAT problem we solve (i.e. the number of variables and clauses) remains polynomial in $n$. In summary, we solve one instead of exponentially many instances of an NP-hard problem, and our problem has a significantly smaller size.

We acknowledge this point isn’t clearly conveyed and will clarify it with a more detailed discussion.

## Quadratic complexity for multi-district
We make this claim in Remark 3 of the paper. Specifically, the quadratic complexity of our method in terms of the number of districts arises from the fact that the number of variables and clauses in our SAT construction for a multi-district set $S$ with $r$ districts scales as $r^2$. The formal justification for this claim lies in Theorem 2, where we prove that MCID is equivalent to a SAT formulation with size quadratic in $r$, the number of districts. 

Regarding the time complexity of the approach by Akbari et al., 2022, this is due to their method requiring the enumeration of all possible partitions of the districts, the count of which (the so-called Bell number) grows super-exponentially with the number of districts. They solve an instance of single-district MCID problem for each of these possible partitions. We mentioned this in line 171.

We recognize that this point may not be clearly communicated in the current manuscript, and as it is a significant contribution of our paper, we will revise the paper to ensure this aspect is highlighted more effectively.

## Unformalized justification and fast claim
The justification for our claims is present in the paper, and we want to clarify that our response is based on information already included in the manuscript (as referenced in our responses to the formal result regarding quadratic worst-case time complexity in terms of the number of districts, discussion around how we achieve a significant speedup compared to Akbari et al., 2022, and comparison of the worst-case complexities of our method and Akbari et al., 2022). However, we acknowledge that this information may be too dispersed to effectively convey the strength of our approach. To address this, we will consolidate these justifications into a dedicated section in the revised manuscript, where we will clearly detail our contributions and demonstrate why our approach outperforms the method of Akbari et al., 2022, both theoretically and in practice.

We sincerely appreciate your thorough review of our paper and your engagement with us during the discussion period. Please let us know if you have any more questions or concerns.
Thank you for your detailed response. Your response addresses my concerns on W3 and W4. 

---

> W1 

I understand that the problem of finding the minimum cost intervention set has been proposed by Akbari et al., 2022. Thank you that you appreciated my comment on W1. 

---

> W2 

I think this issue will not be addressed by simply changing the names and adding the citations, since results such as Proposition 1 are depending on this definition. Please check dependencies of this definition throughout the paper. 

--- 

On W6, can you provide the pointer justifying your responses? Specifically, 

> "Our reformulations not only solve the problem exactly, but also provide a significant speedup of 1,000 to 100,000,000 times for the single-district case." 

It's interesting that there is a significant speedup, given that the worst-case time complexity still remains the same. Can you discuss why this happens? Is the formal discussion included in the paper? Additionally, is there a comparison of the worst/average time complexity between the method proposed by Akbari et al., 2022, and this method? I see that there is an empirical analysis showing this speedup, but if this is a main claim of the paper, there should be a formalized discussion.

> Moreover, for the multiple-district case, our approach is only quadratic in the number of districts (theoretically guaranteed), unlike the previous method which required iterating over an exponential number of partition sets. 

It's an interesting result. Is there a formal result justifying this claim in the paper? 

> We believe therefore the term “fast” is justified. Although the exact solution remains exponential in the worst case, our reformulations make solving these problems practically feasible and significantly more efficient, especially for large graphs.

I think the paper contains many strong empirical results. However, to claim that the proposed method is "fast," there should be a formal discussion on how this speedup is achieved, as well as a comparison of the worst/average time complexity with previous methods.

---

Overall, I agree that the paper provides an interesting approach to an important problem, as proposed by Akbari et al., 2022, within the framework of z/g-ID. Your response also provides some degree of justification for the power of the proposed method, _assuming_ your claim in the response is accurate. However, this justification is not formalized (nor included) in the paper, so as a reviewer, it's hard to take the response at face value without sufficient formalization. I believe that this paper has the potential to be strong, but it needs more work to reach perfection. Therefore, I will keep the score as is.
If the official comment is rational before the reviewers' reply, What is the significance of rebuttal limiting words? Why we need to have two buttons?
We thank the reviewer for reading and responding to our rebuttal. We address your remaining concerns below.

## Regarding limited evaluation regime
To the best of our knowledge, no publicly available dataset includes both costs and ADMGs suitable for our setup. If the reviewer is aware of such a dataset, we would greatly appreciate the suggestion.

That being said, we want to emphasize that the absence of such a dataset should not diminish the validity of our claims or the value of our contribution. First, we have **proven theoretically** that our approach operates quadratically in the number of districts of $S$, a significant improvement over the exponential complexity of the previous method (Remark 3). This theoretical advantage holds regardless of the specific dataset used.

Second, our extensive simulations, detailed in Section 5 and Appendix A, involve testing over 1,000,000 graphs, covering all combinations of directed and bidirected sparsity and density, and demonstrate that our SAT reformulation outperforms the previous approach by factors ranging from 1,000 to 100,000,000 in speed. This significant speed advantage makes it highly unlikely that our approach would perform worse than the previous method in any practical scenario. Additionally, our new rebuttal simulations, which evaluated our approach on **DAGs from 17 distinct real-world applications**, demonstrate the same performance superiority. It is important to note that although the costs are synthetically generated, our experiments in Appendix A.4 confirm that varying costs does *not* impact the relative performance of our method compared to the previous approach. Therefore, our rebuttal simulations provide a reliable indication of how our approach would perform on real-world problems with non-synthetic costs.

## Regarding general examples
We address the problem of determining optimal proxy experiments for causal effect identification, a key issue in many decision-making contexts where direct policy implementation (i.e., intervention) is costly, risky, or time-consuming. Here are two real-world examples.

### Proxy interventions for evaluating diesel vehicle bans in environmental policy​
Consider in environmental policy, where a city is considering a ban on diesel vehicles to reduce air pollution. Instead of implementing the ban outright, the city might first introduce low-emission zones or offer incentives for electric vehicle purchases in certain areas. These low-emission zones can be viewed as proxy experiments (interventions), and they allow the city to estimate the policy's effectiveness before committing to the full-scale ban [1,2].

### Proxy experiments for evaluating nationwide sugary drink tax policies
Consider a scenario where a government is considering a nationwide tax on sugary drinks to reduce obesity rates. Directly implementing the tax across the country could be costly and politically challenging. Instead, the government might conduct proxy experiments by imposing the tax in selected regions or by encouraging voluntary reduction in sugary drink consumption through public campaigns in others. These proxy experiments can help estimate the potential impact of a nationwide policy without the need for immediate, large-scale implementation [3,4].

## Regarding comment on rebuttal policy
We appreciate your diligence in ensuring that the rebuttal process is followed correctly. However, we believe there might be a misunderstanding. After reviewing both the guidelines on the NeurIPS website and the emails sent by program chairs regarding the rebuttal/discussion period, we found no policy that prohibits authors from adding an official comment before the reviewer’s reply.

**Please let us know if there are any remaining questions. In light of this response and our rebuttal, which addressed all of your other comments and questions, we kindly ask that you reconsider your score.**

## References
[1]: Dey, S., Caulfield, B., & Ghosh, B. (2018). Potential health and economic benefits of banning diesel traffic in Dublin, Ireland.  _Journal of Transport & Health_.

[2]: Pérez-Martínez, P., Andrade, M., & Miranda, R. (2017). Heavy truck restrictions and air quality implications in São Paulo, Brazil. _Journal of environmental management_, 202 Pt 1, 55-68.

[3]: Redondo, M., Hernández-Aguado, I., & Lumbreras, B. (2018). The impact of the tax on sweetened beverages: a systematic review. _The American journal of clinical nutrition_, 108 3, 548-563.

[4]: Álvarez-Sánchez, C., Contento, I., Jiménez-Aguilar, A., Koch, P., Gray, H., Guerra, L., Rivera-Dommarco, J., Uribe-Carvajal, R., & Shamah-Levy, T. (2018). Does the Mexican sugar-sweetened beverage tax have a signaling effect? ENSANUT 2016. _PLoS ONE_, 13.
Thanks for the authors' responses. I must point out that, in the rebuttal policy, it is not allowed to add an official comment before the reviewer's reply. 

Additionally, although the authors have pointed out the interesting aspects of this work, the limited evaluation regime is a disadvantage. The real-world application scenarios are semi-synthetic, which makes the results unconvincing. 

Also, I hope the authors can polish this work with more general examples so that readers can understand its challenge.

Overall, I keep my score. Thanks for the work of the authors during the rebuttal.
I thank the authors for their responses, in which they have addressed most of my concerns and have highlighted the interesting aspects of this paper. However, I also acknowledge the valid points raised by the other reviewers. Therefore, I will keep my score unchanged.
We address limitation 1 and the minor comments below.


## Limitations
### L1:
Note that our reformulations allow for solving the MCID problem exactly. Given that the MCID problem is NP-hard, the best achievable solution for an exact algorithm is to provide a faster reformulation of another NP-hard problem, which is precisely what we have accomplished. In addition to vastly better performance in practice, our reformulations offer significant theoretical speedups for multiple-district graphs. Specifically, our algorithm operates quadratically in the number of districts, whereas the original approach is exponential. Thus, while the MCID problem is NP-hard, we have managed to solve it exactly by multiple orders of magnitude faster than the previous approach, as well as providing theoretical guarantees for a polynomial-time complexity in terms of the number of districts.

## Minor comment:
### W7:
Yes, the sentence should read "... a specific class of causal effects in which the effect..." We apologize for the oversight.
Please find our modified example (regarding W5) below.

> Consider a patient taking three types of medications: one for lowering blood pressure (antihypertensives), another for controlling diabetes (anti-diabetics), and a third for managing kidney function (renal function modulators). These medications interact in various ways to manage heart health. For example, antihypertensives directly lower blood pressure, which is closely linked to cardiovascular health. Anti-diabetics help reduce cardiovascular risk by controlling blood sugar levels. Renal function modulators can influence both blood pressure and kidney health. Lifestyle factors and other health conditions, such as metabolic syndrome, can affect how these medications work together. For instance, a healthy diet and regular exercise can enhance the effectiveness of these treatments. To understand the combined effect of these medications on heart disease risk, we could conduct a proxy experiment by adjusting the anti-diabetics, as this is often easier and safer to modify compared to the others. This approach allows us to infer how these medications collectively impact heart health.