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 $\text{NP}^\text{PP}$-complete but is $\text{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.

翻译：单位选择问题的目的是根据观察和干预数据确定最有可能在受到刺激时表现出理想行为模式的物体,即所谓的单位(例如,客户即将发作,但如果鼓励的话,就会改变心意)。 具有反事实客观功能的单位选择是最近才引入的,因为根据观察和干预数据,现有工作的重点是约束特定类别的客观功能,称为效益功能,假设没有完全指定的模型来评估这些功能。我们提出第一个精确的算法,以寻找符合广泛因果客观功能类别和完全指定的结构性因果模型的最佳单位。 我们显示,在这一目标功能类别下选择的单位是$\text{NPZ{text{PP}-完整的,但当单位变量与SCM中的所有外源变量相对应时,则$\text{NP}$是完整的。 我们还为我们拟议的算法提供了基于树线的复杂度界限,同时将它与众所周知的后台(MAP)推断法值联系起来。</s>