Causes and Explanations in the Structural−Model Approach: Tractable Cases

Abstract

This paper continues the research on the computational aspects of Halpern and Pearl's causes and explanations in the structural model approach. To this end, we first explore how an instance of deciding weak cause can be reduced to an equivalent instance in which irrelevant variables in the (potential) weak cause and the causal model are removed, which extends previous work by Hopkins. We then present a new characterization of weak cause for a certain class of causal models in which the causal graph over the endogenous variables has the form of a directed chain of causal subgraphs, called decomposable causal graph. Furthermore, we also identify two important subclasses in which the causal graph over the endogenous variables forms a directed tree and more generally a directed chain of layers, called causal tree and layered causal graph, respectively. By combining the removal of irrelevant variables with this new characterization of weak cause, we then obtain techniques for deciding and computing causes and explanations in the structural-model approach, which can be done in polynomial time under suitable restrictions. This way, we obtain several tractability results for causes and explanations in the structural-model approach. To our knowledge, these are the first explicit ones. They are especially useful for dealing with structure-based causes and explanations in first-order reasoning about actions, which produces large causal models that are naturally layered through the time line, and thus have the structure of layered causal graphs. Furthermore, an important feature of the tractable cases for causal trees and layered causal graphs is that they can be recognized efficiently, namely in linear time. Finally, by extending the new characterization of weak cause, we obtain similar techniques for computing the degrees of responsibility and blame, and hence also novel tractability results for structure-based responsibility and blame.