{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,30]],"date-time":"2026-07-30T14:14:06Z","timestamp":1785420846755,"version":"3.56.0"},"reference-count":56,"publisher":"MDPI AG","issue":"5","license":[{"start":{"date-parts":[[2026,5,2]],"date-time":"2026-05-02T00:00:00Z","timestamp":1777680000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"ONR","award":["N000142212501"],"award-info":[{"award-number":["N000142212501"]}]},{"award":["N000142212501"],"award-info":[{"award-number":["N000142212501"]}],"id":[{"id":"https:\/\/ror.org\/01awap711","id-type":"ROR","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Entropy"],"abstract":"<jats:p>The problem of optimizing a causal objective function emerged in recent work, where the behavior of objects needs to be expressed in terms of interventional or counterfactual probabilities. A key example is the unit selection problem introduced by Li and Pearl, where the goal is to find the individuals who maximize a benefit function that scores their characteristics (called units) using counterfactual probabilities. Previous work on unit selection focused mainly on this specific objective function and on identifying its value using bounds. We complement this line of work by developing a theory that treats unit selection as a computational problem, assuming a fully specified causal model is available and a more general class of objective functions. At the core of our treatment is a novel reduction that transforms the computation of a broad class of causal objective functions into a classical associational probability on a meta-model called the objective model. Based on this reduction, we propose the first exact algorithm for finding the optimal units by applying Variable Elimination (VE) on the objective model. We then characterize the complexity of causal unit selection, showing that it is NPPP-complete, and that the runtime of VE must be exponential in the constrained treewidth of the objective model, which is larger and denser than the original input model. To address this challenge, we compile the objective model into a special class of tractable arithmetic circuits, allowing the optimal units to be computed in time linear in the circuit size. Finally, we present experiments demonstrating the substantial speedup from the circuit-based method over the VE-based method, and the speedup from the VE-based method over a baseline search method, together with a case study on a real-world ecology problem.<\/jats:p>","DOI":"10.3390\/e28050515","type":"journal-article","created":{"date-parts":[[2026,5,4]],"date-time":"2026-05-04T02:06:21Z","timestamp":1777860381000},"page":"515","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["An Algorithmic Treatment of Causal Unit Selection"],"prefix":"10.3390","volume":"28","author":[{"ORCID":"https:\/\/orcid.org\/0009-0006-1105-9798","authenticated-orcid":false,"given":"Haiying","family":"Huang","sequence":"first","affiliation":[{"name":"Computer Science Department, University of California, Los Angeles (UCLA), Los Angeles, CA 90095, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Adnan","family":"Darwiche","sequence":"additional","affiliation":[{"name":"Computer Science Department, University of California, Los Angeles (UCLA), Los Angeles, CA 90095, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"1968","published-online":{"date-parts":[[2026,5,2]]},"reference":[{"key":"ref_1","unstructured":"Pearl, J. (2000). Causality: Models, Reasoning, and Inference, Cambridge University Press."},{"key":"ref_2","unstructured":"Pearl, J., and Mackenzie, D. (2018). The Book of Why: The New Science of Cause and Effect, Basic Books."},{"key":"ref_3","doi-asserted-by":"crossref","unstructured":"Bareinboim, E., Correa, J.D., Ibeling, D., and Icard, T. (2022). On Pearl\u2019s hierarchy and the foundations of causal inference. Probabilistic and Causal Inference: The Works of Judea Pearl, ACM Books.","DOI":"10.1145\/3501714.3501743"},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"669","DOI":"10.1093\/biomet\/82.4.669","article-title":"Causal diagrams for empirical research","volume":"82","author":"Pearl","year":"1995","journal-title":"Biometrika"},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"266","DOI":"10.1214\/ss\/1177010894","article-title":"[Bayesian analysis in expert systems]: Comment: Graphical models, causality and intervention","volume":"8","author":"Pearl","year":"1993","journal-title":"Stat. Sci."},{"key":"ref_6","doi-asserted-by":"crossref","unstructured":"Spirtes, P., Glymour, C.N., and Scheines, R. (2000). Causation, Prediction, and Search, MIT Press.","DOI":"10.7551\/mitpress\/1754.001.0001"},{"key":"ref_7","unstructured":"Shpitser, I., and Pearl, J. (2006, January 16\u201320). Identification of joint interventional distributions in recursive semi-Markovian causal models. Proceedings of the AAAI, Boston, MA, USA."},{"key":"ref_8","doi-asserted-by":"crossref","unstructured":"Imbens, G.W., and Rubin, D.B. (2015). Causal Inference in Statistics, Social, and Biomedical Sciences, Cambridge University Press.","DOI":"10.1017\/CBO9781139025751"},{"key":"ref_9","unstructured":"Balke, A., and Pearl, J. (1994). Probabilistic Evaluation of Counterfactual Queries. Proceedings of the AAAI, The MIT Press."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"151","DOI":"10.1023\/A:1009602825894","article-title":"An axiomatic characterization of causal counterfactuals","volume":"3","author":"Galles","year":"1998","journal-title":"Found. Sci."},{"key":"ref_11","first-page":"1941","article-title":"Complete Identification Methods for the Causal Hierarchy","volume":"9","author":"Shpitser","year":"2008","journal-title":"J. Mach. Learn. Res."},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"Morgan, S.L., and Winship, C. (2015). Counterfactuals and Causal Inference: Methods and Principles for Social Research, Cambridge University Press.","DOI":"10.1017\/CBO9781107587991"},{"key":"ref_13","unstructured":"Koller, D., and Friedman, N. (2009). Probabilistic Graphical Models\u2014Principles and Techniques, MIT Press."},{"key":"ref_14","unstructured":"Pearl, J. (1989). Probabilistic Reasoning in Intelligent Systems\u2014Networks of Plausible Inference, Morgan Kaufmann. Morgan Kaufmann Series in Representation and Reasoning."},{"key":"ref_15","doi-asserted-by":"crossref","unstructured":"Darwiche, A. (2009). Modeling and Reasoning with Bayesian Networks, Cambridge University Press.","DOI":"10.1017\/CBO9780511811357"},{"key":"ref_16","unstructured":"Peters, J., Janzing, D., and Sch\u00f6lkopf, B. (2017). Elements of Causal Inference: Foundations and Learning Algorithms, MIT Press."},{"key":"ref_17","unstructured":"Balke, A., and Pearl, J. (1995). Counterfactuals and Policy Analysis in Structural Models. Proceedings of the UAI, Morgan Kaufmann."},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"Li, A., and Pearl, J. (2019, January 10\u201316). Unit Selection Based on Counterfactual Logic. Proceedings of the International Joint Conference on Artificial Intelligence, Macao, China.","DOI":"10.24963\/ijcai.2019\/248"},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Li, A., and Pearl, J. (2022). Unit Selection with Causal Diagram. Proceedings of the AAAI, AAAI Press.","DOI":"10.1609\/aaai.v36i5.20519"},{"key":"ref_20","unstructured":"Li, A., and Pearl, J. (2022). Unit Selection with Nonbinary Treatment and Effect. arXiv."},{"key":"ref_21","unstructured":"Li, A., and Pearl, J. (2022). Unit Selection: Case Study and Comparison with A\/B Test Heuristic. arXiv."},{"key":"ref_22","unstructured":"Li, A., Jiang, S., Sun, Y., and Pearl, J. (2022). Unit Selection: Learning Benefit Function from Finite Population Data. arXiv."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"163","DOI":"10.1093\/lpr\/mgx012","article-title":"The Probability of Causation","volume":"16","author":"Dawid","year":"2017","journal-title":"Law Probab. Risk"},{"key":"ref_24","doi-asserted-by":"crossref","unstructured":"Mueller, S., Li, A., and Pearl, J. (2021). Causes of Effects: Learning Individual Responses from Population Data, Department of Computer Science, University of California. Available online: http:\/\/ftp.cs.ucla.edu\/pub\/stat_ser\/r505.pdf.","DOI":"10.24963\/ijcai.2022\/376"},{"key":"ref_25","unstructured":"Li, A., Jiang, S., Sun, Y., and Pearl, J. (2022). Learning Probabilities of Causation from Finite Population Data, Department of Computer Science, University of California. Available online: http:\/\/ftp.cs.ucla.edu\/pub\/stat_ser\/r519.pdf."},{"key":"ref_26","unstructured":"Huang, H., and Darwiche, A. (2023, January 11\u201314). An Algorithm and Complexity Results for Causal Unit Selection. Proceedings of the 2nd Conference on Causal Learning and Reasoning, T\u00fcbingen, Germany."},{"key":"ref_27","doi-asserted-by":"crossref","unstructured":"Huang, H., and Darwiche, A. (2024, January 19\u201321). Causal Unit Selection using Tractable Arithmetic Circuits. Proceedings of the International FLAIRS Conference Proceedings, Sandestin Beach, FL, USA.","DOI":"10.32473\/flairs.37.1.135607"},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"317","DOI":"10.1613\/jair.648","article-title":"Axiomatizing causal reasoning","volume":"12","author":"Halpern","year":"2000","journal-title":"J. Artif. Intell. Res."},{"key":"ref_29","unstructured":"Pearl, J., Glymour, M., and Jewell, N.P. (2016). Causal Inference in Statistics: A Primer, John Wiley & Sons."},{"key":"ref_30","unstructured":"Avin, C., Shpitser, I., and Pearl, J. (2005). Identifiability of Path-Specific Effects. Proceedings of the IJCAI, Morgan Kaufmann."},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1023\/A:1018912507879","article-title":"Probabilities of causation: Bounds and identification","volume":"28","author":"Tian","year":"2000","journal-title":"Ann. Math. Artif. Intell."},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"20170018","DOI":"10.1515\/jci-2017-0018","article-title":"Physical and Metaphysical Counterfactuals: Evaluating Disjunctive Actions","volume":"5","author":"Pearl","year":"2017","journal-title":"J. Causal Inference"},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"399","DOI":"10.1016\/0004-3702(94)90072-8","article-title":"Finding MAPs for belief networks is NP-hard","volume":"68","author":"Shimony","year":"1994","journal-title":"Artif. Intell."},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"101","DOI":"10.1613\/jair.1236","article-title":"Complexity Results and Approximation Strategies for MAP Explanations","volume":"21","author":"Park","year":"2004","journal-title":"J. Artif. Intell. Res. (JAIR)"},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"273","DOI":"10.1016\/0004-3702(94)00092-1","article-title":"On the Hardness of Approximate Reasoning","volume":"82","author":"Roth","year":"1996","journal-title":"Artif. Intell."},{"key":"ref_36","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1016\/S0004-3702(99)00059-4","article-title":"Bucket Elimination: A Unifying Framework for Reasoning","volume":"113","author":"Dechter","year":"1999","journal-title":"Artif. Intell."},{"key":"ref_37","doi-asserted-by":"crossref","unstructured":"Han, Y., Chen, Y., and Darwiche, A. (2023, January 19\u201325). On the complexity of counterfactual reasoning. Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence, Macao, China.","DOI":"10.24963\/ijcai.2023\/630"},{"key":"ref_38","unstructured":"Chen, Y., and Darwiche, A. (2022, January 1\u20135). On the definition and computation of causal treewidth. Proceedings of the Uncertainty in Artificial Intelligence, PMLR, Eindhoven, The Netherlands."},{"key":"ref_39","doi-asserted-by":"crossref","unstructured":"Darwiche, A. (2020). An Advance on Variable Elimination with Applications to Tensor-Based Computation. ECAI 2020, IOS Press.","DOI":"10.3233\/FAIA200391"},{"key":"ref_40","unstructured":"Chavira, M., and Darwiche, A. (August, January 30). Compiling Bayesian Networks with Local Structure. Proceedings of the 19th International Joint Conference on Artificial Intelligence (IJCAI), Edinburgh, Scotland."},{"key":"ref_41","unstructured":"Huber, D., Chen, Y., Antonucci, A., Darwiche, A., and Zaffalon, M. (2023). Tractable bounding of counterfactual queries by knowledge compilation. arXiv."},{"key":"ref_42","doi-asserted-by":"crossref","first-page":"280","DOI":"10.1145\/765568.765570","article-title":"A differential approach to inference in Bayesian networks","volume":"50","author":"Darwiche","year":"2003","journal-title":"J. ACM (JACM)"},{"key":"ref_43","unstructured":"Chan, H., and Darwiche, A. (2006, January 13\u201316). On the Robustness of Most Probable Explanations. Proceedings of the 22nd Conference in Uncertainty in Artificial Intelligence (UAI), Cambridge, MA, USA."},{"key":"ref_44","doi-asserted-by":"crossref","unstructured":"Poon, H., and Domingos, P.M. (2011, January 14\u201317). Sum-Product Networks: A New Deep Architecture. Proceedings of the UAI, Barcelona, Spain.","DOI":"10.1109\/ICCVW.2011.6130310"},{"key":"ref_45","unstructured":"Choi, A., and Darwiche, A. (2017, January 6\u201311). On Relaxing Determinism in Arithmetic Circuits. Proceedings of the Thirty-Fourth International Conference on Machine Learning (ICML), Sydney, Australia."},{"key":"ref_46","first-page":"146","article-title":"Tractable Boolean and Arithmetic Circuits","volume":"Volume 342","author":"Darwiche","year":"2021","journal-title":"Neuro-Symbolic Artificial Intelligence"},{"key":"ref_47","unstructured":"Huang, J., Chavira, M., and Darwiche, A. (2006, January 16\u201320). Solving MAP Exactly by Searching on Compiled Arithmetic Circuits. Proceedings of the AAAI, Boston, MA, USA."},{"key":"ref_48","unstructured":"Pipatsrisawat, K., and Darwiche, A. (2009). A new d-DNNF-based bound computation algorithm for functional E-MAJSAT. Proceedings of the Twenty-First International Joint Conference on Artificial Intelligence, Morgan Kaufmann."},{"key":"ref_49","doi-asserted-by":"crossref","first-page":"191","DOI":"10.1613\/jair.2097","article-title":"The language of search","volume":"29","author":"Huang","year":"2007","journal-title":"J. Artif. Intell. Res."},{"key":"ref_50","unstructured":"Chavira, M., and Darwiche, A. (2007, January 6\u201312). Compiling Bayesian Networks Using Variable Elimination. Proceedings of the 20th International Joint Conference on Artificial Intelligence (IJCAI), Hyderabad, India."},{"key":"ref_51","unstructured":"Darwiche, A. (2004). New advances in compiling CNF to decomposable negation normal form. Proceedings of the European Conference on Artificial Intelligence, IOS Press."},{"key":"ref_52","unstructured":"Choi, Y., Vergari, A., and Van den Broeck, G. (2020). Probabilistic Circuits: A Unifying Framework for Tractable Probabilistic Models, UCLA. Available online: http:\/\/starai.cs.ucla.edu\/papers\/ProbCirc20.pdf."},{"key":"ref_53","unstructured":"Choi, Y., Friedman, T., and Van den Broeck, G. (2022, January 28\u201330). Solving marginal map exactly by probabilistic circuit transformations. Proceedings of the International Conference on Artificial Intelligence and Statistics, PMLR, Virtual."},{"key":"ref_54","unstructured":"Kj\u00e6rulff, U.B. (1990). Triangulation of Graphs-Algorithms Giving Small Total State Space, University of Aalborg."},{"key":"ref_55","doi-asserted-by":"crossref","first-page":"e3956","DOI":"10.1002\/ecs2.3956","article-title":"Causal drivers of climate-mediated coral reef regime shifts","volume":"13","author":"Arif","year":"2022","journal-title":"Ecosphere"},{"key":"ref_56","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1613\/jair.505","article-title":"The computational complexity of probabilistic planning","volume":"9","author":"Littman","year":"1998","journal-title":"J. Artif. Intell. Res."}],"container-title":["Entropy"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1099-4300\/28\/5\/515\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,5,20]],"date-time":"2026-05-20T04:11:42Z","timestamp":1779250302000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1099-4300\/28\/5\/515"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,5,2]]},"references-count":56,"journal-issue":{"issue":"5","published-online":{"date-parts":[[2026,5]]}},"alternative-id":["e28050515"],"URL":"https:\/\/doi.org\/10.3390\/e28050515","relation":{},"ISSN":["1099-4300"],"issn-type":[{"value":"1099-4300","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,5,2]]}}}