An Algorithmic Treatment of Causal Unit Selection

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.