{"ID":2875575,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2509.03548","arxiv_id":"2509.03548","title":"Multilinear and Linear Programs for Partially Identifiable Queries in Quasi-Markovian Structural Causal Models","abstract":"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.","short_abstract":"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...","url_abs":"https://arxiv.org/abs/2509.03548","url_pdf":"https://arxiv.org/pdf/2509.03548v1","authors":"[\"João P. Arroyo\",\"João G. Rodrigues\",\"Daniel Lawand\",\"Denis D. Mauá\",\"Junkyu Lee\",\"Radu Marinescu\",\"Alex Gray\",\"Eduardo R. Laurentino\",\"Fabio G. Cozman\"]","published":"2025-09-02T17:51:34Z","proceeding":"cs.AI","tasks":"[\"cs.AI\"]","methods":"[]","has_code":false}