On the Complexity of Counterfactual Reasoning

A common form of counterfactual reasoning is based on the notion of twin network which is a causal graph that represents two worlds, one real and another imaginary. Information about the real world is used to update the joint distribution over the network's causal mechanisms which is then used for hypothetical reasoning in the imaginary world. This is in contrast to associational and interventional reasoning which involve a causal graph over a single world that we shall call a base network. In this paper, we study the complexity of counterfactual reasoning in twin networks in relation to the complexity of associational and interventional reasoning in base networks. We show that counterfactual reasoning is no harder than associational/interventional reasoning in the context of two computational frameworks. One of these is based on the notion of treewidth and includes the classical variable elimination and jointree algorithms. The second, more recent framework is based on the notion of causal treewidth which is directed towards causal graphs used in counterfactual reasoning (e.g., structural causal models). More specifically, we show that the (causal) treewidth of a twin network is at most twice the (causal) treewidth of its base network plus one. This means that if associational/interventional reasoning is tractable then counterfactual reasoning is also tractable. We further extend our results to a form of counterfactual reasoning that is more general than what is commonly discussed in the literature. We finally present empirical results that measure the gap between the complexities of counterfactual reasoning and associational/interventional reasoning on random networks.