The Role of Causal Features in Strategic Classification for Robustness and Alignment

Unknown

Conceptio › Archive › arXiv CS

arXiv CSopen access

The Role of Causal Features in Strategic Classification for Robustness and Alignment

Unknown · 2026 · arxiv_cs

arXiv CS · Papers · License: Open Access · 2026

Open Source ↗Direct PDF ↓

machine learning, deep learning, neural networks

The Role of Causal Features in Strategic Classification for Robustness and Alignment

António Góis∗ 1 Nidhi Hegde2,4

Sophia Günlük∗ 1 Simon Lacoste-Julien1,2

Mila & Université de Montréal Faculty of Computer Science, Technion - Israel Institute of Technology

arXiv:2605.27163v1 [cs.LG] 26 May 2026

Abstract In strategic classification, an institution (e.g., a bank) anticipates adaptation from users who change their features to increase utility in a classification task (e.g., loan repayment). Since a key challenge is the distribution shift induced by users, we turn to causal models, which have been shown to bound the worstcase out-of-distribution (OOD) risk, and establish several new results that link causality and strategic classification. First, we show that causal classification leads to optimal classification error after any sufficiently large adaptation, when the noise is bounded in a certain way. Second, when these assumptions do not hold, we show OOD crossentropy risk of optimal classifiers decomposes into an OOD bias term and a term arising from not using all observable features, allowing us to understand when causal classifiers have an advantage. Finally, we show that the use of causal features can allow alignment of long-term incentives between institutions and users, contrasting with previous work that highlights social costs of such approaches. We validate our theory empirically on synthetic data, finding that our results predict behavior in practice.

INTRODUCTION

As classifiers are deployed in decision-making contexts, it becomes increasingly important to study ∗ Equal contribution, alphabetical order. Proceedings of the 29th International Conference on Artificial Intelligence and Statistics (AISTATS) 2026, Tangier, Morocco. PMLR: Volume 300. Copyright 2026 by the author(s).

Nir Rosenfeld3 Dhanya Sridhar1,2

Canada CIFAR AI Chair Dept. of Computing Science, Amii & University of Alberta, Canada 4

strategic classification (Hardt et al., 2016), where decision-makers seek to maximize accuracy as agents adapt their features in response to classifications. As we develop better algorithms under varying assumptions about adaptation (Levanon and Rosenfeld, 2022; Kleinberg and Raghavan, 2018), there are growing concerns about negative social impact on the agents who adapt to these systems, whether outcomes are static (Milli et al., 2019) or dynamic (Góis et al., 2025). When agents adapt, depending on the underlying causal model (Horowitz and Rosenfeld, 2018; Miller et al., 2020), some changes improve agent outcomes while others constitute gaming the classifier, worsening classification error. In this paper, we study whether classifiers can maintain accuracy without sacrificing alignment with predicted agent’s goals. Taking inspiration from the link between causal models and robustness to distribution shifts (Peters et al., 2017), we explore the impact of causal features in strategic classification, both as a reliable predictor and as an incentive. We consider settings where an unobserved variable confounds prediction by introducing spurious features that do not cause the outcome of interest. We first show that a causal classifier can reach optimal loss when the unobserved variable introduces ambiguity in a bounded region of the input space. Intuitively, if agents are willing to adapt enough, a causal classifier will move points away from ambiguous regions, reducing error, while classifiers that exploit spurious correlations run the risk of gaming. Such classifier is optimal not only against a specific adaptation, but to any large-enough adaptation. Next, we show that even without this bounded influence from the latent, causal features lead to bounded error under changing distributions. We then study how the predicted population is impacted, when an institution switches from vanilla prediction to methods that leverage agent adaptation – dubbed a strategic institution. Although myopic agents concerned with shortterm utility may perceive a drop in utility, considering

The Role of Causal Features in Strategic Classification for Robustness and Alignment

long-term consequences of gaming behavior shows that agents may be better off interacting with a strategic institution. Surprisingly, this can be the case even if the agents’ short-term gain surpasses the long-term cost, when gaming. This shows that, unlike previous work where causal influence of X on Y was not considered, strategic classification may improve agents’ utility instead of imposing a social cost.

RELATED WORK

This paper contributes to the body of work on strategic classification (Hardt et al., 2016), where utilitymaximizing agents are incentivised to adapt their features in response to deployed models, changing the distribution of their features and potentially even outcomes (Kleinberg and Raghavan, 2018; Miller et al., 2020; Perdomo et al., 2020). Work on strategic classification largely focuses on developing algorithms in service of maintaining predictive performance (Dong et al., 2017; Chen et al., 2019; Ahmadi et al., 2020; Levanon and Rosenfeld, 2021), and studying the social costs and (mis)aligned incentives of strategic institutions (Kleinberg and Raghavan, 2018; Bechavod et al., 2021; Levanon and Rosenfeld, 2022; Vo et al., 2024; Chen et al., 2025). Our work most closely follows papers that consider both incentive alignment and robust prediction through the lens of causal models (Shavit et al., 2020; Rosenfeld et al., 2020). Most similar to this work is Horowitz and Rosenfeld (2018), who show that causal classifiers face covariate shift while general classifiers face shifts due to predicted agents gaming. We also build upon Miller et al. (2020) who show that incentivising improvement requires learning causal features. We go beyond these results by establishing a richer range of implications of causal classifiers for strategic classification, from optimality under bounded ambiguity to robustness under no strong assumptions. We further link causal classification to aligned incentives. Milli et al. (2019) show that strategic classification harms social welfare for the predicted, when there is no causal relation between features and outcomes. Somerstep et al. (2024) study agents who can directly manipulate their outcome, identifying conditions where they are positively impacted by strategic classification, in labour markets. We study social welfare when agents can manipulate their features, and outcomes change indirectly via a causal mechanism. Our work also builds extensively on a long line of work on causality and out-of-distribution (OOD) generalization starting with Peters et al. (2016, 2017); HeinzeDeml et al. (2018) that establishes that causal models have bounded OOD risk since they remain invariant to changes in the feature distribution. Much of work in this area focuses on using data from multiple distri-

Figure 1: Causal graph for our data generating process. U is an unobserved confounder between outcome Y and spurious feature Xs . Xc is a direct cause of Y . butions to discover causal models based on the invariance principle (Arjovsky et al., 2019; Perry et al., 2022; Eastwood et al., 2022; Rojas-Carulla et al., 2018). However, Magliacane (2018) go further and show that regression under domain shift entails a trade-off: restricting to invariant features guarantees robustness but may sacrifice predictive information, while using all features risks unbounded error in the target domain. Our work follows mostly closely from this contribution. We establish this tradeoff in the case of strategic classification, analyzing directly the postadaptation cross entropy loss.

SETTING

In strategic classification, we consider institutions that deploy classifiers to make decisions, and predicted agents that strategically respond to these classifications. We start by considering the causal model in Figure 1, which relates d input features and the binary outcome Y realized by a predicted agent. In this model, a set of causal features Xc ∈ Xc ⊆ Rdc directly influence the value of the outcome Y ∈ {0, 1} while spurious features Xs ∈ Xs ⊆ Rds are only predictive of the outcome Y due to confounding from an unobserved variable U ∈ U. The binary outcome Y is: Y = 1{ysco (xc ,u)≥0}

Y ∼ Bernoulli σ(ysco (xc , u)) .

(1)

That is, the outcome is a deterministic or stochastic (potentially nonlinear) function of its causal parents, as specified by the real-valued function ysco (xc , u), and σ refers to the standard sigmoid function. We refer to the set of all observed features as X ∈ X ⊆ Rd . This assumed causal model captures many decision-making scenarios. Consider predicting whether an applicant can pay back their loan: an agent’s income might be causally linked to loan defaulting (the outcome), while an agent’s level of education might only spuriously predict defaulting due to latent common causes like socioeconomic status. Typically, the institution seeks a classifier f : X →

Góis, Günlük, Rosenfeld, Hegde, Lacoste-Julien, Sridhar

R based on all available features and make decisions using the function h : X → {0, 1} such that, ŷ = h(x) = 1{f (x)≥0}

(2)

In standard classification, we want a classifier fˆ(x) that minimizes classification errors (i.e., 0-1 loss), fˆ ∈ arg min E [ℓ0−1 (1{f (x)≥0} , y)]. f ∈F

x,y

(3)

Since the 0-1 loss is costly to minimize directly, we typically deploy classifiers fˆ(x) that minimize a surrogate loss function, e.g., the cross entropy loss that we study later. We also distinguish between two families of classifiers in this work: F, the family of classifiers that use all available features, and Fcausal (⊂ F) which is a subset of classifiers that only use the causal features (essentially masking the spurious ones). In the strategic classification setting, however, after the institution deploys the fˆ(x) and its corresponding decision rule h(x), the predicted agents respond to the classification they receive. Each predicted agent gains utility δ from a positive prediction (ŷ = 1), and 0 utility from ŷ = 0. Hence, a utility-maximizing agent spends at most a budget δ to flip ŷ = 0 into ŷ = 1. Expanding on the typical assumption that δ is static, we provide results that are valid both for a static δ and for any δ ′ > δ, i.e. under a shift in the agents’ budget. This represents, for instance, malicious or highly motivated actors – such as an applicant who has a lot to gain by getting a loan approved – who will go to greater lengths to adjust their features than what is observed in historical training data. Given knowledge of fˆ and a cost function c(x, x′ ) : X ×X → R≥0 , agents with ŷ = 0 compute the cheapest intervention over x that flips their prediction: ∆h (x; δ) : X × F × R≥0 → X ≜ arg max δh(x′ ) − c(x, x′ )

(4)

x′ ∈X

In the rest of the paper we assume a tie-breaking rule, making this solution set a singleton. Since predicted agents can take actions to change their features in order to improve their outcome, as described above, classifiers induce new distributions over the population. We denote the post-adaptation distribution (after one step of adaptation) as D(f,δ) , where D is the original distribution, f is a classifier that induces the adaptation, and δ is the agents’ budget. Formally, D(f,δ) is obtained by mapping each point (x, y) from D to its adapted counterpart, i.e. (x, y) 7→ (∆h (x), y(∆h (x), u)),

(5)

where the notation y(∆h (x), u) is the counterfactual outcome after adaptation given observed features x

and the unobserved value u. In the running example, this counterfactual reflects whether a particular loan applicant would repay their loan if they increased their salary from x to x′ , given their unobserved socioeconomic status u. An institution that is strategic anticipates the responses of the predicted agents, and seeks a classifier f ∗ (x) that minimizes the classification error after one step of adaptation. That is, the institution wants to minimize their post-adaptation 0-1 loss, Ex,u [ℓ0−1 (h(∆h (x)), y(∆h (x), u))].

(6)

Main idea. The goal of this paper is to shed light on how the causal model (in Figure 1) of the outcome is related to the optimal post-adaptation classifier f ∗ (x). At a high-level, we leverage two key insights to develop results about the role of causal features in strategic classification. First, when predicted agents change their causal features, they can improve their postadaptation outcome y(∆h (x), u) (Miller et al., 2020). Second, causal features are related to the outcome y by the mechanism ysco (xc , u) that remains invariant to distribution shifts. In contrast, the relationship between spurious features and the outcome changes as predicted agents adapt these features (Magliacane, 2018). We show that by using causal features, institutions can obtain good post-adaptation loss and align their incentives with those of the predicted agents.

OPTIMALITY OF CAUSAL CLASSIFIERS AFTER ADAPTATION

We start by considering the setting where the outcome Y is a deterministic function of the causal features Xc and the unobserved variable U , i.e., y = 1{ysco (xc , u) ≥ 0}. For ease, in this section, we will directly refer to the decision function h(x) = 1{f (x) ≥ 0} as the classifier. In this setting, we study the impact for an institution when it deploys a causal classifier: a classifier that uses only the causal features Xc , variables that are invariant predictors of the outcome. We prove that, under some assumptions, causal classifiers h(xc ) lead to zero post-adaptation 0-1 loss ( E [ℓ0−1 (h(∆h (xc ; δ)), y)] = 0). Furthermore they rexc ,u

main optimal to any budget δ ′ > δ, and are in this sense robust to all large-enough adaptations. To show this result, intuitively, we note that the unobserved variable U creates ambiguity in the outcome values. If this ambiguity can be limited to a specific region in the input space X ⊆ Rd , and predicted agents have a sufficient budget δ to move out of this region, then by deploying a causal classifier h(xc ), an institution induces previously misclassified agents to improve into

The Role of Causal Features in Strategic Classification for Robustness and Alignment

We first define the region of causal feature space Xc where the outcome Y is uncertain, to characterize its boundaries and conditions to move points outside it. Definition 4.1. (Domain with ambiguous outcome) The domain with ambiguous outcome, Xambiguous ⊆ Xc , is the subset of causal features where the unobserved u can flip the outcome’s sign. A point xc is considered ambiguous if we can find two latent states, u, u′ ∈ U, such that ysco (xc , u) ≥ 0 but ysco (xc , u′ ) < 0. In what follows we’ll study the scenario where this region is bounded, i.e., Xc \ Xambiguous ̸= ∅. We begin by introducing an assumption on the distance from any ambiguous xc to a non-ambiguous xc , in Lp -norm. Assumption 4.2. (Ambiguity compensation by δ) We assume that any ambiguous point can be pushed to a non-negative outcome using a perturbation of bounded size. Formally, there exists a finite constant δ ≥ 0 such that for any ambiguous feature xc ∈ Xambiguous , there is a vector v ∈ Rd bounded by ∥v∥p ≤ δ that satisfies ysco (xc + v, u) ≥ 0 for all u. The intuition for this assumption is that each data point has the possibility to improve its true outcome given enough effort. Improvement is only possible when effort is applied to features xc with a causal impact on the outcome y. Alternatively, applying effort to features xs that do not affect y but change the prediction consists in gaming. This is close in spirit to recourse, but our assumption applies to the true generative process whereas in recourse it is with respect to the classifier. To help characterize an optimal classifier, we rely on the concept of an Os -nondecreasing function (Boyd and Vandenberghe, 2004) defined with respect to an orthant Os in Rd (where an orthant is a subset of Rd as detailed in Appendix A). We define a partial ordering such that x ⪯Os y if and only if the difference y − x belongs to Os . A function f is then considered Os -nondecreasing when x ⪯Os y implies f (x) ≤ f (y). Similarly, we write x ≺Os y to indicate strict inequality, meaning y − x lies in the interior of the orthant, denoted int(Os ). Assuming ysco is Os -nondecreasing with respect to xc , we define the decision boundary ∂u for a specific latent state u as the set of features xc where the score is exactly zero (ysco (xc , u) = 0). Note that while ysco

∂U = 0 ∂U = 1 ∂upp

0.8

0.6

Xc2

true positives. Conversely, if the institution deploys a classifier that uses spurious features, predicted agents can waste their adaptation budget δ on feature changes that do not affect their true outcome value, thereby gaming and only contributing to false positives postadaptation. We show that this optimality holds even when we consider post-adaptation cross-entropy loss.

ysco ≥ 0 0.4

0.2

ambiguou s

ysco < 0

∂low

max-gap

} 3

Xc1

Figure 2: Example of bounds ∂ for an O-nondecreasing ysco (xc , u). Here Os is the positive orthant, so increasing either XC1 or XC2 leads to an improvement in ysco . The unobserved U ∈ {0, 1} is a binary variable in this example. ∂U =0 and ∂U =1 show the boundary for each u, where ysco flips between negative and positive values. From them we can determine the overall boundaries ∂upp , ∂low , delimiting the ambiguous region where U can flip the sign of ysco . The max-gap is determined from ∂upp and ∂low .

does not need to be Os -nondecreasing with respect to u, the orthant Os must remain S the same across all values of U . We then let B = u ∂u denote the union of all such boundaries over u. This allows us to define the bounds of the ambiguous domain: Definition 4.3. (Upper and lower bound of Xambiguous ) We define the upper bound of the ambiguous domain, denoted ∂upp , as the subset of boundary points xupp ∈ B for which no strictly larger point belongs to B. Formally, the intersection of the shifted interior orthant int(xupp + Os ) with the boundary union B is empty. Similarly, the lower bound ∂low is the subset of boundary points xlow ∈ B for which no strictly smaller point belongs to B, meaning the intersection int(xlow − Os ) ∩ B is empty. Using the previous assumptions together with the continuity of ysco , we can show that ∂upp and ∂low separate the ambiguous domain from two non-empty regions of definitive outcomes. Lemma 4.4. (Partition of Xc through ∂upp and ∂low ) Assume y = sign(ysco ), the score ysco is continuous and Os -nondecreasing with respect to xc , and Assumption 4.2 holds. The bounds ∂upp and ∂low partition the causal feature space Xc into three disjoint, non-empty subsets: the ambiguous domain Xambiguous , an unambiguously positive region, and an unambiguously negative region. Specifically, for any point xc ∈ Xc : 1. If there exists a point xupp ∈ ∂upp such that xupp ⪯Os xc , then xc is outside the ambiguous domain and yields a non-negative score for all latent states (ysco (xc , u) ≥ 0 for all u).

Góis, Günlük, Rosenfeld, Hegde, Lacoste-Julien, Sridhar

2. If there exists a point xlow ∈ ∂low such that xc ≺Os xlow , then xc is outside the ambiguous domain and yields a strictly negative score for all latent states (ysco (xc , u) < 0 for all u). The proof is provided in Appendix A, Corollary A.6. Additionally, we define the max-gap as the maximum Lp distance from any point in the ambiguous domain to the upper bound ∂upp . Formally, this is given by max max min ∥xupp − xlow ∥p . In the following u

xlow ∈∂u xupp ∈∂upp

lemma, we establish that this gap is strictly bounded: Lemma 4.5. (Bounded max-gap in Xambiguous ) For every point xc in the ambiguous domain Xambiguous , the shortest Lp distance to the upper bound ∂upp is at most the max-gap, which is guaranteed to be finite. That is, for any xc ∈ Xambiguous :

min

xupp ∈∂upp

max max u

min

||xupp − xc ||p ≤

xlow ∈∂u xupp ∈∂upp

||xupp − xlow ||p < +∞

The proof is provided in Appendix A.7. Note that this result is well-defined following Lemma 4.4, which shows that the boundaries ∂upp , ∂low , and each specified subset of Xc are non-empty sets. We show a visualization of the concept of Xambiguous and its boundaries in Figure 2 for the setting of Xc = R2 and U = {0, 1}. Further, assuming the cost of adapting features is an Lp -norm, we prove there exists a causal classifier which achieves zero ℓ0−1 post-adaptation, for all adaptations where δ is high enough. This is achieved by moving points away from Xambiguous and anticipating the adaptation’s impact on post-adaptation outcome y: Theorem 4.6. (Causal ℓ0−1 -optimality) Suppose the assumptions of Lemma 4.4 hold and the adaptation cost is an Lp -norm. Then there exists a finite threshold e ∈ R and a causal classifier hc ∈ Hcausal ⊂ H (whose outputs are unaffected by spurious features xs ) such that for any adaptation budget δ ≥ e, the expected postadaptation 0-1 loss is strictly zero. That is,

to game (introducing false positives) rather than improve to true positives. Hence this post-adaptation optimal classifier hc (x) remains optimal even if agents adapt with δ ′ > δ at a subsequent time point. This is further validated in the empirical studies, and in Appendix E we also illustrate this mathematically with an example, showing that the causal classifier characterized by Theorem 4.6 can remain optimal even outside the range δ ∈ [max-gap, +∞) proved here. In that example we show a phase transition, where a causal classifier suddenly becomes optimal as δ increases. Additionally, we note that the same optimality result holds for cross-entropy in this setting. For a ˆ learned probability estimator f (x) : X → [0, 1], define ˆ ˆ ℓCE (f (x), y) ≜ − y log f (x) + (1 − y) log(1 − fˆ(x)) . Corollary 4.7. (Causal cross-entropy optimality under bounded Xambiguous ) Under the assumptions of Theorem 4.6, we have zero ℓCE (fˆ(x), y) for all postadaptation points, using a large-enough δ. Proof in Appendix B.

ROBUSTNESS OF CAUSAL CLASSIFIERS IN STOCHASTIC SETTINGS

We now consider the setting where the outcome Y is a stochastic function of the causal features Xc and the unobserved variable U , i.e., there is some function of causal parents g(xc , u) ≜ P (Y = 1|xc , u) = σ(ysco (xc , u)). Unlike in the previous setting where we consider a bounded ambiguous region where the latent variable U influences the value of the outcome Y , here, without further assumptions, the latent variable is informative about the outcome in all regions of the input. This means that we cannot simply deploy a causal classifier f ∈ Fcausal to move predicted agents out of the ambiguous region to achieve optimal loss post-adaptation. Nevertheless, in this setting, we show a different advantage of causal classifiers: if we only have access to historical data before observing agents’ adaptation, by training causal classifiers, we can incur bounded CE loss after the classifier is deployed, while spurious classifiers risk arbitrarily bad post-adaptation CE loss. We start by defining optimal classifiers,

Ex,u [ℓ0−1 (hc (∆hc (x; δ)), sign(ysco (∆hc (x; δ), u)))] = 0.

fˆ = arg min ED [KL (g(xc , u)∥f (x))]

The proof is provided in Appendix A, Theorem A.9.

fˆδ∗ = arg min ED(fˆ,δ) [KL (g(xc , u)∥f ∗ (x))] f ∗ ∈F

f ∈F

The essence of this result is that the causal classifier works by being overly demanding but incentivising false negatives in Xambiguous to adapt, turning them into true positives. Intuitively, a spurious classifier wastes effort in the sense that users use their budget

(7)

The classifier fˆ minimizes the cross entropy loss on the training data – that is, the historical data obtained before agents adapt to a deployed classifier. The classifier fˆ∗ refers to the classifier that minimizes cross

The Role of Causal Features in Strategic Classification for Robustness and Alignment

entropy loss on the distribution induced by deploying the classifier fˆ. That is, we consider samples from the ˆ distribution D(f ,δ) . With classifiers defined this way, we can now analyze the impact of minimizing CE loss on training data to generalize to samples that result from predicted agents adapting to classifications. First, we show that the CE loss post-adaptation follows a decomposition that gives us insights into the behavior of causal classifiers. Lemma 5.1. (Decomposition of CE loss postadaptation, informal) Under mild assumptions on measurability and support of the classifiers, postadaptation cross-entropy loss of a classifier fˆ that was trained on pre-adaptation data with family F can be decomposed as: h i LCE (fˆ, δ) = ED(fˆ,δ) KL g(xc , u)∥fˆδ∗ (xc , xs ) {z } | incomplete information error

" + ED(fˆ,δ) g(xc , u) log

| +

fˆδ∗ (xc , xs ) fˆ(xc , xs )

# 1 − fˆδ∗ (xc , xs ) +(1 − g(xc , u)) log 1 − fˆ(xc , xs ) {z } transfer error

E (fˆ,δ) [H (g(xc , u))] {z } |D

entropy of post-adapt distribution

where H(X) is the entropy of X. We derive this decomposition in Appendix C.1. Here, we extend results from Magliacane (2018) who derive a similar tradeoff when considering the bias of classifiers that are trained on different distributions. In the next result, we consider what happens when we restrict our hypothesis class to functions f ∈ Fcausal versus when we consider all functions including those that use spurious features. Theorem 5.2. (Robustness of causal classifiers) For a classifier fˆ in the family Fcausal of causal classifiers, assuming that it is the optimal classifier in the sense of Equation (7), the post-adaption cross-entropy loss LCE (fˆ, δ) is bounded by the sum of entropy terms H(U ) + H(Y |X). The post-adaptation loss of an optimal classifier fˆ in the family of spurious classifiers Fall cannot be bounded due to non-zero transfer error. We derive this result in Appendices C.3 and C.4. When we consider classifiers that only use causal features, i.e. f ∈ Fcausal , the pre-adaptation optimal classifier fˆ is the same as the post-adaptation optimal classifier fˆδ∗ , avoiding transfer error. Intuitively, this is because the causal relationship between Xc and the

outcome Y remains invariant to changing the feature distribution P(Xc ), a fact that we formalize in Appendix C.3.2. However, the optimal causal classifier fˆ incurs incomplete information error by discarding spurious features, which is equivalent to the conditional mutual information between the latent variable U and Y given causal features Xc , and bounded by the entropy of U . In contrast, in Appendix C.4 we show that a classifier fˆ that uses all the features avoids some incomplete information error (bounded by the entropy of U conditioned on Xs in the post-adaptation distribution). This is because even after predicted agents intervene on their spurious features Xs , changing its association with the latent variable U , it may still remain informative about U and thus, the outcome Y (which relies on the value of U ). However, a classifier that uses all features incurs transfer error exactly because of the intervention that agents perform on their features: by changing their spurious features Xs , they can arbitrarily change how well the outcome is predicted by these features. Thus, the transfer error of a spurious classifier cannot be bounded. In the Appendix C.4.3, we further analyze thresholded classifiers and establish conditions under which transfer error can be made arbitrarily large. Note that defining the classifiers fˆ and fˆ∗ as optimal classifiers before and after adaptation is key to this interpretation, since if these classifier were not optimal, the transfer error could be nonzero even for a causal classifier. Finally, note that this analysis can be extended to consider the post-adaptation loss of classifiers fˆ that are trained on data after historical deployments where agents had a different budget δ ′ , which we show in Appendix C.2.

INCENTIVE ALIGNMENT

We now consider the question of how agents are impacted in a strategic setting and whether their interests are aligned with the institution. If Y is static (i.e. there is no causal effect of X on Y ) and agents seek positive predictions h(∆h (x)) = 1, Milli et al. (2019) show that strategic classification harms utility of predicted agents. Levanon and Rosenfeld (2022) study the case where alignment is built-in – the predicted agents gain from accuracy just like the institution, and Y is static. Miller et al. (2020) provide an equivalency between agent improvement and causal discovery, but leave unclear whether the agents and/or the institution benefit from this improvement. This leaves unanswered the question of whether strategic classification can benefit the predicted agents, when X causally affects Y and agents seek positive predictions Ŷ = 1.

Góis, Günlük, Rosenfeld, Hegde, Lacoste-Julien, Sridhar

We begin by defining the long-term goals of the institution and of the predicted agents. An agent with a positive prediction (h(∆h (x)) = 1) has an immediate gain, but may suffer a loss in the long-term if its true outcome is negative (h(∆h (x)) = 1 ∧ y(∆h (x), u) = 0). For instance an agent can get a home loan approved but later lose it by defaulting, or be accepted to college but then fail courses. Analogously an institution aims to minimize ℓ0−1 , but in the long-term may benefit more from true positives (TPs) than true negatives (TNs) — banks need to identify good borrowers and universities need good students. We now define longterm rewards or utilities. Definition 6.1. (Predicted agents’ long-term utility) Agents gain δ from a positive prediction, and we let δ2 denote the loss when agents obtain a false positive. Setting δ2 = 0 represents a short-term goal.

rp (h, x, u) =δh(∆h (x)) − c(x, ∆h (x)) − δ2 h(∆h (x))(1 − y(∆h (x), u)) Definition 6.2. (Institution’s long-term utility) Institution gains from lowering post-adaptation 0-1 loss ℓ0−1 and, among correct predictions, prefers true positives over true negatives over the long term. We call this an ϵ-advantage where ϵ denotes a loss in the institution utility due to true negatives. When ϵ = 0, the utility represents a short-term goal. ri (h, x, u) = − 1{h(∆h (x)) ̸= y(∆h (x), u)} − ϵ1{h(∆h (x)) = y(∆h (x), u) = 0} We are interested in understanding how these two goals interact in the strategic setting, where agents react to predictions by modifying X and the institution anticipates agent modifications. For this analysis we introduce the notion of h-change, the expected change in utility when the classifier is changed. Definition 6.3. (h-change) Expected change in utility when switching from classifier h into h′ , for role k, where k ∈ {p, i} is predicted agent p or institution i:

the goals of agents whose Y = 1 but not whose Y = 0, in the following sense (proof in Appendix F.2): ∆rp|Y =1 (h′ , h) > 0 ⇐⇒ ∆ri|Y =1 (h′ , h) > 0 ∆rp|Y =0 (h′ , h) < 0 ⇐⇒ ∆ri|Y =0 (h′ , h) > 0 Intuitively, agents in the Y = 0 group are either TNs or false positives (FPs). Since in this static setting, agents cannot improve their outcomes, institution only gains utility from an h′ that switches FPs into TNs, which strictly lowers agents’ utility. We now consider the more general case where agents can adapt ∆h (x) ̸= x, and hence change y(∆h (x), u). The institution becomes strategic when it switches from a classifier that wrongly assumes agents are static (hpre ), into one considering agents’ adaptation (hpost ). Note that, by definition, ∆ri (hpost , hpre ) ≥ 0. There is alignment if, as the institution becomes strategic, predicted agents also benefit. Definition 6.5. (Aligned incentives) Consider hpre , the classifier that maximizes Ex,u [ri (h, x, u)] wrongly assuming that ∆h (x) = x, and hpost maximizing Ex,u [ri (h, ∆h (x), u)] with the correct ∆h (x) (i.e. postadaptation). We say that incentives are aligned if: ∆rp (hpost , hpre ) ≥ 0 To study short-term alignment when agents are strategic, we first consider the set of pre-adaptation x that adapted towards a point ∆h (x). We define it as its ′ d ′ preimage ∆−1 h (x; δ) := {x ∈ R : ∆h (x ; δ) = x}. The next lemma shows that by assuming X has support over all values that could have adapted given δ, short-term goals (δ2 = ϵ = 0), and a flexible enough H, fewer points receive h(x) = 1 post-adaptation. Lemma 6.6. (Support over positive predictions) For h(x) = 1{f (x) ≥ 0} let its boundary be ∂h = {x ∈ X : f (x) = 0}. Assume full support over points pre ) ∪ that can adapt towards hpre and hpost : ∆−1 hpre (∂h −1 post ∆hpost (∂h ) ⊂ X , and δ2 = ϵ = 0. For a flexible enough hypothesis family H we have (proof in F.2):

∆rk (h′ , h) = Ex,u [rk (h′ , ∆h′ (x), u)] − Ex,u [rk (h, ∆h (x), u)] Before we consider the case of strategic agents, we build intuition by first considering static agents that can never adapt, ∆h (x) = x (c(·) → +∞), and the setting of short-term goals (δ2 = ϵ = 0). Proposition 6.4. (Static alignment) Let ∆rk|Y =y (h′ , h) be the h-change for the subpopulation Y = y (F.1). Assume ∆h (x) = x and δ2 = ϵ = 0. For any pair of classifiers (fˆ′ , fˆ), institution’s goals match

{x ∈ X : hpost (x) = 1} ⊂ {x ∈ X : hpre (x) = 1} Under the assumptions above, less agents receive a positive prediction under hpost than under hpre . With Lemma 6.6 and the assumptions above, we now show misalignment in short-term goals, where agent utility in the short-term decreases when institution becomes strategic. Proposition 6.7. (Short-term misalignment) Let ∆rp-short be the h-change for δ2 = 0, and hpost-short

The Role of Causal Features in Strategic Classification for Robustness and Alignment

be optimal for ϵ = 0. Under the assumptions of Lemma 6.6, we have (proof in F.2):

∆rp-short (hpost-short , hpre ) < 0. Having shown that there is misalignment in short-term goals, we now show that considering long-term goals allows incentives to be aligned. In particular, we show that maintaining a flexible H with ϵ = 0 for institution, and a high-enough δ2 for agents, enables alignment. Consider all four post-adaption cases, when switching from hpre into a more demanding hpost (F.2.2): • (maint) Maintained FP or TP at higher cost; • (impr) Switched from gaming to improvement (FP→ TP); • (TP→ N) Switched from TP into FN or TN; • (FP→ TN) Switched from FP into TN. For each of these Rcases, denote their densities as: P(maint) := P(x), and similarly x∈{maint} P(impr), P(TP → N), P(FP → TN). Define ∆c(x) ≜ c(x, ∆hpost R (x)) − c(x, ∆hpre (x)). Their total costs are c(all) := x∈X ∆c(x)P(x). Our next result shows a lower bound for the cost of FP, such that agents value enough switching from gaming to improvement, in order to have alignment. Proposition 6.8. (Long-term alignment) Considering a flexible enough H and ϵ = 0, having alignment requires (proof in F.2): c(all) + δ(P(TP → N) + P(FP → TN)) δ2 > P(impr) + P(FP → TN) We provide an example in Appendix E.2.3 where alignment occurs for any δ2 > c, for a constant c < δ. If we additionally consider ϵ > 0, interactions between δ2 , ϵ and alignment become more complex. We resort to simulations to illustrate their behaviour in Figure 4, and analyze mathematically an example in Appendix F.3. Note that, by our definition, we study alignment of optimal classifiers, which are causal classifiers under the conditions presented in § 4. Our theory does not exclude alignment with classifiers using both causal and spurious features, under different conditions. If no causal features are present, Milli et al. (2019) show that alignment is not possible for δ2 = 0.

Figure 3: 0-1 Loss. Left: As δ increases, the optimal classifier on simulated post-adaptation data puts progressively less weight on spurious feature Xs , until arriving at the optimal causal classifier characterized in Theorem 4.6. We averaged the optimal weight over three datasets of size N = 20000 to obtain the error bars. Right: When training and evaluation involve different levels of strategic shift δtrain and δtest , a classifier restricted to the causal feature recovers this optimal post-adaptation classifier, while one that exploits the spurious feature leads to poor performance when the shift is larger than anticipated.

EXPERIMENTS

We empirically validate our theoretical results with simulated data from the causal model in Figure 1 parameterized by a linear outcome and two features: u ∼ Bernoulli(pu ) xc ∼ N (0, σc2 ) xs = wu→s u + εs ,

εs ∼ N (0, σs2 )

ysco ≜ wc xc + wu u + b (det) y = 1{ysco (xc , u)} (stoch) y ∼ Bernoulli στ (ysco (xc , u)) . We assume L2 -norm for the agents’ adaptation cost c(x′ , x) ≜ ||x′ − x||2 , and they adapt following 4. Optimality under bounded ambiguity. First, we study Theorem 4.6, which says that with a bounded ambiguous region, a causal classifier can incur zero ℓ0−1 loss post-adaptation given that agents have enough budget δ to adapt away from the ambiguous region. To validate this result, we plot the coefficients of the classifier f ∗ ∈ F that achieves optimal postadaptation ℓ0−1 . Because the post-adaptation data distribution involves computing agents’ best response to a classifier, we cannot use gradient-based optimization to minimize post-adaptation loss. Instead, we perform a grid search over the coefficients of linear classifiers f and select the model that minimizes the loss on the post-adaptation distribution generated by some adaptation budget δ. The left panel in Figure 3 shows that with sufficient δ, optimal classifiers post-

Góis, Günlük, Rosenfeld, Hegde, Lacoste-Julien, Sridhar

adaptation choose to ignore the spurious feature, validating the result. Robustness to changing δ. The optimality result of Theorem 4.6 also holds if, after deployment, agents increase their adaptation budget so that δ ′ > δ. We study this in the right panel of Figure 3, by performing the same grid search procedure over two classifier families, one that considers all features and another that considers only causal features, both optimized for a fixed adaptation budget we refer to as δtrain . We evaluate the best classifier in each family on data generated by deploying that classifier but with a different, unseen δtest . We see that when δtest > δtrain , causal classifiers remain optimal as expected while spurious classifiers incur error due to differences between the train and test distributions. Additionally, the causal classifier is able to achieve zero loss after sufficiently large δtrain (i.e. ≥ max-gap, marked by the light grey line). In Appendix D.1, we also evaluate the implications of the result on robustness in Theorem 5.2, finding settings where causal classifiers’ zero transfer loss translates into advantages post-adaptation. Incentive Alignment. We explore how alignment (Definition 6.5) is impacted as we vary properties of agent utility rp (Definition 6.1) and institution utility ri (Definition 6.2). Specifically, as we increase δ2 , agents increasingly prefer to avoid false positives in the long term, and as we increase ϵ, institutions prefer true positives over true negatives. Following Proposition 6.8 we observe in Figure 4 there is a minimum δ2 to have alignment (∆rp > 0) for ϵ = 0. This is due to hpost preventing more gaming than hpre (TN→FP), which is more valued by agents with higher δ2 . As ϵ increases, hpre avoids TN by increasing FP, since it cannot anticipate agent adaptation. hpost can avoid TN by encouraging points to improve (TN→TP) instead of allowing gaming (TN→FP). A switch from gaming to improvement is valued by agents when δ2 is higher, whereas low δ2 makes agents care only about the total count of positive predictions (FP+TP). The dynamics between alignment and utilities are further explored in Appendix F.3. While these experiments were performed on fully synthetic data, we also have semi-synthetic results using real-world data for the observed feature in Appendix D.2 which also confirms our theoretical findings hold under real-world observed distributions.

CONCLUSION

In this work we characterize the role of causal variables in classification, when agents adapt to predic-

Figure 4: Simulation for δ = 0.3. As the institution anticipates agent adaptation to maximize ri (i.e., becomes strategic) agents’ utility rp can increase as well, depending on δ2 and ϵ. The grey dashed line indicates where rp stays constant, and to its right there is alignment (i.e. an increase in rp ). tions. Strategic classification is inherently a causal problem, since whether feature adaptation translates to outcomes depends on the underlying causal model. While previous work connects causality to robustness, we take a step further and identify conditions where causal classifiers are simultaneously optimal to a range of adaptations. Additionally, we show a nuanced picture of how the welfare of predicted agents is affected by strategic classification. While existing work highlights a social burden imposed on the population, we identify conditions where both predicted and predictor can be better off under strategic classification. This is possible due to the causal modeling aspect of our generative process. Assuming the existence of a bounded feature region where outcomes are ambiguous, and an acceptable effort that moves points out of such region, are limitations of our analysis. Therefore, future work should characterize optimality inside ambiguous regions under adaptation. Developing practical methods for strategic classification is also an important line of research. In this direction, designing learning algorithms that encourage data points to move outside ambiguous regions is also a promising avenue for future work. Acknowledgements This research was supported in part by the Canada CIFAR AI Chair program, by a grant from Samsung Electronics Co., Ltd., an unrestricted gift from Google, an NSERC Discovery Grant (RGPIN-2023-04869) and the Israel Science Foundation (grant no. 278/22). Simon Lacoste-Julien is a CIFAR Associate Fellow in the Learning in Machines & Brains program. We would like to thank Pedram Khorsandi for their feedback.

The Role of Causal Features in Strategic Classification for Robustness and Alignment

References Ahmadi, S., Beyhaghi, H., Blum, A., and Naggita, K. (2020). The strategic perceptron. CoRR, abs/2008.01710. Arjovsky, M., Bottou, L., Gulrajani, I., and LopezPaz, D. (2019). Invariant risk minimization. In arXiv preprint arXiv:1907.02893. Bechavod, Y., Ligett, K., Wu, Z. S., and Ziani, J. (2021). Gaming helps! learning from strategic interactions in natural dynamics. In Proceedings of the 38th International Conference on Machine Learning (ICML), volume 139, pages 756–765. PMLR. Boyd, S. P. and Vandenberghe, L. (2004). Convex optimization. Cambridge university press. Chen, Y., Estornell, A., Vorobeychik, Y., and Liu, Y. (2025). To give or not to give? the impacts of strategically withheld recourse. In Proceedings of the 28th International Conference on Artificial Intelligence and Statistics (AISTATS). PMLR. Chen, Y., Liu, Y., and Podimata, C. (2019). Grinding the space: Learning to classify against strategic agents. CoRR, abs/1911.04004. Dong, J., Roth, A., Schutzman, Z., Waggoner, B., and Wu, Z. S. (2017). Strategic classification from revealed preferences. CoRR, abs/1710.07887. Eastwood, C., Robey, A., Singh, S., von Kügelgen, J., Hassani, H., Pappas, G. J., and Schölkopf, B. (2022). Probable domain generalization via quantile risk minimization. In Proceedings of the 36th Conference on Neural Information Processing Systems (NeurIPS). Góis, A., Mofakhami, M., Santos, F. P., LacosteJulien, S., and Gidel, G. (2025). Performative prediction on games and mechanism design. In International Conference on Artificial Intelligence and Statistics, pages 1855–1863. PMLR. Hardt, M., Megiddo, N., Papadimitriou, C., and Wootters, M. (2016). Strategic classification. In Proceedings of the 2016 ACM conference on innovations in theoretical computer science, pages 111–122. Heinze-Deml, C., Peters, J., and Meinshausen, N. (2018). Invariant causal prediction for nonlinear models. Journal of Causal Inference, 6(2). Horowitz, G. and Rosenfeld, N. (2018). Causal strategic classification: A tale of two shifts. In Proceedings of the 40th International Conference on Machine Learning (ICML 2023). Kleinberg, J. M. and Raghavan, M. (2018). How do classifiers induce agents to invest effort strategically? CoRR, abs/1807.05307.

Levanon, S. and Rosenfeld, N. (2021). Strategic classification made practical. CoRR, abs/2103.01826. Levanon, S. and Rosenfeld, N. (2022). Generalized strategic classification and the case of aligned incentives. In International Conference on Machine Learning, pages 12593–12618. PMLR. Magliacane, S. (2018). Domain adaptation by using causal inference to predict invariant conditional distributions. In 32nd Conference on Neural Information Processing Systems (NIPS 2018). Miller, J., Milli, S., and Hardt, M. (2020). Strategic classification is causal modeling in disguise. In International Conference on Machine Learning, pages 6917–6926. PMLR. Milli, S., Miller, J., Dragan, A. D., and Hardt, M. (2019). The social cost of strategic classification. In Proceedings of the conference on fairness, accountability, and transparency, pages 230–239. Perdomo, J., Zrnic, T., Mendler-Dünner, C., and Hardt, M. (2020). Performative prediction. In International Conference on Machine Learning, pages 7599–7609. PMLR. Perry, R., von Kügelgen, J., and Schölkopf, B. (2022). Causal discovery in heterogeneous environments under the sparse mechanism shift hypothesis. In Proceedings of the 36th Conference on Neural Information Processing Systems (NeurIPS). Peters, J., Bühlmann, P., and Meinshausen, N. (2016). Causal inference using invariant prediction: identification and confidence intervals. In Journal of the Royal Statistical Society, Series B (Statistical Methodology), volume 78, pages 947–1012. Peters, J., Janzing, D., and Schölkopf, B. (2017). Elements of Causal Inference: Foundations and Learning Algorithms. MIT Press, Cambridge, MA. Rojas-Carulla, M., Schölkopf, B., Turner, R., and Peters, J. (2018). Invariant models for causal transfer learning. In Proceedings of the 21st International Conference on Artificial Intelligence and Statistics (AISTATS), volume 84 of Proceedings of Machine Learning Research, pages 164–173. Rosenfeld, N., Hilgard, S., Ravindranath, S. S., and Parkes, D. C. (2020). From predictions to decisions: Using lookahead regularization. In 34th Conference on Neural Information Processing Systems (NeurIPS 2020). Curran Associates, Inc. Shavit, Y., Edelman, B. L., and Axelrod, B. (2020). Learning from strategic agents: Accuracy, improvement, and causality. ArXiv, abs/2002.10066. Somerstep, S., Sun, Y., and Ritov, Y. (2024). Learning in reverse causal strategic environments with ramifications on two sided markets. In Kim, B., Yue, Y.,

Góis, Günlük, Rosenfeld, Hegde, Lacoste-Julien, Sridhar

Chaudhuri, S., Fragkiadaki, K., Khan, M., and Sun, Y., editors, International Conference on Learning Representations, volume 2024, pages 56533–56555. Tse, L. (2018). Credit risk dataset. https://www.kaggle.com/datasets/laotse/ credit-risk-dataset. Accessed: Nov. 25, 2025. Vo, K. Q. H., Aadil, M., Chau, S. L., and Muandet, K. (2024). Causal strategic learning with competitive selection. In Proceedings of the 38th AAAI Conference on Artificial Intelligence (AAAI 2024). AAAI Press.

Checklist 1. For all models and algorithms presented, check if you include: (a) A clear description of the mathematical setting, assumptions, algorithm, and/or model. [Yes] (b) An analysis of the properties and complexity (time, space, sample size) of any algorithm. [Not Applicable] (c) (Optional) Anonymized source code, with specification of all dependencies, including external libraries. [Not Applicable] 2. For any theoretical claim, check if you include: (a) Statements of the full set of assumptions of all theoretical results. [Yes] (b) Complete proofs of all theoretical results. [Yes] (c) Clear explanations of any assumptions. [Yes] 3. For all figures and tables that present empirical results, check if you include: (a) The code, data, and instructions needed to reproduce the main experimental results (either in the supplemental material or as a URL). [Yes] (b) All the training details (e.g., data splits, hyperparameters, how they were chosen). [Yes] (c) A clear definition of the specific measure or statistics and error bars (e.g., with respect to the random seed after running experiments multiple times). [Yes] (d) A description of the computing infrastructure used. (e.g., type of GPUs, internal cluster, or cloud provider). [Not Applicable] 4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets, check if you include:

(a) Citations of the creator If your work uses existing assets. [Not Applicable] (b) The license information of the assets, if applicable. [Not Applicable] (c) New assets either in the supplemental material or as a URL, if applicable. [Not Applicable] (d) Information about consent from data providers/curators. [Not Applicable] (e) Discussion of sensible content if applicable, e.g., personally identifiable information or offensive content. [Not Applicable] 5. If you used crowdsourcing or conducted research with human subjects, check if you include: (a) The full text of instructions given to participants and screenshots. [Not Applicable] (b) Descriptions of potential participant risks, with links to Institutional Review Board (IRB) approvals if applicable. [Not Applicable] (c) The estimated hourly wage paid to participants and the total amount spent on participant compensation. [Not Applicable]

The Role of Causal Features in Strategic Classification for Robustness and Alignment

The Role of Causal Features in Strategic Classification for Robustness and Alignment: Supplementary Materials

0-1 optimality of causal classifier under enough shift

We assume y is a deterministic function of (xc , u) given by sign(ysco (xc , u)). Note that knowing the deterministic effect of xc on ysco requires knowing u, which is an unobserved random variable. The function ysco (xc , u) is not explicitly defined here, and is not necessarily linear. Assumption A.1. (Sign function y) y(xc , u) ≜ 1{ysco (xc , u) ≥ 0}, where ysco : Rd × R → R Assumption A.2. (ysco continuity) ysco is continuous with respect to xc . Following Boyd and Vandenberghe (2004) we define an O-nondecreasing function. Let the collection of all orthants in Rd be O = {{x ∈ Rd : si xi ≥ 0, ∀ i ∈ [d]}, s ∈ {−1, +1}d }, and Os ∈ O be the orthant defined by s. We define a partial ordering on Rd as x ⪯Os y ⇔ y − x ∈ Os . Similarly we have x ≺Os y ⇔ y − x ∈ int(Os ). We say a function f : Rd → R is called O-nondecreasing if x ⪯Os y ⇒ f (x) ≤ f (y). We then assume ysco (xc , u) is O-nondecreasing with respect to xc , using the same orthant Os for all u ∈ U. Assumption A.3. (O-nondecreasing ysco ) ∃ Os ∈ O ∀ xc ∈ Xc , x′c ∈ Xc , u ∈ U : xc ⪯Os x′c =⇒ ysco (xc , u) ≤ ysco (x′c , u) We define Xambiguous as the subset of causal feature space where ysco can take both negative and positive values. Definition A.4. (Domain with ambiguous outcome) Xambiguous ≜ {xc s.t. ∃ u ∈ U : ysco (xc , u) ≥ 0, ∃ u′ ∈ U : ysco (xc , u′ ) < 0} ⊆ Xc Assumption A.5. (Ambiguity compensation through xc ) ∃ δ ∈ R : ∀xc ∈ Xambiguous : ∃ v ∈ Rd , ||v||p ≤ δ : ∀ u, ysco (xc + v, u) ≥ 0 Corollary A.6. (Partition of Xc through ∂upp and ∂low ) Assume A.2, A.3, A.5. Let ∂u = {xc : ysco (xc , u) = 0, ∀x̃c ∈ int(xc − Os ), ysco (x̃c , u) < 0}, where the last condition prevents “thick” boundary regions. Let B ≜ ∪ ∂u . u

Define ∂upp ≜ {xc ∈ B : int(xc + Os ) ∩ B = ∅} and ∂low ≜ {xc ∈ B : int(xc − Os ) ∩ B = ∅}. It follows that ∀xc : ∃ xupp ∈ ∂upp , xupp ⪯Os xc ⇒ xc ̸∈ Xambiguous , ∀u : ysco (xc , u) ≥ 0 and ∀xc : ∃ xlow ∈ ∂low , xc ≺Os xlow ⇒ xc ̸∈ Xambiguous , ∀u : ysco (xc , u) < 0. Hence, we can partition Xc into three disjoint subsets, separated by ∂upp and ∂low : Xambiguous , {xc : ∀u, ysco (xc , u) ≥ 0} and {xc : ∀u, ysco (xc , u) < 0}. Proof. We prove by contradiction that ∀x̃c : ∃ xupp ∈ ∂upp , xupp ⪯Os x̃c ⇒ x̃c ̸∈ Xambiguous , ∀u : ysco (x̃c , u) ≥ 0. Suppose ∃ u′ , x̃c : ysco (x̃c , u′ ) < 0, ∃ xupp ∈ ∂upp , xupp ⪯Os x̃c . From the definition of ∂upp , we have that ∃ xupp ∈ ∂upp , xupp ⪯Os x̃c ⇒ int(x̃c + Os ) ∩ B = ∅ and hence int(x̃c + Os ) ∩ ∂u′ = ∅. Due to continuity (A.2) there exists an ϵ-ball around x̃c where ysco (x̃c , u′ ) < 0, particularly ∃ ϵ ∈ Os : ysco (x̃c + ϵ, u′ ) < 0. It follows that int(x̃c + Os ) ∩ ∂u′ = ∅ ⇒ int(x̃c + ϵ + Os ) ∩ ∂u′ = ∅. However, from A.5, ysco (x̃c + ϵ, u′ ) < 0 ⇒ ∃ v ∈ Rd : ysco (x̃ + ϵ + v, u′ ) = 0. From A.3 there must also be a vector v ′ ∈ Os which increases ysco to zero, ∃ q ∈ Os , v ′ ≜ q + v : v ′ ∈ Os , ysco (x̃c + ϵ + v ′ , u′ ) = 0. Hence int(x̃c + ϵ + Os ) ∩ ∂u′ ̸= ∅, which is a contradiction. We can show similarly by contradiction that ∀xc : ∃ xlow ∈ ∂low , xc ≺Os xlow ⇒ xc ̸∈ Xambiguous , ∀u : ysco (xc , u) < 0.

Góis, Günlük, Rosenfeld, Hegde, Lacoste-Julien, Sridhar

Corollary A.7. (Bounded distance to Xambiguous boundary) ∀xc ∈ Xambiguous ⇒ max

min

xlow ∈∂low xupp ∈∂upp

||xupp − xlow ||p = max max u

min

xlow ∈∂u xupp ∈∂upp

min

xupp ∈∂upp

||xupp − xc ||p ≤

||xupp − xlow ||p < +∞

Proof. By contradiction, suppose that ∃ x̃c ∈ Xambiguous :

min

xupp ∈∂upp

||xupp − x̃c ||p >

max

min

xlow ∈∂low xupp ∈∂upp

||xupp −

xlow ||p . It follows that x̃c ̸∈ ∂low . Denote x̃upp ≜ arg min ||xupp − x̃c ||p . From A.3, we have that x̃upp ∈ x̃c + Os . To prove this, consider xupp ∈∂upp

x̃upp−O ≜

min

x∈∂upp ∩x̃c +Os

||x − x̃c ||p . We know ∀x ∈ ∂upp \ {xupp−O } ⇒ x ̸∈ xupp−O − int(Os ). Hence ∀x ∈

∂upp \ {xupp−O }, p < +∞ ⇒ ||x − x̃c ||p > ||xupp − x̃c ||p , therefore xupp = xupp−O . For p = +∞ there can be ties with other arg min, but we pick xupp since it is one of the minimizers. Since x̃c ̸∈ ∂low , then ∃ xlow ∈ ∂low : xlow ∈ x̃c − Os . Hence ∀p, ||xupp − xlow ||p > ||xupp − x̃c ||p , leading to a contradiction. This shows that min ||xupp − xc ||p ≤ max min ||xupp − xlow ||p . xupp ∈∂upp

The equality

max

min

xlow ∈∂low xupp ∈∂upp

||xupp − xlow ||p = max max u

min

xlow ∈∂u xupp ∈∂upp

||xupp − xlow ||p comes from the definition of

B and ∂low . Assumption A.5 provides a finite upper bound on the distance between any point in the ambiguous region and a positive point outside it, and the path between these points necessarily crosses the boundary ∂upp . Note that any point xlow lies either in the ambiguous region or on one of its two boundaries (by definition), and that any xlow that lies on a boundary ∂u has a bounded distance to ∂upp (from above). Therefore, it follows that: max max u

min

xlow ∈∂u xupp ∈∂upp

||xupp − xlow ||p < +∞.

Assumption A.8. (Agent adaptation with Lp -norm cost) Before being classified, agents have knowledge of classifier h(x). They adapt their features, from x into ∆h (x), by maximizing their reward rp (h, x) = δh(∆h (x))− c(x, ∆h (x)). Assume c(x, x′ ) := ||x′ − x||p . Under the previous assumptions, there exists a classifier which achieves zero 0-1 loss post-adaptation, by ignoring spurious features and setting a threshold that moves points away from Xambiguous . Theorem A.9. (Causal ℓ0−1 optimality) Assume A.1, A.2, A.3, A.5, A.8. Let hc be a causal classifier whose outputs are not changed by xs . ∃ e ∈ R, hc ∈ H : ∀ δ ≥ e : Ex,u [ℓ0−1 (hc (∆hc (x; δ)), sign(ysco (∆hc (x; δ), u)))] = 0 Proof. Consider the following definitions from Corollary A.6, of ∂u = {xc ∈ Xc : ysco (xc , u) = 0, ∀x̃c ∈ int(xc − Os ), ysco (x̃c , u) < 0} ⊂ Xc , and B := ∪ ∂u . u

Denote the learned classification boundary of a hypothesis h(x) = 1{f (x) ≥ 0} by ∂h = {x ∈ X : f (x) = 0}. Given ∂h , h(x) is such that if ∃ x′ ∈ ∂h : x′ ⪯Os x then h(x) = 1, else h(x) = 0. We can build the optimal classifier named hc (xc ) : Xc → {0, 1} s.t. xc ∈ ∂hc if xc ∈ B and int(xc + Os ) ∩ B = ∅. We split the proof in three parts: 1. Static TPs (true positives where ∆h (x) = x) are correctly classified as h(∆h (x)) = 1; 2. All points in Xambiguous adapt (∆h (x) ̸= x) such that they are correctly classified as h(∆h (x)) = 1; 3. Pre-adaptation TNs are correctly classified post-adaptation, either remaining static (∆h (x) = x) with h(∆h (x)) = 0, or adapting into TPs.

The Role of Causal Features in Strategic Classification for Robustness and Alignment

1. Correct classification of static TPs: From A.8, ∀x : h(x) = 1 ⇒ ∆h (x) = x, since a point with h(x) = 1 cannot further increase its utility by adapting features. hc (x̃) = 1 ⇒ ∀u′ : ysco (x̃, u′ ) ≥ 0. Below we prove this by contradiction. This implies all points hc (x̃) are correctly classified since their true outcome y = 1 (from A.1). Assume ∃ u′ : ysco (x̃, u′ ) < 0, h(x̃) = 1. Since h(x̃) = 1, we know from the definition on hc that int(x̃ + Os ) ∩ B = ∅ and hence int(x̃ + Os ) ∩ ∂u′ = ∅. Due to continuity (A.2) there exists an ϵ-ball around x̃ where ysco < 0, particularly ∃ ϵ ∈ Os : ysco (x̃ + ϵ, u′ ) < 0. It follows that int(x̃ + Os ) ∩ ∂u′ = ∅ ⇒ int(x̃ + ϵ + Os ) ∩ ∂u′ = ∅. However, from A.5, ysco (x̃ + ϵ, u′ ) < 0 ⇒ ∃ v ∈ Rd : ysco (x̃ + ϵ + v, u′ ) = 0. From A.3 there must also be a vector v ′ ∈ Os which increases ysco to zero, ∃ q ∈ Os , v ′ ≜ q + v : v ′ ∈ Os , ysco (x̃ + ϵ + v ′ , u′ ) = 0. Hence int(x̃ + ϵ + Os ) ∩ ∂u′ ̸= ∅, which is a contradiction. 2. Correct classification of Xambiguous post-adaptation: We proved above that hc (x̃) = 1 ⇒ ∀u′ : ysco (x̃, u′ ) ≥ 0. From A.1 we have the same implication for postadaptation data points: ∀x̃, hc (∆hc (x̃)) = 1 ⇒ ∀u′ , y(∆hc (x̃), u′ ) = 1. From A.3, A.8 and the definition of hc , we have ∀x : hc (x) = 0, hc (∆hc (x)) = 1 ⇒ ∆hc (x) ∈ ∂hc for any Lp -norm cost. To show by contradiction assume ∃ x : hc (x) = 0, hc (∆hc (x)) = 1, ∆hc (x) ̸∈ ∂hc . From the definition of hc and A.3, ∃ b ∈ ∂hc : x ⪯Os b ⪯Os ∆hc (x). From A.8 we have c(x, b) < c(x, ∆hc (x)) for any Lp -norm, hence x must have adapted instead to b ∈ ∂hc . c(x, x′ ). From A.7 we have that this quantity is bounded. Define e ≜ max max min ′ u

x∈∂u x ∈∂h

δ ≥ e ⇒ ∀x ∈ Xambiguous , ∆hc (x) ∈ ∂hc , hc (x) = 1, ∀u, y(x, u) = 1. 3. Correct classification of static TNs: If any remaining points xneg ∈ Xc exist not covered by the cases above, it has ∀u′ : ysco (xneg , u′ ) < 0 and hc (xneg ) = 0, since ∀xneg , ∃ xlow ∈ ∂low : xneg ≺Os xlow . After adaptation it either remains unchanged or adapts such that ∀u′ : ysco (∆h (xneg ), u′ ) ≥ 0 and h(∆(xneg )) = 1, since it must have adapted to ∂upp .

CE loss optimality of causal classifier under enough shift

From Corollary A.6, we define the following sets: Xupp ≜ {xc : ∀u, ysco (xc , u) ≥ 0} Xlow ≜ {xc : ∀u, ysco (xc , u) < 0} where the sets Xupp , Xambiguous , Xlow are disjoint subsets of Xc and Xupp ∪ Xambiguous ∪ Xlow = Xc . Note that by this definition and following Assumption A.1, for any u, if xc ∈ Xupp , y(xc , u) = 1, and if xc ∈ Xlow , y(xc , u) = 0.

Góis, Günlük, Rosenfeld, Hegde, Lacoste-Julien, Sridhar

h i LCE (fˆ, δ) = Ex,y∼D(fˆ,δ) −y log fˆ(x) − (1 − y) log(1 − fˆ(x)) h i =Exc ,xs ,u∼D(fˆ,δ) −1{ysco (xc ,u)≥0} log fˆ(xc , xs ) − (1{ysco (xc ,u)<0} ) log(1 − fˆ(xc , xs )) h h ii =Exc ∼D(fˆ,δ) Exs ,u∼D(fˆ,δ) −1{ysco (xc ,u)≥0} log fˆ(xc , xs ) − 1{ysco (xc ,u)<0} log(1 − fˆ(xc , xs )) Z h h ii = PD(fˆ,δ) (xc ) ∗ Exs ,u∼D(fˆ,δ) −1{ysco (xc ,u)≥0} log fˆ(xc , xs ) − 1{ysco (xc ,u)<0} log(1 − fˆ(xc , xs )) dxc ZXc h ii h = PD(fˆ,δ) (xc ) ∗ Exs ,u∼D(fˆ,δ) −1{ysco (xc ,u)≥0} log fˆ(xc , xs ) − 1{ysco (xc ,u)<0} log(1 − fˆ(xc , xs )) dxc Xlow Z h h ii + PD(fˆ,δ) (xc ) ∗ Exs ,u∼D(fˆ,δ) −1{ysco (xc ,u)≥0} log fˆ(xc , xs ) − 1{ysco (xc ,u)<0} log(1 − fˆ(xc , xs )) dxc X

Z ambiguous h h ii + PD(fˆ,δ) (xc ) ∗ Exs ,u∼D(fˆ,δ) −1{ysco (xc ,u)≥0} log fˆ(xc , xs ) − 1{ysco (xc ,u)<0} log(1 − fˆ(xc , xs )) dxc Xupp

Z = Xlow

h h ii PD(fˆ,δ) (xc ) ∗ Exs ,u∼D(fˆ,δ) −1 · log(1 − fˆ(xc , xs )) dxc

Z + X

h h ii PD(fˆ,δ) (xc ) ∗ Exs ,u∼D(fˆ,δ) −1{ysco (xc ,u)≥0} log fˆ(xc , xs ) − 1{ysco (xc ,u)<0} log(1 − fˆ(xc , xs )) dxc

Z ambiguous h h ii + PD(fˆ,δ) (xc ) ∗ Exs ,u∼D(fˆ,δ) −1 · log fˆ(xc , xs ) dxc Xupp

Using the same causal classifier from Theorem A.9, we define hc s.t. xc ∈ ∂hc if xc ∈ B and int(xc + Os ) ∩ B = ∅. This means for all points xc ∈ Xupp , hc (xc ) = 1 and x′c ∈ Xlow , hc (x′c ) = 0. We define the “scoring” function fˆc : X → [0, 1] that cross entropy uses as the same function as hc , meaning it outputs strictly 0 and 1. With this data generating process and classifier, we previously proved that for finite δ > e (which we call the max-gap), all points will move from Xambiguous into Xupp , obtaining true outcome y(xc , u) = 1 and correct prediction h(xc ) = 1. Thus, the cross entropy loss after δ > e will also be 0 with this specific causal classifier. We can clearly see this from the derivation above because with this fˆc , the first and last terms will = 0 for any δ, and the middle term will take value 0 once the probability density in that region becomes 0, which occurs when all the points have adapted out of the region, i.e. δ > e.

Cross Entropy Loss Analysis

C.1

Cross Entropy Loss Decomposition

Assuming 0 log 0 := 0, fˆ : X → (0, 1) is measurable, and there is support-compatibility (i.e. {g > 0} ⊆ {fˆ > 0, fˆδ > 0} and {g < 1} ⊆ {fˆ < 1, fˆδ < 1} almost surely), we can decompose the cross entropy loss after adaptation to classifier fˆ as follows:

The Role of Causal Features in Strategic Classification for Robustness and Alignment

h i LCE (fˆ, δ) = Ex,y∼D(fˆ,δ) −y log fˆ(x) − (1 − y) log(1 − fˆ(x)) h i = Exc ,xs ,u∼D(fˆ,δ) −g(xc , u) log fˆ(xc , xs ) − (1 − g(xc , u)) log(1 − fˆ(xc , xs )) h = ED(fˆ,δ) − g(xc , u) log fˆ(xc , xs ) − (1 − g(xc , u)) log(1 − fˆ(xc , xs )) i + (1 − 1) ∗ g(xc , u) log g(xc , u) + (1 − g(xc , u)) log(1 − g(xc , u)) " = ED(fˆ,δ)

1 − g(xc , u) g(xc , u) + (1 − g(xc , u)) log g(xc , u) log fˆ(xc , xs ) 1 − fˆ(xc , xs )

− ED(fˆ,δ) [g(xc , u) log g(xc , u) + (1 − g(xc , u)) log(1 − g(xc , u))] h i = ED(fˆ,δ) KL g(xc , u)∥fˆ(xc , xs ) + ED(fˆ,δ) [H (g(xc , u))] . {z } | {z } | (entropy)

(KL divergence)

" = ED(fˆ,δ)

g(xc , u) 1 − g(xc , u) g(xc , u) log + (1 − g(xc , u)) log fˆ(xc , xs ) 1 − fˆ(xc , xs )

− ED(fˆ,δ) [g(xc , u) log g(xc , u) + (1 − g(xc , u)) log(1 − g(xc , u))] h i + ED(fˆ,δ) (1 − 1) · g(xc , u) log fˆ(∗fˆ,δ) (xc , xs ) + (1 − 1) · (1 − g(xc , u)) log(1 − fˆδ∗ (xc , xs )) # 1 − g(xc , u) g(xc , u) + (1 − g(xc , u)) log = ED(fˆ,δ) g(xc , u) log fˆδ∗ (xc , xs ) 1 − fˆδ∗ (xc , xs ) # " fˆδ∗ (xc , xs ) 1 − fˆδ∗ (xc , xs ) + ED(fˆ,δ) g(xc , u) log + (1 − g(xc , u)) log 1 − fˆ(xc , xs ) fˆ(xc , xs ) "

− ED(fˆ,δ) [g(xc , u) log g(xc , u) + (1 − g(xc , u)) log(1 − g(xc , u))] # " h i 1 − fˆδ∗ (xc , xs ) fˆδ∗ (xc , xs ) ∗ ˆ = ED(fˆ,δ) KL g(xc , u)∥fδ (xc , xs ) + ED(fˆ,δ) g(xc , u) log + (1 − g(xc , u)) log 1 − fˆ(xc , xs ) fˆ(xc , xs ) + ED(fˆ,δ) [H (g(xc , u))] If we define fˆ = arg min ED [KL (g(xc , u)∥f (xc , xs ))] f ∈F

fˆδ∗ = arg min ED(fˆ,δ) [KL (g(xc , u)∥f (xc , xs ))] f ∈F

we can interpret the the decomposition as follows:

Góis, Günlük, Rosenfeld, Hegde, Lacoste-Julien, Sridhar

h i LCE (fˆ, δ) = ED(fˆ,δ) KL g(xc , u)∥fˆδ∗ (xc , xs ) | {z } (incomplete information error)

" + ED(fˆ,δ) |

# fˆδ∗ (xc , xs ) 1 − fˆδ∗ (xc , xs ) g(xc , u) log + (1 − g(xc , u)) log fˆ(xc , xs ) 1 − fˆ(xc , xs ) {z } (transfer error)

+ ED(fˆ,δ) [H (g(xc , u))] | {z } (entropy)

Note: all terms are nonnegative. • incomplete information error: KL Divergence is always non-negative. • transfer error: since we define fˆδ∗ = arg min ED(fˆ,δ) [KL (g(xc , u)∥f (xc , xs ))], we have the fact that transfer f ∈F h i error is nonnegative (i.e. ≥ 0). Since ED(fˆ,δ) [KL (g(xc , u)∥fδ∗ (xc , xs ))] ≤ ED(fˆ,δ) KL g(xc , u)∥fˆ(xc , xs ) for all fˆ(xc , xs ) ∈ F, we have: h i LCE (fˆ, δ) = ED(fˆ,δ) KL g(xc , u)∥fˆ(xc , xs ) + ED(fˆ,δ) [H (g(xc , u))] h i ≥ ED(fˆ,δ) KL g(xc , u)∥fˆδ∗ (xc , xs ) + ED(fˆ,δ) [H (g(xc , u))] but from the derivation above, we have: h i LCE (fˆ, δ) = ED(fˆ,δ) KL g(xc , u)∥fˆδ∗ (xc , xs ) + ED(fˆ,δ) [H (g(xc , u))] # " 1 − fˆδ∗ (xc , xs ) fˆδ∗ (xc , xs ) + (1 − g(xc , u)) log + ED(fˆ,δ) g(xc , u) log 1 − fˆ(xc , xs ) fˆ(xc , xs ) implying that the last term (which is transfer error) is nonnegative: # " 1 − fˆδ∗ (xc , xs ) fˆδ∗ (xc , xs ) + (1 − g(xc , u)) log ≥0 ED(fˆ,δ) g(xc , u) log fˆ(xc , xs ) 1 − fˆ(xc , xs ) • entropy: The entropy of a binary variable Y with success probability p = g(xc , u) is nonnegative almost surely, since for all p ∈ [0, 1], entropy −p log p − (1 − p) log(1 − p) is nonnegative and thus the expectation must be nonnegative with probability 1. C.2

Extending to training data with adaptive shifts

We can further extend this decomposition by considering that a classifier has access to some strategic behavior when training the initial classifier fˆ. This means we define the classifier fˆ as the optimal classifier under δ ′ to some classifier f ′ (which could be fˆ itself), formally:

fˆ = arg min ED(f ′ ,δ′ ) [KL (g(xc , u)∥f (xc , xs ))] f ∈F

fˆδ∗ = arg min ED(fˆ,δ) [KL (g(xc , u)∥f (xc , xs ))] f ∈F

The Role of Causal Features in Strategic Classification for Robustness and Alignment

The decomposition still holds with nonnegative terms. Incomplete information and entropy are trivially nonnegative from the same reasoning as before. Transfer error also remains nonnegative since we are still selecting fˆδ∗ to be the optimal classifier on the shifted data, so we still have for all fˆ(xc , xs ) ∈ F: h i h i ED(fˆ,δ) KL g(xc , u)∥fˆδ∗ (xc , xs ) ≤ ED(fˆ,δ) KL g(xc , u)∥fˆ(xc , xs ) This allows us to conclude that even if the learned classifier is able to anticipate some strategic shift or only has access to training data with some shift already present, causal classifiers still provide robustness while spurious classifiers can have arbitrarily large error due to the transfer term. C.3 C.3.1

CE Error of Causal Classifier Family Incomplete Information Error

First, we consider families of causal classifiers only, Fcausal , i.e. classifiers that do not use spurious features for prediction. We defined fˆδ∗ such that fˆδ∗ = arg min ED(fˆ,δ) [KL (g(xc , u)∥f (xc ))], so the incomplete information f ∈Fcausal

error is the minimum value of this objective, and when trying to bound this term, we actually want to bound the minimum. If we assume that Fcausal includes the minimum of this objective, which is the function ED(fˆ,δ) [Y |Xc ] (for example a family of classifiers that includes logistic functions must include any linear combination of logistic functions), then:

min

f ∈Fcausal

i h Exc ,u∼D(fˆ,δ) KL g(xc , u) ∥ fˆ∗ (xc )

Góis, Günlük, Rosenfeld, Hegde, Lacoste-Julien, Sridhar

C.3.2

Transfer Error

We are only considering families of causal classifiers. We previously defined: h i fˆ = arg min ED KL g(xc , u)∥fˆ(xc ) fˆ∈F

h i fˆδ∗ = arg min ED(fˆ,δ) KL g(xc , u)∥fˆ∗ (xc ) fˆ∗ ∈F

which are minimized at ED [Y |Xc ] and ED(fˆ,δ) [Y |Xc ] respectively. U cannot be intervened on and causal mechanisms are invariant, so the only difference is a covariate shift of the distribution, meaning they are both equal to E[Y |Xc ] = E [EU [Y |Xc , U ]]. Since we already assumed this function to be part of the classifier family, fˆ = fˆ∗ and therefore transfer error is 0 when training with a causal classifier family. C.3.3

Entropy Error

The outcome Y is a binary variable i.e. ∈ [0, 1] so: H(Y ) = E[− log P (Y )] ≤ max (− log P (Y = y)) ≤ (− log 0.5) = 1. x

Hence, H(Y ) ≤ 1, (or entropy of any binary variable) with equality iff P (X = 0) = P (X = 1) = 0.5. C.4 C.4.1

CE Error of Spurious Classifier Family Incomplete Information Error

Repeating the same logic as before with a causal classifier family, when considering a family of classifiers F that now uses all features, including spurious ones, fˆδ∗ is defined such that fˆδ∗ = arg min ED(fˆ,δ) [KL (g(xc , u)∥f (xc , xs ))], thus the incomplete information error term is again the minimum value f ∈Fall

of this objective. If we similarly assume that F includes the function ED(fˆ,δ) [Y |Xc , Xs ] :

The Role of Causal Features in Strategic Classification for Robustness and Alignment

Transfer Error

Now considering families of classifiers F that use all features, we have: fˆ = arg min ED [KL (g(xc , u)∥f (xc , xs ))] f ∈F

fˆδ∗ = arg min ED(fˆ,δ) [KL (g(xc , u)∥f (xc , xs ))] f ∈F

which are minimized at ED [Y |Xs , Xc ] and ED(fˆ,δ) [Y |Xs , Xc ] respectively. Only causal mechanisms are invariant, so these conditional expectations can be arbitrarily different based on the distribution shift. Thus, transfer error can be arbitrarily large, since KL divergence can range from 0 to ∞ (for example if there are x ∈ X where g(xc , u) is very high and fˆ(xc , xs ) is very small, this will have a large KL value). C.4.3

Analysis for unbounded transfer error with thresholded classifier

To make this more concrete, consider the following setting: given that minimizing cross-entropy loss learns a probability estimator fˆ(x) : X → [0, 1], institutions may require candidates to exceed a certain probability threshold for a positive prediction (which we previously assumed was 0.5 or 50%); for instance, accepting a loan application only when the estimated repayment probability exceeds τ ∈ [0, 1]: ŷ = h(x) = 1{fˆ(x)≥τ }

Góis, Günlük, Rosenfeld, Hegde, Lacoste-Julien, Sridhar

The transfer error is then affected by three key factors: the cost function c(x, x′ ), which determines which features agents adapt and their relative cost; the budget δ, which bounds how much effort agents can spend; and the threshold τ , which determines the decision boundary agents adapt towards. We can further analyze the transfer error by partitioning the input space as X = X adapt ∪ X stay , where X adapt = {x : PD (x) ̸= PD(fˆ,δ) (x)} contains points whose distribution changed under adaptation, and X stay its complement. Let pa = P (x ∈ X adapt ) and ps = 1 − pa . The transfer error splits as: # " 1 − fˆδ∗ fˆδ∗ adapt x∈X + (1 − g) log transfer error = pa ED(fˆ,δ) g log fˆ 1 − fˆ # " fˆδ∗ 1 − fˆδ∗ + ps ED g log x ∈ X stay , (8) + (1 − g) log fˆ 1 − fˆ ˆ

where the stay term uses D since D and D(f ,δ) agree on X stay by construction. On X adapt , all points have been moved to the decision boundary ∂h , so fˆ(xc , xs ) = τ . Since τ is constant on this region, the adapt term separates as: i h (9) ED(fˆ,δ) g log fˆδ∗ + (1 − g) log(1 − fˆδ∗ ) x ∈ X adapt − ḡ log τ − (1 − ḡ) log(1 − τ ), where ḡ = ED(fˆ,δ) [g(xc , u) | x ∈ X adapt ]. The transfer error on adapted points is amplified under two conditions that expand X adapt : • δ: increasing the adaptation budget δ allows more points to reach the decision boundary, increasing pa and giving this term more weight. • c(x, x′ ): since the cost function is a weighted ℓp -norm, reducing the cost of perturbing spurious features µs has a compounding effect: for a fixed δ, more agents can cross the boundary by modifying spurious features, increasing pa ; simultaneously these agents allocate proportionally more of their budget to changing Xs rather than Xc , so the causal features of adapted points are perturbed less, keeping ḡ bounded away from 1. Furthermore, as τ → 1− , the transfer error on adapted points diverges entirely, driven by the −(1 − ḡ) log(1 − τ ) component, whenever ḡ < 1; that is, whenever any adapted point has nonzero negative-class probability. Since g(xc , u) depends only on causal features and the unobserved variable, and if agents entering X adapt do so by significantly changing spurious features, the expanding region includes points with diverse values of g, ensuring ḡ < 1. This illustrates why classifiers in Fall that rely on spurious features risk unbounded transfer error when strategic behavior is unknown: δ and µs control how much agents adapt and how much of that adaptation targets spurious features, which leads to gaming, while more demanding τ makes the consequences of this gaming increasingly severe for the spurious classifier. C.4.4

Entropy Error

Same as with the causal classifier case, the outcome Y is a binary variable i.e. ∈ [0, 1] so H(Y ) ≤ 1, (or entropy of any binary variable).

Additional Experimental Results

D.1

Robustness under varying ambiguity.

We highlight a trade-off in post-adaptation cross-entropy loss in Theorem 5.2: causal classifiers incur incomplete information loss by ignoring the informative spurious features while spurious classifiers incur transfer loss due to changing optimal predictive distributions. The theory allows us to form another prediction, related to our findings in Section 4: if we further bound how influential the latent U is on the value of the outcome Y (limiting the incomplete information loss further), a causal classifier trained on pre-adaptation data should achieve lower post-adaptation CE loss compared to their spurious counterparts. To implement this idea, we minimally modify

The Role of Causal Features in Strategic Classification for Robustness and Alignment

the outcome model to be: ysco ≜ wc Xc + wu U · 1{Xc ∈(−max-gap,0)} + b

(10)

where max-gap ensures that latent U impacts Y in a bounded region. Figure 5 visualizes the post-adaptation CE loss difference between the pre-adaptation optimal causal and spurious classifiers (blue is better i.e. causal has an advantage) as the adaptation budget δ and max-gap vary. We simulated the data using the setting described in Section 7 with a modified ysco , and used sklearn’s Logistic Regression model to train the optimal classifiers with static data (both pre and post-strategic shift). As expected, for larger values of δ (inducing a bigger distribution shift) and max-gap, transfer loss of a spurious classifier is worse than information loss from masking spurious features, giving causal classifiers the advantage.

Figure 5: Simulations with varying max-gap. When there is a bounded ambiguous region through max-gap in the ysco , a causal classifier trained on pre-adaptation data can have an advantage after sufficiently large δ (denoted by the blue region, grey dashed line represents regret = 0). However, in order to see the effect of incurring a significant amount of transfer error when exploiting spurious features, we need to alter the adaptation incentives, specifically such that agents’ are encouraged to adapt their spurious features more when a classifier puts weight on it. While large enough δ allows for agents to make larger strategic shifts, this may not be enough if they do not shift adversarially. We therefore explicitly model the agents’ cost function of adapting features. We previously assumed the cost of adapting features is a standard Lp norm, but we can instead consider weighted Lp -norm in order to control how much agents’ adapt their spurious features. By lowering cost of changing xs , agents will be incentivized more drastic shifts along xs , which can be adversarial for even slightly spurious classifiers. Based on Theorem 5.2, this leads to significant transfer error for spurious classifiers trained on pre-adaptation data, even with some incomplete information from settings like stochastic Y with an unbounded max-gap. This is because the agents will be incentivized to game and adapt to regions of Xs where the pre-adaptation classifier fˆ very poorly estimates the post-adaptation fˆ = ED(fˆ,δ) [Y |X]. This leads the post-adaptation transfer error term to dominate the causal incomplete information term when there is an incentive to significantly game. We empirically show that the pre-adaptation causal classifier leads to robustness in these settings by reducing the cost of xs . We simulate data using the described setting in Section 7, and use sklearn’s Logistic Regression model to train the classifiers on static data (both pre and post-strategic shift). We consider the cost function to be weighted L2 -norm of the two features in our experiments: sX p ′ c(x, x ) = µj (x′j − xj )2 = µs (x′s − xs )2 + µc (x′c − xc )2 . (11) j

This allows us to confirm our hypothesis that as the cost of changing the spurious feature, µs , decreases, then the spurious transfer error can increases arbitrarily, which can lead spurious classifiers to have significantly more error in the worst case. On the other hand, causal classifiers will have relatively stable error, even when the cost of changing the spurious feature is larger. To ensure causal classifier actually provides robustness, we also look

Góis, Günlük, Rosenfeld, Hegde, Lacoste-Julien, Sridhar

at the performance of the classifiers when the costs are switched, meaning the cost of changing xc is much less than xs . Error decomposition: μs = 0.001 Incomplete Information Error

Transfer Error

Entropy Error 0.572

0.04

0.64

0.63

0.570

0.021

0.03 Causal Spurious 0.02

0.568

Total Error

0.022

Entropy Error

0.023

Transfer Error

Incomplete Information Error

0.024

Total Error Causal Spurious

0.05

0.566 0.564

0.62

0.61

0.60 0.562

0.01

0.59

0.020 0.560

Causal Spurious 0

Causal Spurious

0.00

Budget (δ)

0.58

Budget (δ)

(a) Cost function weights: (µs = 0.001, µc = 1) Error decomposition: μc = 0.001 Incomplete Information Error

Transfer Error

Total Error Causal Spurious

0.64 0.572

0.04

0.63

0.570

0.021

0.03

0.02

0.568

Total Error

Causal Spurious

0.022

Entropy Error

0.023

Transfer Error

Incomplete Information Error

Entropy Error Causal Spurious

0.05 0.024

0.566 0.564

0.62

0.61

0.60 0.562

0.01

0.59

0.020 0.560

Causal Spurious

0.00 0

Budget (δ)

0.58

Budget (δ)

(b) Cost function weights: (µs = 1, µc = 0.001)

Figure 6: Simulations with varying cost. Top: When the cost of changing spurious feature is significantly less that the causal feature (i.e. µs ≪ µc ), transfer error leads the spurious classifier to have a significant disadvantage after strategic shifts. Bottom: On the other hand when µc ≪ µs , transfer error leads the causal classifier to have a slight disadvantage after strategic shifts due to the incomplete information error difference. From Figure 6, we observe that when µc ≪ µs , the spurious advantage is relatively minor compared to the causal advantage when the cost is reversed, due to the transfer error incurred by the spurious classifer. More specifically, when µc ≪ µs , both classifier achieve 0 transfer error because agents are not incentivized to game significantly, meaning the spurious feature remains a good proxy of the unobserved causal feature U . This leads the same spurious classifier to be optimal even after strategic shifts. However, when µs ≪ µc , the spurious feature is cheaper and easier to modify, which incentivizes agents to game more and intervene on their spurious feature. This results in Xs becoming a bad proxy of U after strategic shifts, and thus the optimal post-adaptation spurious classifier changes. This leads to significant transfer error for the spurious classifier, giving the pre-adaptaion causal classifier an advantage overall. The incomplete information also shows the effect of the spurious feature becoming a bad proxy of the unobserved causal feature. In the left-most graph of Figure 6a, the incomplete information error of the spurious classifier increases after strategic shifts. This behavior results from Xs becoming a weaker signal for U , and thus the optimal spurious classifier post-adaptation must mainly rely on the causal feature, the same as the causal classifier. When Xs remains a good proxy of U , which we see in the left graph of Figure 6b, the spurious classifier has a stable advantage due to the stable incomplete information error gap. From the second to last graphs, there are some slight variations in entropy due to the strategic shifts to the causal and spurious classifiers, but neither are large enough (≈ 10− 3) to affect which classifier has an advantage; they in fact just make the “advantage” gap in both cases slightly smaller. Overall, this confirms our interpretation of the decomposition in Section 5 and robustness of causal classifiers. The causal advantage in Figure 6a is due to the spurious classifier’s transfer error, even though the spurious incomplete information error simultaneously increases slightly. On the other hand in Figure 6b, the slight advantage of the spurious classifier comes from the small advantage of using the spurious feature and resulting difference in incomplete information error.

The Role of Causal Features in Strategic Classification for Robustness and Alignment

D.2

Semi-synthetic Data

Because it is impossible to observe true post-adaptation data after agents strategically modify their features, our main experiments are conducted on fully synthetic data, allowing us to precisely control the data-generating process and ensure that the assumptions required by our theory hold. In particular, our theoretical results depend on knowledge of the causal structure and on the ability to compute counterfactual outcomes under strategic shifts, making experiments on purely real-world data infeasible for our purposes. To incorporate real-world feature distributions while retaining these guarantees, we additionally conduct semisynthetic experiments. In this setting, the observed features X are taken from the real world Credit Risk dataset from Kaggle, while the remaining variables (namely U and Y ) are generated synthetically according to a known causal model (Tse, 2018). This allows us to evaluate our results under realistic feature distributions without introducing ambiguity about the underlying causal structure or counterfactual outcomes. Specifically, • From the dataset, we define the causal feature X C to be the applicant’s income and spurious feature X S to be their age (which should not directly cause whether someone will pay back a loan but is likely to be correlated, for example confounded by whether the applicant has a savings account). • We generate U as a Bernoulli variable with probability p = σ(X S ) so that U and X S are correlated. • We generate Y as a function of X C and U as described in the fully synethetic experiments. Across all experimental settings, we observe the same qualitative behavior as in the fully synthetic case. In Figure 7, the optimal post-adaptation classifier again converges to a causal classifier once the adaptation budget δ is sufficiently large, while classifiers relying on spurious features degrade as δ increases when trained on data with limited adaptation. In Figure 8, the incentive alignment experiments similarly show that the incentives of the institution and agents align for sufficiently large δ2 (the boundary of the region is denoted by the grey dashed line). Finally, the robustness experiments in Figure 9 reproduce the same tradeoff between transfer error and incomplete-information error, which we see through both varying max-gap and different cost functions for adaptation. Optimal spurious coefficient for varying δ

0-1 loss for small δtrain 0.30

Utility Alignment (Δrp(h post, h pre))

0.5

0.4

0.25

0.4

Causal Classifier Error Spurious Classifier Error

0.20

0.2 0.3

0.15

δtrain = 0.1

0.10

0.2

0.4

0.0

0-1 loss

0.6

max-gap = 1

̂ Optimal ŵ s in (f, δ)

0.8

0.05

0.2 −0.2 0.1

0.00

0.0 0.00

0.25

0.50

0.75

1.00

1.25

1.50

Utility Difference (Post - Pre)

1.0

−0.4

0.00

0.25

0.50

0.75

1.00

1.25

1.50

δtest

Figure 7: 0-1 Loss (semi-synthetic data, cf. Figure 3). To obtain error bars we resample U five times, obtaining datasets with varying Y and train-test splits on the entire dataset.

0.0 0.00

0.25

0.50

0.75

1.00 δ2

1.25

1.50

1.75

2.00

Figure 8: Incentive Alignment (semi-syntheic data, cf. Figure 4).

Góis, Günlük, Rosenfeld, Hegde, Lacoste-Julien, Sridhar Error decomposition: μs = 0.001 Incomplete Information Error

0.002

0.0175

0.616

0.0150

0.614

0.0125

Causal Spurious

0.0075

0.0050

0.024

Total Error 0.660 0.655 0.650

0.612

0.0100

Entropy Error

0.025

Entropy Error

0.610

Causal Spurious

0.608

Total Error

0.026

Transfer Error

Incomplete Information Error

Δ total loss (causal − spurious)

3.0

Transfer Error

Causal Spurious

0.027

0.640 0.635

0.606 0.630

0.0025 0.604

2.5

0.645

Causal Spurious

0.625

0.023

max-gap

0.000 1.5

−0.001

1.0

Budget (δ)

Transfer Error 0.0175

Causal Spurious

1.5 Budget(δ)

2.0

2.5

3.0

(a) Varying max-gap (cf. Figure 5).

Budget (δ)

0.026

0.0125

0.025

0.0100

0.0075

0.0050

0.024

Entropy Error

0.616

Causal Spurious

Entropy Error

1.0

Transfer Error

0.5

Incomplete Information Error

0.0

Error decomposition: μc = 0.001 Incomplete Information Error

0.0150

−0.002

Budget (δ)

(b) Cost weights: (µs = 0.001, µc = 1)

0.027

0.5

Budget (δ)

Total Error 0.660

Causal Spurious

0.614

0.655

0.612

0.650

Total Error

0.001 2.0

CE diff (causal − spurious)

0.0000

0.610

0.608

Causal Spurious

0.645 0.640 0.635

0.606 0.630

0.0025 0.604

0.625

0.023 0.0000 0

Budget (δ)

Figure 9: Robustness of causal classifiers ross-entropy loss (semi-synthetic data). (a) Varying max-gap (cf. Figure 5). (b)–(c) Varying cost function weights (cf. Figure 6).

Example Setting

Consider the data generating process below, where X is sampled from a uniform distribution.

U ∼ Bern(0.5) Xc ∼ U(−1, 1) Xs ∼ U(−1 + U, 1 + U ) y = 1{Xc + 0.5U + b ≥ 0} Under this setting, with knowledge of U it would be possible to obtain zero ℓ0−1 , by the following classifier: ( 1{xc ≥ 0} if U = 0 h(x, u) = 1{xc ≥ −0.5} if U = 1

Figure 10: Data generating process where X is sampled from a uniform distribution, and u ∈ {0, 1}. Dashed grey lines are the correct decision boundaries for U = 0 and U = 1. On the right-hand side we have the analogous of Figure 2 for this example, where Xc ⊂ R has one dimension. As long as δ ≥ 0.5, where max-gap= 0.5, our theory predicts the causal classifier hc (xc ) ≜ 1{xc ≥ 0} obtains zero ℓ0−1 post-adaptation.

The Role of Causal Features in Strategic Classification for Robustness and Alignment

However, without knowledge of U , there is an ambiguous region of X pre-adpatation. We can see in Figure 10 that, for δ ≥ 0.5, points can be moved out of this ambiguous region to obtain zero ℓ0−1 (Theorem 4.6). For δ <max-gap, optimality of a causal hc (xc ) is more nuanced, and we study the optimal classifier for this particular example in the next section. E.1

Characterizing post-adaptation ℓ0−1 minimizers for δ <max-gap

When δ < max-gap, existing theory does not predict whether a causal classifier will remain optimal postadaptation. In this example, when δ < 0.5 we lose the guarantee of Theorem 4.6. However, we show that the same causal classifier remains optimal for any δ ≥ 13 , among linear classifiers. We study the minimizer of ℓ0−1 , among a family of linear classifiers defined as hlin (xc , xs ) = 1{xc ≥ axs + b}. We are interested in minimizing post-adaptation loss: min E [ℓ0−1 (hlin (∆hlin (x; δ)), y(x, u))]. a,b x,u

The closed-form expression for ℓ(a, b) depends on how the boundary ∂hlin intersects the edges of the support over X. Here we assume adaptation cost is L1 -norm, resulting in the adaptation boundary xc = axs + b − δ, where agents are indifferent between adapting or not. Other Lp -norms consist simply of shifting this boundary. We split the loss in four regions: FN for U = 0, FN for U = 1, FP for U = 0 and FP for U = 1. For FN, the shape of the error region depends on where the left and right edges of the support X for U = u are intersected by the adaptation boundary xc = axs + b − δ. Denote this boundary as hδ-lin (xs ) ≜ axs + b − δ. For FN in U = 0, we have 9 different possible shapes for the loss region of given a, b parameters. Which of the 9 geometrical figures we get from a certain a, b depends on whether hδ-lin (−1) ≤ 0, hδ-lin (−1) ∈ (0, 1) or hδ-lin (−1) ≥ 1, and hδ-lin (1) ≤ 0, hδ-lin (1) ∈ (0, 1) or hδ-lin (1) ≥ 1, resulting in 3 × 3 combinations. Similarly for FN in U = 1, the error shape depends on whether hδ-lin (−0.5) ≤ 0, hδ-lin (0) ∈ (−0.5, 1) or hδ-lin (0) ≥ 1, and hδ-lin (2) ≤ −0.5, hδ-lin (2) ∈ (−0.5, 1) or hδ-lin (2) ≥ 1. For FP, the shape of the error region depends on the classification boundary. We denote the classification boundary by h0-lin (xs ), where δ = 0. We also obtain 9 possible shapes, which for U = 0 depends on whether h0-lin (−1) ≥ 0, h0-lin (−1) ∈ (0, −1 + δ) or h0-lin (−1) ≤ −1 + δ, and h0-lin (1) ≥ 0, h0-lin (1) ∈ (0, −1 + δ) or h0-lin (1) ≤ −1 + δ. Similarly for U = 1, the area of error of FP depends on whether h0-lin (0) ≥ −0.5, h0-lin (0) ∈ (−0.5, −1+δ) or h0-lin (0) ≤ −1+δ, and h0-lin (2) ≥ −0.5, h0-lin (2) ∈ (−0.5, −1+δ) or h0-lin (2) ≤ −1+δ. To circumvent the combinatorial explosion presented above, we resort to grid-search in this example to identify the shape of error induced by optimal a, b parameters, for a given δ. Let a spurious classifier be an h(xc , xs ) such that xs can change the output (a ̸= 0 in this parameterization). We identify a condition among the possible 94 described above, which is optimal for at least δ ∈ [0.2, 31 ), arriving at a spurious classifier with the following description for ℓ0−1 :

ℓspur (a, b) =

−0.5 + δ − b b 1 δ−b [(b − a − δ)(1 + ) + (0.5 + δ − b)( ) + (1 + )(2δ − b − a) + 4| a } | a a {z {z {z } | } FN for U =0

FN for U =1

FP for U =0

0 |{z}

]

FP for U =1

p ∂· ∂· By solving for ∂a = 0 and ∂b = 0 we get: aspur = − 1/12 − 0.5δ 2 , bspur = δ − 1/6. This analytical solution matches grid-search results and is depicted in Figure 11a. As δ increases, we see though grid-search a sudden transition to the causal classifier acaus = bcaus = 0, with loss ℓcaus (a, b) = 2(0.5 − δ). p By setting ℓcaus (a = 0, b = 0) = ℓspur (a = − 1/12 − 0.5δ 2 , b = δ − 1/6) and solving for δ, we arrive at δ = 13 . This identifies a phase transition, as δ increases, switching suddenly from an optimal spurious classifier into a causal one, when δ increases beyond 13 . Interestingly, our theory predicted this causal classifier to be optimal for δ > 21 , which is our max-gap for this setting. When δ <max-gap it becomes challenging to charaterize the optimal solution generally. However, we provide here an example where the same causal solution remains optimal even for δ <max-gap, particularly for any δ ∈ ( 31 , +∞) despite max-gap= 12 .

Góis, Günlük, Rosenfeld, Hegde, Lacoste-Julien, Sridhar

(a) Optimal classifier for δ = 0.3.

(b) Optimal classifier for δ = 0.34.

Figure 11: Optimal classifiers for different δ, near the transition between causal and spurious solutions. E.2

Including negative impact of FP’s in population’s utility

Consider the generative process described in the beginning of this section, and δ = 0.5. We compute below the population’s utility (Definition 6.1) after deploying 2 classifiers: the one optimizing post-adaptation ℓ0−1 (which is causal, since δ ≥max-gap) and the one optimizing pre-adaptation ℓ0−1 (which uses the spurious feature). We then characterize alignment in this example, for varying δ2 . E.2.1

Best ℓ0−1 post-adapt

Assume δ = 0.5. The causal classifier a = 0, b = 0 obtains zero ℓ0−1 post-adaptation (Theorem 4.6).

Figure 12: Best ℓ0−1 post-adaptation classification boundary ∂h , for δ = 0.5, under the data generating process of section E. Regions where points adapted are labeled following Definition F.4. This yields: • 75% positive labels • Zero FPs

The Role of Causal Features in Strategic Classification for Robustness and Alignment

R 1 • Expected cost of adapting Ex [c(x, ∆fˆ(x))] = 0.0625. This comes from xc ,xs c(x, ∆fˆ(x))P(xc , xs ) = 0.5 2 ∗4+ 0 ∗ 43 , where 0.5 2 is the average cost of adapting for those who move. (area of a triangle with base 0.5 and height 0.5 — those who move from furthest spend 0.5, the ones touching the boundary spend 0). The expected utility of the predicted agents E[rp (hpost , x, u)] is then .75 ∗ .5 − .0625 − 0δ2 = 0.3125. E.2.2

Best ℓ0−1 pre-adapt

The parameters for the linear classifier that minimizes pre-adaptation ℓ0−1 are a = −0.224, b = −0.138, which uses the spurious feature since a ̸= 0 (obtained through grid-search).

(a) Support for U = 0.

(b) Support for U = 1.

Figure 13: Best ℓ0−1 pre-adaptation classification boundary ∂h , under the data generating process of section E. Regions where points adapted are labeled following Definition F.4. • 87.25% positive labels • 16.16% FPs • Expected cost of adapting is 0.0542 < Ex [c(x, ∆fˆ(x))] < 0.0557. It is 0.0625 − d where 0.0068 < d < 0.0083 is the small triangle outside support X (with area .384 ∗ .086/2) multiplied by its cost (which varies between .5 and .414 inside the triangle). The expected utility for the predicted agents E[rp (hpre , x, u)] is then upper-bounded by .8725∗.5−0.0542−.1616δ2 and lower-bounded by .8725 ∗ .5 − 0.0557 − .1616δ2 , or 0.38055 − .1616δ2 < E[rp (h, x, u)] < 0.38205 − .1616δ2 . E.2.3

Comparing predicted agents’ utility rp under hpre or hpost

Agent utility from post-adaptation minimizer: E[rp (hpost , x, u)] = 0.3125. Agent utility from pre-adaptation minimizer: 0.38055 − .1616δ2 < E[rp (hpre , x, u)] < 0.38205 − .1616δ2 . The lowest δ2∗ which guarantees alignment (∆rp (hpost , hpre ) ≥ 0) is then upper-bounded by δ2∗ < 0.43, for δ = 0.5. Even if δ > δ2 (i.e., FPs still provide a small gain) we have alignment, ∆rp (hpost , hpre ) ≥ 0. In words, the population still prefers on average a strategic institution that prevents gaming, even though this would bring a small benefit to agents compared to being classified as TN.

Incentive Alignment

Consider the following definition of h-change:

Góis, Günlük, Rosenfeld, Hegde, Lacoste-Julien, Sridhar

Definition F.1. (Conditional h-change) Expected change in utility when switching from classifier h into h′ for role k, where k ∈ {p, i} is either predicted agent p or institution i. For the subset of agents where Y = y, we have ∆rp|Y =y and ∆ri|Y =y : ∆rk|Y =y (h′ , h) = Ex,u|y [rk (h′ , ∆h′ (x), u)] − Ex,u|y [rk (h, ∆h (x), u)] F.1

Static Alignment

Proposition F.2. (Static alignment) Assume ∆h (x) = x and δ2 = ϵ = 0. For any pair of classifiers (fˆ′ , fˆ), institution’s goals match the goals of agents whose y = 1 but not of y = 0, in the following sense: ∆rp|Y =1 (h′ , h) > 0 ⇐⇒ ∆ri|Y =1 (h′ , h) > 0 ∆rp|Y =0 (h′ , h) < 0 ⇐⇒ ∆ri|Y =0 (h′ , h) > 0 Definition F.3. (FN, FP, TN, TP) Consider the following auxiliary definitions: FN(h(x), y) = 1{h(x) = 0 and y = 1} FP(h(x), y) = 1{h(x) = 1 and y = 0} TN(h(x), y) = 1{h(x) = 0 and y = 0} TP(h(x), y) = 1{h(x) = 1 and y = 0} Proof. With static (y, x) pairs, the only changes which can occur from a change in h are: 1. for y = 1, FN ↔ TP 2. for y = 0, FP ↔ TN From the definitions of rp (6.1) and ri (6.2), we see that in case 1. both rp and ri increase with TP and decrease with FN. For case 2. TN increases ri and reduces rp , while FP reduces ri and increases rp . This follows from the fact that agents always gain when a negative prediction (h(∆h (X)) = 0) is changed into positive (h′ (∆h′ (X)) = 1), while the institution only benefits from this change if true outcome is also positive (y = 1). It is illustrated by Table 1. Institution TP FN TN FP

! X ! X

Predicted Agents δ2 = 0 (δ2 > δ) ! X X (!) !(X)

Table 1: Contribution of static points (∆h (x) = x) to utility of institution (ri ) and of predicted agents (rp ). !denotes a non-negative contribution, and X a decrease in utility. Green rows indicate similar impact for institution and agents (contributing to alignment), and red otherwise. Parentheses in predicted agents indicate contribution when δ2 > δ, if it does not match contribution when δ2 = 0. F.2

Dynamic Alignment

To understand how hpost may differ from hpre , we can ask what additional information the institution receives when it knows the correct adaptation model ∆h (x; δ), instead of wrongly assuming static behavior ∆h (x) = x. Agents adapt to increase their utility, which is only possible when, pre-adaptation, they would be assigned a negative label h(x) = 0. This allows enumerating all four kinds of additional information for the institution when it becomes strategic (i.e., when it anticipates agents’ adaptation). For a given classifier hpre , a population of agents may respond through (some of) the following adaptations:

The Role of Causal Features in Strategic Classification for Robustness and Alignment

Definition F.4. (All possible adaptations) For any x : ∆h (x) ̸= x, its adaptation must fall in one of four categories, which we name below. This is because a point only moves to switch from negative h(x) = 0 into positive h(∆h (x)) = 1. We also characterize their impact on ri . • TN→ TP (improvement) ri → • FN→ TP (wasted effort) ri ↗ • TN→ FP (gaming) ri ↘ • FN→ FP (reversed incentive) ri → The arrows describe whether ri goes up (↗), down (↘), or stays constant (→) after agent-adaptation, for a fixed classifier, assuming short-term goals (δ2 = ϵ = 0). Table 2 also depicts this. An illustration is provided in the running example of § E.2 for intuition.

Improvement (TN→ TP) Wasted effort (FN→ TP) Gaming (TN→FP) Reversed incentive (FN→FP)

Institution ϵ = 0 (ϵ > 0) = (!) ! X X

Predicted Agents δ2 = 0 (δ2 > δ) ! ! !(X) !(X)

Table 2: Contribution of dynamic points (∆h (x) ̸= x) to utility of institution (ri ) and of predicted agents (rp ), when they switch from pre-adaptation x into post-adaptation ∆h (x). !denotes an increase in utility, and X a decrease. Green rows indicate similar impact for institution and agents (contributing to alignment), red indicates opposite impact, and grey indicates indifferent for the institution. Parentheses in predicted agents indicate contribution when δ2 > δ, if it does not match contribution when δ2 = 0. Parentheses in institution indicate contribution when ϵ > 0, if it does not match contribution when ϵ = 0. We can then study which changes an institution can make when switching from hpre (x) to hpost (x) (when becoming strategic). Note that, if our family of hypotheses H (where h ∈ H) is sufficiently expressive, we can independently estimate P(Y |X) for each X, and then threshold it to obtain classifier h(x). F.2.1

Short-term Alignment

Lemma F.5. (Support over positive predictions) Let the learned classifier be h(x) = 1{f (x) ≥ 0}, where f (x) estimates P(Y |X), and its boundary be ∂h = {x ∈ X : f (x) = 0}. Assume the family of hypotheses H is flexible enough that it can estimate independently P(Y |X) for each x. Assume full support over points that −1 post pre ) ∪ ∆ post (∂hpost ) ⊂ X , also δ2 = ϵ = 0, h can adapt towards hpre and hpost : ∆−1 ̸= hpre and ysco is hpre (∂h h O-nondecreasing with respect to xc . Then, we have that points obtaining a positive prediction under hpost are a subset of those obtaining a positive prediction under hpre : {x ∈ X : hpost (x) = 1} ⊂ {x ∈ X : hpre (x) = 1}. Proof. Any agent’s adaptation must fall in one of the four categories defined in F.4, since points only adapt to switch from h(x) = 0 into h(∆h (x)) = 1. Given H is flexible enough, hpost ̸= hpre only happens as a response to wasted effort or gaming, since the two remaining adaptations do not impact ri . ysco is O-nondecreasing with respect to xc . Hence, to improve utility as a response to gaming or wasted effort, the boundary should move from hpre to hpost along orthant Os . To prevent gaming, it should increase along the direction where ysco increases (along Os ). Awareness of wasted effort allows to incur in error by being overly demanding (also along Os ) knowing that points will self-correct, by switching, from hpost (x) yielding FN, into hpost (∆hpost (x)) yielding TP. hpost may gain from increasing wasted effort, if it avoids other errors made by hpre , such as FPs. Formally, we have that ∀xpost-∂ ∈ ∂post \ ∂pre , ∃ xpre-∂ ∈ ∂pre \ ∂post : xpost-∂ ∈ Os \ ⃗0 + xpre-∂ . From the full support assumption:

Góis, Günlük, Rosenfeld, Hegde, Lacoste-Julien, Sridhar −1 ′ pre ′ pre ) ⊂ X ⇒ ∀xpre-∂ ∈ ∂hpre ∃ x̃ ∈ ∆ pre (xpre-∂ ) ⊂ X : δ = min c(x̃, x ) s.t. (h ∆−1 (x ) = 1). hpre (∂h h ′ x

pre

Combining both results above, we have that ∃ x̃ : h (∆ (x̃)) = 1, hpost (∆hpost (x̃)) = 0, since any point x̃ pre pre post whose cost of adapting to h was δ and ∆h (x̃) ̸∈ ∂h , has cost of adapting to hpost as δ ′ > δ, hence will not adapt. hpre

Analogously, since the post-adapt boundary became more demanding, no point that is positively classified by hpost is negatively classified by hpre : ∀xpost-∂ ∈ ∂post \ ∂pre , ∃ xpre-∂ ∈ ∂pre : xpost-∂ ∈ xpre-∂ + Os ⇏ ∃ x̃ : hpost (∆hpost (x̃)) = 1, hpre (∆hpre (x̃)) = 0 Since we have points x̃ that lose their positive label post-adapt, and no point that gains one, then: {x ∈ X : hpost (x) = 1} ⊂ {x ∈ X : hpre (x) = 1} Under short term goals δ2 = ϵ = 0, for hpost ̸= hpre , a flexible enough H and O-nondecreasing ysco , we do not have aligned incentives. Proposition F.6. (Short-term misalignment) Let ∆rp-short be h-change for δ2 = 0, and hpost-short be optimal for ϵ = 0. Under the assumptions of Lemma F.5, we have:

∆rp-short (hpost-short , hpre ) < 0 Proof. From the proof of Lemma F.5 we have that hpost is more demanding than hpre , in the sense that ∀xpost-∂ ∈ ∂post \ ∂pre , ∃ xpre-∂ ∈ ∂pre \ ∂post : xpost-∂ ∈ xpre-∂ + Os \ ⃗0. Since ysco is O-nondecreasing with respect to xc , a point x̃ is classified as h(x̃) = 1 if ∃ xb ∈ ∂h : xb ≺Os x̃. We know ∀x̃, ∆hpre (x̃) ̸= x̃ ⇒ h(x̃) = 0, so when the boundary changes by summing v ∈ Os its distance to x̃ increases in Lp -norm. Hence ∀x̃, ∆hpost (x̃) ̸= ∆hpre (x̃), h(∆hpost (x̃)) = 1 : c(x̃, ∆hpost (x̃)) > c(x̃, ∆hpre (x̃)). From Lemma F.5, the number of points receiving δ from h(∆h (x)) = 1 will reduce. From the definition of rp (Definition 6.1), higher cost and reduced δ determine lower E [rp (h, x, u)], since we are x,u

assuming δ2 = 0. Therefore ∆rp-short (hpost-short , hpre ) < 0. F.2.2

Long-term Alignment

Assuming δ2 > 0 and ϵ = 0, we have the same hpost as when δ2 = ϵ = 0, since institution’s utility ri does not change. From Lemma F.5, we have that the boundary ∂hpost becomes more demanding than ∂hpre , by increasing along Os . Then for any x̃, if ∆hpost (x̃) ̸= ∆hpre (x̃), its change from hpre to hpost must have been one of the categories below: • (maint) Maintained FP or TP at higher cost; • (impr) Switched from gaming to improvement (FP→ TP); • (TP→ N) Switched from TP into FN or TN; • (FP→ TN) Switched from FP into TN. Denote a point’s change in adaptation cost as: ∆c(x) ≜ c(x, ∆hpost (x)) − c(x, ∆hpre (x)) To compute ∆rp (hpre , hpost ) we must then consider how each group’s utility rp changed:

The Role of Causal Features in Strategic Classification for Robustness and Alignment

• Increased cost of maintaining FP or TP: −∆c(x) • Gain of improving (FP→ TP): δ2 − ∆c(x) • Cost of TP→ N: −δ − ∆c(x) • Cost of FP→ FN: −(δ − δ2 ) − ∆c(x) R For each of the previous groups, denote their densities as: P(maint) := x∈{maint} P(x), and similarly P(impr), R P(TP → N), P(FP → TN). Their total costs are c(all) := x∈X ∆c(x)P(x). Proposition F.7. (Long-term alignment) Considering a flexible enough H and ϵ = 0, having alignment requires: δ2 >

c(all) + δ(P(TP → N) + P(FP → TN)) P(impr) + P(FP → TN)

Proof. ∆rp (hpost , hpre ) ≥ 0 ⇔ δ2 P(impr) − δP(TP → N) − (δ − δ2 )P(FP → TN) − c(all) ≥ 0 ⇔ δ2 > c(all)+δ(P(TP→N)+P(FP→TN)) P(impr)+P(FP→TN) As long as enough agents benefit from improvement, δ2 > δ is not required. One example of long-term alignment with δ2 < δ is in § E.2.3 in the appendix. F.3

Simulations

To understand Figure 4, we provide additional heatmaps in Figure 14. In (c) we have the same plot as in Figure 4, but for a wider range of ϵ. In (a) and (b) we have expected agent utilities under hpre and hpost , respectively. Note (c) is generated by subtracting (b)−(a). In (b), for low values of ϵ, the classifier hpost is always the same and does not incur any FPs, hence rp is not affected by variations in δ2 . Since hpre for low ϵ incurs some FPs, as δ2 increases agents progressively prefer hpost , as seen in (c). As epsilon increases to intermediate values (around ϵ ∈ (0.3, 0.65)), both hpre and hpost incur in more FPs, as a consequence of avoiding TNs. This makes agents prefer higher ϵ when δ2 is low. However, increasing δ2 reverses this trend, and agents are more harmed by hpre than by hpost , since hpre incurs more FPs. For high values of ϵ, both hpre and hpost arrive at the same solution.

(a) E [rp (hpre , x, u)], expected agent

(b)

expected

utility when minimizing ℓ0−1 unaware of agent adaptation.

agent utility when minimizing ℓ0−1 aware of agent adaptation.

ference between both heatmaps to the left. (hpost − hpre )

x,u

E [rp (hpost , x, u)],

x,u

(d) All three plots above consider ϵ when minimizing pre-adaptation ℓ0−1

Figure 14: Detail version of Figure 4, also using δ = 0.3. (c) is alignment ∆rp (hpost − hpre ), equal to Figure 4 but for a wider range of ϵ. (a) and (b) are expected agent utilities, where the subtraction (b)−(a) leads to plot (c).

Record · ID 229500 · SHA-256 4b100178981aa125
Retrieved via Conceptio — every document is proof-bundled with source, license, and retrieval metadata.