# An Algorithm and Complexity Results for Causal Unit Selection

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 39 references that are in the map.
- First posted on arXiv 28 Feb 2023.

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

- [Probabilities of Causation: Bounds and Identification](https://mlsanity.com/paper/1301.3898/) (2013)
- [Causes of Effects: Learning individual responses from population data](https://mlsanity.com/paper/2104.13730/) (2021)
- [Unit Selection with Causal Diagram](https://mlsanity.com/paper/2109.07556/) (2021)
- [Counterfactuals and Policy Analysis in Structural Models](https://mlsanity.com/paper/1302.4929/) (2013)
- [Causal Inference Using Tractable Circuits](https://mlsanity.com/paper/2202.02891/) (2022)
- [Unit Selection with Nonbinary Treatment and Effect](https://mlsanity.com/paper/2208.09569/) (2022)
- [An Advance on Variable Elimination with Applications to Tensor-Based Computation](https://mlsanity.com/paper/2002.09320/) (2020)
- [On the Complexity of Counterfactual Reasoning](https://mlsanity.com/paper/2211.13447/) (2022)
- [Unit Selection: Learning Benefit Function from Finite Population Data](https://mlsanity.com/paper/2210.08203/) (2022)
- [Unit Selection: Case Study and Comparison with A/B Test Heuristic](https://mlsanity.com/paper/2210.05030/) (2022)

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

- [Causal Unit Selection using Tractable Arithmetic Circuits](https://mlsanity.com/paper/2404.06681/) (2024)

## Abstract (arXiv)

The unit selection problem aims to identify objects, called units, that are most likely to exhibit a desired mode of behavior when subjected to stimuli (e.g., customers who are about to churn but would change their mind if encouraged). Unit selection with counterfactual objective functions was introduced relatively recently with existing work focusing on bounding a specific class of objective functions, called the benefit functions, based on observational and interventional data -- assuming a fully specified model is not available to evaluate these functions. We complement this line of work by proposing the first exact algorithm for finding optimal units given a broad class of causal objective functions and a fully specified structural causal model (SCM). We show that unit selection under this class of objective functions is NPPP-complete but is NP-complete when unit variables correspond to all exogenous variables in the SCM. We also provide treewidth-based complexity bounds on our proposed algorithm while relating it to a well-known algorithm for Maximum a Posteriori (MAP) inference.