When does the ID algorithm fail?
Ilya Shpitser
The ID algorithm solves the problem of identification of interventional
distributions of the form p(Y | do(a)) in graphical causal models, and has been
formulated in a number of ways [12, 9, 6]. The ID algorithm is sound (outputs
the correct functional of the observed data distribution whenever p(Y | do(a))
is identified in the causal model represented by the input graph), and complete
(explicitly flags as a failure any input p(Y | do(a)) whenever this
distribution is not identified in the causal model represented by the input
graph).
  The reference [9] provides a result, the so called "hedge criterion"
(Corollary 3), which aims to give a graphical characterization of situations
when the ID algorithm fails to identify its input in terms of a structure in
the input graph called the hedge. While the ID algorithm is, indeed, a sound
and complete algorithm, and the hedge structure does arise whenever the input
distribution is not identified, Corollary 3 presented in [9] is incorrect as
stated. In this note, I outline the modern presentation of the ID algorithm,
discuss a simple counterexample to Corollary 3, and provide a number of
graphical characterizations of the ID algorithm failing to identify its input
distribution.