% JAIR version.

\long\def\comment#1{}  
  
\documentstyle[jair,twoside,11pt,theapa,psfig]{article}
\newcommand{\jmp}[3]{#1}

%\documentstyle[11pt,msrtr,theapa,psfig]{article}
%\newcommand{\jmp}[3]{#2}

%\documentstyle[11pt,theapa,psfig]{article}
%\newcommand{\jmp}[3]{#3}

\jmp{
\jairheading{3}{1995}{405-430}{6/95}{12/95}
\ShortHeadings{Decision-Theoretic Foundations for Causal Reasoning}
{Heckerman \& Shachter}
\firstpageno{405}
}{
\textwidth 6.0in
\textheight 8.5in
\topmargin -0.25in
\oddsidemargin 0.25in
\evensidemargin 0.25in
\renewcommand{\baselinestretch}{1.25}
}{
\textwidth 6.0in
\textheight 8.5in
\topmargin -0.25in
\oddsidemargin 0.25in
\evensidemargin 0.25in
\renewcommand{\baselinestretch}{1.25}
}

\newtheorem{definition}{Definition} 
\newtheorem{fact}{Fact} 
\newtheorem{assumption}{Assumption} 
\newtheorem{theorem}{Theorem} 
\newtheorem{corollary}[theorem]{Corollary} 
\newtheorem{lemma}[theorem]{Lemma} 
\newtheorem{remark}[theorem]{Remark} 
\newtheorem{proposition}{Proposition} 
\newtheorem{conjecture}{Conjecture} 
\newtheorem{algorithm}{Algorithm} 
 
\newcommand{\Thm}[1]{Theorem~\ref{#1}} 
\newcommand{\Thms}[1]{Theorems~\ref{#1}} 
\newcommand{\Cor}[1]{Corollary~\ref{#1}} 
\newcommand{\Prop}[1]{Proposition~\ref{#1}} 
\newcommand{\Lem}[1]{Lemma~\ref{#1}} 
\newcommand{\Def}[1]{Definition~\ref{#1}} 
\newcommand{\Ass}[1]{Assumption~\ref{#1}} 
\newcommand{\Fig}[1]{Figure~\ref{#1}} 
\newcommand{\Tab}[1]{Table~\ref{#1}} 
\newcommand{\Eq}[1]{Equation~\ref{#1}} 
\newcommand{\Eqs}[1]{Equations~\ref{#1}} 
\newcommand{\qed}{\mbox{$\large\Box$}} 
\newcommand{\Sec}[1]{Section~\ref{#1}} 
\newcommand{\Algo}[1]{Algorithm~\ref{#1}} 
 
\newcommand{\Prb}[1]{p(#1)} 
\newcommand{\Pa}[1]{Pa^G(#1)} 
\newcommand{\Ind}[3]{\mbox{$(#1 \perp #3 | #2)$}} 
\newcommand{\notI}[3]{\mbox{$(#1 \perp \!\!\!\!\! /  
  \ #3 | #2)$}} 
 
\newcommand{\var}[1]{{\em #1}} 
 
\newcommand{\urs}{\not\hookleftarrow}
\newcommand{\rs}{\hookleftarrow}

\newcommand{\bS}{{\bf S}}
\newcommand{\bD}{{\bf D}}
\newcommand{\bDone}{{\bf D_1}}
\newcommand{\bDtwo}{{\bf D_2}}
\newcommand{\bE}{{\bf E}}
\newcommand{\bY}{{\bf Y}}
\newcommand{\bZ}{{\bf Z}}
\newcommand{\bC}{{\bf C}}
\newcommand{\bX}{{\bf X}}
 
 
\title{Decision-Theoretic Foundations for Causal Reasoning}

\jmp{
\author{\name David Heckerman \email heckerma@microsoft.com \\
       \addr Microsoft Research, One Microsoft Way\\
       Redmond, WA  98052-6399 USA
       \AND
       \name Ross Shachter \email shachter@camis.stanford.edu \\
       \addr Stanford University\\
       Stanford, CA 94305-4025 USA}
}{
\author{David Heckerman\\
heckerma@microsoft.com\\
\\
Ross Shachter\\
Department of Engineering-Economic Systems\\
Stanford, CA 94305-4025\\
shachter@camis.stanford.edu}

\date{March 1994 (Revised October 1995)}
\msrtrno{MSR-TR-94-11}
}{
\author{David Heckerman\\
Microsoft Research, Bldg 9S\\ 
Redmond WA 98052-6399\\ 
heckerma@microsoft.com\\
\\
Ross Shachter\\
Department of Engineering-Economic Systems\\
Stanford, CA 94305-4025\\
shachter@camis.stanford.edu}
}

\begin{document} 
 
\jmp{
\maketitle
}{
\msrtrmaketitle
}{
\maketitle
}

 
\begin{abstract} 

We present a definition of cause and effect in terms of
decision-theoretic primitives and thereby provide a principled
foundation for causal reasoning.  Our definition departs from the
traditional view of causation in that causal assertions may vary with
the set of decisions available.  We argue that this approach provides
added clarity to the notion of cause.  Also in this paper, we examine
the encoding of causal relationships in directed acyclic graphs.  We
describe a special class of influence diagrams, those in canonical
form, and show its relationship to Pearl's representation of cause and
effect.  Finally, we show how canonical form facilitates
counterfactual reasoning.

\end{abstract} 

 
\section{Introduction} \label{sec:intro} 

Knowledge of cause and effect is crucial for modeling the affects of
actions.  For example, if we observe a statistical correlation between
smoking and lung cancer, we can not conclude from this observation
alone that our chances of getting lung cancer will change if we
stop smoking.  If, however, we also believe that smoking is a cause
for lung cancer, then we can conclude that our choice whether to
continue or quit smoking will affect whether we get lung cancer.

Work by artificial intelligence researchers, statisticians, and
philosophers have emphasized the importance of identifying causal
relationships for purposes of modeling the effects of actions.  For
example, Simon (1977),\nocite{Simon77} Robins (1986),\nocite{Robins86}
Spirtes et al.\ (1993),\nocite{Spirtes93} and Pearl (1993,
1995)\nocite{Pearl93,Pearl95bm} have developed graphical models of
cause and effect, and have demonstrated how these models are important
for reasoning about the effects of actions.  In addition, Robins
(1986)\nocite{Robins86}, Rubin (1978)\nocite{Rubin78}, Pearl and Verma
(1991)\nocite{Pearl91}, and Spirtes et al.\ (1993)\nocite{Spirtes93}
have developed approaches that embrace causality for learning the
effects of actions from data.

One useful framework for causal reasoning is that of Pearl (1993,
1995)---herein Pearl.  Using his framework, we construct a {\em causal
graph} $G$.  The nodes in $G$ correspond to a set of variables $U$
that we wish to model.  Each variable has a set of mutually exclusive
and collectively exhaustive values or {\em instances.}  The arcs in
$G$ represent (informal) assertions of cause---in particular, the
parents of $x \in U$ are direct causes of $x$.  Pearl gives these
informal assertions of cause an operational meaning by introducing a
special class of actions on the variables $U$ and then describing the
affects of these actions using the structure of the causal graph.
Specifically, he posits that, for every variable $x \in U$, there
exists another variable $\hat{x}$, which we call an {\em atomic
intervention on} $x$.  The variable $\hat{x}$ has an instance {\bf
set}$({\bf x})$ for every instance ${\bf x}$ of $x$, and an instance
{\bf idle}.  The instance {\bf set}$({\bf x})$ corresponds to an
action that forces $x$ to take on instance ${\bf x}$ and indirectly
affects other variables through the change in $x$.  The instance {\bf
idle} corresponds to the action of doing nothing.\footnote{We adopt a
variant of Pearl's notation for the instances of an atomic
intervention.  In addition, whereas Pearl calls the action {\bf
set}$({\bf x})$ an atomic intervention, we find it convenient to use
this phrase to refer to the entire variable $\hat{x}$.}  Pearl then
asserts that the effects of atomic interventions on the variables in
$U$ are determined by the {\em structural equations}
\[
x = f_x(Pa^G(x), \hat{x}, \epsilon_x)
\]
for all $x \in U$, where (1) $Pa^G(x)$ are the parents of $x$ in
$G$---that is, the direct causes of $x$, (2) the variables
$\epsilon_x$ are {\em exogenous} and mutually independent {\em random
disturbances}, and (3) the function $f_x$ has the property that
$x={\bf x}$ when $\hat{x}=${\bf set}$({\bf x})$ regardless of the values of
$Pa^G(x)$ and $\epsilon_x$.  Following Pearl, we call this framework
for defining cause a {\em structural-equation model.}  

Another useful framework for causal reasoning, closely related to
Pearl's, is that of Spirtes et al.\ (1993)---herein SGS.

Despite these and other important advances in reasoning about cause
and effect, foundations for such approaches are lacking.  In any
framework for causal reasoning, it is important to consider what
concepts are {\em primitive}---that is, assumed to be self evident and
used to define other concepts.  As much as is possible, these
primitives should have simple and universal meanings so that claims of
causation can be empirically tested and causal inferences can be
trusted.  Unfortunately, the primitives used by Pearl, SGS, and other
researchers are not ideal in this respect.

For example, SGS take cause itself to be a primitive.  Given the
controversies in statistics and other disciplines concerning the
meaning of cause, we believe that a better primitive can be found.
Pearl takes random disturbance, exogenous variable, and atomic
intervention as primitives.  One problem with this approach is that we
need an understanding of cause and effect to identify an intervention
as atomic.  To illustrate the problem, suppose we wish to model the
causal relationship between the binary variables $w$ and $h$
representing whether or not a person considers himself to be wealthy
and happy, respectively.  Further, suppose we can give this person a
large sum of stolen money along with the knowledge that this money is
stolen.  Now we ask the question: Is this action an instance of an
atomic intervention for $w$?  If this person does not care about how
he becomes wealthy, then the answer is ``yes.''  If this person is
more typical, however, then the answer is ``no,'' because this action
would affect both $w$ and $h$ directly.  Thus, we must first determine
whether or not the action is a direct cause of $h$ to determine
whether or not this action is an instance of an atomic intervention.

In this paper, we provide a principled foundation for causal
reasoning.  In particular, we explicate a set of primitives from
decision theory, and use these primitives to define the concepts of
cause and atomic intervention as well as those of random disturbance
and exogenous variable.  These primitives are simple to understand and
used uniformly across many disciplines.

The basic idea behind our definition of cause is as follows.  Following
the paradigm of decision theory, we focus on a person---the decision
maker---who has one or more decisions to make.  For each variable that
we wish to model in considering these decisions, we distinguish the
variable as being either a decision variable or chance variable.  A
{\em decision variable} is a variable whose instances correspond to
possible actions among which the person can choose.  A {\em chance
variable} is any other variable.  This framework is similar to
Pearl's, where chance variables correspond to the variables $U$ and
decision variables correspond to interventions.  The differences are
that (1) we do not require there to be a decision variable for every
chance variable, and (2) decision variables need not be atomic
interventions.

Now, for simplicity, suppose that we have a model consisting of only
one decision variable $d$ and a set of chance variables $U$.  Imagine
that we choose one of the instances of $d$ and subsequently observe
$x \in U$.  If we believe that $x$ can be different for different
choices, then, by our definition, we say that $d$ is a cause for
$x$.  For example, suppose decision variable $s$ represents the
decision of whether or not to continue smoking and chance variable $l$
represents whether or not we get lung cancer.  If we believe that we
will get lung cancer if we continue smoking and that we may not get
lung cancer if we quit, then we can say that $s$ is a cause of $l$.

Our definition is related to the notion of a {\em counterfactual}: a
hypothetical statement or question that can not be verified or
answered through observation (Lewis, 1973; Holland,
1986).\nocite{Lewis73cf,Holland86} In our smoking example, we ask the
question ``Will deciding differently possibly change our health
outcome?''  This question can not be answered by any observation,
because we must either quit or continue to smoke; we can not do both.
Using counterfactuals, Rubin (1978)\nocite{Rubin78} defines a notion
of {\em causal effect} that is closely related to our definition
of cause.

The problem with most definitions of cause based on intervention is
that they do not allow chance variables to be the causes of other
chance variables.  Consider the variables $g$ and $c$ representing a
person's gender at birth and whether or not that person gets breast
cancer, respectively.  Although $g$ is a chance variable (we cannot
choose our gender), we often hear people say in natural discourse that
$g$ causes $c$.  In general, we would like to accommodate such
assertions.

The definition of cause that we present does indeed permit chance
variables to be causes.  There is, however, one catch.  Namely, when
we assert that a set of chance variables $X$ is a cause of chance
variable $y$, we must also specify the decision or decisions that
bring about the possible changes in $X$ and $y$.  In our breast-cancer
problem, we can assert that $g$ causes $c$, but we must explicate a
decision that possibly leads to a change in gender and breast cancer.
For example, we can say that $g$ causes $c$ with respect to decision
variable $d$, where $d$ represents the decision of whether or not to
perform genetic surgery at conception.

By including a decision context in assertions of cause, our definition
departs from the traditional view of causation.  Nonetheless, this
departure makes causal assertions more precise.  For example, consider
another decision that will likely lead to a change in gender: a
decision $o$ of whether or not to have a sex-change operation at
birth.  In this case, it may be reasonable to assert that $g$ is not a
cause of $c$ with respect to $o$.  Thus, causal relationships among
chance variables may depend on the decisions available for
intervention; and our definition accommodates this dependence.

Our paper is organized into four parts.  In part 1
(Sections~\ref{sec:unresp} and \ref{sec:cause}), we develop our
definition of cause, using the decision-theoretic primitives of Savage
(1954).  In Section~\ref{sec:unresp}, we introduce a simpler relation
than cause, which we call limited unresponsiveness.  In
Section~\ref{sec:cause}, we define cause in terms of limited
unresponsiveness.

In part 2 (Sections~\ref{sec:id} through \ref{sec:hcf}), we address
the graphical representation of cause.  In \Sec{sec:id}, we review a
directed-acyclic-graph (DAG) representation, known as an {\em
influence diagram}, which has been used for two decades by decision
analysts to model the effects of decisions (Howard and Matheson,
1981).\nocite{Howard81} We demonstrate the inadequacies of the
influence diagram as a representation of cause.  In the following
three sections, we develop a special condition on the influence
diagram, known as {\em canonical form}, that improves the
representation of cause.

In part 3 (\Sec{sec:pearl}), we use our definitions of cause, atomic
intervention, and mapping variable, along with canonical form to build
a correspondence with (and thus a foundation for) Pearl's causal
framework.  

In part 4 (\Sec{sec:persis}), we demonstrate an important use of
canonical form.  Namely, we show how to use influence diagrams in
canonical form to do general counterfactual reasoning.

We present our framework in the traditional decision-analytic paradigm
of a ``one shot'' decision.  In particular, we do not consider
experimental studies, where variables are measured repeatedly.
Nonetheless, one can easily extend our framework to such situations by
introducing the assumption of exchangeability (de Finetti,
1937).\nocite{deFinetti37} Bayesian methods for learning models of
cause that are based on this approach are discussed in Angrist et
al.\ (1995)\nocite{AIR95} and Heckerman (1995).\nocite{H95uai}

 
\section{Unresponsiveness} \label{sec:unresp} 

In this section, we introduce the notion of limited unresponsiveness,
a fundamental relation that we use to define cause.  We define limited
unresponsiveness using primitives from decision theory as explicated
(for example) by Savage (1954).

We begin with a description of the primitives {\em act}, {\em
consequence}, and {\em possible state of the world.}  Savage describes
and illustrates these concepts as follows:

\begin{quotation}
To say that a decision is to be made is to say that one or more acts
is to be chosen, or decided on.  In deciding on an act, account must
be taken of the possible states of the world, and also of the
consequences implicit in each act for each possible state of the
world.  A {\em consequence} is anything that may happen to the
person.

Consider an example.  Your wife has just broken five good eggs into a
bowl when you come in and volunteer to finish making the omelet.  A
sixth egg, which for some reason must either be used for the omelet or
wasted altogether, lies unbroken beside the bowl.  You must decide
what to do with this unbroken egg.  Perhaps it is not too great an
oversimplification to say that you must decide among three acts only,
namely, to break it into the bowl containing the other five, to break
it into a saucer for inspection, or to throw it away without
inspection.  Depending on the state of the egg, each of these three
acts will have some consequence of concern to you, say that indicated
by \Tab{tab:savage}.
\end{quotation}

\begin{table}  
\begin{center} 
\begin{tabular}{|c|l|l|l|} 
\hline 
\multicolumn{1}{|c|}{state of the} & \multicolumn{3}{c|}{act} \\
\cline{2-4}
\multicolumn{1}{|c|}{world}
  & \multicolumn{1}{c|}{break into bowl} 
  & \multicolumn{1}{c|}{break into saucer}
  & \multicolumn{1}{c|}{throw away} \\
\hline
good egg &  six-egg omelet &  six-egg omelet and a & five-egg omelet and one \\
         &                 &  \ \ saucer to wash   & \ \ good egg destroyed  \\
bad egg  & no omelet and five good & five-egg omelet and a & five-egg omelet \\
         & \ \ eggs destroyed      & \ \ saucer to wash    & \\
\hline
\end{tabular} 
\end{center} 
\caption{An example illustrating acts, possible states of the world, 
and consequences. (Taken from Savage [1954].)}
\label{tab:savage}
\end{table} 

For purposes of our discussion, there are two points to emphasize from
Savage's exposition.  First, it is important to distinguish between
that which we can choose---namely, acts---and that which we can not
choose---namely, consequences.  Second, once we choose an act, the
consequence that occurs is logically determined by the state of the
world.  That is, the consequence is a deterministic function of the
act and the state of the world.  Of course, the consequence can be
(and usually is) uncertain, and this uncertainty is captured by
uncertainty in the state of the world.  The concepts of act,
consequence, and state of the world, together with the deterministic
mapping from act and state of the world to consequence are our only
primitives.\footnote{Savage (1954) {\em defines} an act to be ``a
function attaching a consequence to each state of the world.''  In
contrast, we take act to be a primitive, as do many decision analysts
(e.g., Howard, 1990).\nocite{Howard90}}

In the omelet story, the possible states of the world readily come to
mind given the description of the problem.  Furthermore, we can
observe the state of the world (i.e., the condition of the egg).  In
many if not most situations, however, the state of the world is
unobservable.  That is, the assertion ``the state of the world is
${\bf x}$'' is a counterfactual.  In these situations, we can bring
the possible states to mind by thinking about the acts and
consequences.  For example, suppose we have a decision to continue
smoking or quit, and we model the consequences of getting cancer or
not.  These acts and consequences bring to mind four possible states
of the world, as shown in \Tab{tab:smoke}.  These possible states have
no familiar names; and we simply label them with numbers.  The actual
state of the world is not observable, because, if we decide to quit,
then we won't know for sure what would have happened had we continued,
and vice versa.

The acts and consequences in this problem may actually bring to mind
more than four---even an infinite number---of states of the world.
For example, the state of the world may correspond to degree of
susceptibility of lung tissue to tar as measured by a biochemical
assay.  Nonetheless, given the discrete acts and consequences that we
have chosen to model in the problem, the four states in
\Tab{tab:smoke} are sufficiently detailed.  Savage recognizes this
issue of detail in his definition of state of the world: ``a
description of the world, leaving no relevant aspect undescribed.''
In general, if we have a decision problem with $c$ consequences and
$a$ acts, then at most $c^a$ possible states of the world need be
distinguished.\footnote{When acts and consequences are continuous, the
specification of $S$ is more complicated.  In this paper, we address
only situations where acts and consequences are discrete.}

\begin{table}  
\begin{center} 
\begin{tabular}{|c|l|l|} 
\hline 
\multicolumn{1}{|c|}{state of the} & \multicolumn{2}{c|}{act} \\
\cline{2-3}
\multicolumn{1}{|c|}{world} 
  & \multicolumn{1}{c|}{continue} 
  & \multicolumn{1}{c|}{quit} \\
\hline
1 & cancer    & no cancer \\
2 & no cancer & no cancer \\
3 & cancer    & cancer \\
4 & no cancer & cancer \\
\hline
\end{tabular} 
\end{center} 
\caption{The four possible states of the world for a decision to continue 
or quit smoking.}
\label{tab:smoke}
\end{table}

The idea that the state of the world may not be observable can be
traced to Neyman (1923)\nocite{Neyman23}, who derived statistical
methods for estimating the differences in yields of different crops
planted on the same plot of land, in circumstances where only one crop
was actually planted on a plot.  Rubin (1978) and Howard (1990) have
formalized this idea.

In practice, it is often cumbersome if not impossible to reason about
a monolithic set of acts, possible states of the world, or
consequences.  Therefore, we typically describe each of these items in
terms of a set of variables that take on two or more values or {\em
instances}.  We call a variable describing a set of consequences a
{\em chance variable.}  For example, in the omelet story, we can
describe the consequences in terms of three chance variables: (1) {\em
number of eggs in the omelet?}\footnote{To emphasize the distinction
between chance and decision variables, we put a question mark at the
end of the names of chance variables.} ($o$) having instances {\bf
zero}, {\bf five}, and {\bf six}, (2) {\em number of good eggs
destroyed?} ($g$) having instances {\bf zero}, {\bf one}, and {\bf
five}, and (3) {\em saucer to wash?} ($s$) having instances {\bf no}
and {\bf yes}.  That is, every consequence corresponds to an assignment
of an instance to each chance variable.

We call a variable describing a set of acts a {\em decision variable}
(or {\em decision}, for short).  For example, suppose we have a set of
possible acts about how we are going to dress for work.  In this case,
we can describe the acts in terms of the decision variables {\em
shirt} ({\bf plain} or {\bf striped}), {\em pants} ({\bf jeans} or
{\bf corduroy}), and {\em shoes} ({\bf tennis shoes} or {\bf
loafers}).  In this example and in general, every act corresponds to a
choice of an instance for each decision variable.

The description of possible states of the world in terms of component
variables is a bit more complicated, and is not needed for our
explication of unresponsiveness and limited unresponsiveness.  We
defer discussion of this issue to \Sec{sec:mapping}.

As a matter of notation, we use $D$ to denote the set of decisions
that describe the acts for a decision problem, and lower-case
letters (e.g., $d,e,f$) to denote individual decisions in the
set $D$.  Also, we use $U$ to denote the set of chance variables that
describe the consequences, and lower-case letters (e.g., $x,y,z$) to
denote individual chance variables in $U$.  In addition, we use the
variable $S$ to denote the state of the world (the instances of $S$
correspond to the possible states of the world).\footnote{We use an
uppercase ``$S$'' to denote this single variable, because later we
decompose $S$ into a set of variables.}  Thus, any given decision
problem---or {\em domain}, as we sometimes call it---is described by
the variables $U$, $D$, and $S$.\footnote{Sometimes, for simplicity,
we leave $S$ implicit in the specification of a decision problem.}

With this introduction, we can discuss the concept of limited
unresponsiveness.  To illustrate this concept, consider the following
decision problem adapted from Angrist et al.\ (1995)\nocite{AIR95}.
Suppose we are a physician who has to decide whether to recommend for
or against a particular treatment.  Given our recommendation, our
patient may or may not actually accept the treatment, and may or may
not be cured as a result.  Here, we use a single decision variable
{\em recommendation} ($r$) to represent our acts (i.e., $D=\{r\}$),
and two chance variables {\em taken?} ($t$) and {\em cured?} ($c$) to
represent whether or not the patient actually accepts the treatment
and whether or not the patient is cured, respectively (i.e.,
$U=\{t,c\}$).

The possible states of the world for this problem are shown in
\Tab{tab:lu}.  For example, consider the first row in the table.
Here, the patient will accept the treatment if and only if we
recommend it, and will be cured if and only if he takes the
treatment.  We describe this state by saying that the patient is a
complier and is helped by the treatment.  We discuss the description
of these states in more detail in
\Sec{sec:mapping}.

\begin{table}  
\begin{center} 
\begin{tabular}{|l|cc|cc|} 
\hline 
  & \multicolumn{4}{c|}{$r$ ({\em recommendation}) } \\
\cline{2-5} 
\multicolumn{1}{|c|}{$S$ (state of the world) } 
 & \multicolumn{2}{c|}{take}  & \multicolumn{2}{c|}{don't take} \\
\cline{2-5} 
 & \multicolumn{1}{c}{$t$ ({\em taken?}) } 
 & \multicolumn{1}{c|}{$c$ ({\em cured?}) }  
 & \multicolumn{1}{c}{$t$ ({\em taken?}) } 
 & \multicolumn{1}{c|}{$c$ ({\em cured?}) } \\ 
\hline
\ 1: complier, helped         & yes & yes & no  & no  \\
\ 2: complier, hurt           & yes & no  & no  & yes \\
\ 3: complier, always cured   & yes & yes & no  & yes \\
\ 4: complier, never cured    & yes & no  & no  & no  \\
\ 5: defier, helped           & no  & no  & yes & yes \\
\ 6: defier, hurt             & no  & yes & yes & no  \\
\ 7: defier, always cured     & no  & yes & yes & yes \\
\ 8: defier, never cured      & no  & no  & yes & no  \\
\ 9: always taker, cured      & yes & yes & yes & yes \\
 10: always taker, not cured  & yes & no  & yes & no  \\
 11: never taker, not cured   & no  & no  & no  & no  \\
 12: never taker, cured       & no  & yes & no  & yes \\
 13: (impossible)             & yes & yes & yes & no  \\
 14: (impossible)             & yes & no  & yes & yes \\
 15: (impossible)             & no  & no  & no  & yes \\
 16: (impossible)             & no  & yes  & no  & no  \\
\hline
\end{tabular} 
\end{center} 
\caption{A decision problem about recommending a medical treatment.}
\label{tab:lu}
\end{table} 

As is indicated in the table, suppose that we believe the last four
states of the world are impossible (i.e., have a probability of
zero).  These last four states share the property that $t$ takes on
the same instance for both acts, whereas $c$ does not.  Thus, this
decision problem satisfies the following property: in all of the
states of the world that are possible, if $t$ is the same for the two
acts, then $c$ is also the same.  We say that $c$ is unresponsive to
$r$ in states limited by $t$.

In general, suppose we have a decision problem described by variables
$U$, $D$, and $S$.  Let $X$ be a subset of $U$, and $Y$ be a subset of
$U \cup D$.  We say that $X$ is unresponsive to $D$ in states limited
by $Y$ if we believe that, for all possible states of the world, if
$Y$ assumes the same instance for any two acts then $X$ must also
assume the same instance for those acts.  We describe the notion of
limited unresponsiveness in earlier work in terms of a {\em
conditional fixed set} (Heckerman and Shachter, 1994).\nocite{HS94uai}
Angrist et al.\ (1995) discuss an instance of limited unresponsiveness,
which they call the {\em exclusion restriction}.

To be more formal, let $X[\bS,\bD]$ be the instance that $X$ assumes
(with certainty) given the state of the world $\bS$ and the
act $\bD$.  For example, in the omelet story, if $\bS$ is the
state of the world where the egg is good, and $\bD$ is the act
{\bf throw away}, then $o[\bS,\bD]$ (the number of eggs in the omelet)
assumes the instance {\bf five}.  Then, we have the following
definition.

\begin{definition}[Limited (Un)responsiveness] \label{def:crs}
Given a decision problem described by \linebreak chance variables $U$,
decision variables $D$, and state of the world $S$, and variable sets
$X \subseteq U$ and $Y \subseteq D \cup U$, {\em $X$ is said to be
unresponsive to $D$ in states limited by $Y$,} denoted $X \urs_Y D$,
if we believe that
\[
\forall \ \bS \in S,
\ \bDone \in D,
\ \bDtwo \in D: \ \ 
  Y[\bS,\bDone] = Y[\bS,\bDtwo] \Longrightarrow X[\bS,\bDone] = X[\bS,\bDtwo]
\]
{\em $X$ is said to be responsive to $D$ in states limited by $Y$,}
denoted $X \rs_Y D$, if it is not the case that $X$ is unresponsive to
$D$ in states limited by $Y$---that is, if we believe that
\[
\exists \ \bS \in S, 
\ \bDone \in D, 
\ \bDtwo \in D \ \ {\rm s.t.} \ \ 
  Y[\bS,\bDone] = Y[\bS,\bDtwo] \ {\rm and} \  X[\bS,\bDone] \neq X[\bS,\bDtwo]
\]
\end{definition}

\vspace{\medskipamount}

When $X$ is (un)responsive to $D$ in states limited by $Y =
\emptyset$, we simply say that {\em $X$ is (un)responsive to $D$.}
The notion of unresponsiveness is significantly simpler than that of
limited unresponsiveness.  That is, when $Y = \emptyset$, the
equalities on the left-hand-side of the implications in \Def{def:crs}
are trivially satisfied.  Thus, $X$ is unresponsive to $D$ if we
believe that, in each possible state of the world, $X$ assumes the
same instance for all acts; and $X$ is responsive to $D$ if
there is some possible state of the world where $X$ differs for two
different acts.

As examples of responsive variables, consider the omelet story.  Let
$\bS$ denote the state where the egg is good, and $\bDone$ and
$\bDtwo$ denote the acts {\bf break into bowl} and {\bf throw away},
respectively.  Then, for the variable $o$ ({\em number of eggs in
omelet?}), we have $o[\bS,\bDone]=${\bf six} and $o[\bS,\bDtwo]=${\bf
five}.  Consequently, $o$ is responsive to $D$.\footnote{Technically,
we should say that $\{o\}$ is responsive to $D$.  For simplicity,
however, we usually drop set notation for singletons.}  In a similar
manner, we can conclude that $g$ ({\em number of good eggs
destroyed?}), and $s$ ({\em saucer to wash?}) are each responsive to
$D$.

Note that if a chance variable $x$ is responsive to $D$, then---to
some degree---it is under the control of the decision maker.
Consequently, the decision maker can not observe $x$ prior to choosing
an act for $D$.  For example, in the omelet story, we can not
observe any of the responsive variables $o$, $g$, or $s$ before
choosing an act.\footnote{To be more precise, the variable $o$
represents the number of eggs in the omelet {\em after} we choose an
act for $D$.  This variable should not be confused with
another variable--say $o'$---corresponding to the number of eggs in
the omelet {\em before} we choose $D$.  Whereas $o$ is responsive
to $D$ and cannot be observed before choosing an act, $o'$
is unresponsive to $D$ and can be observed before choosing $D$.}

As an example of an unresponsive variable, suppose we include $S$ (the
state of the world) as a variable in $U$.  (E.g., in the omelet story,
we can take $U$ to be $\{S,o,g,s\}$.)  By Savage's definition of $S$,
it must be unresponsive to $D$.  Note that including $S$ in $U$
creates no new states of the world.

As we have discussed, the notions of unresponsiveness and limited
unresponsiveness are closely related to concepts in counterfactual
reasoning.  When we determine whether or not a chance variable $x$ is
unresponsive to decisions $D$, we essentially answer the query ``Will
the outcome of $x$ be the same no matter how we choose $D$?''
Furthermore, when we determine whether or not $x$ is unresponsive to
$D$ in states limited by $Y$, we answer the query ``If $Y$ will not
change as a result of our choice for $D$, will the outcome of $x$ be
the same?''  One of the fundamental assumptions of our work presented
here is that these counterfactual queries are easily answered.  In our
experience, we have found that decision makers are indeed comfortable
answering such restricted counterfactual queries.

The concepts of responsiveness and probabilistic independence are
related, as illustrated by the following theorem.

\begin{theorem} \label{thm:ur-indp}
If a set of chance variables $X$ is unresponsive to a set of decision
variables $D$, then $X$ is probabilistically independent of $D$.
\end{theorem}

\noindent {\bf Proof:} By definition of unresponsiveness, $X$ assumes
the same instance for all acts in any possible state of the
world.  Consequently, we can learn about $X$ by observing $S$, but not
by observing $D$.
\qed

Nonetheless, the two concepts are not identical.  In particular, the
converse of \Thm{thm:ur-indp} does not hold.  For example, let us
consider the simple decision of whether to bet heads or tails on the
outcome of a coin flip.  Assume that the coin is fair (i.e., the
probabilities of heads and tails are both 1/2) and that the person who
flips the coin does not know our bet.  Here, the possible outcomes of
the coin toss correspond to the possible states of the world.
Further, let decision variable $b$ denote our bet, and chance
variable $w$ describe the possible consequences that we win or not.
In this situation, $w$ is responsive to $b$, because for both possible
states of the world, $w$ will be different for the different bets.
Nonetheless, the probability of $w$ is 1/2, whether we bet heads or
tails.  That is, $w$ and $b$ are probabilistically independent.

Limited unresponsiveness and conditional independence are less closely
related than are their unqualified counterparts.  Namely, limited
unresponsiveness does not imply conditional independence.  For
example, in the medical-treatment story, $c$ ({\em cured?})  is
unresponsive to $r$ ({\em recommendation}) in states limited by $t$
({\em taken?}), but it is reasonable for us to believe that $c$ and
$r$ are not independent given $t$, perhaps because there is some factor
that---partially or completely---determines how a person reacts to
both recommendations and treatment.

We can derive several interesting properties of limited
unresponsiveness from its definition.

\begin{enumerate}
\item
$X \urs_Y D \Longleftrightarrow \forall x \in X, x \urs_Y D$

\item
$X \urs_W D \Longleftrightarrow X\cup W \urs_W D$

\item
$X \urs_D D$

\item
$X \urs_Y D \Longrightarrow X \urs_{Y\cup Z} D$

\item
$X \urs_{Y \cup Z} D {\rm \ and\ }Y \urs_Z D \Longrightarrow X \urs_Z D$

\item
$X \rs_Z D {\rm \ and\ } W \urs_Z D \Longrightarrow X \rs_{W \cup Z} D$
\end{enumerate}
where $D$ is the set of decision variables in the domain, $X$ and $W$
are arbitrary sets of chance variables in $U$, and $Y$ and $Z$ are
arbitrary sets of variables in $U \cup D$.

The proofs of these properties are straightforward.  For example,
consider property 5.  Given $X \urs_{Y \cup Z} D$, we have
\[
\forall \ \bS \in S, \ \bDone \in D, \ \bDtwo \in D: \ \
  Y[\bS,\bDone] = Y[\bS,\bDtwo] \ {\rm and}\ 
  Z[\bS,\bDone] = Z[\bS,\bDtwo]
\]
\vspace{-\bigskipamount}
\[
    \Longrightarrow X[\bS,\bDone] = X[\bS,\bDtwo]
\]
Given $Y \urs_Z D$, we have
\[
\forall \ \bS \in S, \ \bDone \in D, \ \bDtwo \in D: \ \ 
  Z[\bS,\bDone] = Z[\bS,\bDtwo]
    \Longrightarrow Y[\bS,\bDone] = Y[\bS,\bDtwo]
\]
Consequently, we obtain
\[
\forall \ \bS \in S, \ \bDone \in D, \ \bDtwo \in D: \ \ 
  Z[\bS,\bDone] = Z[\bS,\bDtwo]
    \Longrightarrow X[\bS,\bDone] = X[\bS,\bDtwo]
\]
That is, $X \urs_Z D$.

Other properties follow from these.  For example, it is true trivially
that $\emptyset \urs_Y D$.  Consequently, by Property 2, we know that
$Y \urs_Y D$.  As another example, a special case of Property 4 is
that whenever $X$ is unresponsive to $D$, then $X$ will be
unresponsive to $D$ in states limited by any $Z$.  Also, Properties 4
and 5 imply that limited unresponsiveness is transitive: $X
\urs_Y D$ and $Y \urs_Z D$ imply $X \urs_Z D$.

In closing this section, we note that the definition of limited
unresponsiveness can be generalized in several ways.  In one
generalization, we can define what it means for $X \subseteq U$ to be
unresponsive to $D$ in states of the world limited by ${\cal Y}$, a set
of instances of $Y$.  Namely, we say that $X$ is unresponsive to $D$
in states limited by ${\cal Y}$ if, for all possible states of the
world $\bS$, and for any two acts $\bDone$ and $\bDtwo$,
$Y[\bS,\bDone]=Y[\bS,\bDtwo] \in {\cal Y}$ implies
$X[\bS,\bDone]=X[\bS,\bDtwo]$.

In a second generalization, we can define what it means for a set of
chance variables to be unresponsive to a {\em subset} of all of the
decisions.  In particular, given a domain described by $U$ and $D$, we
say that $X \subseteq U$ is unresponsive to $D' \subseteq D$ in states
limited by $Y$ if $X \urs_{Y \cup (D \setminus D')} D$.  


\section{Definition of Cause} \label{sec:cause}

Given the notion of limited unresponsiveness, we can formalize our
definition of cause.
 
\begin{definition}[Causes with Respect to Decisions] \label{def:cause} 
Given a decision problem described by $U$ and $D$, and a variable $x
\in U$, {\em the variables $C \subseteq D \cup U \setminus \{x\}$ are
said to be causes for $x$ with respect to $D$} if $C$ is a
minimal set of variables such that $x \urs_C D$.
\end{definition}

In our framework, decision variables can not be caused, because they
are under the control of the decision maker.  Consequently, we define
causes for chance variables only.  Also, as we have discussed, our
definition is an extension of existing intervention-based definitions
of cause (e.g., Rubin [1978]) in that we allow causes to include
chance variables.  In addition, our definition of cause departs from
traditional usage of the term in that cause-effect assertions may vary
with the set of decisions available.  We discuss the advantages of
this departure shortly.

As an example of our definition, consider the decision to continue or
quit smoking, described by the decision variable $s$ ({\em smoke}) and
the chance variable $l$ ({\em lung cancer?}).  If we believe that $s$
and $l$ are probabilistically dependent, then, by \Thm{thm:ur-indp},
it must be that $l \rs s$.  Furthermore, by Property 3, we know that
$l \urs_s s$.  Consequently, by \Def{def:cause}, we have that $s$
is a cause of $l$ with respect to $s$.

As another example, consider the medical-treatment story.  We have
that $c$ ({\em cured?})  is responsive to $r$ ({\em
recommendation}), because (among other reasons) in the first row in
\Tab{tab:lu}, the patient is cured if and only if we recommend the
treatment.  Furthermore, as we discussed in the previous section, $c$
is unresponsive to $r$ in states limited by $t$ ({\em taken?}).
Consequently, we have that $t$ is a cause of $c$ with respect to
$r$.

The advantage of defining cause relative to decisions is made clear by
our breast-cancer example given in the introduction.  Let $g$ and $c$
denote the chance variables {\em gender?} and {\em breast cancer?},
respectively.  Now, imagine two decisions available to alter gender:
$o$, a decision to have a sex-change operation at birth, and $d$, a
decision to change chromosomes at conception by microsurgery.  It is
possible for someone to believe that $c \urs o$ and yet $c \rs d$ and
$c \urs_g d$.  That is, it is possible for someone to believe that
gender is a cause of breast cancer with respect to the chromosome
change but not with respect to the sex-change operation.  In this
situation, it does not make sense to make the unqualified statement
``gender is a cause of breast cancer.''  In general, our
decision-based definition provides added clarity.

Several consequences of \Def{def:cause} are worth mentioning.  First,
although cause is irreflexive by definition, it is not always
asymmetric.  For example, in our story about the coin toss, consider
another variable $m$ that represents whether or not the outcome of the
coin toss matches our bet $b$.  In the story as we have told it, $m$
is a deterministic function of $w$ ({\em win?}), and vice versa.
Consequently, we have $w \urs_m b$ and $m \urs_w b$; and so $m$ is
a cause of $w$ and $w$ is cause of $m$ with respect to $b$.
Note that any hint of uncertainty destroys this symmetry.  For
example, if there is a possibility that the person tossing the coin
will cheat (so that we may lose even if we match), then we can
conclude that $m$ is a cause of $w$, but not vice versa.  This
symmetry would also be destroyed if we had a decision controlling $w$
to which $m$ is unresponsive.

Second, cause is transitive for single variables.  In particular, if
$x$ is a cause for $y$ and $y$ is a cause for $z$ with respect
to $D$, then $z \rs _D$ and (by the transitivity of unresponsiveness)
$z \urs_x D$.  Consequently, $x$ is a cause for $z$ with respect
to $D$.  Note that transitivity does not necessarily hold for causes
containing sets of variables, because the minimality condition in
\Def{def:cause} may not be satisfied.

Third, $C=\emptyset$ is a set of causes for $x$ with respect to $D$ if
and only if $x$ is unresponsive to $D$.

Fourth, we have the following theorem, which follows from
\Def{def:cause} and several of the properties of limited
unresponsiveness given in
\Sec{sec:unresp}.

\begin{theorem} \label{thm:rc}
Given any $x \in U$, if $C$ is a set of causes for $x$ with respect to
$D$, and $w \in C \cap U$, then $w$ must be responsive to $D$.
\end{theorem}

\noindent {\bf Proof:}
For any chance variable $w \in C$, let $C' = C \setminus \{w\}$.
By the minimality condition in our definition, we have
\begin{equation} \label{eq:rc1}
x \rs_{C'} D
\end{equation}
Suppose that $w \urs D$.  Then, by Property 4, we have
\begin{equation} \label{eq:rc2}
w \urs_{C'} D
\end{equation}
Applying \Eqs{eq:rc1} and \ref{eq:rc2} to Property 6, we have
that $x \rs_C D$, which contradicts that $C$ is a set of causes
for $x$ with respect to $D$. \qed

To illustrate the use of this theorem, let us extend the
medical-treatment example by imagining that there is some gene that
affects how a person reacts to both our recommendation and to
therapy.  In this situation, it is reasonable for us to assert that
the variable $g$ ({\em genotype?}) is unresponsive to $r$.  Thus, by
\Thm{thm:rc}, $g$ can not be among the causes for any 
variable.

This consequence of our definition may seem unappealing.  Intuitively,
we would like to be able to say that (in some sense) $g$ is a cause of
$c$.  Indeed, our definition does not preclude the ability to make
such assertions.  Namely, there is no reason to require that the
decisions $D$ be implementable in practice or at all.  If we want to
think about whether or not the patient's genotype is a cause for his
cure, then we can imagine an action that can alter one's genetic
makeup---for example, retroviral therapy ($v$).  In this case, it is
reasonable to conclude that $\{r,g\}$ is a cause for $t$ with respect
to the decisions $\{r,v\}$.  Nonetheless, as we have discussed, we
must be clear about the action(s) that alter genotype to make this
statement of cause precise.

Finally, we can generalize our definition of what it means for a set
of {\em variables} to cause $x$ to a definition of what it means for a
set of {\em instances} to cause $x$.  Namely, we say that ${\cal C}$,
a set of instances of $C$, is a cause for $x \notin C$ with respect to
$D$ if $C$ is a minimal set of variables such that $x$ is unresponsive
to $D$ in states limited by ${\cal C}$.  That is, ${\cal C}$ is a
cause for $x$ with respect to $D$ if we replace our definition of
cause with the weaker requirement that $x$ be unresponsive to $D$ in
states limited by ${\cal C}$.


\section{Influence Diagrams}
\label{sec:id} 

In this and the following three sections, we examine the graphical
representation of cause within our framework.  This study is useful in
its own right, and also will help to relate our framework with Pearl's
structural equation model.  We begin, in this section, with a review
of the influence-diagram representation.

An {\em influence diagram} is (1) a acyclic directed graph $G$
containing decision and chance nodes corresponding to decision and
chance variables, and information and relevance arcs, representing
what is known at the time of a decision and probabilistic dependence,
respectively, (2) a set of probability distributions associated with
each chance node, and optionally (3) a utility node and a
corresponding set of utilities (Howard and Matheson,
1981)\nocite{Howard81}.

An {\em information arc} is one that points to a decision node.  An
{\em information arc} from chance or decision node $a$ to decision
node $d$ indicates that variable $a$ will be known when
decision $d$ is made.  (We shall use the same notation to refer to a
variable and its corresponding node in the diagram.)  A {\em relevance
arc} is one that points to a chance node.  The {\em absence} of a
possible relevance arc represents conditional independence.  To
identify relevance arcs, we start with an ordering of the variables in
$U=(x_1,\ldots,x_n)$.  Then, for each variable $x_i$ in order, we ask
the decision maker to identify a set $\Pa{x_i}
\subseteq
\{x_1,\ldots,x_{i-1},D\}$ that renders $x_i$ and 
$\{x_1,\ldots,x_{i-1},D\}$ conditionally independent. 
That is, 
\begin{equation} \label{eq:i-pi} 
\Prb{x_i|x_1,\ldots,x_{i-1},D,\xi} = \Prb{x_i|\Pa{x_i},\xi} 
\end{equation}  
where $\Prb{X|Y,\xi}$ denotes the probability distribution of $X$
given $Y$ for a decision maker with background information $\xi$.  For
every variable $z$ in $\Pa{x_i}$, we place a relevance arc from $z$ to
$x_i$ in graph $G$ of the influence diagram.  That is, the nodes
$\Pa{x_i}$ are the {\em parents} of $x_i$ in $G$.

Associated with each chance node $x_i$ in an influence diagram are the
probability distributions $\Prb{x_i|\Pa{x_i},\xi}$.  From the chain rule
of probability, we know that
\begin{equation} \label{eq:chain} 
\Prb{x_1,\ldots,x_n|D,\xi} =  
  \prod_{i=1}^n  \Prb{x_i|x_1,\ldots,x_{i-1},D,\xi} 
\end{equation}
Combining Equations~\ref{eq:i-pi} and \ref{eq:chain}, we see that any 
influence diagram for $U \cup D$ uniquely determines a joint probability 
distribution for $U$ given $D$.  That is, 
\begin{equation} \label{eq:prod-decomp} 
\Prb{x_1,\ldots,x_n|D,\xi} = \prod_{i=1}^n  \Prb{x_i|\Pa{x_i},\xi} 
\end{equation} 

Influence diagrams may also contain special chance nodes.  A {\em
deterministic node} corresponds to variable that is a deterministic
function of its parents.  A {\em utility node} encodes preferences of
the decision maker.  Finally, an influence diagram is unambiguous when
its decision nodes are totally ordered---that is, when there is a
directed path in the influence diagram that traverses all decisions.
This total order corresponds to the order in which decisions are
made.

In this paper, we concern ourselves neither with the ordering of
decision nodes nor the observation of chance variables before making
decisions.  Therefore, we are not concerned with information arcs.
Likewise, although our new concepts apply to models that include
utility nodes, we can illustrate these concepts with models containing
only chance, deterministic, and decision variables.

\Fig{fig:id}a contains an influence diagram for the omelet
story.  As is illustrated in the figure, we use ovals, double ovals,
and squares to represent chance, deterministic, and decision nodes,
respectively.  Among the possible relevance arcs in the influence
diagram, several are missing.  For example, there is no arc from $D$
to $S$, representing the independence of $D$ and $S$ (which follows
from the assertion that $S$ is unresponsive to $D$).
Figures~\ref{fig:id}b and \ref{fig:id}c contain influence diagrams for
the medical-treatment example.  The chance variable $g$ ({\em
genotype?})  is explicitly modeled in \Fig{fig:id}c.

\begin{figure}   
\begin{center}  
\leavevmode  
\psfig{figure=fidegs.eps,width=6in}  
\end{center}  
\caption{Influence diagrams for (a) the omelet story, and (b,c)
the medical-treatment example.}
\label{fig:id} 
\end{figure}  

The ordinary influence diagram was designed to be a representation of
conditional independence.  Furthermore, as we have discussed, the
concepts of conditional independence and limited unresponsiveness
are only loosely related.  Consequently, the influence diagram is an
inadequate representation of causal dependence, at least by our
definition of cause.  

In particular, an influence diagram may contain an arc from node $x$
to node $y$, even though $x$ is not among a set of causes for $y$.
For example, the influence diagram of \Fig{fig:id}b has an arcs from
$r$ and $t$ to $c$ due to the dependencies in the domain.
Nonetheless, we have established that the singleton $\{t\}$ is a cause
for $c$ with respect to $r$.

Furthermore, an influence diagram may contain no arc from $x$ to $y$,
even though $x$ is a cause of $y$.  For example, consider the coin
example, illustrated by the influence diagram in \Fig{fig:coin}a.
If we believe that the coin is fair, and if we do not bother to model
the variable $c$ explicitly (as shown in \Fig{fig:coin}b), then we
need not place an arc from $d$ to $w$, because the probability of
winning will be $1/2$, regardless of our choice $d$.  Nonetheless,
$b$ is a cause for $w$ with respect to $b$, by our definition.

Despite these limitations, the influence diagram {\em is} adequate for
purposes of making decisions under uncertainty.  In the introduction,
we argued that causal information is needed for predicting the effects
of actions.  Thus, the question arises: ``Why do we need anything more
than the influence diagram as a representation of the effects of
actions?''  We give an answer to this question in \Sec{sec:persis},
where we discuss counterfactual reasoning.  There, we show that the
ordinary influence diagram is inadequate for purposes of
counterfactual reasoning unless it is in canonical form---a form that
accurately reflects cause.
  

\section{Direct and Atomic Interventions} \label{sec:man}

In order to define canonical form, we need the concept of a mapping
variable.  Likewise, in order to define a mapping variable, we need the
concept of atomic intervention.  We also need the concept of atomic
intervention to explicate Pearl's structural-equation model.  In this
section, we define atomic intervention along with a more general
concept called direct intervention.

%format: moved down
\begin{figure}   
\begin{center}  
\leavevmode  
\psfig{figure=fcoin.eps,width=2.2in}  
\end{center}  
\caption{Influence diagrams for betting on a coin flip.}
\label{fig:coin} 
\end{figure}  

Roughly speaking, we say that a set of decisions $I$ is a direct
intervention on a set of chance variables $X$ if the effects of $I$ on
all chance variables are mediated only through the effects of $I$ on
$X$.  SGS, who take cause to be a primitive, provide a formal
definition of direct intervention (which they call a direct
manipulation) that is consistent with our notion.  We find it simpler
to define direct intervention in terms of limited unresponsiveness.

\begin{definition}[Direct Intervention] \label{def:dm} 
Given a domain described by $U$ and $D$, a set of decisions $I
\subseteq D$ is said to be a {\em direct intervention on $X \subseteq
U$ with respect to $D$} if (1) for all $x \in X$, $x \rs I$, and (2)
for all $y \in U$, $y \urs_X I$.
\end{definition}

For example, in the medical-treatment story, $r$ is a direct
intervention on $t$, because $t \rs r$ and $c \urs_t r$.  As
another example, suppose the physician has an additional decision $p$
of whether or not to pay the patient to take the treatment.  It is
reasonable to expect that $t \rs p$.  Furthermore, if the amount of
payment is small, it is reasonable that $c \urs_t p$.  Consequently,
$p$ qualifies as a direct intervention on $t$.  Nonetheless,
if the amount of payment is sufficiently large, the patient may use
that money to improve his health care.  Thus, $c \rs_t p$; and $p$
does not satisfy the condition 2 for a direct intervention on
$t$.

Given the notion of direct intervention, we can define atomic
intervention.

\begin{definition}[Atomic Intervention] \label{def:am} 
Given a domain described by $U$ and $D$, a decision $\hat{x} \in D$ is
said to be an {\em atomic intervention on $x \in U$ with respect to
$D$} if (1) $\{\hat{x}\}$ is a direct intervention on $\{x\}$ with
respect to $D$, and (2) $\hat{x}$ has precisely the instances (a)
{\bf idle}, which corresponds to the instance of doing nothing to $x$,
and (b) {\bf set}$({\bf x})$ for every instance ${\bf x}$ of $x$,
where $x={\bf x}$ whenever $\hat{x}=${\bf set}$({\bf x})$.
\end{definition}

As we discussed in the introduction, Pearl takes the concept of atomic
intervention to be primitive.  Whether or not a decision is a direct
(or atomic) intervention, however, depends on the underlying causal
relationships in the domain.  In the medical-treatment story, suppose
the physician has a decision $k$ of whether or not to administer the
treatment (a drug) without the patient's knowledge.  If we believe
that the treatment is truly effective and has no placebo effect, then
we can assert that $k$ is a direct intervention on $t$.  If,
however, we believe that the treatment has only a placebo effect, then
$k$ will not be a direct intervention on $t$, because $k$ will
also directly affect $c$.  Thus, the notions of direct and atomic
intervention require definitions, lest the meaning of cause would be
hidden in these primitives.

We note that, when there are bi-directional causal relationships among
variables in $U$, it is not always possible for every chance variable
to have its own atomic intervention.  For example, consider an
adiabatic system consisting of a cylindrical chamber with a moveable
top, in which we model the variables {\em pressure?} ($p$) and {\em
volume?} ($v$).\footnote{This example is not appropriate technically,
as it uses continuous variables.  Nonetheless, this example
illustrates our point.}  If we allow the top of the chamber to move
freely, then placing various weights on the top of the chamber
constitutes an atomic intervention on $p$; and we have that $p$ is
a cause of $v$ with respect to $\hat{p}$.  In contrast, fixing the top
of the chamber at particular locations constitutes an atomic
intervention on $v$; and we have that $v$ is a cause of $p$ with
respect to $\hat{v}$.  By the laws of physics, however, both decisions
$\hat{p}$ and $\hat{v}$ can not be available simultaneously.


\section{Mapping Variables} \label{sec:mapping}

To understand the concept of a mapping variable, let us reexamine
Savage's basic formulation of a decision problem.  Recall that the
chance variables $U$ are a deterministic function of the decision
variables $D$ and the state of the world $S$.  In effect, each
possible state of the world defines a mapping from the decisions $D$
to the chance variables $U$.  Thus, $S$ represents all possible
mappings from $D$ to $U$.  We can characterize $S$ as a mapping
variable for $U$ as a function of $D$, and use the suggestive notation
$U(D)$ to denote this mapping variable.

In general, given a domain described by $U$, $D$, and $S$, a set of
decision variables $Y \subseteq D$, and a set of chance variables $X
\subseteq U$, the mapping variable $X(Y)$ is a variable that
represents the possible mappings from $Y$ to $X$.  

As an example, consider the medical-treatment story.  The mapping
variable $t(r)$ represents the possible mappings from the decision
variable $r$ ({\em recommendation}) to the chance variable $t$ ({\em
taken?}).  In this example, the instances of $t(r)$, shown in
\Tab{tab:tr}, have a natural interpretation.  In particular, the
instance where the patient accepts treatment if and only if we
recommend it represents a patient who complies with our
recommendation; the instance where the patient accepts treatment if
and only if we recommend against it represents a patient who defies
our recommendation; and so on.

\begin{table}  
\begin{center} 
\begin{tabular}{|l|l|l|} 
\hline 
\multicolumn{1}{|c|}{instance of $t(r)$} 
  & \multicolumn{1}{c|}{$r=$take} 
  & \multicolumn{1}{c|}{$r=$don't take} \\
\hline
1: complier     & $t=$yes  & \ \ \ \ $t=$no  \\
2: defier       & $t=$no   & \ \ \ \ $t=$yes \\
3: always taker & $t=$yes  & \ \ \ \ $t=$yes \\
4: never taker  & $t=$no   & \ \ \ \ $t=$no  \\
\hline
\end{tabular} 
\end{center} 
\caption{The mapping variable $t(r)$.}
\label{tab:tr}
\end{table}

The notion of a mapping variable is discussed in Heckerman and
Shachter (1994)\nocite{HS94uai}, and in Balke and Pearl
(1994)\nocite{BP94uai} under the name ``response function.''  A
related counterfactual variable is described by Neyman
(1923)\nocite{Neyman23}, Rubin (1978)\nocite{Rubin78}, and Howard
(1990)\nocite{Howard90}.  They discuss what we would denote
$X(Y=\bY)$: the variable $X$ {\em if} we choose instance $\bY$ for
$Y$.

An important property concerning mapping variables is that, given
variables $X,Y,$ and $X(Y)$, we can always write $X$ as a
deterministic function of $Y$ and $X(Y)$.  For example, $t$ is a
deterministic function of $r$ and $t(r)$; and $U$ is a deterministic
function of $D$ and $U(D) \equiv S$.

In the discussions that follow, it is useful to extend the definition
of a mapping variable to include chance variables as arguments.  For
example, in the medical-treatment story, it seems reasonable to
define the mapping variable $c(t)$ with instances {\bf helped},
{\bf hurt}, {\bf always cured}, and {\bf never cured}.  Together, the
mapping variables $t(r)$ and $c(t)$ describe the possible states of
the world $U(D) \equiv S$.  (E.g., $t(r)=${\bf complier} and
$c(t)=${\bf helped} corresponds to state 1 in
\Tab{tab:lu}.)  As we shall see, this decomposition of $U(D)$ 
facilitates the graphical representation of causal relationships.

Unfortunately, defining mapping variables with chance-variable
arguments is not always possible.  In the medical-treatment domain,
when the patient is an always taker (states 10 and 11 in
\Tab{tab:lu}), $t$={\bf yes} regardless of $r$.  Consequently,
we can not tell whether $c(t)$ is {\bf helped} or {\bf always
cured}---that is, $c(t)$ is not uniquely identified.  Because Savage's
decision-theoretic framework requires that the state of the world and
the act uniquely determine the instance of $c(t)$ (a consequence), the
instance of $c(t)$ is not well defined.  Nonetheless, $c(t)$ is well
defined whenever $D$ includes an atomic intervention on $t$
($\hat{t}$), guaranteeing that $t$ will take on all instances (as
$\hat{t}$ varies) in every state of the world.

In general, we have the following definition of mapping variable.

\begin{definition}[Mapping Variable] \label{def:ue} 
Given a domain described by $U$ and $D$, chance variables $X$, and
variables $Y$ such that, for every $y \in Y \cap U$, there exists
an atomic intervention $\hat{y} \in D$,\footnote{Recall from
\Sec{sec:man} that it is not always possible to have atomic
interventions for every $y \in Y$.}  the {\em mapping variable
$X(Y)$} is the chance variable that represents all possible mappings
from $Y$ to $X$.
\end{definition} 

There are several important points to be made about mapping variables
as we have now defined them.  First, as in the more specific case, $X$
is always a deterministic function of $Y$ and $X(Y)$.

Second, additional probability assessments typically are required when
introducing a mapping variable into a probabilistic model.  For
example, two independent assessments are needed to quantify the
relationship between $r$ and $t$ in the medical-treatment story;
whereas three independent assessments are required for the node
$t(r)$.  In general, many additional assessments are required.  If $X$
has $c$ instances and $Y$ has $a$ instances, then $X(Y)$ has as many
as $c^a$ instances.  In real-world domains, however, reasonable
assertions of independence decrease the number of required
assessments.  In some cases, no additional assessments are necessary
(see, e.g., Heckerman et al., 1994\nocite{HBR94dx}).

Third, we have the following theorem, which follows immediately from
the definitions of limited unresponsiveness and mapping variable.  In
this and subsequent theorems that mention mapping variables, we assume
that atomic interventions required for the proper definition of the
mapping variables are included in $D$.

\begin{theorem}[Mapping Variable] \label{thm:map}
Given a decision problem described by $U$ and $D$, variables $X
\subseteq U$, and $Y \subseteq U \cup D$, $X \urs_Y D$ if and only if
$X(Y) \urs D$.
\end{theorem}

\noindent 
For example, in the medical treatment domain that includes the atomic
intervention $\hat{t}$, we have $c \urs_t \{r,\hat{t}\}$ and $c(t)
\urs \{r,\hat{t}\}$.  Roughly speaking, \Thm{thm:map} says that $X$ is
unresponsive to $D$ in states limited by $Y$ if and only if the way
$X$ depends on $Y$ does not depend on $D$.  This equivalence provides
us with an alternative set of conditions for cause.

\begin{corollary}[Causes with Respect to Decisions] \label{cor:cause} 
Given a decision problem described by $U$ and $D$, and a chance
variable $x \in U$, the variables $C \subseteq D \cup U \setminus
\{x\}$ are causes for $x$ with respect to $D$ if only if $C$ 
is a minimal set of variables such that $x(C) \urs D$.
\end{corollary}

When $C$ are causes for $x$ with respect to $D$, we call $x(C)$ a {\em
causal mapping variable with respect to $D$.}  Thus, we have the
following consequence of \Thm{thm:map}.

\begin{corollary}[Causal Mapping Variable] \label{cor:mech}
If $x(C)$ is a causal mapping variable for $x$ with respect to $D$,
then $x(C)$ is unresponsive to $D$.
\end{corollary}


\section{Canonical Form Influence Diagrams} \label{sec:hcf} 

We can now define what it means for an influence diagram to be in
canonical form.
 
\begin{definition}[Canonical Form] \label{def:hcf} 
An influence diagram for a decision problem described by $U$ and $D$
is said to be in {\em canonical form} if (1) all chance nodes that are
responsive to $D$ are descendants of one or more decision nodes and
(2) all chance nodes that are descendants of one or more decision
nodes are deterministic nodes.
\end{definition} 

\noindent
An immediate consequence of this definition is that any chance node
that is not a descendant of decision node must be unresponsive to
$D$.

We can construct an influence diagram in canonical form for a given
problem by including in the influence diagram a causal mapping
variable for every variable that is responsive to the decisions.  In
doing so, we can make every responsive variable a deterministic
function of its mapping variable and the corresponding set of causes.
For example, consider the medical-treatment story as depicted in the
influence diagram of \Fig{fig:xfrm}a.  The variables $t$ and $c$ are
responsive to $r$, but their corresponding nodes are not
deterministic.  Consequently, this influence diagram is not in
canonical form.  To construct a canonical form influence diagram, we
introduce the mapping variables $t(r)$ and $c(r)$, as shown in
\Fig{fig:xfrm}b.  The responsive variables are now deterministic; and
the mapping variables are unresponsive to the decision.  This example
illustrates an important point: Mapping variables may be
probabilistically dependent.  We return to this issue in
\Sec{sec:pearl}.

\begin{figure}   
\begin{center}  
\leavevmode  
\psfig{figure=fxfrm2.eps,width=2.2in}  
\end{center}  
\caption{(a) An influence diagram for the medical-treatment
story. (b) A corresponding influence diagram in canonical form.}
\label{fig:xfrm}
\end{figure}

In general, we can construct an influence diagram in canonical form
for any decision problem characterized by $U$ and $D$ as follows.

\begin{algorithm} [Canonical Form] \label{algo:cf} 
\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ 
\begin{enumerate} 
\item Add a node to the diagram corresponding to each variable in $U \cup D$

\item Order the variables $x_1,\ldots,x_n$ in $U$ so that
the variables unresponsive to $D$ come first 

%format:
\pagebreak

\item For each variable $x_i \in U$ that is responsive to $D$,
\begin{enumerate} 
\item Add a causal-mapping-variable chance node $x_i(C_i)$ to the diagram, \\
where $C_i \subseteq D \cup \{x_1,\ldots,x_{i-1}\}$
 
\item Make $x_i$ a deterministic node with parents $C_i$ and $x_i(C_i)$ 
\end{enumerate} 
 
\item Assess independencies among the variables that are 
unresponsive to $D$\footnote{Because mapping variables are random
variables, the assessment of dependencies among the unresponsive
variables is, in principle, no different than that for assessing
dependencies among ordinary random variables.  Nonetheless, the
counterfactual nature of the variables can be confusing.  Howard
(1990) describes a method of probability assessment that addresses
this concern.}
\end{enumerate} 
\end{algorithm} 
 
This algorithm is well defined, because it is always possible to find
a set $C_i$ satisfying the condition in step 3a.  In particular, $x_i
\urs_D D$ by Property 3.  Consequently, even when $D$ contains no
atomic intervention, we can always create a causal mapping variable for
every responsive variable in $U$.

Also, the structure of any influence diagram constructed using
\Algo{algo:cf} will be valid.  
Namely, by \Cor{cor:mech}, all causal mapping variables added in step
3 are unresponsive to $D$.  Thus, suppose we identify the relevance
arcs and deterministic nodes according to \Eq{eq:i-pi} by using a
variable ordering where the nodes in $D$ are followed by the
unresponsive nodes (including the causal mapping variables), which are
in turn followed by the responsive nodes in the order specified at
step 2.  Then, (1) we would add no arcs from $D$ to the unresponsive
nodes by \Thm{thm:ur-indp} (and the algorithm adds none); (2) we would
add arcs among the unresponsive nodes as described in step 4; and (3)
for every responsive variable $x_i$, we would make $x_i$ a
deterministic node (as described in step 3b) by definition of a
mapping variable.

In addition, the structure that results from \Algo{algo:cf} will be in
canonical form.  In particular, because there are no arcs from $D$ to
the unresponsive nodes, only responsive variables can be descendants
of $D$.  Also, by \Thm{thm:rc}, we know that every responsive
node is a descendant of $D$, and (by construction) a deterministic
node.

Furthermore, by construction, every responsive variable $x_i \in U$ has
one set of causes explicitly encoded in the diagram ($C_i$).

To illustrate the algorithm, consider the medical-treatment story as
depicted by the influence diagram in \Fig{fig:hcf}a, where the variable
$g$ ({\em genotype?}) is represented explicitly, and where $c \urs_t
\{r,\hat{t}\}$ and $g \urs \{r,\hat{t}\}$.  To construct an influence
diagram in canonical form for this problem, we first add the variables
$\{r,\hat{t},g,t,c\}$ to the diagram and choose the ordering
$(g,t,c)$.  Both $t$ and $c$ are responsive to $D=\{r,\hat{t}\}$, and
have causes $\{r,\hat{t}\}$ and $t$, respectively.  Consequently,
we add causal mapping variables $t(r,\hat{t})$ and $c(t)$ to the new
diagram, and make $t$ a deterministic function of $r$, $\hat{t}$, and
$t(r,\hat{t})$ and $c$ a deterministic function of $t$ and $c(t)$.
Finally, we assess the dependencies among the unresponsive variables
$\{g,t(r,\hat{t}),c(t)\}$, adding arcs from $g$ to $t(r,\hat{t})$ and
$c(t)$ under the assumption that the causal mapping variables are
conditionally independent given $g$.  The resulting canonical form
influence diagram is shown in \Fig{fig:hcf}b.

\begin{figure}   
\begin{center}  
\leavevmode  
\psfig{figure=fhcfhat.eps,width=3.5in}  
\end{center}  
\caption{(a) Another influence diagram for the medical-treatment
story. (b) A corresponding influence diagram in canonical form.}
\label{fig:hcf} 
\end{figure}

Canonical form is a generalization of Howard Canonical Form, which was
developed by Howard (1990)\nocite{Howard90} to facilitate the
computation of value of information.\footnote{Influence diagrams in
HCF do not allow mapping variables whose arguments contain chance
variables.}  Before making important decisions, decision analysts
investigate how useful it is to gather additional information.  This
investigation is typically done by computing the extra value the
decision maker would obtain by observing earlier one or more chance
variables in the domain.  If the decision maker does not expect to
observe chance variable $x$ prior to making decision $d$, the {\em
value of information about $x$} is the extra value he would obtain if
he were able to observe chance variable $x$ just before making
decision $d$.  The value of information is never negative, and it
serves as a bound on the value of any experiment: it would never be
worthwhile to spend more than the value of information about $x$ to
obtain any (possibly imperfect) observation about $x$ just before
making decision $d$.

Given an ordinary influence diagram, we can not compute the value of
information about variables responsive to $D$, because such variables
can not be observed before decisions $D$ are made.  In contrast, we
can always compute the value of information about mapping variables
corresponding to responsive variables in a canonical form influence
diagram, because such variables are unresponsive to $D$ by
definition.  For example, consider the decision to continue or quit
smoking described by decision variable $s$ ({\em smoke}) and chance
variables $l$ ({\em lung cancer?}) and $l(s)$.  Although we cannot
compute the value of information about $l$ because it is responsive to
$D$, we can compute the value of information about $l(s)$.

At first glance, it may seem pointless to determine the value of
information about a variable that cannot be observed (such as
$l(s)$).  Nonetheless, we can often learn {\em something} about a
mapping variable.  For example, imagine a test that measures the
susceptibility of someone's lung tissue to lung cancer in the presence
of tobacco smoke.  Learning the result of such a test may well update
our probability distribution over $l(s)$.  By computing the value of
information of $l(s)$, we obtain an upper bound on the most we would
be willing to pay to undergo such a test.


\section{Pearl's Causal Framework} \label{sec:pearl}

We can now demonstrate the relationship between Pearl's causal
framework and ours.  As mentioned, Pearl's framework is similar to
that of SGS (see the background notes in SGS for a discussion).  Thus,
many of the remarks in the section apply to SGS's model for cause as
well.  A notable exception is that SGS formally define direct
intervention.

The following theorem outlines the relationship.

\begin{theorem} \label{thm:pearl}
Given chance variables $U$, suppose the set of decision variables $D$
contains a unique atomic intervention $\hat{x}$ for every $x \in U$
and no other decisions.  Given graph $G$, a directed acyclic graph
with nodes corresponding to the variables in $U$, suppose that, for
all $x \in U$, $Pa^G(x) \cup \{\hat{x}\}$ are causes for $x$ with
respect to $D$.\footnote{It is not difficult to show that this
condition is consistent with the condition that, for all $x \in U$,
$\hat{x}$ is an atomic intervention on $x$.}  Then, the relationships
among the variables in $U \cup D$ can be expressed by the set of
simultaneous equations
\[
x = f_x(Pa^G(x),\hat{x},x(Pa^G(x),\hat{x}))
\]
for all $x \in U$, where $f_x$ is a deterministic function
such that $x={\bf x}$ if $\hat{x}=${\bf set}$({\bf x})$.
\end{theorem}

\noindent {\bf Proof:} 
The theorem follows by applying \Algo{algo:cf} using an ordering over
$U$ consistent with the graph $G$. \qed

Thus, we see that Pearl's structural-equation model is a 
specialization of canonical form when we identify (1)
Pearl's domain variables with our chance variables $U$, (2) Pearl's
atomic interventions with our atomic interventions $D$, (3) Pearl's
causal graph with our graph $G$, and (4) Pearl's random disturbance
$\epsilon_x$ with our causal mapping variable $x(Pa^G(x),\hat{x})$.

This correspondence permits several clarifications of Pearl's
framework.  First, we have a precise definition of atomic
intervention.  Unlike Pearl's model, where the concept of atomic
intervention is primitive, our framework provides a way to verify that
interventions are indeed atomic.

Second, we see what it means for the random disturbances to be
exogenous.  Namely, these random variables are {\em unresponsive} to
the decisions $D$.

Third, we have a precise definition of random disturbance in terms of
causal mapping variable.  Consequently, we have a means for assessing
the joint probability distribution of these variables, and---in
particular---a means for assessing independencies among these
variables.  In fact, whereas Pearl requires that random disturbances
be marginally independent, our definition imposes no such
requirement.

\Thm{thm:pearl} shows that any structural-equation model can
be encoded as an influence diagram in canonical form.  The converse is
also true---that is, any influence diagram in canonical form can be
encoded as a structural-equation model.  This result may seem
surprising, because in Pearl's model every domain variable must have
an atomic intervention, all decision variables must be atomic
interventions, and random disturbances must be independent.  Given an
influence diagram in canonical form, however, we can encode its chance
and decision variables in a structural equation model.  Specifically,
a chance variable $x$ can be encoded as the variable pair
$\{x,\hat{x}\}$ where $\hat{x}$ is instantiated to {\bf idle}, and a
decision variable $d$ can be encoded as the variable pair
$\{d,\hat{d}\}$ where the act {\bf idle} is forbidden.  In addition,
as noted by Pearl, we can remove dependencies among mapping variables
(at least in practice) by introducing hidden common
causes.\footnote{The assumption that the mapping variables are
independent has the convenient consequence that the graph $G$ can be
interpreted as a Bayesian network in the traditional sense.  That is,
if variables $X$ and $Y$ are d-separated by $Z$ in $G$, then $X$ and
$Y$ are conditionally independent given $Z$ according to the
structural-equation model corresponding to $G$.  (See Pearl,
1988,\nocite{Pearl88} for a definition of d-separation.)  SGS (p. 54)
refer to this association as the {\em causal Markov condition.}}

Nonetheless, because hidden common causes sometimes need to be
introduced, Pearl's structural-equation model can be a less efficient
representation than canonical form.  For example, to represent the
relationships in \Fig{fig:hcf}b, we would use a structual-equation
model with disturbance variables corresponding to $g(\hat{g})$,
$t(r,g,\hat{t})$, and $c(t,g,\hat{c})$.  Assuming $r,g,t$ and $c$ are
binary variables, the disturbance variables have 2, 16, and 16
instances, respectively.\footnote{Note that the mapping variable
$x(Y,\hat{x})$ has the same number of instances as does the mapping
variable $x(Y)$.}  Assuming the disturbance variables are independent,
the joint probability distribution of these variables contain 31
probabilities.  In contrast, both mapping variables in
\Fig{fig:hcf}b have only four instances.  Consequently, the 
joint probability distribution over the unresponsive variables in the
canonical-form representation contain only 13 probabilities.

We note that Balke and Pearl (1994)\nocite{BP94uai} relax the
assumption that mapping variables are independent.  Nonetheless, their
generalization of the structural-equation model, which they call a
{\em functional model}, is still less efficient than canonical form.
The inefficiency comes from the fact that canonical form encodes a
joint probability distribution among all unresponsive variables
(possibly including both domain and mapping variables), whereas a
functional model encodes a joint probability distribution among
mapping variables only.  For example, the canonical-form influence
diagram in \Fig{fig:hcf}b encodes the assertion that $t(r,\hat{t})$
and $c(t)$ are independent given $g$.  This assertion can not be
encoded in the Balke-Pearl representation.  When we represent the
relationships in \Fig{fig:hcf}b using a functional model, we can
include the variable $g$, in which case we obtain the 31-probability
model described in the previous paragraph.  Alternatively, we can
exclude variable $g$ from the model, and encode the dependency between
the mapping variables $t(r,\hat{t})$ and $c(t,\hat{c})$ with an arc
between these two variables.  The resulting Balke-Pearl model has 15
probabilities in contrast to the 13 required by canonical form.


\section{Counterfactual Reasoning} \label{sec:persis} 
 
As we have noted, the ordinary influence diagram is adequate for
making decisions under uncertainty, but is inadequate for
counterfactual reasoning.  In this section, we examine this form of
reasoning and suggest how it can be facilitated by influence diagrams
in canonical form.

Given a domain described by $U$ and $D$ with $X,Y,Z \subseteq U$,
counterfactual reasoning addresses questions of the form: If we choose
$D=\bDone$ and observe $X=\bX$, what is the probability that $Y=\bY$
if we choose $D=\bDtwo$ and observe $Z=\bZ$?  For example, in the
medical-treatment domain, we may wish to know: If we recommend the
treatment and the patient takes the drug and is cured, what is the
probability that the patient will be cured if we recommend against the
treatment?  Such reasoning is often important in the real-world---for
example, in legal argument (Ginsberg, 1986; Balke and Pearl, 1994;
Goldszmidt and Darwiche, 1994; Heckerman et
al., 1994).\nocite{Ginsberg86,BP94uai,HBR94dx,GD94uai}

We can answer such queries using influence diagrams in canonical
form.  To illustrate this approach, consider the medical-treatment
question in the previous paragraph.  To answer this query, we begin
with the influence diagram in canonical form shown in \Fig{fig:hcf}b.
Then, we duplicate all decision variables and all chance variables
that are responsive to the decisions, as shown in
\Fig{fig:persis}.  The original variables represent the act 
$r=${\bf take}, $\hat{t}$={\bf idle} and its consequences.  The
duplicate variables (denoted with primes) represent the act $r'=${\bf
don't take}, $\hat{t}$={\bf idle} and its consequences.  There is no
need to duplicate the unresponsive variables (including the causal
mapping variables) because, by definition, they can not be affected by
the decisions.\footnote{In general, we need duplicate only (1) those
decision variables that change in the query and (2) those chance
variables that are responsive to the decisions that change.}  Next, we
copy the deterministic function associated with each original variable
to its primed counterpart.  Then, we instantiate the decision and
chance variables as described in the query ($r=${\bf take},
$\hat{t}$={\bf idle}, $t=${\bf taken}, $c=${\bf cured}, $r'=${\bf
don't take}, and $\hat{t'}$={\bf idle}).  Finally, we use a standard
Bayesian-network inference method to compute the probability of the
variable(s) of interest ($c'$ in our example).

\begin{figure}   
\begin{center}  
\leavevmode  
\psfig{figure=fperhat.eps,width=3.5in}  
\end{center}  
\caption{The use of canonical form to compute a counterfactual query.
Shaded variables are instantiated.}  
\label{fig:persis} 
\end{figure}

The canonical form influence diagram is a natural representation for
counterfactual reasoning for two reasons.  One, the deterministic
relationships between a responsive chance variable and its parents
remains the same for any choice of $D$.  Two, the instances assumed by
unresponsive variables are unaltered by the decisions.  The ordinary
influence diagram offers neither of these guarantees.

Our approach, described in Heckerman and Shachter (1994), is similar
to that of Balke and Pearl (1994).\nocite{BP94uai} The main difference
between the two approaches is that Balke and Pearl use their
functional model as the base representation, making their approach
less efficient than ours.  Goldszmidt and Darwiche (1994) describe a
graphical language for modeling the evolution of real-world systems
over time.  Although their approach does not explicitly address
counterfactual reasoning, it can be adapted to so do, yielding an
alternative to our approach.


\section{Conclusions} 

We have presented a definition of cause and effect in terms of the
decision-theoretic primitives of act, state of the world, and
consequence determined by act and state of the world, and have shown
how this definition provides a foundation for causal reasoning.  Our
definition departs from the traditional view of causation in that our
causal assertions are made relative to a set of decisions.
Consequently, as we have argued, our definition allows for a more
precise specification of causal relationships.

In addition, we have shown how our definition provides a basis for the
graphical representation of cause.  We have described a special class
of influence diagrams, those in canonical form, and have shown that it
is equally expressive and more efficient than Pearl's
structural-equation model.  Finally, we have shown how influence
diagrams in canonical form, unlike ordinary influence diagrams, can be
used for counterfactual reasoning.


\section*{Acknowledgments}

We thank Jack Breese, Tom Chavez, Max Chickering, Eric Horvitz, Ron
Howard, Christopher Meek, Judea Pearl, Mark Peot, Glenn Shafer, Peter
Spirtes, Patrick Suppes, and anonymous reviewers for useful comments.


\bibliographystyle{theapa} 
%\bibliography{david} 

\begin{thebibliography}{}

\bibitem[\protect\BCAY{Angrist, Imbens, \BBA\ Rubin}{Angrist
  et~al.}{1995}]{AIR95}
Angrist, J., Imbens, G., \BBA\ Rubin, D. \BBOP1995\BBCP.
\newblock \BBOQ Identification of causal effects using instrumental
  variables\BBCQ\
\newblock {\Bem Journal of the American Statistical Association}, in
  press.

\bibitem[\protect\BCAY{Balke \BBA\ Pearl}{Balke \BBA\ Pearl}{1994}]{BP94uai}
Balke, A.\BBACOMMA\  \BBA\ Pearl, J. \BBOP1994\BBCP.
\newblock \BBOQ Probabilistic evaluation of counterfactual queries\BBCQ\
\newblock In {\Bem Proceedings of Tenth Conference on Uncertainty in Artificial
  Intelligence, {\rm Seattle, WA}}, \BPGS\ 46--54. Morgan Kaufmann.

\bibitem[\protect\BCAY{de~Finetti}{de~Finetti}{1937}]{deFinetti37}
de~Finetti, B. \BBOP1937\BBCP.
\newblock \BBOQ La pr\'{e}vision: See lois logiques, ses sources
  subjectives\BBCQ\
\newblock {\Bem Annales de l'Institut Henri Poincar\'{e}}, {\Bem 7}, 1--68.
\newblock Translated in Kyburg and Smokler, 1964.

\bibitem[\protect\BCAY{Ginsberg}{Ginsberg}{1986}]{Ginsberg86}
Ginsberg, M. \BBOP1986\BBCP.
\newblock \BBOQ Counterfactuals\BBCQ\
\newblock {\Bem Artificial Intelligence}, {\Bem 30}, 35--79.

\bibitem[\protect\BCAY{Goldszmidt \BBA\ Darwiche}{Goldszmidt \BBA\
  Darwiche}{1994}]{GD94uai}
Goldszmidt, M.\BBACOMMA\  \BBA\ Darwiche, A. \BBOP1994\BBCP.
\newblock \BBOQ Action networks: {A} framework for reasoning about actions and
  change under uncertainty\BBCQ\
\newblock In {\Bem Proceedings of Tenth Conference on Uncertainty in Artificial
  Intelligence, {\rm Seattle, WA}}, \BPGS\ 136--144. Morgan Kaufmann.

\bibitem[\protect\BCAY{Heckerman}{Heckerman}{1995}]{H95uai}
Heckerman, D. \BBOP1995\BBCP.
\newblock \BBOQ A {Bayesian} approach for learning causal networks\BBCQ\
\newblock In {\Bem Proceedings of Eleventh Conference on Uncertainty in
  Artificial Intelligence, {\rm Montreal, QU}}, \BPGS\ 285--295. Morgan
  Kaufmann.

\bibitem[\protect\BCAY{Heckerman, Breese, \BBA\ Rommelse}{Heckerman
  et~al.}{1994}]{HBR94dx}
Heckerman, D., Breese, J., \BBA\ Rommelse, K. \BBOP1994\BBCP.
\newblock \BBOQ Sequential troubleshooting under uncertainty\BBCQ\
\newblock In {\Bem Proceedings of Fifth International Workshop on Principles of
  Diagnosis, {\rm New Paltz, NY}}, \BPGS\ 121--130.

\bibitem[\protect\BCAY{Heckerman \BBA\ Shachter}{Heckerman \BBA\
  Shachter}{1994}]{HS94uai}
Heckerman, D.\BBACOMMA\  \BBA\ Shachter, R. \BBOP1994\BBCP.
\newblock \BBOQ A decision-based view of causality\BBCQ\
\newblock In {\Bem Proceedings of Tenth Conference on Uncertainty in Artificial
  Intelligence, {\rm Seattle, WA}}, \BPGS\ 302--310. Morgan Kaufmann.

\bibitem[\protect\BCAY{Holland}{Holland}{1986}]{Holland86}
Holland, P. \BBOP1986\BBCP.
\newblock \BBOQ Statistics and causal inference\BBCQ\
\newblock {\Bem Journal of the American Statistical Association}, {\Bem 81},
  945--968.

\bibitem[\protect\BCAY{Howard}{Howard}{1990}]{Howard90}
Howard, R. \BBOP1990\BBCP.
\newblock \BBOQ From influence to relevance to knowledge\BBCQ\
\newblock In Oliver, R.\BBACOMMA\  \BBA\ Smith, J.\BEDS, {\Bem Influence
  Diagrams, Belief Nets, and Decision Analysis}, \BCH~1. Wiley and Sons, New
  York.

\bibitem[\protect\BCAY{Howard \BBA\ Matheson}{Howard \BBA\
  Matheson}{1981}]{Howard81}
Howard, R.\BBACOMMA\  \BBA\ Matheson, J. \BBOP1981\BBCP.
\newblock \BBOQ Influence diagrams\BBCQ\
\newblock In Howard, R.\BBACOMMA\  \BBA\ Matheson, J.\BEDS, {\Bem Readings on
  the Principles and Applications of Decision Analysis}, \lowercase{\BVOL}~II,
  \BPGS\ 721--762. Strategic Decisions Group, Menlo Park, CA.

\bibitem[\protect\BCAY{Lewis}{Lewis}{1973}]{Lewis73cf}
Lewis, D. \BBOP1973\BBCP.
\newblock {\Bem Counterfactuals}.
\newblock Harvard University Press, Cambridge, MA.

\bibitem[\protect\BCAY{Neyman}{Neyman}{1923}]{Neyman23}
Neyman, J. \BBOP1923\BBCP.
\newblock \BBOQ On the application of probability theory to agricultural
  experiments\BBCQ\
\newblock Translated in {\em Statistical Science,} 5:465-480 (1990).

\bibitem[\protect\BCAY{Pearl}{Pearl}{1988}]{Pearl88}
Pearl, J. \BBOP1988\BBCP.
\newblock {\Bem Probabilistic Reasoning in Intelligent Systems: Networks of
  Plausible Inference}.
\newblock Morgan Kaufmann, San Mateo, CA.

\bibitem[\protect\BCAY{Pearl}{Pearl}{1993}]{Pearl93}
Pearl, J. \BBOP1993\BBCP.
\newblock \BBOQ Comment: Graphical models, causality, and intervention\BBCQ\
\newblock {\Bem Statistical Science}, {\Bem 8}, 266--269.

\bibitem[\protect\BCAY{Pearl}{Pearl}{1995}]{Pearl95bm}
Pearl, J. \BBOP1995\BBCP.
\newblock \BBOQ Causal diagrams for empirical research\BBCQ\
\newblock {\Bem Biometrika}, in press.

\bibitem[\protect\BCAY{Pearl \BBA\ Verma}{Pearl \BBA\ Verma}{1991}]{Pearl91}
Pearl, J.\BBACOMMA\  \BBA\ Verma, T. \BBOP1991\BBCP.
\newblock \BBOQ A theory of inferred causation\BBCQ\
\newblock In Allen, J., Fikes, R., \BBA\ Sandewall, E.\BEDS, {\Bem Knowledge
  Representation and Reasoning: Proceedings of the Second International
  Conference}, \BPGS\ 441--452. Morgan Kaufmann, New York.

\bibitem[\protect\BCAY{Robins}{Robins}{1986}]{Robins86}
Robins, J. \BBOP1986\BBCP.
\newblock \BBOQ A new approach to causal interence in mortality studies with
  sustained exposure results\BBCQ\
\newblock {\Bem Mathematical Modelling}, {\Bem 7}, 1393--1512.

\bibitem[\protect\BCAY{Rubin}{Rubin}{1978}]{Rubin78}
Rubin, D. \BBOP1978\BBCP.
\newblock \BBOQ Bayesian inference for causal effects: {The} role of
  randomization\BBCQ\
\newblock {\Bem Annals of Statistics}, {\Bem 6}, 34--58.

\bibitem[\protect\BCAY{Simon}{Simon}{1977}]{Simon77}
Simon, H. \BBOP1977\BBCP.
\newblock {\Bem Modles of Discovery and Other Topics in the Methods of
  Science}.
\newblock D. Reidel, Dordrecht, Holland.

\bibitem[\protect\BCAY{Spirtes, Glymour, \BBA\ Scheines}{Spirtes
  et~al.}{1993}]{Spirtes93}
Spirtes, P., Glymour, C., \BBA\ Scheines, R. \BBOP1993\BBCP.
\newblock {\Bem Causation, Prediction, and Search}.
\newblock Springer-Verlag, New York.

\end{thebibliography}

\end{document} 
