# Multilinear and Linear Programs for Partially Identifiable Queries in Quasi-Markovian Structural Causal Models

arXiv: https://arxiv.org/abs/2509.03548 · HTML: https://mlsanity.com/paper/2509.03548/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 7 of its 19 references that are in the map.
- First posted on arXiv 2 Sep 2025.

## Builds on (most cited first, 7 of 7)

- [Probabilities of Causation: Bounds and Identification](https://mlsanity.com/paper/1301.3898/) (2013)
- [Counterfactual Probabilities: Computational Methods, Bounds and Applications](https://mlsanity.com/paper/1302.6784/) (2013)
- [An Automated Approach to Causal Inference in Discrete Settings](https://mlsanity.com/paper/2109.13471/) (2021)
- [Structural Causal Models Are (Solvable by) Credal Networks](https://mlsanity.com/paper/2008.00463/) (2020)
- [A General Method for Deriving Tight Symbolic Bounds on Causal Effects](https://mlsanity.com/paper/2003.10702/) (2020)
- [Efficient Computation of Counterfactual Bounds](https://mlsanity.com/paper/2307.08304/) (2023)
- [Scalable Computation of Causal Bounds](https://mlsanity.com/paper/2308.02709/) (2023)

## Built on by (most cited first, 2 of 2)

- [Bounds and Identification of Joint Probabilities of Potential Outcomes and Observed Variables under Monotonicity Assumptions](https://mlsanity.com/paper/2602.18762/) (2026)
- [Identification and Bounding of Central Moments of Causal Effects Using Marginal Moments Information](https://mlsanity.com/paper/2607.04957/) (2026)

## Abstract (arXiv)

We investigate partially identifiable queries in a class of causal models. We focus on acyclic Structural Causal Models that are quasi-Markovian (that is, each endogenous variable is connected with at most one exogenous confounder). We look into scenarios where endogenous variables are observed (and a distribution over them is known), while exogenous variables are not fully specified. This leads to a representation that is in essence a Bayesian network where the distribution of root variables is not uniquely determined. In such circumstances, it may not be possible to precisely compute a probability value of interest. We thus study the computation of tight probability bounds, a problem that has been solved by multilinear programming in general, and by linear programming when a single confounded component is intervened upon. We present a new algorithm to simplify the construction of such programs by exploiting input probabilities over endogenous variables. For scenarios with a single intervention, we apply column generation to compute a probability bound through a sequence of auxiliary linear integer programs, thus showing that a representation with polynomial cardinality for exogenous variables is possible. Experiments show column generation techniques to be superior to existing methods.