Paper deep dive

Agent Incentives: A Causal Perspective

Tom Everitt, Ryan Carey, Eric D. Langlois, Pedro A. Ortega, Shane Legg

Year: 2021Venue: arXiv preprintArea: Formal/TheoreticalType: TheoreticalEmbeddings: 69

Intelligence

Status: succeeded | Model: google/gemini-3.1-flash-lite-preview | Prompt: intel-v1 | Confidence: 96%

Last extracted: 3/12/2026, 7:40:29 PM

Summary

The paper introduces a formal framework for analyzing agent incentives in AI systems using causal influence diagrams (CIDs) and structural causal influence models (SCIMs). It provides sound and complete graphical criteria for Value of Information (VoI), Value of Control (VoC), Response Incentives (RI), and Instrumental Control Incentives (ICI), offering tools to evaluate AI safety and fairness.

Entities (6)

Causal Influence Diagram · framework · 100%Instrumental Control Incentive · incentive-concept · 100%Response Incentive · incentive-concept · 100%Structural Causal Influence Model · model · 100%Value of Control · incentive-concept · 100%Value of Information · incentive-concept · 100%

Relation Signals (3)

SCIM → combines → Influence Diagram

confidence 95% · This can be formalised as the structural causal influence model (SCIM)... a hybrid of the influence diagram and the SCM.

Causal Influence Diagram → supports → Incentive Analysis

confidence 95% · We present a framework for analysing agent incentives using causal influence diagrams.

Response Incentive → indicates → Counterfactual Unfairness

confidence 90% · A response incentive on a sensitive attribute indicates that counterfactual unfairness is incentivised

Cypher Suggestions (0)

No Cypher suggestions yet.

Abstract

Abstract:We present a framework for analysing agent incentives using causal influence diagrams. We establish that a well-known criterion for value of information is complete. We propose a new graphical criterion for value of control, establishing its soundness and completeness. We also introduce two new concepts for incentive analysis: response incentives indicate which changes in the environment affect an optimal decision, while instrumental control incentives establish whether an agent can influence its utility via a variable X. For both new concepts, we provide sound and complete graphical criteria. We show by example how these results can help with evaluating the safety and fairness of an AI system.

PDF

Open source PDF →Open local PDF →

Trouble viewing inline? Open PDF directly →

Full Text

69,041 characters extracted from source content.

Expand or collapse full text

arXiv:2102.01685v2 [cs.AI] 15 Mar 2021 Agent Incentives: A Causal Perspective Tom Everitt, *1 Ryan Carey, *2 Eric D. Langlois, *1,3,4 Pedro A. Ortega, 1 Shane Legg 1 1 DeepMind, 2 University of Oxford, 3 University of Toronto, 4 Vector Institute, * Equal Contribution tomeveritt@google.com, ry.duff@gmail.com, edl@cs.toronto.edu, pedroortega@google.com Abstract We present a framework for analysing agent incentives using causal influence diagrams. We establish that a well-known criterion for value of information is complete. We propose a new graphical criterion for value of control, establishing its soundness and completeness. We also introduce two new concepts for incentive analysis: response incentives indicate which changes in the environment affect an optimal deci- sion, while instrumental control incentives establish whether an agent can influence its utility via a variable X. For both new concepts, we provide sound and complete graphical cri- teria. We show by example how these results can help with evaluating the safety and fairness of an AI system. Introduction A recurring question in AI research is how to choose an objec- tive to induce safe and fair behaviour (O’Neil 2016; Russell 2019). In a given setup, will an optimal policy depend on a sensitive attribute, or seek to influence an important variable? For example, consider the following two incentive design problems, to which we will return throughout the paper: Example 1(Grade prediction).To decide which applicants to admit, a university uses a model to predict the grades of new students. The university would like the system to predict accurately, without treating students differently based on their gender or race (see Figure 1a). Example 2(Content recommendation).An AI algorithm has the task of recommending a series of posts to a user. The designers want the algorithm to present content adapted to each user’s interests to optimize clicks. However, they do not want the algorithm to use polarising content to manipulate the user into clicking more predictably (Figure 1b). ContributionsThis paper provides a common language for incentive analysis, based on influence diagrams (Howard 1990) and causal models (Pearl 2009). Traditionally, influ- ence diagrams have been used to help decision-makers make better decisions. Here, we invert the perspective, and use the diagrams to understand and predict the behaviour of machine learning systems trained to optimize an objective in a given environment. To facilitate this analysis, we prove a number of relevant theorems and introduce two new concepts: •Value of Information(VoI): First defined by Howard (1966), a graphical criterion for detecting positive VoI in influence diagrams were proposed and proven sound by Fagiuoli and Zaffalon (1998), Lauritzen and Nilsson (2001), and Shachter (2016). Here we offer the first correct completeness proof, showing that the graphical criterion is unique and cannot be further improved upon. •Value of Control(VoC): Defined by Shachter (1986), Math- eson (1990), and Shachter and Heckerman (2010), an in- complete graphical criterion was discussed by Shachter (1986). Here we provide a complete graphical criterion, along with both soundness and completeness proofs. •Instrumental Control incentive(ICI): We propose a refine- ment of VoC to nodes the agent can influence with its de- cision. Conceptually, this is a hybrid of VoC andrespon- siveness(Shachter 2016). We offer a formal definition of instrumental control incentives based on nested counterfac- tuals, and establish a sound and complete graphical crite- rion. •Response incentive(RI): Which changes in the environ- ment does an optimal policy respond to? This is a central problem in fairness and AI safety (e.g. Kusner et al. 2017; Hadfield-Menell et al. 2017). Again, we give a formal def- inition, and a sound and complete graphical criterion. Our analysis focuses on influence diagrams with a single- decision. This single-decision setting is adequate to model supervised learning, (contextual) bandits, and the choiceof a policy in an MDP. Previous work has also discussed ways to transform a multi-decision setting into a single-decisionset- ting by imputing policies to later decisions (Shachter 2016). ApplicabilityThis paper combines material from two preprints (Everitt et al. 2019c; Carey et al. 2020). Since the release of these preprints, the unified language of causal influ- ence diagrams have already aided in the understanding of in- centive problems such as an agent’s redirectability, ambition, tendency to tamper with reward, and other properties (Arm- strong et al. 2020; Holtman 2020; Cohen, Vellambi, and Hut- ter 2020; Everitt et al. 2019a,b; Langlois and Everitt 2021). Race High school Education Grade Predicted grade Gender Accuracy (a) Fairness example: grade prediction Posts to show Model of original opinions Original user opinions Clicks Influenced user opinions (b) Safety example: content recommendation structurenode decision node utility node Figure 1: Two examples of decision problems represented as causal influence diagrams. In a) a predictor at a hypothetical university aims to estimate a student’s grade, using as inputs their gender and the high school they attended. We ask whether the predictor is incentivised to behave in a discriminatory manner with respect to the students’ gender and race. In this hypothetical cohort of students, performance is assumed to be a function of the quality of the high-school education they received. A student’s high-school is assumed to be impacted by their race, and can affect the quality of their education. Gender, however, is assumed not to have an effect. In b) the goal of a content recommendation system is to choose posts that will maximise the user’s click rate. However, the system’s designers prefer the system notto manipulate the user’s opinions in order to obtain more clicks. Setup To analyse agents’ incentives, we will need a graphical frame- work with the causal properties of a structural causal model and the node categories of an influence diagram. This sec- tion will define such a model after reviewing structural causal models and influence diagrams. Structural Causal Models Structural causal models (SCMs) Pearl (2009) are a type of causal model where all randomness is consigned toexoge- nousvariables, while deterministicstructuralfunctions re- late theendogenousvariables to each other and to the ex- ogenous ones. As demonstrated by Pearl (2009), thisstruc- turalapproach has significant benefits over traditional causal Bayesian networks for analysing (nested) counterfactuals and “individual-level” effects. Definition 1(Structural causal model; Pearl 2009, Chapter 7).Astructural causal model(with independent errors) is a tuplehE,V,F, Pi, whereEis a set of exogenous variables; Vis a set of endogenous variables; andF=f V V∈V is a collection of functions, one for eachV. Each function f V : dom(Pa V ∪E V )→dom(V)specifies the value of Vin terms of the values of the corresponding exogenous variableE V and endogenous parentsPa V ⊂V, where these functional dependencies are acyclic. The domain of a variableVisdom(V)and for a set of variables, dom(W) := × W∈W dom(W). The uncertainty is encoded through a probability distributionP(ε)such that the exogenous variables are mutually independent. For example, Figure 2b shows an SCM that models how posts(D) can influence a user’sopinion(O) andclicks(U).x The exogenous variablesEof an SCM represent factors that are not modelled. For any valueE=εof the exogenous variables, the value of any set of variablesW⊆Vis given by recursive application of the structural functionsFand is denoted byW(ε). Together with the distributionP(ε) over exogenous variables, this induces a joint distribution Pr(W=w) = ∑ ε|W(ε)=w P(ε). SCMs modelcausal interventionsthat set variables to par- ticular values. These are defined via submodels: Definition 2(Submodel; Pearl 2009, Chapter 7).LetM= hE,V,F, Pibe an SCM,Xa set of variables inV, andxa particular realization ofX. The submodelM x represents the effects of aninterventiondo(X=x), and is formally defined as the SCMhE,V,F x , Piwhere F x =f V |V /∈X∪X=x. That is to say, the original functional relationships ofX∈Xare replaced with the con- stant functionsX=x. More generally, asoft interventionon a variableXin an SCMMreplacesf X with a functiong X : dom(Pa X ∪ E X )→dom(X)(Eberhardt and Scheines 2007; Tian and Pearl 2001). The probability distributionPr(W g X)on any W⊆Vis defined as the value ofPr(W)in the submodel M g XwhereM g XisMmodified by replacingf X withg X . IfWis a variable in an SCMM, thenW x refers to the same variable in the submodelM x and is called apotential response variable. In Figure 2b, the random variableOrep- resents user opinion under “default” circumstances whileO d in Figure 2c represents the user’s opinion given an interven- tiondo(D=d)on the content posted. Note also how the intervention onDsevers the link fromε D todin Figure 2c, as the intervention onDoverrides the causal effect fromD’s parents. Throughout this paper we use subscripts to indicate submodels or interventions, and superscripts for indexing. More elaborate hypotheticals can be described with a nested counterfactual, in which the intervention is itselfa po- tential response variable. In Figure 2c, theclickprobabilityU depends on both the chosenpostsDand the useropinionO, which is in turn also influenced byD. The nested potential response variableU O d , defined byU O d (ε) : =U o (ε)where o=O d (ε), represents the probability that a user clicks on a “default” postDgiven that their opinion has been influenced by a hypothetical postd. In other words, the effect of the in- terventiondo(D=d)is propagated toUonly throughO. Causal Influence Diagrams Influence diagrams are graphical models with special deci- sion and utility nodes, developed to model decision making problems (Howard 1990; Lauritzen and Nilsson 2001). Influ- ence diagrams do not in general have causal semantics, al- though some causal structure can be inferred (Heckerman and Shachter 1995). We will assume that the edges of the D O U E D E O E U Opinion O=f O (D,E O ) Clicks U=f U (D, O,E U ) (a) SCIM D O U E D E O E U Posts D=π(E D ) Opinion O=f O (D,E O ) Clicks U=f U (D, O,E U ) (b) SCM D O U E D E O E U d O d U O d Posts d=apolitical Opinion O d =f O (d,E O ) Clicks U O d =f U (D, O d ,E U ) (c) SCM with nested counterfactual exogenous node structuralnode intervened node decision node utility node Figure 2: An example of a SCIM and interventions. In the SCIM,either political or apolitical postsDare displayed. These affect the user’s opinionO.DandOinfluence the user’s clicksU(a). Given a policy, the SCIM becomes a SCM (b). Interventions and counterfactuals may be defined in terms of this SCM. For example, the nested counterfactualU O d represents the number of clicks if the user has the opinions that they would arrive at,after viewing apolitical content (c). influence diagram reflect the causal structure of the environ- ment, so we use the term “Causal Influence Diagram”. Definition 3(Causal influence diagram).Acausal influence diagram(CID) is a directed acyclic graphGwhere the vertex setVis partitioned intostructure nodesX,decision nodes D, andutility nodesU. Utility nodes have no children. We usePa V andDesc V to denote the parents and descen- dants of a nodeV∈V. The parents of the decision,Pa D , are also called observations. An edge from nodeVto nodeYis denotedV→Y. Edges into decisions are called information links, as they indicate what information is available at the time of the decision. A directed path (of length at least zero) is denotedV99KY. For sets of variables,V99KYmeans thatV99KYholds for someV∈V,Y∈Y. Structural Causal Influence Models For our new incentive concepts, we define a hybrid of the influence diagram and the SCM. Such a model, originally proposed by Dawid (2002), has structure and utility nodes with associated functions, exogenous variables with an asso- ciated probability distributions, and decision nodes, without any function at all, until one is selected by an agent. 1 This can be formalised as thestructural causal influence model (SCIM, pronounced ‘skim’). Definition 4(Structural causal influence model).Astruc- tural causal influence model(SCIM) is a tupleM= hG,E,F, Piwhere: •Gis a CID with finite-domain variablesV(partitioned into X,D, andU) where utility variable domains are a subset ofR. We say thatMiscompatible withG. •E=E V V∈V is a set of finite-domainexogenous vari- ables, one for each endogenous variable. •F=f V V∈V is a set ofstructural functions f V : dom(Pa V ∪E V )→dom(V)that specify how each non-decision endogenous variable depends on its par- ents inGand its associated exogenous variable. 1 Dawid called this a “functional influence diagram”. We favour the term SCIM, because the corresponding term SCM is more preva- lent than “functional model”. •Pis a probability distribution forEsuch that the individual exogenous variablesE V are mutually independent. We will restrict our attention to single-decision settings withD=D. An example of such a SCIM for the con- tent recommendation example is shown in Figure 2a. In single-decision SCIMs, the decision-making task is to max- imize expected utility by selecting a decisiond∈dom(D) based on the observationsPa D . More formally, the task is to select a structural function forDin the form of apol- icyπ: dom(Pa D ∪ E D )→dom(D). The exogenous variableE D provides randomness to allow the policy to be a stochastic function of its endogenous parentsPa D . The specification of a policy turns a SCIMMinto an SCM M π :=hE,V,F∪π, Pi, see Figure 2b. With the result- ing SCM, the standard definitions of causal interventions ap- ply. Note that what determines whether a node is observed or not at the time of decision-making is whether the node is a parent of the decision. Commonly, some structure nodes represent latent variables that are unobserved. We usePr π andE π to denote probabilities and expecta- tions with respect toM π . For a set of variablesXnot in Desc D ,Pr π (x)is independent ofπand we simply write Pr(x). Anoptimal policyfor a SCIM is defined as any policyπthat maximisesE π [U], whereU : = ∑ U∈U U. A potential responseU x is defined asU x : = ∑ U∈U U x . Materiality Next, we review a characterization of which observations arematerialfor optimal performance, as this will be a fundamental building block for most of our theory. 2 Definition 5(Materiality; Shachter 2016).For any given SCIMM, letV ∗ (M) = max π E π [U]be the maximum at- tainable utility inM, and letM X6→D beMmodified by removing any information linkX→D. The observation X∈Pa D ismaterialifV ∗ (M X6→D )<V ∗ (M). Nodes may often be identified as immaterial based on the graphical structure alone (Fagiuoli and Zaffalon 1998; 2 In contrast to subsequent sections, the results in this section and the VoI section do not require the influence diagrams to be causal. Lauritzen and Nilsson 2001; Shachter 2016). The graphical criterion uses uses the notion of d-separation. Definition 6(d-separation; Verma and Pearl 1988).A pathp is said to be d-separated by a set of nodesZif and only if: 1.pcontains a colliderX→W←Y, such that the middle nodeWis not inZand no descendants ofWare inZ, or 2.pcontains a chainX→W→Yor forkX←W→Y whereWis inZ, or 3. one or both of the endpoints ofpis inZ. A setZis said to d-separateXfromY, written (X⊥Y|Z)if and only ifZd-separates every path from a node inXto a node inY. Sets that are not d-separated are called d-connected. According to the graphical criterion of Fagiuoli and Zaf- falon (1998), an observation cannot provide useful informa- tion if it is d-separated from utility, conditional on otherob- servations. This condition is called nonrequisiteness. Definition 7(Nonrequisite observation; Lauritzen and Nils- son 2001).LetU D :=U∩Desc D be the utility nodes down- stream ofD. An observationX∈Pa D in a single-decision CIDGisnonrequisiteif: X⊥U D ∣ ∣ ( Pa D ∪D\X ) (1) In this case, the edgeX→Dis also called nonrequisite. OtherwiseXandX→Darerequisite. For example, in Figure 3a,high schoolis a requisite obser- vation whilegenderis not. Value of Information Materiality can be generalized to nodes not observed, to as- sess which variables a decision-maker would benefit from knowing before making a decision, i.e. which variables have VoI (Howard 1966; Matheson 1990). To assess VoI for a vari- ableX, we first makeXan observation by adding a link X→D, and then test whetherXis material in the updated model (Shachter 2016). Definition 8(Value of information).A nodeX∈V D in a single-decision SCIMMhasVoIif it is material in the modelM X→D obtained by adding the edgeX→DtoM. A CIDGadmits VoIforXifXhas VoI in a a SCIMM compatible withG. Since Definition 8 adds an information link, it can only be applied to non-descendants of the decision, lest cycles be cre- ated in the graph. Fortunately, the structural functions need not be adapted for the added link, since there is no structural function associated withD. We prove that the graphical criterion of Definition 7 is tight for both materiality and VoI, in that it identifies every zero VoI node that can be identified from the graphical structure (in a single decision setting). Theorem 9(Value of information criterion).A single deci- sion CIDGadmits VoI forX∈V D if and only ifX is a requisite observation inG X→D , the graph obtained by addingX→DtoG. The soundness direction (i.e. theonly ifdirection) follows from d-separation (Fagiuoli and Zaffalon 1998; Lauritzen and Nilsson 2001; Shachter 2016). In contrast, the complete- ness direction does not follow from the completeness prop- erty of d-separation. The d-connectedness ofXtoUimplies thatUmay be conditionally dependent onX. It does not imply, however, that the expectation ofUor the utility attain- able under an optimal policy will change. Instead, our proof (Appendix C.1) constructs a SCIM such thatXis material. This differs from a previous attempt by Nielsen and Jensen (1999), as discussed in Related Work. We apply the graphical criterion to the grade prediction ex- ample in Figure 3a. One can see that the predictor has an in- centive to use the incoming student’s high school but not gen- der. This makes intuitive sense, given thatgenderprovides no information useful for predicting the university grade in this example. Response Incentives There are two ways to understand a material observation. One is that it provides useful information. From this perspective, a natural generalisation is VoI, as described in the previous section. An alternative perspective is that a material observa- tion is one that influences optimal decisions. Under this inter- pretation, the natural generalisation is the set of all (observed and unobserved) variables that influence the decision. We say that these variables have a response incentive. 3 Definition 10(Response incentive).LetMbe a single- decision SCIM. A policyπrespondsto a variableX∈X if there exists some interventiondo(X=x)and some set- tingE=ε, such thatD x (ε)6=D(ε). The variableXhas a response incentiveif all optimal policies respond toX. A CIDadmitsa response incentive onXif it is compatible with a SCIM that has a response incentive onX. For a response incentive onXto be possible, there must be: i) a directed pathX99KD, and i) an incentive forDto use information from that path. For example, in Figure 3a,gender has a directed path to the decision but it does not provide any information about the likely grade, so there is no response incentive. The graphical criterion for RI builds on a modified graph with nonrequisite information links removed. Definition 11(Minimal reduction; Lauritzen and Nilsson 2001).Theminimal reductionG min of a single-decision CID Gis the result of removing fromGall information links from nonrequisite observations. The presence (or absence) of a pathX99KDin the mini- mal reduction tells us whether a response incentive can occur. Theorem 12(Response incentive criterion).A single- decision CIDGadmits a response incentive onX∈Xif and only if the minimal reductionG min has a directed path X99KD. 3 The termresponsiveness(Heckerman and Shachter 1995; Shachter 2016) has a related but not identical meaning – it refers to whether a decisionDaffects a variableXrather than whetherX affectsD. Race High school Education Grade Predicted grade Gender Accuracy (a) Admits response incentive on race Race High school Education Grade Predicted grade Gender Accuracy VoI RI (b) Admits no response incentive on race Figure 3: In (a), the admissible incentives of the grade prediction example from Figure 1a are shown, including a response incentive on race. In (b), the predictor no-longer has access to the students’ high school, and hence there can no-longer be any response incentive on race. Proof.Theif(completeness) direction is proved in Lemma 28 in Appendix C.2. For the soundness direction, as- sume that forG, the minimal reductionG min does not contain a directed pathX99KD. LetM=hG,E,F, Pibe any SCIM compatible withG. LetM min = 〈 G min ,E,F, P 〉 be M, but with the minimal reductionG min . By Lemma 25 in Appendix C, there exists aG min -respecting policy ̃πthat is optimal inM. InM min ̃π ,Xis causally irrelevant forDso D(ε) =D x (ε). Furthermore,M ̃π andM min ̃π are the same SCM, with the functionsF∪ ̃π. SoD(ε) =D x (ε)also in M ̃π , which means that there is an optimal policy inMthat does not respond to interventions onXfor anyε. The intuition behind the proof is that an optimal decision only responds to effects that propagate to one of its requisite observations. For the completeness direction, we show in Ap- pendix C.2 that ifX99KDis present in the minimal reduc- tionG min , then we can select a SCIMMcompatible withG such thatDreceives useful information along that path, that any optimal policy must respond to. In a safety setting, it may be desirable for an AI system to have an incentive to respond to its shutdown button, so that when asked to shut down, it does so (Hadfield-Menell et al. 2017). In a fairness setting, on the other hand, a response incentive may be a cause for concern, as illustrated next. Incentivised unfairnessResponse incentives are closely related to counterfactual fairness (Kusner et al. 2017; Kilber- tus et al. 2017). A prediction — or more generally a decision — is considered counterfactually unfair if a change to asensi- tive attributelike race or gender would change the decision. Definition 13(Counterfactual fairness; Kusner et al. 2017). A policyπiscounterfactually fairwith respect to a sensitive attributeAif Pr π ( D a ′ =d|pa D , a ) = Pr π ( D=d|pa D , a ) for every decisiond∈dom(D), every contextpa D ∈ dom(Pa D ), and every pair of attributesa, a ′ ∈dom(A)with Pr(pa D , a)>0. A response incentive on a sensitive attribute indicates that counterfactual unfairness is incentivised, as it implies thatall optimal policies are counterfactually unfair: Theorem 14(Counterfactual fairness and response incen- tives).In a single-decision SCIMMwith a sensitive at- tributeA∈X, all optimal policiesπ ∗ are counterfactually unfair with respect toAif and only ifAhas a response incen- tive. The proof is given in Appendix C.5. A response incentive on a sensitive attribute means that counterfactual unfairness is not just possible, but incentivised. As a result, it has a more restrictive graphical criterion. The graphical criterion for counterfactual fairness states that a decision can only be counterfactually unfair with respect to a sensitive attribute if that attribute is an ancestor of the decision (Kusner et al. 2017, Lemma 1). For example, in the grade prediction example of Figure 3a, it is possible for a predictor to be counterfactually unfair with respect to eithergenderorrace, because both are ancestors of the decision. The response incentive criterion can tell us in which case counterfactual unfairness is actually incentivised. In this example, the minimal reduction includes the edge fromhigh schooltopredicted gradeand hence the directed path fromracetopredicted grade. However, it excludes the edge fromgendertopredicted grade. This means that the agent is incentivised to be counterfactually unfair with respect toracebut not togender. Based on this, how should the system be redesigned? According to the response incentive criterion, the most important change is to remove the path fromracetopre- dicted gradein the minimal reduction. This can be done by removing the agent’s access tohigh school. This change is implemented in Figure 3b, where there is no response incentive on either sensitive variable. Value of information is also related to fairness. For a sensi- tive variable that is not a parent of the decision, positive VoI means thatifthe predictor gained access to its value, then the predictor would use it. For example, if in Figure 3b an edge is added fromracetopredicted grade, then unfair be- haviour will result. In practice, such access can result from unanticipated correlations between the sensitive attribute and parents of the decision, rather than the system being given direct access to the attribute. Analysing VoI may help detect such problems at an early stage. However, VoI is less closely related to counterfactual fairness than response incentives. In particular,racelacks VoI in Figure 3a, but counterfactual un- fairness is incentivised. On the other hand, Figure 3b admits positive VoI forrace, but counterfactual unfairness is not in- centivised. The incentive approach is not restricted to counterfactual fairness. For any fairness definition, one could assess whether that kind of unfairness is incentivised by checking whetherit is present under all optimal policies. Value of Control A variable has VoC if a decision-maker could benefit from setting its value (Shachter 1986; Matheson 1990; Shachter and Heckerman 2010). Concretely, we ask whether the at- tainable utility can be increased by letting the agent decide the structural function for the variable. Definition 15(Value of control).In a single-decision SCIM M, a non-decision nodeXhaspositive value of controlif max π E π [U]<max π,g X E π [U g X ] whereg X : dom(Pa X ∪E X )→dom(X)is a soft inter- vention atX, i.e. a new structural function forXthat respects the graph. A CIDGadmits positive value of controlforXif there exists a SCIMMcompatible withGwhereXhas positive value of control. This can be deduced from the graph, using again the minimal reduction (Definition 11) to rule out effects through observations that an optimal policy can ignore. Theorem 16(Value of control criterion).A single-decision CIDGadmits positive value of control for a nodeX∈V\ Dif and only if there is a directed pathX99KUin the minimal reductionG min . Proof.Theif(completeness) direction is proved in Lemma 29. The proof ofonly if(soundness) is as follows. LetM=hG,E,F, Pibe a single-decision SCIM. LetM g X beM, but with the structural functionf X replaced withg X . LetM min andM min g X be the same SCIMs, respectively, but replacing each graph with the minimal reductionG min . Recall thatE π [U g X]is defined by applying the soft in- terventiong X to the (policy-completed) SCMM π . How- ever, this is equivalent to applying the policyπto the modi- fied SCIMM g X, as the resulting SCMs are identical. Since M g Xis a SCIM, Lemma 25 can be applied, to find aG min - respecting optimal policy ̃πforM g X. Consider now the expected utility under an arbitrary inter- ventiong X for a policyπoptimal forM g X: E π [U g X ]inM =E π [U]inM g Xby SCM equivalence =E ̃π [U]inM g Xby Lemma 25 =E ̃π [U]inM min g X since ̃πisG min -respecting =E ̃π [U]inM min by Lemma 23 =E ̃π [U]inMonly increasing the policy set ≤max π ∗ E π ∗ [U]inMmaxdominates all elements. This shows thatXmust lack value of control. The proof of the completeness direction (Appendix C.3) establishes that if a path exists, then a SCIM be selected where the intervention onXcan either directly controlU or increase the useful information available atD. To apply this criterion to the content recommendation example (Figure 4a), we first obtain the minimal reduction, which is identical to the original graph. Since all non- decision nodes are upstream of the utility in the minimal reduction, they all admit positive VoC. Notably, this includes nodes likeoriginal user opinionsandmodel of user opinions that the decision has no ability to control according to the graphical structure. In the next section, we proposeinstru- mental control incentives, which incorporate the agent’s limitations. Instrumental Control Incentive Would an agent use its decision to control a variableX? This question has two parts: whetherXis useful to control (VoC), and whetherXis possible to control (responsiveness). As de- scribed in the previous section, VoC usesU g X to consider the utility attainable from arbitrary control ofX. Meanwhile,X d describes the wayXcan be controlled byD. These notions can be combined with a nested counterfactualU X d , which expresses the effect thatDcan have onUby controllingX. Definition 17(Instrumental control incentive).In a single- decision SCIMM, there is aninstrumental control incentive on a variableXin decision contextpa D if, for all optimal policiesπ ∗ , E π ∗ [U X d |pa D ]6=E π ∗ [U |pa D ].(2) Conceptually, an instrumental control incentive can be in- terpreted as follows. If the agent got to chooseDto influence Xindependently of howDinfluences other aspects of the environment, would that choice matter? We call it aninstru- mentalcontrol incentive, as the control ofXis a tool for achieving utility (cf.instrumental goalsOmohundro 2008; Bostrom 2014). ICIs do not consider side-effects of the op- timal policy: for instance, it may be that all optimal policies affectXin a particular way, even ifXis a not an ancestor of any utility node — in such cases, no ICI is present. Finally, in Pearl’s (2001) terminology, an instrumental control incentive corresponds to anatural indirect effectfromDtoUviaXin M π ∗ , for all optimal policiesπ ∗ . A CIDGadmitsan instrumental control incentive onXif Gis compatible with a SCIMMwith an instrumental control incentive onXfor some decision contextpa D . The follow- ing theorem gives a sound and complete graphical criterion for which CIDs admit instrumental control incentives. Theorem 18(Instrumental Control Incentive Criterion).A single-decision CIDGadmits an instrumental control incen- tive onX∈Vif and only ifGhas a directed path from the decisionDto a utility nodeU∈Uthat passes throughX, i.e. a directed pathD99KX99KU. Proof.Completeness (theifdirection) is proved in Ap- pendix C.4. The proof of soundness is as follows. LetMbe any SCIM compatible withGandπany policy forM. We consider variables in the SCMM π . If there is no directed pathD99KX99KUinG, then eitherD699KXor X699KU. IfD699KX, thenX d (ε) =X(ε)for any setting ε∈dom(E)and decisiond(Lemma 20). Therefore,U(ε) = U X d (ε). Similarly, ifX699KUthenU(ε) =U x (ε)for every settingε∈dom(E),x∈dom(X)andU∈UsoU(ε) = U X d (ε). In either case,E π [U |pa D ] =E π [U X d |pa D ]and there is no instrumental control incentive onX. The logic behind the soundness proof above is that if there is no path fromDtoXtoU, thenDcannot have any effect onUviaX. For the completeness direction proved in Ap- pendix C.4, we show how to construct a SCIM so thatU X d differs from the non-intervenedUfor any diagram with a pathD99KX99KU. Posts to show Model of original opinions Original user opinions Clicks Influenced user opinions (a) Admits instrumental control incentive on user opinion Posts to show Model of original opinions Original user opinions Predicted Clicks Influenced user opinions VoC ICI (b) Admits no instrumental control incentive on user opinion Figure 4: In (a), the content recommendation example from Figure 1b is shown to admit an instrumental control incentive on user opinion. This is avoided in (b) with a change to the objective. Let us apply this criterion to the content recommendation example in Figure 4a. The only nodesXin this graph that lie on a pathD99KX99KUareclicksandinfluenced user opinions. Sinceinfluenced user opinionshas an instrumental control incentive, the agent may seek to influence that variable in order to attain utility. For example, it may be easier to predict what content a more emotional user will click on and therefore, a recommender may achieve a higher click rate by introducing posts that induce strong emotions. How could we instead design the agent to maximise clicks without manipulating the user’s opinions (i.e. without an in- strumental control incentive oninfluenced user opinions)? As shown in Figure 4b, we could redesign the system so that instead of being rewarded for the true click rate, it is re- warded for the clicks it would be predicted to have, based on a separately trained model of the user’s preferences. An agent trained in this way would view any modification of user opin- ions as irrelevant for improving its performance; however, it would still have an instrumental control incentive forpre- dicted clicksso it would still deliver desired content. To avoid undesirable behaviour in practice, the click prediction must truly predict whether the original user would click the con- tent, rather than baking in the effect of changes to the user’s opinion from reading earlier posts. This could be accom- plished, for instance, by training a model to predict how many clicks each post would receive if it was offered individually. This dynamic is related to concerns about the long-term safety of AI systems. For example, Russell (2019) has hy- pothesised that an advanced AI system would seek to ma- nipulate its objective function (or human overseer) to ob- tain reward. This can be understood as an instrumental con- trol incentive on the objective function (or the overseer’sbe- haviour). A better understanding of incentives could there- fore be relevant for designing safe systems in both the short and long-term. Related Work Causal influence diagramsJern and Kemp (2011) and Kleiman-Weiner et al. (2015) define influence diagrams with causal edges, and similarly use them to model decision- making of rational agents (although they are less formal than us, and focus on human decision-making). An informal precursor of the SCIM that also used structural functions (as opposed to conditional probabil- ity distributions) was the “functional influence diagram” (Dawid 2002). The most similar alternative model is the Howard canonical form influence diagram (Howard 1990; Heckerman and Shachter 1995). However, this only permits counterfactual reasoning downstream of decisions, which is inadequate for defining the response incentive. Similarly, the causality property for influence diagrams introduced by Heckerman and Shachter (1994) and Shachter and Hecker- man (2010) only constrains the relationships to be partially causal downstream of the decision (though adding new decision-node parents to all nodes makes the diagram fully causal). Appendix A shows by example why the stronger causality property is necessary for most of our incentive concepts. An open-source Python implementation of CIDs has re- cently been developed 4 (Fox et al. 2021). Value of information and controlTheorems 9 and 16 for value of information and value of control build on previous work. The concepts were first introduced by Howard (1966) and Shachter (1986), respectively. The VoI soundness proof follows previous proofs (Shachter 1998; Lauritzen and Nils- son 2001), while the VoI completeness proof is most similar to an attempted proof by Nielsen and Jensen (1999). They propose the criterionX6⊥U D |Pa D for requisite nodes, which differs from (1) in the conditioned set. Taken literally, 5 their criterion is unsound for requisite nodes and positiveVoI. For example, in Figure 3a,High schoolis d-separated from accuracygivenPa D , so their criterion would fail to detect thatHigh schoolis requisite and admits VoI. 67 To have positive VoC, it is known that a node must be an ancestor of a value node (Shachter 1986), but the authors know of no more-specific criterion. The concept of arele- vantnode introduced by Nielsen and Jensen (1999) also bears some semblance to VoC. 4 https://github.com/causalincentives/pycid 5 Def. 6 defines d-separation for potentially overlapping sets. 6 Furthermore, to prove that nodes meeting the d-connectedness property are requisite, Nielsen and Jensen claim that “Xis [requi- site] forDifPr(dom(U)|D,Pa D )is a function ofXandUis a utility function relevant forD”. However,Ubeing a function of Xonly proves thatUis conditionally dependent onX, not that it changes the expected utility, or is requisite or material. Additional argumentation is needed to show that conditioning onXcan actually change the expected utility; our proof provides such an argument. 7 Since a preprint of this paper was placed online (Everitt et al. 2019c), this completeness result was independently discovered by Zhang, Kumor, and Bareinboim (2020, Thm. 2) and Lee and Barein- boim (2020, Thm. 1). Theorem 2 in the latter also provides a crite- rion for material observations in a multi-decision setting. The relation of the current technical results to prior work is summarised in Table S1 in the Appendix. Instrumental control incentivesKleiman-Weiner et al. (2015) use (causal) influence diagrams to define a notion of intention, that captures which nodes an optimal policy seeks to influence. Intention is conceptually similar to instrumen- tal control incentives and uses hypothetical node deletions to ask which nodes the agent intends to control. Their concept is more refined than ICI in the sense that it includes includes only the nodes that determine optimal policy behaviour, but the definition is not properly formalized and it is not clear that it can be applied to all influence diagram structures. AI fairnessAnother application of this work is to evaluate when an AI system is incentivised to behave unfairly, on some definition of fairness. Response incentives address this question for counterfactual fairness (Kusner et al. 2017; Kilbertus et al. 2017). An incentive criterion corresponding to path-specific effects (Zhang, Wu, and Wu 2017; Nabi and Shpitser 2018) is deferred to future work. Nabi, Malinsky, and Shpitser (2019) have shown how a policy may be chosen subject to path-specific effect constraints. However, they assume recall of all past events, whereas the response incentive criterion applies to any CID. Mechanism designThe aim of mechanism design is to un- derstand how objectives and environments can be designed, in order to shape the behavior of rational agents (e.g. Nisan et al. 2007, Part I). At this high level, mechanism design is closely related to the incentive design results we have devel- oped in this paper. In practice, the strands of research look rather different. The core challenge of mechanism design is that agents have private information or preferences. As we take the perspective of an agent designer, private informa- tion is only relevant for us to the extent that some types of agents or objectives may be harder to implement than oth- ers. Instead, our core challenge comes from causal relation- ships in agent environments, a consideration of little interest to most of mechanism design. Discussion and Conclusion We have proved sound and complete graphical criteria for two existing concepts (VoI and VoC) and two new concepts: response incentive and instrumental control incentive. The re- sults have all focused on the (causal) structure of the interac- tion between agent and environment. This is both a strength and a weakness. On the one hand, it means that formal con- clusions can be made about a system’s incentives, even when details about the quantitative relationship between variables is unknown. On the other hand, it also means that these re- sults will not help with subtler comparisons, such as the rel- ative strength of different incentives. It also means that the causal relationships between variables must be known. This challenge is common to causal models in general. In the con- text of incentive design, it is partially alleviated by the fact that causal relationships often follow directly from the de- sign choices for an agent and its objective. Finally, causal diagrams struggle to express dynamically changing causal re- lationships. While important to be aware of, these limitations do not prevent causal influence diagrams from providing a clear, useful, and unified perspective on agent incentives. It has seen applications ranging from value learning (Armstrong et al. 2020; Holtman 2020), interruptibility (Langlois and Everitt 2021), conservatism (Cohen, Vellambi, and Hutter 2020), modeling of agent frameworks (Everitt et al. 2019b), and reward tampering (Everitt et al. 2019a). Through such applications, we hope that the incentive analysis described in this paper will ultimately contribute to more fair and safe AI systems. Acknowledgements Thanks to James Fox, Lewis Hammond, Michael Cohen, Ra- mana Kumar, Chris van Merwijk, Carolyn Ashurst, Michiel Bakker, Silvia Chiappa, and Koen Holtman for their invalu- able feedback. This work was supported by the Leverhulme Centre for the Future of Intelligence, Leverhulme Trust, under Grant RC- 2015-067. We acknowledge the support of the Natural Sciences and Engineering Research Council of Canada (NSERC), [fund- ing reference number CGSD3-534795-2019]. Cette recherche a ́et ́e financ ́e par le Conseil de recherches en sciences naturelles et en g ́enie du Canada (CRSNG), [num ́ero de r ́ef ́erence CGSD3-534795-2019]. References Armstrong, S.; Orseau, L.; Leike, J.; and Legg, S. 2020. Pit- falls in learning a reward function online. InInternational Joint Conference on Artificial Intelligence (IJCAI). Bostrom, N. 2014.Superintelligence: Paths, Dangers, Strate- gies. Oxford University Press. Carey, R.; Langlois, E.; Everitt, T.; and Legg, S. 2020. The Incentives that Shape Behaviour. InSafeAI AAAI workshop. Cohen, M. K.; Vellambi, B. N.; and Hutter, M. 2020. Asymp- totically Unambitious Artificial General Intelligence. In AAAI Conference on Artificial Intelligence. Correa, J.; and Bareinboim, E. 2020. A calculus for stochas- tic interventions: Causal effect identification and surrogate experiments. InAAAI Conference on Artificial Intelligence. Dawid, A. P. 2002. Influence diagrams for causal modelling and inference.International Statistical Review. Eberhardt, F.; and Scheines, R. 2007. Interventions and causal inference.Philosophy of Science. Everitt, T.; Hutter, M.; Kumar, R.; and Krakovna, V. 2019a. Reward Tampering Problems and Solutions in Reinforce- ment Learning: A Causal Influence Diagram Perspective. CoRR. Everitt, T.; Kumar, R.; Krakovna, V.; and Legg, S. 2019b. Modeling AGI Safety Frameworks with Causal Influence Di- agrams. InWorkshop on Artificial Intelligence Safety, vol- ume 2419 ofCEUR Workshop Proceedings. Everitt, T.; Ortega, P. A.; Barnes, E.; and Legg, S. 2019c. Understanding Agent Incentives using Causal Influence Di- agrams. Part I: Single Action Settings.CoRR. Fagiuoli, E.; and Zaffalon, M. 1998. A note about redun- dancy in influence diagrams.International Journal of Ap- proximate Reasoning. Fox, J.; Hammond, L.; Everitt, T.; Abate, A.; and Wooldridge, M. 2021. Equilibrium Refinements for Multi-Agent Influ- ence Diagrams: Theory and Practice. InAAMAS. Galles, D.; and Pearl, J. 1997. Axioms of Causal Relevance. Artificial Intelligence. Hadfield-Menell, D.; Dragan, A.; Abbeel, P.; and Russell, S. J. 2017. The Off-Switch Game. InInternational Joint Conference on Artificial Intelligence (IJCAI). Heckerman, D.; and Shachter, R. 1994. A Decision-Based View of Causality. InUncertainty in Artificial Intelligence (UAI), 302–310. Heckerman, D.; and Shachter, R. D. 1995. Decision- Theoretic Foundations for Causal Reasoning.Journal of Ar- tificial Intelligence Research3: 405–430. doi:10.1613/jair. 202. Holtman, K. 2020. AGI Agent Safety by Iteratively Improv- ing the Utility Function.International Conference on Artifi- cial General Intelligence. Howard, R. A. 1966. Information Value Theory.IEEE Trans- actions on Systems Science and Cybernetics. Howard, R. A. 1990. From influence to relevance to knowl- edge.Influence diagrams, belief nets and decision analysis . Jern, A.; and Kemp, C. 2011. Capturing mental state rea- soning with influence diagrams. InProceedings of the 2011 Cognitive Science Conference, 2498–2503. Kilbertus, N.; Rojas-Carulla, M.; Parascandolo, G.; Hardt, M.; Janzing, D.; and Sch ̈olkopf, B. 2017. Avoiding Discrim- ination through Causal Reasoning. InAdvances in Neural Information Processing Systems, 656–666. Kleiman-Weiner, M.; Gerstenberg, T.; Levine, S.; and Tenen- baum, J. B. 2015. Inference of intention and permissibility in moral decision making. InProceedings of the 37th Annual Conference of the Cognitive Science Society, 1123–1128. Kusner, M. J.; Loftus, J. R.; Russell, C.; and Silva, R. 2017. Counterfactual Fairness. InAdvances in Neural Information Processing Systems. Langlois, E.; and Everitt, T. 2021. How RL Agents Behave when their Actions are Modified. InAAAI. Lauritzen, S. L.; and Nilsson, D. 2001. Representing and Solving Decision Problems with Limited Information.Man- agement Science. Lee, S.; and Bareinboim, E. 2020. Characterizing optimal mixed policies: Where to intervene and what to observe.Ad- vances in Neural Information Processing Systems33. Matheson, J. E. 1990. Using influence diagrams to value information and control. In Oliver, R. M.; and Smith, J. Q., eds.,Influence Diagrams, Belief Nets, and Decision Analysis. Wiley and Sons. Nabi, R.; Malinsky, D.; and Shpitser, I. 2019. Learning opti- mal fair policies.Proceedings of machine learning research . Nabi, R.; and Shpitser, I. 2018. Fair Inference on Outcomes. InAAAI Conference on Artificial Intelligence. Nielsen, T. D.; and Jensen, F. V. 1999. Welldefined Decision Scenarios. InUncertainty in Artificial Intelligence (UAI). Nisan, N.; Roughgarden,T.; Tardos, E.; and Vijay V Vazirani, eds. 2007.Algorithmic Game Theory. Cambridge University Press. Omohundro, S. M. 2008. The Basic AI Drives. In Wang, P.; Goertzel, B.; and Franklin, S., eds.,Artificial General Intelli- gence, volume 171. IOS Press. O’Neil, C. 2016.Weapons of Math Destruction. Crown Books. Pearl, J. 2001. Direct and Indirect Effects. InUncertainty in Artificial Intelligence (UAI). Pearl, J. 2009.Causality: Models, Reasoning, and Infer- ence. Cambridge University Press, 2nd edition edition. ISBN 9780521895606. Russell, S. J. 2019.Human Compatible: Artificial Intelli- gence and the Problem of Control. Viking. Shachter, R. D. 1986. Evaluating Influence Diagrams.Oper- ations Research. Shachter, R. D. 1998. Bayes-Ball: The Rational Pastime (for Determining Irrelevance and Requisite Information in Belief Networks and Influence Diagrams).Uncertainty in Artificial Intelligence (UAI). Shachter, R. D. 2016. Decisions and Dependence in Influ- ence Diagrams. InInternational Conference on Probabilistic Graphical Models. Shachter, R. D.; and Heckerman, D. 2010. Pearl Causality and the Value of Control. In R. Dechter, H. G.; and Halpern, J. Y., eds.,Heuristics, Probability and Causality: A Tribute to Judea Pearl. College Publications. Tian, J.; and Pearl, J. 2001. Causal discovery from changes. InUncertainty in Artificial Intelligence (UAI). Verma, T.; and Pearl, J. 1988. Causal Networks: Semantics and Expressiveness. InUncertainty in Artificial Intelligence (UAI). Zhang, J.; Kumor, D.; and Bareinboim, E. 2020. Causal im- itation learning with unobserved confounders.Advances in Neural Information Processing Systems33. Zhang, L.; Wu, Y.; and Wu, X. 2017. A causal framework for discovering and removing direct and indirect discrimina- tion. InIJCAI International Joint Conference on Artificial Intelligence. DefinitionCriterionSoundnessCompleteness VoI Howard 1966; Matheson 1990 Fagiuoli and Zaffalon 1998; Lauritzen and Nilsson 2001; Shachter 2016 Fagiuoli and Zaffalon 1998; Lauritzen and Nilsson 2001; Shachter 2016 First correct proof to our knowledge (see Related Work) VoC Shachter 1986; Matheson 1990; Shachter and Heckerman 2010 Incomplete version by Shachter (1986) (see Related Work) New; proved using do-calculus and VoI New; proved constructively (cf. “relevant utility nodes” Nielsen and Jensen (1999)) RINewNew New; proved using do-calculus and VoI New; proved constructively ICINewNew New; proved using do-calculus New; proved constructively Table S1: Comparison with related work. The concepts of positive value of information (VoI), and positive value of control (VoC) are well-known. For VoI, a new, corrected, proof is provided. For VoC, the present work offers a new criterion, proving itsound and complete. For response incentive (RI) and instrumentalcontrol incentive (ICI), the criterion and all proofs are new. DU X X=D U=X+D D∈ 0,1 (a) A causal influence diagram reflecting the causal structure of the environment DU X X=D U= 2·D D∈ 0,1 (b) Influence diagram that is causal in the sense of Hecker- man and Shachter (1994, 1995) Figure 5: Two different influence diagram representations of the same situation, with different VoC and ICI. A Causality Examples Causal influence diagrams that reflect the full causal structure of the environment are needed to correctly capture response incentives, value of control and instrumental control incen- tives. We begin with showing this for instrumental control incentives and value of control, leaving response incentive to the end of this section. Consider the two influence diagrams in Figure 5. If we assume thatXreally affectsU, only the di- agram in Figure 5a correctly represents this causal structure, whereas Figure 5b lacks the edgeX→U. According to Def- initions 15 and 17,Xhas positive value of control and an instrumental control incentive. Only Figure 5a gets this right. The influence diagram literature has discussed weaker no- tions of causality, under which Figure 5b is considered a valid alternative representation of the situation described by Fig- ure 5a. For example, if we only consider their joint distribu- tions conditional on various policies, then Figures 5a and 5b are identical. Both diagrams are also in the canonical form of Heckerman and Shachter (1995), as every variable respon- sive to the decision is a descendant of the decision. For the same reason, both diagrams are also causal influence dia- D XY U Y∼0,1 X=Y U=X+D D∈ 0,1 (a) A causal influence diagram reflecting the causal structure of the environment D XY U X∼0,1 Y=X U=X+D D∈ 0,1 (b) Influence diagram that is causal in the sense of Hecker- man and Shachter (1994, 1995) Figure 6: Two different influence diagram representations of the same situation, with different RI and VoC. In Figure 6a, Yis sampled from some arbitrary distribution on0,1, for example a Bernoulli distribution withp= 0.5. In Figure 6b, Xis sampled in the same way. grams in the terminology of Heckerman and Shachter (1994) and Shachter and Heckerman (2010). Since only Figure 5a gets the incentives right, we see that the stronger notion of causal influence diagram introduced in this paper is neces- sary to correctly model instrumental control incentives and value of control. To show that response incentives also rely on fully causal influence diagrams, consider the diagrams in Figure 6. Again, we assume that Figure 6a accurately depicts the environment, while Figure 6b has the edgeY→Xreversed. Again, both diagrams have identical joint distributions given any policy. Both diagrams are also causal in the weaker sense of Heck- erman and Shachter (1994) and Shachter and Heckerman (2010). Yet only the fully causal influence diagram in Fig- ure 6a exhibits thatYcan have a response incentive or posi- tive value of control. B Proof Preliminaries Our proofs will rely on the following fundamental results about causal models from (Galles and Pearl 1997) and (Pearl 2009). Definition 19(Causal Irrelevance).Xiscausally irrelevant toY, givenZ, written(X6→Y|Z)if, for every setW disjoint ofX∪Y∪Z, we have ∀ε,z,x,x ′ ,wY xzw (ε) =Y x ′ zw (ε) Lemma 20.For every SCMMcompatible with a DAGG, (X699KY|Z) G ⇒(X6→Y|Z) Proof.By induction over variables, as in (Galles and Pearl 1997, Lemma 12). Lemma 21(Pearl 2009, Thm. 3.4.1, Rule 1).For any disjoint subsets of variablesW,X,Y,Zin the DAGG, E(Y x |z,w) =E(Y x |w)ifY⊥Z|(X,W)in the graph G ′ formed by deleting all incoming edges toX. Lemma 22(Pearl 2009, Thm. 1.2.4).For any three disjoint subsets of nodes(X,Y,Z)in a DAGG,(X⊥ G Y|Z)if and only if(X⊥Y|Z) P for every probability functionP compatible withG. Lemma 23(Correa and Bareinboim 2020, Sigma Calculus Rule 3).For any disjoint subsets of nodes(X,Y)⊆Vand Z⊆Vin a DAGGPr(X|Z;g Y ) = Pr(X|Z;g ′Y )ifX⊥ Y|ZinG Y(Z) whereY(Z)⊆Yis the set of elements inY that are not ancestors ofZinGandG W denotesGbut with edges incoming to variables inWremoved. C Proofs C.1 Value of Information Criterion First, we introduce the notion of aG min -respecting optimal policy. Our proof of its optimality is similar to Theorem 3 from (Lauritzen and Nilsson 2001). It builds on the following intersection property of d-separation. Lemma 24(d-separationintersectionproperty).For all dis- joint sets of variablesW,X,Y, andZ, (W⊥X|Y,Z)∧(W⊥Y|X,Z)⇒(W⊥(X∪Y)|Z) Proof.Suppose that the RHS is false, so there is a path from WtoX∪Yconditional onZ. This path must have a sub- path that passes fromWtoX∈Xwithout passing through Yor toY∈Ywithout passing throughX(it must traverse one set first). But this implies thatWis d-connected toX givenY,Zor toYgivenX,Z, meaning the LHS is false. So if the LHS is true, then the RHS must be true. Lemma 25(G min -respecting optimal policy).Every single- decision SCIMM=hG,E,F, Pihas an optimal pol- icy ̃πthat depends only on requisite observations. In other words, ̃πis also a policy for the minimal modelM min = 〈 G min ,E,F, P 〉 . We call ̃πaG min -respecting optimal policy. Proof.First partitionPa D G into the requisite parentsPa D min = W∈Pa D :W6⊥U D | D∪Pa D \W, and non- requisite parentsPa D − =Pa D G D min . Letπ ∗ be an optimal policy inM. To construct aG min - respecting version ̃π, select any value ̃ pa D − ∈dom(Pa D − )for whichPr π ∗ (Pa D − = ̃ pa D − )>0. For allpa D min ∈dom(Pa D min ) andε D ∈dom(E D ), let ̃π(pa D min ,pa D − , ε D ) : =π ∗ (pa D min , ̃ pa D − , ε D ). The policy ̃πis permitted inM min because it does not vary withPa D − . Now let us prove that ̃πthat is optimal inM. PartitionU intoU D =U∩Desc D andU =U D .Dis causally irrelevant for everyU∈U so every policyπ(in particular, ̃π) is optimal with respect toU : = ∑ U∈U U. We now considerU D . By definition,W⊥U D | D∪ Pa D \ Wfor everyW∈Pa D − . By inductively applying the intersection property of d-separation (Lemma 24) over elements ofPa D − we obtain Pa D − ⊥U D |D∪Pa D min .(3) Next, we establish thatE ̃π [U D ] =E π ∗ [U D ]by showing thatE ̃π [U D |pa D ] =E π ∗ [U D |pa D ]for ev- erypa D ∈dom(Pa D )withPr(pa D )>0. First, the expected utility of ̃πgiven any(pa D min ,pa D − )with Pr(Pa D min =pa D min ,pa D − =pa D − )>0is equal to the expected utility ofπ ∗ on input(pa D min , ̃ pa D − ): E ̃π [U D |pa D min ,pa D − ] = ∑ u,d ( uPr(U D =u|d,pa D min ,pa D − ) ·Pr ̃π (D=d|pa D min ,pa D − ) ) = ∑ u,d ( uPr(U D =u|d,pa D min , ̃ pa D − ) ·Pr π ∗ (D=d|pa D min , ̃ pa D − ) ) =E π ∗ [U D |pa D min , ̃ pa D − ] where the middle equality follows from (3) and the definition of ̃π. Second, the expected utility ofπ ∗ given input ̃ pa D − is the same as its expected utility on any inputpa D − : = max d E π ∗ [U D d |pa D min , ̃ pa D − ] = max d E π ∗ [U D d |pa D min ,pa D − ] =E π ∗ [U D |pa D min ,pa D − ] where the first equality follows from the optimality ofπ ∗ and the second from Lemma 21. The expressionE π ∗ [U D d | ·] means that we first assign the policyπ ∗ then intervene to set D=d, which rendersπ ∗ effectively irrelevant but formally necessary for creating an SCM. This result shows that ̃πis optimal forU D and hasE ̃π [U D ] =E π ∗ [U D ]. Since ̃πis opti- mal for bothU D andU , ̃πis optimal inM. We now prove Theorem 9 by establishing the soundness and completeness of the value of information criterion. Lemma 26(VoI criterion soundness).If, in the single- decision CIDG,X∈V D has X⊥U D ∣ ∣ ( Pa D ∪D\X ) whereU D : =U∩Desc D , thenXdoes not have positive value of information in any SCIMMcompatible withG. The result is already known from (Lauritzen and Nilsson 2001; Fagiuoli and Zaffalon 1998), but we prove it here to make the paper more self-contained. Proof.LetM=hG,E,F, Pibe any SCIM compatible withG. LetG X→D andG X6→D be versions ofGmodi- fied by adding and removingX→Drespectively. Let G min X→D be the minimal reduction ofG X→D . LetM X6→D := hG X6→D ,E,F, PiandM min X→D :=hG min X→D ,E,F, Pibe SCIMs with the same domains and structural functions. By Lemma 25, there is aG min -respecting policy ̃πad- missible inM min X→D and optimal inM X→D . We prove thatG min X→D is a subgraph ofG X6→D , meaning that ̃πis also admissible inM X6→D . By assumption,GhasX⊥ U D ∣ ∣ ( Pa D ∪D\X ) . AddingX→DtoGcannot causeXto be d-connected toU D givenPa D ∪D, because any new path alongX→Dis blocked byDandPa D \X. SoG min X→D is a version ofGwithX→D(and possibly other nodes) removed. This makes it a subgraph ofG X6→D , imply- ing that ̃πis admissible inM X6→D . Since ̃πis admissible inM X6→D and optimal inM X→D , V ∗ (M X6→D )6<V ∗ (M X→D ). Lemma 27(VoI criterion completeness).If in the single- decision CIDG,X∈V D is d-connected to a utility node that is a descendant ofDconditional on the decision and other parents: X6⊥U D ∣ ∣ ( Pa D ∪D\X ) (4) whereU D : =U∩Desc D thenXhas VoI in at least one SCIMMcompatible withG. This follows from the response incentive completeness Lemma 28 in Appendix C.2, so we defer the proof to that section. C.2 Response Incentive Criterion The Response Incentives section contains a proof of the soundness of the response incentive criterion. We now prove its completeness in order to finish the proof of Theorem 12. Figure 7 illustrates the model constructed in the proof. Lemma 28(Response Incentive Criterion Completeness).If X99KDin the minimal reductionG min of a single-decision CIDGthen there is a response incentive onXin at least one SCIMMcompatible withG. Proof.Starting from the assumption thatX99KDinG min , we explicitly construct a compatible model forGfor which the decision of every optimal policy causally depends on the value ofX. Let −→ XDbe a directed path fromXtoDthat only contains a single requisite observation that we labelW(ifX is itself a requisite observation, thenWandXis the same node). SinceWis a requisite observation forD, there exists some utility nodeUdescending fromDthat is d-connected toWinGwhen conditioning onPa D ∪ D \ W. Let −→ DUbe a directed path fromDtoUand let W Ube a path betweenWandUthat is active when conditioning onPa D ∪ D\W. By the definition of d-connecting paths, W U has the following structure (m≥0): W S 0 C 1 S 1 · C m S m U consisting of directed sub-paths leaving source nodesS i and entering collider nodesC i , where there is a directed path from each collider toPa D ∪D\Wand no non-collider node is inPa D ∪D\W. It may be the case thatWand S 0 are the same node. For eachi∈1, . . . , m, let −→ C i O i be a directed path fromC i to someO i ∈Pa D such that no other node along −→ C i O i is inPa D . We make the following assumptions without loss of gener- ality: •W Ufirst intersects −→ DUat some variableY(possiblyY isU) and thereafter both W Uand −→ DUfollow the same directed path fromYtoU(otherwise, letYbe the first intersection point and replace theY99KUsub-path of W Uwith theY99KUsub-path of −→ DU). • TheS 0 99KWsub-path of reversed W Ufirst intersects −→ XDat some nodeZand thereafter both follow the same directed path fromZtoW(same argument as forY). • The paths −→ C i O i are mutually non-intersecting (if there is an intersection between −→ C i O i and −→ C j O j withj6=ithen replace the part of W UbetweenC i andC j with the path through the intersection point, which becomes the new col- lider; this can only happen finitely many times as it reduces the number of collider nodes). The resulting structure is shown in Figure 7. We now formally define the model represented in the fig- ure. The domains of all endogenous variables are set to −1,0,1. All exogenous variables are given independent discrete uniform distributions over−1,1. Unless other- wise specified, we setB=Afor each edgeA→Bwithin the directed paths shown in Figure 7, i.e.f B (pa B , ε B ) =a. Nodes at the heads of directed paths can therefore be defined in terms of nodes at the tails. We begin by describing func- tions for the “default” case depicted by Figure 7, and discuss adaptations for various special cases below. •S i =E S i , givingS i a uniform distribution over−1and1. •U=Y, and •Y=S m ·D, soDmust matchS m to optimize utility. •C i =S i−1 ·S i , and S m C m O m C 1 O 1 S 0 WZ X . . . . . . . . . D YU Y=S m ·D O 1 =C 1 O m =C m U=Y W=Z Z=S 0 ·X X= 1 C m =S m−1 ·S m S m ∼Uniform(−1,1) S 0 ∼Uniform(−1,1) C 1 =S 1 ·S 2 chooseD∈ −1,0,1 Figure 7: Outline of the variables involved in the response incentive construction. Every graph that satisfies the response incentive graphical criterion contains this structure (allowing alldashed paths except those toC i orYto have length zero). An optimal policy for the given model isD=W· ∏ i O i =S m , yielding utilityU=Y=X(S m ) 2 = 1, and all optimal policies must depend on the value ofW. •O i =C i , so the colliderC i reveals (only) whetherS i−1 andS i have the same sign or not. •X= 1, •Z=X·S 0 , and •W=Z, soWreflects the value ofS 0 , unlessXis inter- vened upon. All other variables not part of any named path are set to0. Special cases arise when two or more of the labeled nodes in Figure 7 refer to the same variable. WhenW,Y, orO i is the same node as one of its parents, then it simply takes the function of this parent (instead of copying its value). Mean- while, theS i ,C i , andYnodes must be distinct by construc- tion, so no special cases treatment is required. Finally, the functions forX,S 0 andZare adapted per the following cases: Case 1:X,S 0 , andZare all the same node. LetX= Z=S 0 =E S 0 , i.e. the node takes a uniform distribution over−1,1. Case 2:Zis the same node asS 0 , but different fromX. In this case, letZ=S 0 =X·E S 0 . Case 3:Xis the same node asZ, but different fromS 0 . In this case, letX=Z=S 0 . The final combination ofXandS 0 being the same, while different fromZ, cannot happen by the definition ofZ. Regardless of which case applies, an optimal policy isD= W· ∏ m i=1 O i , which yields a utility of1. Now consider the intervention that setsX= 0, and con- sequentlyW X=0 =Z X=0 = 0. Without the information inW,S m is independent of(Pa D ) X=0 and hence indepen- dent ofD X=0 regardless of the selected policy. 8 Therefore, E π [U D X=0 ] =E π [S m ·D X=0 ] =E π [S m ]·E π [D X=0 ] = 0 for every policyπ. In particular, for any optimal policyπ ∗ , E π ∗ [U D X=0 ]6=E π ∗ [U] = 1so there must be someεsuch thatD X=0 (ε)6=D(ε). Therefore, there is a response incen- tive onX. With this result we can now prove the completeness of the value of information criterion. Proof of Lemma 27 (VoI criterion completeness).IfX6⊥ U D |(Pa D ∪ D \ X)thenXis a requisite obser- vation inG X→D (whereG X→D isGmodified to include the edgeX→Dif the edge does not exist already) and X→Dis a path in the minimal reductionG min X→D . By Lemma 28, there exists a modelM X→D compatible with G X→D that has a response incentive onX. If every optimal policy forM X→D depends onXthen it must be the case thatV ∗ (M X6→D )<V ∗ (M X→D ). C.3 Value of Control Criterion The Value of Control section contains a proof of the sound- ness of the value of control criterion. We complete the proof of Theorem 16 by showing that the criterion is also complete. 8 Note that ifm= 0andS 0 isZthen(S m ) X=0 = 0but the fact that this is predictable is irrelevant because we compareD X=0 against the pre-intervention variableS m , which remains indepen- dent of(Pa D ) X=0 . Lemma 29(VoC criterion completeness).IfX99KUin the minimal reductionG min of a single-decision CIDGand X6∈DthenXhas positive value of control in at least one SCIMMcompatible withG. Proof.Assume thatX99KUforX /∈ Dand fix a par- ticular directed pathρfromXto some utilityU∈U. We consider two cases depending on whetherDis inρand con- struct a SCIM for each: Case 1:ρdoes not containD.Let the domain of all vari- ables be0,1. Set all exogenous variable distributions arbi- trarily. SetFsuch thatX= 0with every other variable along ρcopying the value ofXforward. All remaining variables are set to the constant0. With this model, an interventiong X that setsXto1instead of0increases the total expected utility by1, which means there is an instrumental control incentive forX. Case 2:ρcontainsD.This implies that a directed path X→Dis present inG min so we can construct (a modified version of) the response incentive construction used in the proof of Lemma 28. We make one change: instead of starting withf X (·) = 1we start withf X (·) = 0. As noted in the response incentive completeness proof, this means thatS m is independent ofPa D so regardless of the policy the optimal attainable utility is0. If we perform the interventiong X (·) = 1then the attainable expected utility is1once again so the interventiong X strictly increases the optimal expected utility. C.4 Instrumental Control Incentive Criterion The Instrumental Control Incentive section contains a proof of the soundness of the instrumental control incentive crite- rion. We prove its completeness to finish the proof of Theo- rem 18. Lemma 30(ICI Criterion Completeness).If a single- decision CIDGcontains a path of the formD99KX99KU then there is an instrumental control incentive onXin at least one SCIMMcompatible withG. Proof.Assume thatGcontains a directed pathD=Z 0 → Z 1 → · →Z n =UwhereU∈UandZ i =Xfor somei∈ 0, . . . , n. We construct a compatible SCIM for which there is an instrumental control incentive onX. Let all variables along the pathZ 0 →. . .→Z n be equal to their predecessor, exceptZ 0 =D, which has no struc- ture function. All other variables are set to 0. In this model, U=D∈ 0,1and all other utility variables are always 0so the only optimal policy isπ ∗ (pa D ) = 1, which gives E π ∗ [U |Pa D =0] = 1. Meanwhile,U X d =dso ford= 0 we haveE π ∗ [U X d |Pa D =0] = 0. C.5 Counterfactual Fairness Theorem 14(Counterfactual fairness and response incen- tives).In a single-decision SCIMMwith a sensitive at- tributeA∈X, all optimal policiesπ ∗ are counterfactually unfair with respect toAif and only ifAhas a response incen- tive. Proof.We begin by showing that if there exists an optimal policyπthat is counterfactually fair, then there is no response incentive onA. To this end, let supp π (D|pa D ) =d|Pr π (D=d|pa D )>0 ∀a,supp π (D a |pa D ) =d|Pr π (D a =d|pa D )>0 be the sets of decisions taken byπwith positive probability with and without an intervention onA. As a first step, we will show that for anyε∈dom(E)and any interventionaonA, supp π ( D|Pa D (ε) ) =supp π ( D a |Pa D (ε) ) .(5) By way of contradiction, suppose there exists a decision d∈supp π ( D|Pa D (ε) ) π ( D a |Pa D (ε) ) .(6) Sinced∈supp π ( D|Pa D (ε) ) , we have Pr π ( D=d|Pa D (ε), A(ε) ) >0.(7) And sinced6∈supp π ( D a |Pa D (ε) ) , there exists noε ′ with positive probability such thatPa D (ε ′ ) =Pa D (ε),A(ε ′ ) = A(ε), andD a (ε ′ ) =d. This gives Pr π ( D a =d|Pa D (ε), A(ε) ) = 0.(8) Equations (7) and (8) violate the counterfactual fairness prop- erty, Definition 13, which shows that (6) is impossible. An analogous argument shows thatd∈supp π ( D a |Pa D (ε) ) \ supp π ( D|Pa D (ε) ) also violates the counterfactual fairness property Definition 13. We have thereby established (5). Now select an arbitrary ordering of the elements of dom(D)and define a new policyπ ∗ such thatπ ∗ (pa D )is the minimal element of supp π (D|pa D ). Thenπ ∗ is optimal becauseπis optimal. Further,π ∗ will make the same deci- sion in decision contextsPa D (ε)andPa D a (ε)because of (5). In other words,D a (ε) =D(ε)inM π ∗ for the optimal pol- icyπ ∗ , which means that there is no response incentive on A. Now we prove the reverse direction — that if there is no response incentive then some optimalπ ∗ is counterfactually fair. Choose any optimal policyπ ∗ whereD a (ε) =D(ε)for allε. Since an interventionacannot changeDin any setting, Pr(D a =d| ·) = Pr(D=d| ·)for any condition and any decisiond, henceπ ∗ is counterfactually fair.

Instant research discovery