betaFeedback

WorksComputer Science

Probabilities of Causation in Nondeterministic Causal Models

Abstract

We study probabilities of causation in nondeterministic causal models, where mechanisms may remain intrinsically stochastic even after all latent variables are fixed. Focusing on binary treatments and outcomes, we develop a generic identification program that represents observational and interventional data as moment constraints on latent stochastic mechanism types and computes minimal/maximal values of counterfactual quantities via constrained optimization. Within this framework, we derive sharp analytic bounds on the probabilities of causation under several assumptions tailored to nondeterministic models. Resulting identification regions are often more informative than those attainable under deterministic alternatives. We illustrate the practical relevance of these results in a case study on personalized treatment decisions and experiments on semi-synthetic datasets. Our results clarify how classical bounds relate to nondeterministic causal semantics, generalizing previous works and providing a unified route from qualitative structural restrictions to computable partial identification regions.

Introduction

Suppose that variable XX (say, smoking) causes variable YY (say, cancer). How should we evaluate the strength of this relationship? One influential proposal relies on counterfactual quantities known as the probabilities of causation [35]. These answer questions not just about whether smoking and cancer co-occur, or whether randomly assigning people to a smoking group increases their chance of cancer. Probabilities of causation are strictly more informative—telling us, for instance, how likely someone would be to develop cancer had they smoked, given that they did not smoke and do not have cancer. Such counterfactual reasoning represents the topmost rung of Pearl’s ladder of causation [25, 3]. These sorts of inferences are essential for mechanistic understanding and scientific explanation [40, 16], and have become increasingly prevalent in explainable AI [20, 5, 38, 36].

Formulating a rigorous logic of counterfactuals has proven contentious. Classical philosophical accounts, most notably that of Lewis [22], evaluate counterfactuals by comparing the actual world to suitably “close” possible worlds, but leave substantial work to the choice of similarity relation. Modern causal inference instead typically formalizes counterfactuals through potential outcomes [30] or structural causal models [25], where interventions modify a system of structural equations. This approach has itself attracted criticism. Dawid [12], for example, questions the need for counterfactual variables in many causal inference problems and emphasizes the assumptions required to interpret unobserved potential responses. More recently, several authors have sought to define counterfactual semantics directly for probabilistic causal mechanisms. Galhotra and Halpern Galhotra and Halpern [14] develop such a semantics for causal Bayesian networks, while Beckers Beckers [7] relaxes the usual deterministic uniqueness assumptions altogether, yielding probabilistic nondeterministic structural causal models (PNSCMs), as opposed to the standard Pearlian probabilistic deterministic structural causal models (PDSCMs).

Preprint.

PNSCMs have the advantage that they do not require latent variables in order to explain the presence of a probabilistic relationship. In Markovian graphs, the absence of latent variables makes counterfactual identification possible. However, this advantage disappears under latent confounding, which poses nontrivial challenges on any causal semantics. A common strategy in deterministic models is to introduce assumptions such as exogeneity and monotonicity to tighten the range of feasible solutions for counterfactuals, even providing point identification in some cases. Such assumptions can be ill-suited to PNSCMs, since they require extreme probabilities given a complete assignment to a variable’s causal parents.

We study the problem of identifying probabilities of causation when mechanisms are irreducibly stochastic. Specifically, we examine the semi-Markovian case, where latent confounding makes point identification generally impossible. Our main contributions include: (1) a formal statement of the constrained optimization task that presents causal probability bounds as the solution to a generalized nonlinear program; (2) provably sharp analytic bounds that apply under a range of structural assumptions well-suited to nondeterministic models; (3) a case study on personalized treatment decisions; and (4) experimental results on semi-synthetic datasets that confirm the utility of our approach.

Background

Let X∈{x,x′}X \in\{x, x'\} be a direct cause of Y∈{y,y′}Y \in\{y, y'\} in model M\mathcal{M}, where we encode these values as x≡1x \equiv1, x′≡0x' \equiv0 and y≡1y \equiv1, y′≡0y' \equiv0 whenever convenient. Let U∈UU \in\mathcal{U} be a latent variable that is not caused by XX or YY, but which may be a cause of one or both. In the latter case, we say that UU is a latent confounder. The resulting directed acyclic graph (DAG) is presented in Fig. 1. We will refer to observational probabilities such as p(y∣x)p(y \mid x) as L1\mathcal{L}_1 data, to indicate the first rung of Pearl [25]’s ladder of causation. We write p(yx)p(y_x) to denote the probability that Y=yY = y under a hard intervention of the form X←xX \leftarrow x, which assigns value xx to variable XX no matter the latent state uu. This is an L2\mathcal{L}_2 quantity, sometimes but not always identifiable from L1\mathcal{L}_1 data [33]. Our focus in this work is counterfactuals, which correspond to the highest rung of Pearl’s ladder, L3\mathcal{L}_3. Such quantities are encoded in the full model M\mathcal{M}, but are underdetermined by the data D:={p(X,Y),p(Yx),p(Yx′)}\mathcal{D} := \{p(X,Y), p(Y_x), p(Y_{x'})\}. We will generally assume complete knowledge of L1\mathcal{L}_1 and L2\mathcal{L}_2 distributions, as well as strict positivity of all quantities in D\mathcal{D} (including relevant marginals).1 Let M\mathfrak{M} denote the class of admissible models, i.e. fully specified causal models on binary X,YX,Y consistent with the structure X→YX \to Y. We write M(D):={M∈M:M⊨D}\mathfrak{M}(\mathcal{D}) := \{\mathcal{M} \in\mathfrak{M} : \mathcal{M} \models\mathcal{D}\} to denote the set of admissible models compatible with D\mathcal{D}.

Figure 1. DAG for the confounded model M\mathcal{M}. The dashed node is unobserved.

In a seminal article, Tian and Pearl [35] (henceforth TP) define the probability of necessity (PN), the probability of sufficiency (PS), and the probability of necessity and sufficiency (PNS):

PN:=p(yx′∣x,y),PS:=p(yx∣x′,y′),PNS:=p(yx,yx′).\mathrm{PN} := p(y_{x'} \mid x,y), \qquad\mathrm{PS} := p(y_x \mid x',y'), \qquad\mathrm{PNS} := p(y_x,y_{x'}).

To continue with our running example, PN answers the question: if I smoke and have cancer, how likely would I be to not have cancer had I not smoked? Inversely, PS answers the question: if I do not smoke and do not have cancer, how likely would I be to have cancer had I smoked? PNS represents the joint probability of both potential outcomes. Collectively, these three quantities constitute the probabilities of causation. Though these L3\mathcal{L}_3 estimands are not generally point identifiable from L1\mathcal{L}_1 and L2\mathcal{L}_2 data, TP derive a linear program (LP) for computing sharp bounds on each under a range of different assumptions, including exogeneity and monotonicity (formally defined below).

PNSCMs replace deterministic structural equations with conditional probability kernels, allowing stochastic outcomes even given all causal parents [7]. Their counterfactual semantics employ actualized refinement: observed parent–child assignments are preserved whenever the same parental configuration obtains (thereby ensuring consistency), while alternative configurations retain their stochastic mechanisms. Joint counterfactual probabilities are then defined by a product coupling conditional on the actual world, followed by marginalization over worlds.

We refer the reader to [6] for a detailed justification of this semantics and here only sketch the basic idea. PNSCMs are meant to represent models that are causally complete, which means that there are no missing parents of endogenous variables. (This condition is thus stronger than causal sufficiency.) For our model M\mathcal{M}, this means that UU is assumed to be the only latent parent of YY. Conditional on all its parents, any remaining variation in a child variable must be intrinsic, and therefore the counterfactual mechanism consists of the same conditional distributions as the actual one. Since the actual mechanism assigns a unique value – namely the actual one – to the child variable conditional on its actual parents, so does the counterfactual mechanism. For M\mathcal{M}, it follows that XX, YxY_x and Yx′Y_{x'} are mutually independent conditional on U=uU=u, with p(yx∣u)=p(y∣x,u)p(y_x \mid u)=p(y\mid x,u) and p(yx′∣u)=p(y∣x′,u)p(y_{x'}\mid u)=p(y\mid x',u) (see Appx. A.2 for the derivation). With no latent variables, this yields PN=p(y′∣x′)\mathrm{PN}=p(y'\mid x'), PS=p(y∣x)\mathrm{PS}=p(y\mid x), and PNS=p(y∣x) p(y′∣x′)\mathrm{PNS}=p(y\mid x)\,p(y'\mid x'). However, these point-identification results do not extend to models with latent confounding.

An important preliminary result delimits what nondeterminism does and does not buy us.

Proposition 2.1 (Inheritance). The sets of joint distributions over (X,Yx,Yx′)(X,Y_x,Y_{x'}) attainable by PNSCMs and PDSCMs in M\mathcal{M} coincide. Absent additional structural restrictions, this common set is the full probability simplex over {0,1}3\{0,1\}^3.

See Appx. A for all proofs. An immediate corollary of Prop. 2.1 is that any sharp bound on PN, PS, or PNS that depends only on the unrestricted joint law of (X,Yx,Yx′)(X,Y_x,Y_{x'}) carries over unchanged from PDSCMs to PNSCMs. However, stochastic mechanisms allow for stochastic constraints that cannot be formalized using PDSCM semantics. We consider several such constraints below.

A generic identification program

Before introducing specific structural assumptions, we formulate the partial identification problem in a common optimization framework. We begin by reparameterizing the model with separate variables for each source of latent influence:

A(U):=p(x∣U)⏟treatment propensity,B(U):=p(y∣x,U),C(U):=p(y∣x′,U)⏟stochastic response variables\underbrace{A(U):=p(x\mid U)}_{\text{treatment propensity}},\qquad\underbrace{B(U):=p(y\mid x,U),\quad C(U):=p(y\mid x',U)}_{\text{stochastic response variables}}

This parameterization works because all observational, interventional, and counterfactual quantities considered below depend on the latent state uu only through the triple (A(u),B(u),C(u))(A(u),B(u),C(u)). Redrawing our DAG with potential outcome variables, we see that AA, BB and CC represent the three channels through which latent information flows (see Figure 2). Since these define an equivalence class over latent mechanisms, we henceforth replace the original UU with its canonical representation U:=(A,B,C)∈[0,1]3U:=(A,B,C)\in[0,1]^3, with corresponding latent law μ\mu.

Modified DAG, replacing Y with potential outcomes and introducing latent nodes for treatment propensity A and stochastic response variables B, C

Figure 2. Modified DAG, replacing YY with potential outcomes (shaded) and introducing latent nodes (dashed) for treatment propensity AA and stochastic response variables B,CB,C.

For a fixed collection of L1,L2\mathcal{L}_1,\mathcal{L}_2 distributions D\mathcal{D}, compatibility imposes five generalized moment constraints on μ\mu, which we separate into observational and interventional components:

p(x)=∫a dμp(yx)=∫b dμp(x,y)=∫ab dμp(yx′)=∫c dμp(x′,y)=∫(1−a)c dμ\begin{aligned} p(x)&=\int a\,d\mu& p(y_x)&=\int b\,d\mu\\ p(x,y)&=\int ab\,d\mu& p(y_{x'})&=\int c\,d\mu\\ p(x',y)&=\int(1-a)c\,d\mu&& \end{aligned}

Together with ∫dμ=1\int d\mu=1, these constraints characterize the latent laws compatible with D\mathcal{D}, thereby defining M(D)\mathcal{M}(\mathcal{D}).

Next, we define target estimands in terms of our latent variables, observing that each probability of causation is a linear functional of μ\mu (for an explicit derivation, see Appx. A.2):

qPN(a,b,c):=ab(1−c)p(x,y),qPS(a,b,c):=(1−a)b(1−c)p(x′,y′),qPNS(a,b,c):=b(1−c).q_{\mathrm{PN}}(a,b,c):=\frac{ab(1-c)}{p(x,y)},\qquad q_{\mathrm{PS}}(a,b,c):=\frac{(1-a)b(1-c)}{p(x',y')},\qquad q_{\mathrm{PNS}}(a,b,c):=b(1-c).

Let P([0,1]3)\mathcal{P}([0,1]^3) denote the set of Borel probability measures on the three-dimensional unit cube. Let C\mathcal{C} denote some additional structural restriction on the canonical latent law, e.g. the exogeneity and monotonicity conditions of TP. Then for Q∈{PN,PS,PNS}Q \in\{\mathrm{PN},\mathrm{PS},\mathrm{PNS}\}, the generic identification task is:

min⁡/max⁡μ∈P([0,1]3)∫qQ dμ,subject toobs,int, μ⊨C.(1)\underset{\mu\in\mathcal{P}([0,1]^3)}{\operatorname{min}/\operatorname{max}}\quad\int q_Q \,d\mu,\qquad\text{subject to}\quad\mathbf{obs},\mathbf{int},\ \mu\models\mathcal{C}. \tag*{(1)}

Observational and interventional distributions therefore determine a generalized moment fiber, while extra assumptions enter through constraint(s) C\mathcal{C}. We say that bounds are sharp under C\mathcal{C} if endpoints equal the min/max of the corresponding QQ over all models compatible with D\mathcal{D} that satisfy C\mathcal{C}.

This constrained optimization task is closely related to the LP of TP—itself adapted from prior work by Balke and Pearl [1]—who take the latent state to be the deterministic Boolean counterfactual type UTP:=(X,Yx,Yx′)∈{0,1}3U_{\mathrm{TP}} := (X,Y_x,Y_{x'}) \in\{0,1\}^3 and optimize directly over the eight cell probabilities pijk:=p(X=i,Yx=j,Yx′=k)p_{ijk} := p(X=i,Y_x=j,Y_{x'}=k). Both the constraints and objectives are then linear in pijkp_{ijk}, yielding a finite LP. In the present setting, U=(A,B,C)U=(A,B,C) instead indexes stochastic mechanisms. A single latent type may induce probability on several Boolean counterfactual configurations, with pijk=∫ai(1−a)1−ibj(1−b)1−jck(1−c)1−k dμp_{ijk} = \int a^i(1-a)^{1-i}b^j(1-b)^{1-j}c^k(1-c)^{1-k}\,d\mu. Absent further restrictions, the inheritance result of Prop. 2.1 implies that both formulations generate the same feasible binary counterfactual region and therefore the same assumption-free bounds. The distinction only becomes clear once restrictions C\mathcal{C} are imposed on latent mechanisms.

Although (opt) is formally an optimization over probability measures, many structural assumptions reduce it exactly to a finite-dimensional problem. Call a constraint set C\mathcal{C} finitely reducible for the present identification task if there exists some finite KK such that every feasible value of QQ admits a compatible atomic law μ=∑i=1Kπiδ(ai,bi,ci)\mu=\sum_{i=1}^{K}\pi_i\delta_{(a_i,b_i,c_i)}, where ∀i:πi≥0\forall i:\pi_i\ge0 and ∑iπi=1\sum_i\pi_i=1. Under such a representation, all integrals are replaced with summations over simplex weights πi\pi_i. This property holds, in particular, for finite collections of support restrictions and generalized moment constraints. Below, we focus on assumptions that are natural for nondeterministic causal models and finitely reducible w.r.t. (opt).

Mechanism Uncertainty

In this section, we consider a range of structural assumptions on the causal mechanisms for X∣UX\mid U and Y∣X,UY\mid X,U. Each assumption constrains the support of our latent variables A,B,CA,B,C, leading to sharp bounds on the probabilities of causation. All proofs are deferred to Appx. A.

Margin condition

References

  1. [1]Alexander Balke and Judea Pearl. Counterfactual probabilities: Computational methods, bounds and applications. In Uncertainty in Artificial Intelligence, pages 46–54, 1994.arxiv.org/abs/1302.6784
  2. [2]Alexander Balke and Judea Pearl. Bounds on treatment effects from studies with imperfect compliance. Journal of the American Statistical Association, 92(439):1171–1176, 1997.DOI
  3. [3]Elias Bareinboim, Juan D. Correa, Duligur Ibeling, and Thomas Icard. On Pearl’s Hierarchy and the Foundations of Causal Inference, page 507–556. 2022.DOI
  4. [4]Barry Becker and Ronny Kohavi. Adult. UCI Machine Learning Repository, 1996. URL https://archive.ics.uci.edu/dataset/2/adult.
  5. [5]Sander Beckers. Causal explanations and XAI. In Proceedings of the First Conference on Causal Learning and Reasoning, pages 90–109, 2022.arxiv.org/abs/2201.13169
  6. [6]Sander Beckers. Causal counterfactuals reconsidered, 2025. arxiv.org/pdf/2512.12804.arxiv.org/abs/2512.12804
  7. [7]Sander Beckers. Nondeterministic causal models. In Fourth Conference on Causal Learning and Reasoning, 2025.arxiv.org/abs/2405.14001
  8. [8]Sander Beckers, Hana Chockler, and Joseph Y. Halpern. Quantifying harm. In Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence (IJCAI-23), pages 363–371, 2023. doi: 10.24963/ijcai.2023/41.DOI
  9. [9]Sander Beckers, Hana Chockler, and Joseph Y. Halpern. A causal analysis of harm. Minds and Machines, 34:34, 2024. doi: 10.1007/s11023-024-09689-7.DOI
  10. [10]Sander Beckers, Hana Chockler, and Joseph Y. Halpern. Quantifying harm (extended version), 2026. arXiv:2209.15111.
  11. [11]Timothy G. Conley, Christian B. Hansen, and Peter E. Rossi. Plausibly exogenous. The Review of Economics and Statistics, 94(1):260–272, 2012.
  12. [12]A. Philip Dawid. Causal inference without counterfactuals. Journal of the American Statistical Association, 95(450):407–424, 2000. doi: 10.1080/01621459.2000.10474210.DOI
  13. [13]A. Philip Dawid and Stephen Senn. Personalised decision-making without counterfactuals. Observational Studies, 2025. To appear. arXiv:2301.11976.arxiv.org/abs/2301.11976
  14. [14]Sainyam Galhotra and Joseph Y. Halpern. Intervention and conditioning in causal Bayesian networks. In Advances in Neural Information Processing Systems, volume 37, pages 89019–89041, 2024.arxiv.org/abs/2405.14728
  15. [15]Sandeep K. Gupta. Intention-to-treat concept: A review. Perspectives in Clinical Research, 2(3):109–112, 2011.DOI
  16. [16]Joseph Y. Halpern and Judea Pearl. Causes and explanations: A structural-model approach. Part II: Explanations. The British Journal for the Philosophy of Science, 56(4):889–911, 2005.
  17. [17]Miguel A. Hernan and James M. Robins. Causal Inference: What If. CRC Press, Boca Raton, 2025.
  18. [18]G. W. Imbens and D. B. Rubin. Causal Inference in Statistics, Social, and Biomedical Sciences: An Introduction. Cambridge University Press, 2015.
  19. [19]Ziwei Jiang, Lai Wei, and Murat Kocaoglu. Approximate causal effect identification under weak confounding. In Proceedings of the 40th International Conference on Machine Learning, 2023.arxiv.org/abs/2306.13242
  20. [20]Amir-Hossein Karimi, Bernhard Schölkopf, and Isabel Valera. Algorithmic recourse: from counterfactual explanations to interventions. In Proceedings of the 2021 ACM Conference on Fairness, Accountability, and Transparency, pages 353–362, 2021.arxiv.org/abs/2002.06278
  21. [21]Jessica Lally, Milad Kazemi, Nicola Paoletti, David Watson, and Sander Beckers. Robust counterfactual policy optimisation via nondeterministic causal models. In UAI 2026 Workshop on Causality for Decision Making, 2026.arxiv.org/abs/2608.02893
  22. [22]David Lewis. Counterfactuals. Blackwell, Oxford, 1973.
  23. [23]Scott Mueller and Judea Pearl. Personalized decision making – a conceptual introduction. Journal of Causal Inference, 11(1):20220050, 2023.arxiv.org/abs/2208.09558
  24. [24]Judea Pearl. Probabilities of causation: Three counterfactual interpretations and their identification. Synthese, 121(1):93–149, 1999.
  25. [25]Judea Pearl. Causality. Cambridge University Press, New York, 2009.
  26. [26]Roland R. Ramsahai. Causal bounds and observable constraints for non-deterministic models. J. Mach. Learn. Res., 13(29):829–848, 2012.
  27. [27]Jonathan G. Richens, Rory Beard, and Daniel H. Thompson. Counterfactual harm. In Advances in Neural Information Processing Systems, volume 35, 2022.
  28. [28]James M. Robins and Sander Greenland. The probability of causation under a stochastic model for individual risk. Biometrics, 45 4:1125–1138, 1989.pubmed.ncbi.nlm.nih.gov/2611320
  29. [29]Paul R. Rosenbaum and Donald B. Rubin. The central role of the propensity score in observational studies for causal effects. Biometrika, 70(1):41–55, 1983.
  30. [30]Donald B. Rubin. Estimating causal effects of treatments in randomized and nonrandomized studies. Journal of Educational Psychology, 66(5):688–701, 1974.DOI
  31. [32]Aaron L. Sarvet and Mats J. Stensrud. Perspectives on “harm” in personalized medicine. American Journal of Epidemiology, 194(6):1743–1748, 2025.
  32. [33]Ilya Shpitser and Judea Pearl. Complete identification methods for the causal hierarchy. Journal of Machine Learning Research, 9(64):1941–1979, 2008.
  33. [34]Ricardo Silva and Robin Evans. Causal inference through a witness protection program. Journal of Machine Learning Research, 17(56):1–53, 2016.
  34. [35]Jin Tian and Judea Pearl. Probabilities of causation: Bounds and identification. Annals of Mathematics and Artificial Intelligence, 28(1):287–313, 2000.arxiv.org/abs/1301.3898
  35. [36]Sahil Verma, Varich Boonsanong, Minh Hoang, Keegan Hines, John Dickerson, and Chirag Shah. Counterfactual explanations and algorithmic recourses for machine learning: A review. ACM Comput. Surv., 56 (12), 2024.arxiv.org/abs/2010.10596
  36. [37]Amiram D. Vinokur, Richard H. Price, and Yaacov Schul. Impact of the jobs intervention on unemployed workers varying in risk for depression. American Journal of Community Psychology, 23(1):39–74, 1995.
  37. [38]David S. Watson, Limor Gultchin, Ankur Taly, and Luciano Floridi. Local explanations via necessity and sufficiency: Unifying theory and practice. Minds and Machines, 32(1):185–218, 2022.
  38. [39]David S. Watson, Jordan Penn, Lee M. Gunderson, Gecia Bravo-Hermsdorff, Afsaneh Mastouri, and Ricardo Silva. Bounding causal effects with leaky instruments. In Proceedings of the 40th Conference on Uncertainty in Artificial Intelligence, 2024.arxiv.org/abs/2404.04446
  39. [40]James Woodward. Making Things Happen: A Theory of Causal Explanation. Oxford University Press, Oxford, 2003.

Paper details

vlnc:W_dcba6qtt
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 3

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents