Learning to Incentivize Improvements from Strategic Agents 
Authors: Yatong Chen
Jialu Wang
Yang Liu
Venue: Accepted by TMLR ()

Abstract: Machine learning systems are often used in settings where individuals adapt their features to obtain a desired outcome. 
In such settings, strategic behavior leads to a sharp loss in model performance in deployment. In this work, we aim to address this problem by learning classifiers that encourage decision subjects to change their features in a way that leads to improvement in both predicted and true outcome. We frame the dynamics of prediction and adaptation as a two-stage game, and characterize optimal strategies for the model designer and its decision subjects. In benchmarks on simulated and real-world datasets, we find that classifiers trained using our method maintain the accuracy of existing approaches while inducing higher levels of improvement and less manipulation.

Published in Transactions on Machine Learning Research (06/2023)
Learning to Incentivize Improvements from Strategic Agents
Yatong Chen
ychen.990@ucsc..ede
Computer Science and Engineering University of Colifornia, Santa Cruz
Jialu Wang
faldict@ucsc. edu
Computer Science and Engèneering University of California, Santa Crus
Yang Liu
yonglin@uusc.edu
Computer Science and Engineering University of California, Santa Cruz
Reviewed OpenReview:
Abstract
Machine learning systems are often used in settings where individuals adapt their features to obtain desired outcome. In such settings, strategic behavior leads to sharp loss in model performance in deployment. In this work, aim to address this problem by learning classifiers that encourage decision subjects to change their features in way that leads to improvement in both predicted and true outcome. We frame the dynamics of prediction and adaptation as a two-stage game, and characterize optimal strategies for the model designer and its decision subjects. In benchmarks on simulated and real-world datasets, we find that classifiers trained using our method maintain the accuracy of existing approaches while inducing higher levels of improvement and less manipulation.
1 Introduction
Individuals subject to classifier's predictions may act strategically to influence their predictions. Such behavior, oflen referred to as stralegic manipulation (Hardt et al. 2016a), may lead to sharp deterioration in classification performance. However, not all strategic behavior is detrimental: in many applications, model designers stand to benefit from strategic adaptation if they deploy a classifier that incentivizes decision
subjects perform adaptations that improve their true outcome (Haghtalab al. 2020 Shavit al. 2020 For example:
Lending: In lending, classifier predicts loan applicant's ability to repay their loan. If the classifier is designed so to incentivize the applicants to improve their income, it will also improve the likelihood of repayment.
In online shopping, recommender system suggests products to customers based their relevance. Ideally, the algorithm should incentivize the product sellers to publish accurate product descriptions by aligning this with improved recommendation rankings.
Content Moderation:
Course design: an instructor designs schoolwork incentivize students invest their efforts on studying rather than cheating an exam (Kleinberg & Raghavan 2020)
Car insurance determination: an auto insurer tries prodict drivers' expected accident costs, and by designing determination criterion, encourages safe driving behavior (Haghtalab al. 2020 Shavit et al, 2020
1

---

Published in Transactions on Machine Learning Research (06/2023)
In this work, we study the following mechanism design problem: model designer needs to train classifier that will make predictions over decision subjects who will alter their features to obtain specific prediction. Our goal is to learn a classifier that is accurate and that incentivizes decision subjects to adapt their features in a way that improves both their predicted and truc outcomes. Our main contributions are as follows:
1. We introduce a new approach to handle strategic adaptation in machine learning, based on new concept we call the constructive adaptation risk, which trains classifiers that incentivize decision subjects to adapt their features in ways that improve true outcomes. Under the assumption a feature taxonomy that distinguishes improvable features (features that, changed, lead to changes in the true qualification) from non-causal features (which do not lead to changes in the truc qualification), we provide formal evidence that this risk captures both the strategic and constructive dimensions of decision subjects' behavior.
2. We characterize the dynamics of strategic decision subjects and the model designer in a classification setting using a two-player sequential game. We begin by generalizing cost functions used in previous works on strategic classification to the Mahalanobis distance, which provides way to capture correlations between changes in different. features. Under this generalization we derive closed-form expressions for the decision subjects' optimal strategies (Theorem []. These expressions (Section 3.3) reveal insights about decision subjects' behavior when the model designer uses non-causal features (features that do not affect the true outcome) as predictors.
3.
We formulate the problem of training such a desired classifier as a risk minimization problem. We evaluate our method on simulated and real-world datasets to demonstrate how it can be used to incentivize improvement discourage adversarial manipulation. Our empirical results show that our method outperforms existing approaches, even when some feature types are misspecified. In addition, provide a potential way to extend our main result into non-linear setting using LIME (Ribeiro et al. 2016).
The details for reproducing our experimental results can be found at con/ Bttp///SSSSSAAAAA/CCC/tttttttttT
1.1
Related work
Our paper builds on the strategic classification literature in machine learning Hardt et al.
2016a
Cai et al,
2015
Ben-Porat & Tennenholtz, 2017; Chen et al.] 2018 Dong et al., 2018 Dekel ct al.
2010 Chen al.
2020
Taittss et al. 2019). We study the interactions between model designer and decision subjects using
sequential two-player Stackelberg game (see e.g., Hardt et al. 2016a Brückner & Scheffer 2011 Balcan et al., 2015
Dong et al.) 2018 for similar formulations). Departing from previous work, which aims to suppress all adaptations, we consider a sctting in which stratogic adaptation can consist of manipulation as well as improvement. Our broader goal of designing a classifier that encourages improvement is characteristic of recent work in this area (see e.g.. Kleinberg & Raghavan 2020 Haghtalab et al. 2020;; Shavit et al.) 2020 Rosenfeld et al.) 2020). Specifically, Haaghaalb et al. (2020) study how to design an evaluation mochanism that incentivizes individuals to improve a desired quality. However, the success of their method requires explicit assumptions on the linear mapping of features to true qualifications, as well as projection matrix P that maps the observed features back to the full features. Their setting also does not account for correlations between different features. Another recent work by Shavit et al. (2020) also focuses on finding a decision rule that maximizes decision subjects' true qualifications. Their setting similar to ours, but they focus on how decision makers can perform causal interventions through the deployment of different decision rules, rather than designing a classifier relying only on observational data. Moreover, they assume that decision subjects take actions in some action space that maps linearly to features in feature space; this also does not capture correlations between features.
This paper also broadly relates to work on recourse (Ustun et al. 2019 Venkalasuuramaanian & Alfano 2020;
Karimi et al. 2020a] Gupta et al. 2019 Karimi et al. 2020b von Kügelgen et al. 22020). Formally speaking, recourse defined as the ability of a person to obtain desired outcome from a fixed model (Ustun et al., 2019). In our paper, we aim to fit models that provide constructive recourse, i.c. actions that allow decision subjects to improve both their predicted and true outcomes.
2

---

Published in Transactions on Machine Learning Research (06/2023)
Our approach may be useful for mitigating the disparate effects of strategic adaptation (Hu et al. 2019
Milli et al.
2019 Liu et al. 2020) that stem from differences in the cost of manipulation (see Proposition
Our results may be helpful for developing robust classifiers in dynamic environments, where both decision subjects' features and the deployed models may vary across time periods (Kilbertus et al., 2020 Shavit
et al. 2020: Liu & Chen 2017). Also relevant is the recent work on performative prediction (Perdomo el al.
2020
et al., 2020), in which the choice of model itself affects the distribution over instances. However, this literature differs from ours in that we focus on inducing
Miller et al.) 22021] Izzo et al., 2021 Mendler-Dünnn
constructive adaptations from decision subjects at single step, rather than finding an optimal policy that incurs the minimum deployment error.
Due to page limit, we provide additional related work on strategic classification, algorithmic recourse, causal modeling, and incentive design in Appendix
2
Problem statement
In this section, we describe our approach to training a classifier that incentivizes improving actions.
2.1 Preliminaries
We consider standard classification task of training a classifier h R² + {-1,+1} from dataset of n examples {22,, y;) where example consists of vector of features o; Fº and binary label V (11,+1]. Example corresponds to an agent who wishes to receive positive prediction h(x,) +1, and who will alter their features to obtain such prediction once the model is deployed. We assume that an agent's true qualification (or label), denoted as y, is always function of its feature vector and define the truc unknown qualification function y : X {0,1) the mapping between the feature vector x E R and {0, 1}.
the true qualification /labell
We formalize these dynamics as a sequential game between the following two players: the model designer, and the decision subjects The objectives for the two players are as follows:
1. A model designer, who trains a classifier h : X + +1] from a hypothesis class H,which is also their action space.
2. Decision subjects, who adapt their features from x. to a' so as to be assigned h(x') = +1 if possible. We assume that decision subjects ineur cost for altering their features, which we represent using cost function X' X + R*. The action space for the decision subjects includes all feature vectors that are within given manipulation budget B, namely Va E IR. such that e(x, x') < B.
We intentionally do not provide the formal definitions of the utilities for the two players here due to the need to provide a clear and accessible introduction to our framework. We will provide more detailed discussions on the agent and decision maker's utility function in Section 3.2 and Section 2.3 respectively.
We assume that dccision subjects know the model designer's classifier, and the model designer knows the decision subjects' cost function. Decision subjects alter their features based on their current features æ, the cost function c, and the classifier h, that their altered features can be written x, A(x; h, c) where A(-) is the best response function. The model designer only observes the altered feature x, but not the original and private one z the decision subject holds. In other words, we consider the standard setting in strategic classification where the model designer has no strong verification power to verify truthfulness of x..
We allow adaptations that alter the true qualification y. In practice, the relationship between features and true qualification unknown, and in fact is known that distinguishing causal features (features that affect the true outcome) from non-causal features reduces to solving non-trivial causal inference problem Miller et al. (2020) Addressing this aspect is not the aim of the present work; instead, we will assume that changes in certain features are known to affect the qualification - for example, in loan application, such features can
Thhoogghot the paper, we will also use strategic agents, or agents, interchangeably.
3

---

Published in Transactions on Machine Learning Research (06/2023)
be the agent's education level and salary, and changing those features will affect qualification is the agent's ability to pay for the loan.
When an agent adapts its feature vector from a to A(x), its qualification becomes v()(z)), which may differ from y(z). We consider a setting in which during the training process, the decision maker cannot observe how decision subjects' true qualifications change after they alter their features. We introduced the shorthand notation y refer to (z), the qualification for the original feature vector, for the sake of simplicity. For the rest of our paper, label y always denotes the true qualification before adaptation. 2.2 Background
In standard prediction setting, model designer trains classifier that minimizes the empirical risk:
hERM
arg min (h) NEW
where (h) Ex>p[L(h(x)) # y)]. This classifier performs poorly in setting with strategic adaptation, since the model is deployed population with different distribution over A' (as decision subjects alter their features) and y (as changes in features may alter true outcomes).
Existing approaches in strategic classification tackle these issues by training a classifier that is robust to all adaptation. This approach treats all adaptation as undesirable, and seeks to maximize accuracy by discouraging entirely. Formally, they train a classifier that minimizes the strategic risk:
hsc E arg min Rsc (h) NEH
where (sc(h) = Eg-DD/ (Ib() # y)1, and A(x, h; denotes the features of decision subject after adaptation. However, this classifier still has suboptimal accuracy because y changes as result of the adaptation in æ. Further, this design choice misses the opportunity to encourage a profile æ to truly improve to change their y-
2.3
CA risk: minimizing error while encouraging constructive adaptation
In many applications, model designers are better off when decision subjects adapt their features in way that yields specific true outcome, such as y = +1. Consider typical lending application where model is used to predict whether customer will repay a loan. In this case, model designer benefits from y = +1, as this means that a borrower will repay their loan.
2.3.1 Ideal objective function for the decision maker
Ideally, the decision maker should aim to classify the agents correctly using their adapted features with respect to the corresponding new qualification. Mathematically, this corresponds to training classifier h* that minimizes the following quantity:
h" arg ((( v hEH
(1)
where A(x) the agent's adapted feature, and v()(z)) the true qualification after the adaptation. However, since the true mapping function y _dd + {0, 1} is unknown, and the decision maker cannot observe how decision subjects' true qualifications change after they alter their features, we need to propose an alternative approach to achieve similar goals of this ideal objective function, which we call CA risk minimization.
2.3.2 Our proposed CA risk
To help explain our proposed approach, we assume that we can write x = [x] 2M FiMl where 2n RM and FIM denote the following categories of features:
Immudable features (2i)) which cannot be altered (e.g. race, age).
4

---

Published in Transactions on Machine Learning Research (06/2023)
Improvable features (zi), which can be altered in way that will either increase decrease the true outcome v(œ) (e.g. increasing education level might help improve the probability of repayment).
Manipulable features (#M), which can be altered without changing the true outcome y(z) (c.g. social media presence, which can be used as a proxy for influence). Notice that it is the change these features that is undesirable; the features themselves may still be useful for prediction.
Incomplete taxonomy of features. There may also be features that can be altered but whose effect is unknown. In this work, we treat them as manipulable features. We would like to point out that in practice, implementing our proposed solution does not require the decision-maker know exactly how to characterize every single feature. In fact, our method can be applied to settings where the decision-makers only know some features are improvable and focus on incentivizing adaptations on them, while treating changes on the rest of the features as undesirable. In this case, using our training method is still strictly better than performing no intervention (i.c. simply letting decision subjects perform their unconstrained best response).
X1
MI
Y
7
X
M2
Figure 1: A causal DAG for the toy data. Zi and Zo are improvable features that determine the true qualification Y, Xı Z₁, and X2 is noisy proxy for Zz. In our context, all we require is the knowledge that X1, X2 are the factors that causally affect Y, rather than complete knowledge of the DAG. We can dircctly observe X, and X2 but not Z, or Zz. In addition, Mj and M2 are manipulated features that correlate with Y.
Please see Figure for a demonstration the differences between improvable and manipulable features. We also use FA = [a] MM] to denote the actionable features, and dA to denote its dimension. Note that the question of how to decide which features are of which type beyond the scope of the present work; however, this is the topic of intense study in the causal inference literature (Miller al., 2020 Analogously, we define the following variants of the best response function A:
a (2, c):: the improving best response, which involves adaptation that only alters improvable features.
-"- = = l;; e): the manipulating best response, which involves an adaplation that only alters manipulable features.
Note that in reality, a decision subject can still alter both types of features, which means that they will perform A(x, h;; c), unless the model designer explicitly forbids changing certain features. However, still worth distinguishing different types of best responses when the model designer designs the classifier: we can think of the improving best. response A the best possible adaplation which only consists of honest improvement, while the manipulating best response AM is the worst possible adaptation that consists of pure manipulation. The model designer would like to design classifier such that for the decision subjects, Axx, h; c) appears to be close to (x, c). We therefore propose to train classifier that minimizes the constructive adaplation (CA) risk ReA, which balances robustness to manipulation and incentivization of improvement:
hicA arg arg (h)(h) = RM (h) + Rh) NEW.
The first term, (M) Eg (1(h(() # v)], is the manipulation risk, which penalizes pure manipulation. The second term, (h) EyyDD! (h(x², # +1)], the improvement risk, which rewards decision subjects for
5

---

Published in Transactions on Machine Learning Research (06/2023)
playing their improving best response. The parameter À 0 trades off between these competing objectives. Setting À -> 0 results in objective that simply discourages manipulation, whereas increasing À - oo yields trivial classifier that always predicts +1.
A natural question to ask is: how good the proposed objective function Equation (2 is compared to the ideal objective function in Equation ( We show that the two terms in the objective function can be viewed as proxies for the ideal objective function. In particular, in Section 4 we show that under reasonable conditions, the following hold:
The first term, RM (h), is an upper bound on (h). Thus minimizing the manipulation risk also minimizes the traditional strategic risk (Proposition 5).
A decrease in the second term, (h) reflects increase in Pr(y(=') +1). Thus improvement in the prediction outcome aligns with improvement in the true qualification (Proposition 6
3
Decision subjects' best response
We now characterize the decision subjects' best response.
3.1
Setup
We restrict analysis to the setting in which model designer trains linear classifier h(x) = sign(w (T)) x)
where w [ug. wI...., wal E Rd+1 denotes vector of + 1 weights. We capture the cost of altering to through the Mahalanobis norm of the changes 2
clz,²') V(eA ( IA' (zA -ZA')
Here, S- E 4R x d is symmetric cost covariance matriz in which ST. represents the cost of altering features j and & simultaneously. To ensure that c(-) is a valid norm, we require s to be positive defivile, meaning FA 55 x. > for all IA + 0 E Rd Additionally, we assume s is block matrix of the form
(S (s
(S ) (S- )M or = Sj SIM
S
s- =
3))
(S-)) Mi
SMi
SM
Notice that the 1-th block of matrix S_1 (i.e. (i) does not necessarily equal to its inverse's I-th block component (i.e. S S
We allow the cost matrix contain non-zero elements on non-diagonal entries. This means that our results hold even when there are interaction effects when altering multiple features. This generalizes prior work on strategic classification in which the cost is based on the l norm of the changes, which is tantamount to setting S = J, and therefore assumes the change in each feature cibtributes independently to the overall cost (sce o.g., Hardt et al. 2016a Haghtalab et al. 2020).
3.2 Decision subject's best response model
we can define and analyze the decision subjects' best response. We start by defining the decision subject's s payoff function. Given a classifier h, decision subject who alters their features from x to x' derives total utility
Given the assumptions of Section 3.1
Uzzz'') h(x²) - c(x,x')
Naturally, a decision subject tries maximize their utility; that is, they play their best response:
Definition 3.1 (F-Best Response Function). Let F (I, A}, and let xF denote the set of vectors that differ from x only in features of lype F. Lel AF : X - X' denole the F-best response of a decision subject with features x to h, defined as:
AF(x) = arg max (xx 2'EX((2) (z)
Since immutable features Z' cannot be altered, the cost function involves only the actionable features a

---

Published in Transactions on Machine Learning Research (06/2023)
Setting F == gives the improving best response (1(x), in which the adaptation changes only the improvable features; setting F = M yields the manipulating best response (m()), in which only manipulable features are changed. Setting F= A, we get the standard unconstroined best response (A in which any actionable features can be changed. As we mentioned carlier, we will also use x¹, == AF(x) as shorthand for the F-best response, and we denote (x)) == Ax(x).
Intuitively, the cost of manipulation should be smaller than the cost of actual improvement. For example, improving onc's coding skills should take more effort, and thus be more costly, than simply memorizing answers to coding problems. As result, unconstrained best response (xx) to flip negative decision more casily than the improving best response A1(x). In Section 3.3 we formalize this notion (Proposition 2
would expect the gaming best response (m(z) and the
For case of notation, let Sp = ((S-)))) > We prove the following theorem characterizing the decision subject's different best responses:
Theorem 1 (F-Best Response in Closed-Form). Given a linear threshold function h(x) - sign(w x) and a
TouT
decision subject with features x such that h(x) = 1, reorder the features so that x = [ | IA(F rIM], and let Ω2 WF T Spup. Then x has F-best response
w of
SpOF
FAYF
FIM-
if w
AF(x)
(4)
otherwise
with correspouding cost
w x
S
2
c(zx, (F())
Dt
=
0
otherwise
All proofs in this section are included in Appendix B
Example: When F = M, op TM and #AYE = [zy]. After reordering features, we get the following closod-form
expression for the manipulating best response:
1
TM
w SMMM
| TiM
if
S
2
(x
otherwise
with corresponding cost.
I w Duu
if
c(x, Am(z))
DM
=
0
otherwise
3.3 Discussion
We now discuss the implications of different decision subject's responses derived in Theorem In this section, we consider a slightly more structured cost matrix that is diagonal blocked matrix (in which case, Sm SMi 0), which corresponds to a setting where there are no correlations between the cost of changing manipulated feature versus the cost of changing improvable features. We include the proofs in Appendix C
Firstly, we demonstrate a basic limitation for the model designer: if the classifier uses any manipulable features predictors, then decision subjects will find way to exploit them. Hence the only way to avoid any possibility of manipulation is to train classifier without such features.
Proposition 1 (Preventing Manipulation Hard). Suppose there erists a manipulated feature (m) whose weight in the classifier w/A (m) is nonzero. Then for almost every x E X, A (m) (x) o x (m)
In our paper, the subscript (e.g. xm) refers to the entire feature vector (e.g., Zm Rm where dm the total number of the manipulative features), while the superseript. (m) refers to the particular index of particular manipulation feature.
7

---

Published in Transactions on Machine Learning Research (06/2023)
Next, we show that the unconstrained best response A dominates the improving best response (1(z), thus highlighting the difficulty of inducing decision subjects to change only their improvable features when they are also allowed to change manipulable features.
Proposition 2 (Unconstrained Best Response Dominates Improving Best Respouse). Suppose there exists (m) is nonzero. Then, if a decision subject con flip her decision by playing the improving best response, she can also do so by playing the unconstrained best response. The converse is not true: there exist decision subjects who can flip their predictions through their unconstrained best response but not their improving best response.
manipulable feature m(()) whose weight in the classifier w'A
Next, we show how correlations between features affect the cost of adaptation. This can be demonstrated by looking any cost. matrix and adding small nonzero quantity to some i,j-th and j, i-th entries. Such perturbation can reduce every decision subject's best-response cost:
Proposition 3 (Correlations between Features May Reduce Cost). For any cost matriz 5-1 and any nontrivial classifier h, there exist indices k, l E [dA] and T E R such that every feature vector a has lower best- respoes cost under the cost matrix 5-1 given by
ST +T, S
fi=kkj=
= =
olherwise
than under s that is, Cg-1 A(x)) < cs- (2, (x)) for all
In many applications, decision subjects may incur different costs for modifying their features, resulting in disparities in prediction outcomes (see Hu et al. 2019 for a discussion). To formalize this phenomenon, suppose & and & are two groups whose costs of changing improvable features are identical, but members of + incur higher costs for changing manipulable features. Tet & and vp be two people from these groups who share the same profile, i.c. Fg Fzg We show the following:
Proposition 4 (Cost Disparities between Subgroups). Suppose there exists a manipulated feature x (m) whose corresponding weight in the classifier w())) nonzero. Then if decision subjects are allowed to modify any features, & must pay higher cost than vb to flip their classification decision.
Proposition | highlights the importance for model designer to account for these differences when serving population with heterogeneous subgroups. Indeed, when one group achieves more favorable prediction outcomes due to a lower cost of manipulation, our method mitigates the cost disparities between different subgroups by oncouraging changes in improvable features and penalizing manipulation.
4 Constructive adaptation risk minimization
In this section we analyze the training objective for the model designer, formulating it as an empirical risk minimization (ERM) problem. Any omitted details be found in Appendix D
The model designer's goal is to publish classifier h that maximizes the classification accuracy while incentivizing individuals to change their improvable features. By Theorem we have
TTe The
27
I'
SMuM
ZiM
if 2 Sa otherwise
(5)
F,
x²_
21
Q
Skwj
2
ZiM
if w <
(6)
otherwisc
Recall from Section
2.3 that the model designer's optimization program is as follows:
min
[1(h(=") y)1 + E [h((aa) + +1)]
KER
rDD
s.L. F. in Eq.
5 _²__ in Eqq
(7)

---

Published in Transactions on Machine Learning Research (06/2023)
Interpreting the objective. The two terms in the objective function can be viewed as proxies for two other familiar objectives. The first term, Bz-D [1 (h(x")) & v)], directly penalizes pure manipulation. But as the following proposition suggests, minimizing this term also minimizes the traditional strategic risk when the true qualification does not change:
Proposition 5. Assume that the manipulating best response is more likely to result in a positive prediction than the unconstruined best response, given that the true labels do not change. Then
E RND
[1[h(x.)
+ 1 vl S E [I((((")) 9)]. IND
Intuitively, the assumption within Proposition 5 may be fulfilled in settings where a population of agents cach have the same fixed budget on the cost or effort they are willing to expend, and manipulative or cheating-type actions (for instance, (controlling recent purchase behaviors and borrowing money from family members right before applying for a credit card) confer greater immediate advantages than honest improvement (e.g. spending frugally and accruing savings from personal income over several years).
The second term, Eg (M(at)) * +1)], explicitly rewards decision subjects for playing their improving best response (closely related to the notion of recourse). Of course, without positing a causal graph, cannot know whether performing the improving best response leads to a positive change in the true qualification, namely whether (Y) = +1; however, when the distribution of X may change but not the conditional label distribution Pr(Y|X) we can show that an increase in Pr(h(X) = +1) reflects an increase in Pr(Y = +1). This gives formal evidence that our prediction outcome aligns with improvement in the true qualification:
Proposition 6. Let D be the new distribution after decision subject's best response. Denote wn(x) = (X=x) denote the amount of adaptation induced at feature vector æ. Suppose y(X) and h(X) are both positively correlated with wn
Pra(X==)
wx(X) (X), and that the distribution of the true label Y given a particular feature vector X is unchanged is the same before and after adaptation. Then the following are equivalent:
Pr[h(x')) = +1] > Pr[h(z) = +1] + Pr(u(a")) = +1] > Pr[u(x) = +1].
Proofs of Propositions 5 and f can be found in Appendix D.1 and
D.2
We also provide further derivation for
model designer's objective function in Appendix D.3
Here we provide some motivation for the premise of Proposition An unchanged Pr(Y|X) means that the mapping from feature vector X to its corresponding true qualification Y(X) remains the same despite population-level distribution shift. This is a useful and natural simplification in numerous settings. An example is in credit card applications: suppose X is an applicant's credit score and Y is whether they are truly qualified. For people with the same credit score, we assume they have equal chances of being truly qualified.
Algorithm 1 Best Response for Non-Linear Model
Input: Non-Linear classifier h, an individual data point r
Result: x² and x²,
Step 1. Call LIME to get the approximated weights w of local linear classifier for non-linear model h around the individual point æ
Step 2. Substitute w into Eq. 5 and Eq. (6 to get x. and x',, respectively
Extension to non-linear models. The above approach in Eq. 7 presumes linear classifier such that we can derive a closc-form solution of the agent's 's best response. However, the recourse scheme will be typically infeasible with non-linear classifiers. To extend our approach to nonlinear models, we propose to substitute 2 and z², in Eq. (7) with an approximated best response acquired from a local linear classifier. We note that a prior work LIME [Ribeiro et al.] (2166) can provide an approximate lincar decision boundary for arbitrary individual points any non-linear models. The idea is to sample the spherical neighborhood of the data point and fit. local linear model with the target model's certified predictions. As shown in A Algorithm 1
9

---

Published in Transactions on Machine Learning Research (06/2023)
integrate LIME into the oracle that can return any decision subjects' best response in terms of the approximated local linear classifier. Once get the best response x- and x.,, we iteratively plug them back to Eqq 77) as the learning objective of the non-linear classifier. We will demonstrate the effectiveness of this oracle procodure when optimizing a non-linear neural network with gradient descent in Appendix F Nonetheless, even with the above extension, all of our theoretical guarantees is not Atraightforwardl clear to analysis with an oracle of non-linear models' best response, so we let the current paper focus on linear models.
5 Experiments
In this section, we present empirical results to benchmark our proposed method on synthetic and real-world datasets. We test. the effectiveness of our approach in terms of its ability to incentivize improvement as well as to disincentivize manipulation (see Evaluation Criteria for details). We also compare its performance with other standard approaches (sce Methods). Our submission includes all datasets, scripts, and source code used to reproduce the results in this section.
5.1 Setup
Datasets and Cost Matrix. We consider five datasets:
toy, synthetic dataset based on the causal DAG in Fig. D credit, dataset for predicting whether individual will default on upcoming credit payment Yeh & Lien 2009); adult, census-based dataset for predicting adult annual incomes; german, dataset to assess credit risk in loans; and spambase, a dataset for email spam detection. The last three are from the UCT MI. Repository (Dua & Graff 2017). We provide a detailed description of each dataset along with a partitioning of features in Table 3 in the Appendix.
We assume the cost of manipulation is lower than that of improvement and refer the specific cost matrix S to Appendix F.2 in particular, specify the cost matrix S as follows: use cost matrices S / and SM -1 = 0.2I. We also provide results for non-diagonal cost matrix in the Appendix F.4
1, if j and i eel if jj and je M 1. if the cost of changing features i and j are negatively correlated
0.2,
S.y'
1, if the cost changing features i and j are positively correlated otherwise
0.
We use the credit dataset as a demonstration of how we specify the non-diagonal element in the cost matrix. For two feature variables that have a positive correlation, c.g., CheckingccoounBalluce and AaningsAcoou//Baamcc,, we assign -1 to the corresponding elements in the cost matrix S. For two feature variables that have negative correlation, e.g., Cheesking to the corresponding elements in the cost matrix. In practice, the cost matrix S should be determined using domain expertise. The purpose of the cost matrix used in these experiments is not to accurately specify costs per se, but to demonstrate the relative difficulty of changing different features.
and MisseddPayments we assign +1
Methods. We fit linear classifiers for each dataset using the following methods: ST, a static classifier trained using lz-logistic regression without accounting for strategic adaptation; DF, classifier trained using Ez-logistic regression without any manipulated features; MP, a classifier that considers the agent's unconstrained best response (i.e. with changes in any actionable features TA allowed) during training, as typically done in the strategic classification literature (Hardt et al. 2016a CA, linear logistic regression classifier that results from solving the optimization program in Eq. [23). which is a smooth differentiable surrogate version of
the objective function Eq. Please refer to Appendix D.3 for a detailed derivation. Using the BFGS
algorithm Byrd et al. 1995 J. CA represents our approach.
Evaluation Criteria. We run each method with 5-fold cross- validation and report the following:
10

---

Published in Transactions on Machine Learning Research (06/2023)
Eed orro dnulyyteet
0.34
SIEE CITE DE deplivtiie
tash ertee at deddloooonn Pestloymmnnt
THE SIVE dng opteeet prgornnrent Dos
0.30
Povooi 0000
0:5
0.32
0.22
0.38
0.20
0.22
lambda Dog scale)
lamdda (log stale)
lumbda flog scale)
lambda Dog scale)
(a) credit
(b) adul:
(c) german
(d) Spambase
We plot the trade-off between test error at deployment and improvement rate in terms of cost matrix. We observe that the test error increases consistently with the increase of the improvement rate. Table I: Performance metrics for different specifications (Spec.) which features may be misspecified. For each method, we report test error, deployment error, and improvement rate. In Full, the model designer has full knowledge of the causal DAG. In Mis. M, mistaken for an improvable feature. In Mis. II, the improvable feature X1 is miscategorized manipulable.
Figure 2:
METHODS
Spec.
Metrics
ST
DF
MP
CA
test error deployment ervor
10.29
28.0
11.91
11.62
Full
35.79
35.15
24.1
20.61
improvement rale
11.54
13.13
14.63
23.49
Lest. error
11.39
10.52
11.26
11.04
Mis.
deployment error
37.37
10.53
19.79
25.30
improvement rate
37.23
39.74
0.62
23.04
test error deployment error
10.58
35.77
29.52
10.80
Mis. II
12.37
41.51
27.68
23.58
improvement rate
1.12
5.74
3.36
19.82
Test Error: the error of a classifier after training but before decision subjects' adaptations, i.c. Emay)> 1[h(x)) + y).
(Worst-Cass Deployment Error: the lest error of classifier after decision subjects play their manipulating best response, i.e. B( 1 [h(x"") # y].
(Best- Cast-Case Improvement Rate: the percent of improvement, defined as the proportion of the population who originally would be rejectod but are accepted if they perform constructive adaptation (improving best response), i.e. B(Z)) [[h(x'.) +1 (()) -1].
5.2 Controlled experiments on synthetic dataset
We perform controlled experiments using synthetic toy dataset to test the effectiveness of our model at incentivizing improvement in various situations. As shown in Fig. [ we set Z₁ and Zg as improvable features, X, and X₂ as their corresponding noisy proxies, M1 and M2 as manipulable features, and Y as the true outcome. Since we have full knowledge of this DAG structure, we can observe the changes in the true outcome after the decision subject's best response. As shown Table [ Our method achieves the lowest deployment error (20.61%) and the best improvement rate (23.04%) when the model designer has full knowledge of the causal graph.
We also run experiments in which some features are misspecified, simulating realistic scenarios in which the model designer may not be able to observe all the improvable features (Haghtalab et al. 2020 Shavit et al. 2020). or mistakes one type of feature for another. We model these situations by changing M, into an improvable feature and X, into a manipulable feature; the results, shown in Table [ show that our classifier maintains relatively high improvement in these cases, without sacrificing much deployment accuracy.
11

---

Published in Transactions on Machine Learning Research (06/2023)
Table 2: Performance metrics for all methods over real data sets with non-diagonal cost matrix. We report the mean and standard deviation for 5-fold cross validation. The constructive adaptation (CA) consistently achieves high accuracy deployment while providing the highest improvement rates across all four datasets.
METHODS
Dataset
Metrics test error deploy error
ST
DF
MP
CA
29.52 = 0.37
29.66 = 0.40
29.63 + 0.41
29.60 + 0.44
CREDTT
31.25 0.56
29.66 + 0.40
29.41 + 0.32
29.49 + 0.38
improvement rate
46.35 = 3.81
44.71 = 4.75
36.76 + 0.53
48.27 = 5.50
test error deploy error
23.05 = 0.47
33.55 + 0.73
24.94 + 0.52
27.22 + 0.65
ADULT
38.64 = 4.46
33.55 + 0.73
26.85 + 0.59
29.34 1 0.45
improvement rote
30.92 = 3.31
60.63 = 29.40
36.70 = 1.62
63. + 7.80
test error deploy error improvement. rale
30.85 = 0.82
36.10 + 1.97
33.25 + 1.44
34.70 + 2.15
GERMAN
33.40 = 1.78
36.10 - 1.97
34.60 + 1.94
34.25 + 1.78
41.20 = 5.77
42.10 + 9.07
33.50 2.53
56.10 6.40
test error deploy error
7.11 = 0.52
10.18 + 0.45
11.52 + 0.12
14.37 + 0.24
SPAMBASE
22.40 = 3.14
10.18 = 0.45
12.92 + 0.58
14.70 + 0.36
improvement rule
40.04 + 13.06
32.46 + 14.63
26.42 + 4.80
43.98 + 6.18
5.3 Results
We summarize the performance of each method in Table _ To wrap up, our method produces classifiers that achieve almost the highest deployment accuracy while providing the highest percentage of improvement across all four datasets. The static classifier, which does not account for adaptations, is vulnerable to strategic manipulation and consequently has the highest deployment error on every dataset. Naively cutting off the manipulated features may harm the accuracy at test time DF incurs high test errors on Adult (33.55%) and German (36.10)). In particular, the strategic classificr MP induces the lowest improvement rates on the Credit (36.6%%) and German (34.50%) datasels.
Effect of tradc-off paramcter X. Fig. 2 shows the performance of linear classifiers for different values of on four real datasels. Note that, since the objective function non-convex, the trends for test error deployment are necessarily monotonic. In general, we observe trade-off between the improvement rate and deployment error: both increase À increases from 0.01 10 in all four datasets.
6 Conclusion
In this work, we study how to train a linear classifier that encourages constructive adaption. We characterize the equilibrium behavior of both the decision subjects and the model designer, and prove other formal statements about the possibilities and limits of constructive adaptation. Finally, our empirical evaluations demonstrate that classifiers trained via our method achieve favorable trade-offs between predictive accuracy and inducing constructive behavior. Our work has several limitations:
1. As first foray into strategic classification with constructive adaptation, our focus linear threshold classifiers helps capture the challenges unique to this setting; indeed, this is ultimately what allows for closed-form best response (Theorem I even with significantly more general cost function than in preceding literature. However, this is clearly not true of many models actually in deployment.
2. In order to focus on the strategic aspects constructive adaptation, we assume that the feature taxonomy is simply given; however, distinguishing improvable fcatures from non-improvable features is an interesting question in its own right, and has been shown to be reducible nontrivial causal inference problem Miller et al. 2020).
12

---

Published in Transactions on Machine Learning Research (06/2023)
3. In real-world scenarios, causal features are often intertwined with non-causal features, and improving may affect the other. While in our paper, we simplify the setting by assuming independence wetn the effects, we acknowledge that this is not always the case in practice. One potential way to address this issue is to incorporate additional modeling techniques that account for the causal interactions between leatures, such as causal inference methods or structural equation modeling.
Boarder Impact. Since our method incentivizes people to behave in certain way, to ensure it works fairly and accurately in practice it should be paired with a rigorous study of the causal relationship between features to decide which are improvable versus manipulable.
Acknowledgments
This work is partially supported by the National Science Foundation (NSF) under grants ITS-2143880 and IIS-2040800.
References
Alekh Agarwal, Alina Beygelzimer Miroslav Dudík, John Langford, and Hanna Wallach. A reductions approach to fair classification. In International Conference on Machine Learning, pp. 60-69. PMLR, 2018,
Maria-Florina Balcan, Avrim Blum, Nika Haghtalab, and Ariel D Procaccia. Commitment without regrets: Online learning in stackelberg security games. In Proceedings of the sinteenth ACM conference economics and computation, pp. 61 78, 2015.
Yahav Bechavod, Katrina Ligett, Zhiwci Steven Wu, and Juba Ziani. Causal feature discovery through strategic modification, 2020.
Rachel KE Bellamy, Kuntal Dey, Michael Hind, Samuel C Hoffman, Stephanie Houde, Kalapriya Kannan, Pranay Lohia, Jacquelyn Martino, Sameep Mehta, Aleksandra Mojsilovic, et al. Ai fairness 360: An extensible toolkit for detecting, understanding. and mitigating unwanted algorithmic bias. arXio preprint arXiv:1810.0100 2018.
Omer PoraP and Moshe Tennenholtz. Best response regression. In Proceedings of the 31st International Conference on Neural Information Processing Systems, pp. 1498-1507, 2017.
Umang Bhatt, Alice Xiang, Shubham Sharma, Adrian Weller, Ankur Taly, Yunhan Jía, Joydeep Ghosh, Ruchir Puri, José MF Moura, and Peter Eckersley. Explainable machine learning in deployment. In
Proceedings of the 2020 Conference on Fairness, Accountability, and Transparency, pp. 648 657, 2020.
Stephen Boyd and Lieven Vandenberghe. Conver optimization. Cambridge university press, 2004.
Michael Brückner and Tobias Scheffer. Stackelberg games for adversarial prediction problems. In Proceedings of the 17th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 547-555, 2011.
Richard H. Byrd, Peihuang Lu, Jorge Nocedal, and Ciyou Zhu. A limited memory algorithm for bound constrained optimization. SIAM J. Sci. Comput. 16(5):1190 1208, September 1995.
Yang Cai, Constantinos Daskalakis, and Christos Papadimitriou. Optimum statistical estimation with strategic data sources. In Conference Learning Theory, pp. 280-296. PMLR, 2015.
Yiling Chen, Chara Podimata, Ariel Procaccia, and Nisarg Shah. Strategyproof linear regression high dimensions. In Proceedings of the 2018 ACM Conference on Economics and Compulation, pp. 9 9-26, 2018.
Yiling Chen, Yang Liu, and Chara Podimata. Learning strategy-aware linear classifiers, 2020.
Alexandra Chouldechova. Fair prediction with disparate impact: A study of bias recidivism prediction instruments. Big data, 5(2):153-110) 163, 2017.
13

---

Published in Transactions on Machine Learning Research (06/2023)
Sarah Dean, Sarah Rich, and Benjamin Recht. Recommendations and user agency: the reachability of collaboratively-filteeed information. In Proceedings of the 2020 Conference on Fairness, Accounlabilily, and Trensperency, pp. 436 445, 2020.
Ofer Dekel, Felix Fischer, and Ariel D Procaccia. Incentive compatible regression learning. Journal of Compuler and System Sciences, 76(8):759 777, 2010.
Jinshuo Dong, Aaron Roth, Zachary Schutzman, Bo Waggoner, and Zhiwei Steven Wu. Strategic classification from revealed preferences. In Proceedings of the 2018 ACM Conference on Economics and Computation, pp. 55-70, 2018.
Dheeru Dua and Casey Graff. UCI machine learning repository, 2017. URL http::/archive.iicom uci
edu/ml ml
Cynthia Dwork, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Richard Zomel. Fairness through awareness. In Proceedings of the 3rd innovalions in theoretical computer science conference, pp. 214 226, 2012.
Frederick Eberhardt and Richard Scheines. Interventions and causal inference. Philosophy of Science, 74(5): 981 995, 2007. ISSN 00318248, 1539767X.
Michael Feldman, Sorelle A Friedler, John Moeller, Carlos Scheidegger, and Suresh Venkatasuubamannan. Certifying and removing disparate impact. In proceedings of the 21th ACM SIGKDD international conference knowledge discovery and data mining, pp. 259-268, 2015.
Gene H. Golub and Charles F Van Loan. Malris compulations, volume JHU press, 2013.
Vivek Gupta, Pegah Nokhiz, Chitradeep Dutta Roy, and Suresh Venkatasubramanian. Equalizing recourse across groups. Xivi preprint 1909.0009000166 2019.
Nika Haghtalab, Nicole Immorlica, Brendan Lucier, and Jack Z. Wang. Maximizing welfare with incentive- aware evaluation mechanisms. In Christian Bessiere (ed.), Proceedings of the Cotenty-Ninthl International Joint Conference on Artificial Intelligence, IJCAT-20, pp. 160-166. International Joint Conferences on doi: 10.2 10.24963/ijcal 20/.:///.....2//3.....
Artificial Intelligence Organization, 2020.
URL
24963/1jcai /2200///23222223333333
2020/23
Moritz Hardt, Nimrod Megiddo, Christos Papadimitrion, and Mary Wootters. Strategic classification. Tn Proceedings of the 2016 ACM conference on innovations in theoretical computer science, pp. 111-122, 2016a.
Moritz Hardt, Eric Price, and Nathan Srebro. Equality of opportunity in supervised learning. In Proceedings of the 30th International Conference on Neural Information Processing Systems, pp.
2016b.
Mignel A. Hernán, Wei Wang, and David E. Leaf. Target Trial Emulation: A Framework for Causal Inference From Observational Data. JAMA, 328(24):2446 2447, 12 2022. ISSN 0098-7484. doi: 10.1001/jama.2025 2022. 21383.
Lily Hu, Nicole Immorlica, and Jennifer Wortman Vaughan. The disparate effects of strategic manipulation. In Proceedings of the Conference on Fairness, Accountabiliyy, and Transparency, pp. 259 268, 2019.
Zachary Izzo, Lexing Ying, and James Zou. How learn when data reacts to your model: Performative gradient descent. CoRR, 2021.
Amir-Hossein Karimi, Gilles Barthe, Bernhard Schölkopf, and Isabel Valera. A survey of algorithmic recourse: definitions, formulations, solutions, and prospects, 2020a.
Karimi, Julius von Kügelgen, Bernhard Schölkopf, and Isabel Valera. Algorithmic recourse under imperfect causal knowledge: probabilistic approach, 2020b.
14

---

Published in Transactions on Machine Learning Research (06/2023)
Niki Kilbertus, Manuel Gomez Rodriguez, Bernhard Schölkopf. Krikamol Muandet, and Isabel Valera. Fair decisions despite imperfect predictions. In Silvia Chiappa and Roberto Calandra (eds.), Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, volume 108 of Proceedings of Machine Learning Research, pp. 277-287. PMLR, 2020. URL http::/prooeeednggs press press/
.htmmmm00.mmllm
Jon Kleinberg and Manish Raghavan. How do classifiers induce agents to invest effort strategically? ACM Transactions on Economics and Compulation (TEAC), 8(4):1-23, 23, 2020.
Matt J Kusner, Joshua Loftus, Chris Russell, and Ricardo Silva. Counterfactual fairness. In I. Guyon,
U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett (eds.), Aduances in Neural Information Processing Systems 30, pp. 4066 4076. Curran Associates, Inc., 2017. URL http: //papers.
http/ppprr//99--ootttfaaaaaaaaaa www.entstt......ssss.sasaa..s... pdf
Lydia T Liu, Ashia Wilson, Nika Haghtalab, Adam Tauman Kalai, Christian Borgs, and Jennifer Chayes.
The disparate equilibria of algorithmic decision making when individuals invest rationally. In Proceedings of the 2020 Conference on Fairness, Accountability, and Transparency, pp.
2020.
Yang Liu and Yiling Chen. Machine-learning aided peer prediction. In Proceedings of the 2017 ACM Conference on Economics and Computation, pp. 63 80, 2017.
Celestine Mendler-Dünner, Juan Perdomo, Tijana Zrnic, and Moritz Hardt. Stochastic optimization for performative prediction. Advances in Newral Information Processing Systems, 33, 2020.
John Miller, Smitha Milli, and Moritz Hardt. Strategic classification is causal modeling in disguise. In International Conference on Machine Learning, pp. 6917 6926. PMLR, 2020.
John Miller, Juan Perdomo, and Tijana Zrnic. Outside the echo chamber: Optimizing the performative risk, 2021.
Smitha Milli, John Miller, Anca D Dragan, and Moritz Hardt. The social cost of strategic classification. In Proceedings of the Conference on Fairness, Accounlabillly, and Transparency, pp.
2019.
Juan Perdomo, Tijana Zrnic, Celestine Mendler-Dünner, and Moritz Hardt. Performative prediction. In International Conference on Machine Learning, pp. 7599-7609. PMLR, 2020.
Marco Tulio Ribeiro, Sameer Singh, and Carlos Guestrin. 'why should i trust you?': Explaining the predictions of any classifier. In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD '16, pp. 1135 1144, New York, NY, USA, 2016. Association for Computing Machinery. ISBN 9781450342322. doi: 22.114//2939672.9933777 URL https://doi
org 01..0..11152999911 2939778
Nir Rosenfeld, Sophie Hilgard, Sai Srivatsa Ravindranath, and David C. Parkes. From predictions to decisions:
Using lookahead regularization, 2020.
Yonadav Shavit, Benjamin Edelman, and Brian Axelrod. Causal strategic linear regression. pp. 8676-8680 2020.
Stratis Tsirtsis, Behzad Tabibian, Moein Khajehnejad, Adish Singla, Bernhard Schölkopf, and Manuel Gomez- Rodriguez. Optimal Decision Making Under Stratogic Behavior. arXiv e-prints, pp. wrXiv:1905.09233 May 2019.
Berk Ustun, Alexander Spangher, and Yang Liu. Actionable recourse in lincar classification. In Proceedings of the Conference on Fairness, Accounlabilily, and Transparency, pp. 10-19. 19, 2019.
Suresh Venkatasubramanian and Mark Alfano. The philosophical basis of algorithmic recourse. In Proceedings of the 2020 Conference on Fairness, Accomntabilly,, and Transparency, pp. 284 244-293, 2020.
Julius von Kügelgen, Umang Bhatt,
Karimi, Isabel Valera, Adrian Weller, and Bernhard Schölkopf. On the fairness of causal algorithmic recourse, 2020.
15

---

Published in Transactions on Machine Learning Research (06/2023)
Hao Wang, Berk Ustun, and Flavio Calmon. Repairing without retraining: Avoiding disparate impact with counterfactual distributions. In International Conference on Machine Learning, pp. 6618-66186999 08-66677 PMLR, 2019.
T-Cheng Yeh and Che-hui Lien. The comparisons of data mining techniques for the predictive accuracy of probability of default of credit card clients. Expert Systems with Applications, 36(2):2473-248) 2009.
Muhammad Bilal Zafar, Isabel Valera, Manuel fomezz-Rodrggune and Krishna P. Gummadi. Fairness constraints: A fiexible approach for fair classification. Journal of Machine Learning Research, 20(75):1-42, 2019. URL http://jm wttg//pppers//v2//11-222222 262mhhmm
16

---

Published in Transactions on Machine Learning Research (06/2023)
Appendix
A
Organization of the Appendix
The Appendix is organized as follows.
Section
provides the organization of the appendix.
Scction
provides the proof of Theorem 1
Section includes notations and proofs for the discussion in section 3.3
Section
includes the proofs and derivations for section
Section presents additional related works.
Soction shows additional experimental details and results, including basic information on each aset. and the computing infrastructure.
B Proof of Theorem
In this section, we provide the proof of Theorem To simplify our discussion, we focus the unconstrained best response, i.c. the case in which F = A. The proofs for the other two types of best response (F = M, F F= follow the same arguments except that the inverse of (5-1), does not equal to S, but equals to ((S ((S
We first prove two lemmas that allow us to reformulate the best response as an optimization problem. The first states that the decision subject's goal is maximize their utility, but they are unwilling to pay a cost greater than
Lemma (Decision Subject's Best-Responte Function). Given a classifier h X + [-1, a cost function C:Xx x X - R, and set of realizable feature vectors X _ X, the best response of decision subject with features xt is the solution to the following optimization program:
U(z,,') stt. c(x,x')5) 2
max x' EXX
Proof- Since the classifier in game outputs a binary decision (-1 or +1), decision subjects only have incentive to change their features from to x' when c(x,x') 2. To see this, notice that decision subject originally classified as -1 receives default utility of Uzz x) = f(x) 0 = -1 by presenting her original features I. Since costs are always non-negative, she can only hope to increase her utility by flipping the classifier's s decision. If she changes her features to some x' such that f(z') = +1, then the new utility will given by
f(z') -(x, (()==))==(()))d))=====- 1 U
Hence the decision subject will only change her features - c(x, x') 2 f(x) -1, or (x, 22
The next lemma turns the above maximization program into a minimization program, in which the decision subject seeks the minimum-cost. change in that crosses the decision boundary. If the cost exceeds 2, which is the maximum possible gain from adaptation, they would rather not modify any features. Lemma 2. Let x² be an optimal solution to the following optimization problem:
x= arg min cxx, d'E (x)
S... sigu(w T xx' =1
If no solution is returned, we say an x² such that c(z, = oo is returned. Define A(x) as follows:
x+ x(xxx") 22
A(x)
x. otherwise
17

---

Published in Transactions on Machine Learning Research (06/2023)
Then (xx) is optimal solution to the optimization problem in Lemma 4
Proof. Recall that the utility function the decision subject is Uz x') = f(x') - 2(x,x'), and that, by Lemma they will only modify their features the utility increases, i.c. if they achieve f(x') = +1 and while incurring cost c(a, 2.
Consider two cases for x' *
1. When cxx, x²) > 2, there are no feasible points for the optimization problem of Lemma 1
2. When c(z, x') & 2, we only need to consider those feature vectors x' that satisfy f(a') = because if f(x') 1, the docision subject with features x would prefer not change anything. Since maximizing Ux,x)' f(x') c(x, x²) is equivalent to minimizing x²) if f(x') 1, we conclude that when c(2xx') < 2, the optimum of the program of Lemma | is the same as the optimum of the program in Lemma 2
Lemmaa enables us to re-formulate the objective function as follows. Recall that c(zxx') (= (I - =xx) where S-1 symmetric positive definite. Thus S- has the following di- agonalized form, which Q is an hogongll matrix and A is a diagonal matrix:
(A (A
With this, we can re-write the cost function as
(I,,²' V (IA In -S-
(JA - xn'
V(TA - IA') (+)) (A Q)( - IA')
/AA-tQ(2z) - TAx')) = - IA'))
|A MA= - =IA')la
Meanwhile, the constraint in Lemma can be written
sign(w x') sign(w> IA + Wim FIM) = sign(W> IA - (-WIM xIM))
Hence the optimization problem can be reformulated as
min xx EXA
(8)
s.t.
(ign(w'= IAA - (-WIM- 2lM))
(9)
The above optimization problem can be further simplified by getting rid of the sign(-):
Lemma 3. If ZAa an optimal solution to Eq. under constraint Eg. 99. then must satisfy WA aA (-WIM FIM) 0.
Proof. We prove by contradiction. Let oă is optimal solution to Eq. 8 and suppose towards contraction
that W > WIM TIM- Since the original feature vector & was classified as 1, we have
WA
IA
WiM
TIM,
WA AA < 211 TIM
18

---

Published in Transactions on Machine Learning Research (06/2023)
By the continuity properties of linear vector space, there exists μ (0, 1) such that:
WAA TA + (1-M))a)) 11) = -WMM FIM
Let TA" " p. =AA 7 +1 A
Then " -IIM FIM)) 1, ic., x'A also satisfies the constraint.
Since ZA is an optimum of Eq-
we have
MΣ Q = - =A)l S 1 -xAll
However, we also have:
E $ Q((xn" - | | Q(M I IA F + 1)2A =A)I
=| Q(u (0A -
M|| =Q(ZA F ==ZAll
| Q(TAA F -xAill
contradicting our assumption that Zλ optimal. Therefore oÀ must satisfy WAR -WII 2IM
As a result of Lemma 3 we can replace the constraint in Eq. 88 with its corresponding equality constraint
without changing the optimal solution The decision subject's best-response program from Lemma is therefore equivalent to
min II(A II(A= $ Q(( - xxx'')) 1l22 24 EXA
(10)
s.t. WA FA (-WIM 2IM) 0
(11)
The following lemma gives us a closed-form solution for the above optimization problem:
Lemma 4. The optimal solution to the optimization problem defined in Eq. 10 and Eq.
has the following closed form:
1 x SWA
WAA SWA
Proof. Notice that the above program has the form
min ax Eza'
||r - -bl12
s.t. CzA'
where A= ==A= b= A C= WA T and WiM T TIM. Note the following useful equalities:
A = (A --t====
(A 11
A (A (A- QQxA =S-
'A similar argument was made by Haghtalab et al. 2020) but here provide proof for more general case, where the objective function is minimize weighted instead simply ||= 2x '1l--
19

---

Published in Transactions on Machine Learning Research (06/2023)
The above is norm minimization problem with equality constraints, whose optimum 2A + has the following closed form (Boyd & Vandenberghei 2004):
AA (A (T -ICCIICC A d)
S (5 IA- WA(WA SWA) SSS zA) (-WIM =IN)))
WWWWW SWA) "Wa T DA + WiM =m))
w To x
TA
SWA Swa
We can now compute the cost incurred by an individual with features x who plays their best response x
(5A IA 5)
(IrA IA +)
w T
w SWA
SWA
5
WA SWA
WA T
SWA
Iw x1
UuAA SWa
Hence an decision subject who was classified as -1 with feature vector x has the unconstrained best response
F,
if
2 2
Axx)
UAA
SWA
TA
Swa
TIM
otherwise
SwA
which completes the proof of Theorem
C Proofs of Propositions in Section 3.3
Notation.
We make use of the following additional notation:
(1() denotes the i-th element of vector v
For any (A, A & denotes the vector containing only features of type F within the best. response (xx).
0 denotes the vector whose elements are 0
B indicates that matrix B positive definite
E; denotes the vector containing 1 in its i-th component and 0 elsewhere
C.1 Proof of Proposition
(m) # 0, and consider decision subject with original features who was classified as -1. By Theorem the actionable sub-vector of z's unconstrained best response is
Proof. Let uM
(x)
w T
S WA
w S
x
0
wi
w
20 SWA
Si w SM
WA
SWA
WA
SWA
SM
WMM
WA
u0M
20

---

Published in Transactions on Machine Learning Research (06/2023)
And in particular, w x
A AM (x)
SM WMM
WA Sua
Since was initially classified as -1, we have w < O, which means w wASwA
#
For convenience, let.
w/ We have
10g S0r
(x)x)= JM - cSSuui - AM = SM(Cuu - Sm xxM)
Now examine the following:
(cw's - SSM (mM) cuM
(SM JMM) (m))
du
(m)
S (im)
(m)
cWM
IM
Recall that CUM (m) + 0. Hence if Iim (SM (Sm))(tm)
0, or if
cW (m)) M
I
(m)
+
Σ (SM (8m)
then (cWM - SM xM) (m) o O, and therefore cuM SM JM # O. Since SM positive definite, it has full rank, which implies
A MM (z) 2M SM(CIM SM IM) +
required. With this, we have shown that when there exists manipulated feature x (m)) whose corresponding coefficient WA (m) o 0, the classifier is vulnerable to changes in the manipulated features by the vast majority of decision subjects.
]
C.2 Proof of Proposition
Proof. Consider a decision subject with features x such that h(x) = -1. Suppose a can flip this classifica tion result by performing the improving best response (x)x), which implies that the cost of that action is no greater than 2 for this decision subject. We therefore have:
2 2 (x))) = Iw
Iw T
c(æ, A(x))
wi Sjay
T Sjw + WM T SMMM V
V WA Swa
where the strict inequality is due to the fact that SM > 0 and WM * 0. As we have shown that c(x, A(x) < 2, we conclude whenever an decision subject can successfully flip her decision by the improving best response, she can also achieve it by performing the unconstrained best response.
On the other hand, consider the case when the unconstrained best response of decision subject with features x² has cost exactly 2:
IwT x
2 = c(x", ==x))(((x'))
c(x", (((xx))))
V WwA Swa
wi Siw, + WM SMMM
wi Smw)
where the strict incquality is due to the fact that SM > 0 and uM + As we have shown that o(x", A, )) > 2, we conclude that while the unconstrained best response is viable for this decision subject, the improving best response is not.
21

---

Published in Transactions on Machine Learning Research (06/2023)
C.3 Proof of Proposition
Proposition (Correlations between Features May Reduce Cost). For any cost matrix 5 and any nontrivial classifier h, there exist indices k. E [da] and T E R such that every feature vector a has lower best-response cost under the cost matrir S-1 given by
Sij +T,
fi=k,j=
- = Sjh
Sij'
otherwise
than under s that is, og (2, A(x)) < cg (2,, A(x)) for all x.
Proof. Consider any cost matrix S-1 E Rdaxdd and any nontrivial classifier h (i.e. h does not assign every a the same prediction). Since S-1 is positive definite, so is its inverse S, and all of their diagonal entries are positive. And since h is nontrivial, it must contain a nonzero coefficient # O. Additionally, let wy be any other coefficient.
Let 5- + (ege) + e for some constant E to be set later. We claim that there exists 7 such that the best-response adaptation always costs less under S-1 than s-1, To do so, we compute the inverse of 5- and invoke the closed-form cost expression given by Theorem
begin computing the inverse, note that by the Sheemman-Morrionn- Woodbury formula (Golub & Van Loan 2013
$ = -5-1 = =S - -S-SS(e le:
eg]
I I+
[ee
e,]
S
(12)
S/3
= S - S [e
eg]
I+ r
S
(13)
S/
Sig
11 I +
[S
SJ
= S - S 1
eg]
7
S
S
(14)
[ + Sig
S
= S TS (e
e,]
--
S
(15)
S
1 +S
[ + Sig
Sjj
= S - S [e
eg]
S
(16)
Su
Si
e,
Clearly, we can ensure that invertible by setting T so that det(T)) * 0. But as the following lemmas show, we can actually say much more: dct(T) can be made either positive or negative, and morcover, both can be accomplished with choice of or This flexibility in choosing will become crucial later.
First, need the following useful fact about positive definite matrices:
Lemma 5 (Off-diagonal entries of positive definite matrix). If A E n is symmetric positive definite, then for all j.j E [m), VAuAjj > AAgl-
Proof. By positive definiteness, we have, for any nonzero a, E.
(are; + Be,)) A(ae; + Be,)) = a² A² - -B²A, + 22.3Ar >
For a choice of -Ai and 8 Ag, we have
A A/AA, 24 AA 133) >0
Since A 0, must. have A,A, A3₂ 0, from which the claim follows.
22

---

is equivalent to Published in Transactions on Machine Learning Research (06/2023)
Now characterize the possible settings of and det(T):
Lemma 6 (Possible settings of T). There exist max Tiin >> O such that the following hold:
1. det(T) 0 for any R such that Tmax 2 |T| O.
2. det(T) < for any E R such that Tiin
I |T/-
Proof. To prove the first claim, note that having
det(T) (+ Stn)
2 S >
+ Sis
> SS
It suffices choose such that
1
|
/SWS
v SuSS} + |S
So any 7 such that 0 <<17 < S + (S,)) sufficient condition for det(T) < is that
results in det(T) > 0. Analogously, for the second claim, a
<
S 15
By Lemma 5 the right-hand side is positive.
Hence it suffices to pick any such that
| > (vSnS - -15;s)
With this Jemma in place, we can describe the difference between the inverses of S-1 and 5-1 Denote this matrix by E = S S. We show the following:
Lemma 7 (Difference between inverse cost matrices). The k. b-th entry of has the following form:
Exe det(T))
1
(Eke +
1 = T
where Egg and Ei's do not depend on т.
Proof. Assume that t has been chosen so that de'( # 0, as Lemma e showed to possible. We then have
1 + Sig
SS + S
det(T)
S4
Thus continuing from equation 16 have
5 - S det(T)
s [c
ez]
1
+ Stp
-S
E
s
S
+ i5
23

---

Published in Transactions on Machine Learning Research (06/2023)
It can be verified that V is da x da matrix whose only nonzero entries
VB -gg
Vi
-
Vij = Vi + Stz
Next we evaluate the d^ x dA matrix SVS. For any k, l [da], we have
dA da
(S = Σ E Sui
1=1`==1
= S + Ski Sje + S2y S + So
(V has four nonzero entries)
Si + Sky + (Sa Sey
(V, Vja)
- -S - SJ + ( S/s (S + Si)
1
S SK See + S See + Si) + (Sxt + Siy
E
Elee
which proves the claim.
We now compute the marginal best-response cost incurred due to the difference between the inverse cost. matrices, E = S - 3. We have
d
d
WA EWA
ΣΣ
W. we We Ese
k=1 1=1
1 Elet
Wp we
Eke
(by Lemma 7
det((T)
w Ebe
j Eike
det(T)
E"
By Lemma 6 there exists F # 0 such that
sign(det (T)) -sign(F) and sign(7) -iggn(det(T)) sign( (F")
Such choice of results in Wn T FWIA < Finally by Theorem we have for all x that
(z, |wTTr
wwo Tel
w T xx
cg- cg- Az (x))
/u SunA
V WA Tun - WA FAWA
VWA Swn
which completes the proof.
C.4 Proof of Proposition
Proof. Let the cost covariance matrices for groups t and v be
ST = [S]]
S 0
S
M.
SM.y
Here, we see that both groups have the same cost of changing improvable fcatures, as represented in the cost submatrix S However, the cost of manipulation for group higher than that of group V, namely s- SM. SM.e.
24

---

Published in Transactions on Machine Learning Research (06/2023)
We are now equipped to compare the costs for the two decision subjects:
|w TuTar x|
< (xx))) =
V VuA S
V [i Swij + uM SMM WM
1w |w0
lw x
cx (xx)))
V Vwi Swwy
WM T. -SM WM
Since SM. > S.. we have SM. x SM. And since UM # O, this implies 0 < wM T SMM WM < WM T -SM WM. As a result, c( ()x))) > c( ))x)) as requirod.
Proofs and Derivations in Section 4
D.1 Proof of Proposition 5
Proof. We want to show that the standard strategic risk conditioned unchanged true label is upper- bounded by the first lerm in our model designer's 's objective, Raa (h)::
E [1(x..)) R>D
+ v] (y) S E (1(((=") + y)]
RnD
We assume that the manipulating best response more likely to result a positive prediction than the unconstrained best response, given that the true labels do not change:
2~D [1])).)) + al A(v) = 2l s B [1[((>") + vl (M yl
(17)
We therefore have:
E [1(h(="") # y)1
TND
E [n(((a") + y) (M # v) Pr(Am(v) #
+ E [1(h(=*) + v) Am()) = yl Pr|AM = yl anD
E [1(((= 4) (M) =y
(Pr(Am(v) = y] 1)
2 E [[((xx.)) * v) zND
A vl
(by equation 17
D.2 Proof of Proposition 6
Proof. Let D be the distribution induced by deploying classifier h. By the covariate shift assumption,
Pr (Y = y/X = x) = (Y = y|X = r². Therefore
Pr 12(2) = D
+1] = E [1((((z) +1]]
aND
= / 1ly(x) = +1] Pr(X = x)dx
D
/ 1ly(a) +1] Pro (X x))
Pro(X = x) Pr(X x)dr
/ [[b()) +1]w (x) Pr(X = z)dr
D
= E (T)(())))(()) = =+1]]
D
25

---

Published in Transactions on Machine Learning Research (06/2023)
This implies
Pr [1(x) ++] 2 Pr ()() +1] = - +1]] anD
(18)
By similar reasoning, we have
Pr 11(x)==11]] = -[E[((((()))))) +1]l = - (=) =1]] znD
which implies
Pr [h(x) = +1] 2 Pr [1() = = B [[( w~D
1)1(((()) = +1]] 2 0
(19)
anD
It easy to verify that BynD (2)) 1, and this gives us
E (wn (x) - (v() = +1]] = CoVD 1 = +1])
(20)
B (xx) 1) +1] = Cov (x), (M(x) = +1))
(21)
By equation 18
equation
19 and equation 20 the condition
Pr Pr.1(z))=111 Pr [1(xx== +1] +
= > Prlu(e +11 Pr -
m~D"
is equivalent to the condition
(w) +1]) 20 > Covo(ui(1)) = +1]) 2 0
D.3 Derivations for the model designer's objective function
Now that have obtained closed-form expression for both the unconstrained and improving best response from the decision subjects, we can analyze the objective function for the model designer and the model that would be deployed at equilibrium. Recall that the objective function for the model designer is
min wER
E (1((AM(()))) + w)] + À E (1))(A(()) + +1)] AND
RND
By Theorem 1 (x)())) has the closed form
h ((M(2)) +1 if x 2 2 uM T
SMMuM
-1 otherwise
w x 2 -2 uM T SwMu 2
and similarly,
(a)))) 2-1 w. 2 22 wi T Siiy -1
The model designer's objective can then be re-written as follows:
EmnD
[ [[((A + w] +
+1]]
1 (1 (1+h(AM(Z)) h() 9) X(1 (1 + (())()))) 1))
1
E B
2 + -))(Am(=)) - 2 )
E DD
26

---

Published in Transactions on Machine Learning Research (06/2023)
Removing the constants, the objective function becomes:
min E D [A- h(Am(x)) Xh(A)(=))]
min EE D (2.
2. w x -2/ uM Swww -1) y(()) 22 1 w. 2 -2V wi Sww
w
Re-organizing the above equations, we can turn the model designer's constrained optimization problem in equation into the following unconstrained problem:
[- (2 - w DDNxZ-2//A
2/52 -1) 22-22 22 [ x 22/2
min WER DND
(22)
The oplimization problem in equation 22 is intractable since both the objective and the constraints are non-convex. To overcome this difficulty, we train our classifier by replacing the 0-1 loss function with a convex This results in the following ERM problem:
surrogate loss (Ix) log I+c
10 Vi (w x4 + 2//)))) A A.o(w" x; + 2v 2/)
min WER
Σ1
(23)
Conditionally Actionable Features. In practice, individuals can often only change some features in cither a positive or negative direction, but not both. However, modeling this restriction on the decision subject's side precludes a closed-form solution. Instead, we strongly disincentivize such moves in the model designer's objective function. The idea is that the model designer is punished for encouraging an illegal action, the announced classifier will not incentivize such moves from decision subjects. The result that decision subjects encounter implicit direction constraint the relevant variables. To that end, construct. vector dir +11 where dir; represents the prohibited direction of change for the corresponding feature 2;; that is, dir; = +1 if should not be allowed to increase, -1 if it should not decrease, and 0 if there are direction constraints. We then append the following penalty term to the model designer's objective in Eq.
max(dir, (A(x) z);. 0)
(24)
where 1) > 0 is hyperparameter representing the weight given to this penalty term. Eq. (24 penalizes the weights of partially actionable features so that decision subjects would prefer to move towards a certain direction.
E
Additional Related Work
Strategic Classification. There has been extensive research on strategic behavior in classification Hardt
et al. (016a)); Cai et al. (2015): ; Chen et al. (2018) Dong et al. (2018) Dekel et al. (2010): Chen et al.
(2020
Hardt et al. (2) was the first to formalize strategic behavior in classification based on sequential
Iwo-player game (i.e. a Stackelberg game) bet ween decision subjects and classifiers. Since then, other similar
Stackelberg formulations have been studied Balcan al. (2015). Dong al. (2018) considers the setting in which decision subjects arrive in online fashion and the learner lacks full knowledge of decision subjects' utility functions. More recently, Chen el al. (2020) proposes learning algorithm with non-smooth utility and loss functions that adaptively partitions the learner's action space according to the decision subject's 's best responses.
The concept of recourse in machine learning was first introduced in (Ustun et al. 2019 There, an integer programming solution was developed to offer actionable recourse from linear classifier. Our work builds on theirs by considering strategic actions from decision subjects, as well as by aiming incentivize honest improvement. Venkatasubrananian & Alfano 2020 discusses more adequate conceptualization and
Recourse.
27

---

Published in Transactions on Machine Learning Research (06/2023)
operationalization of recourse. Karimi al. (2020a) provides thorough survey of algorithmic recourse in terms of its definitions, formulations, solutions, and prospects. Inspired by the concept of recourse, Dean et al.] (2020) develops a reachability problem to capture the ability of models to accommodate arbitrary changes in the interests individuals in recommender systems. Bellamy et al. (2018) builds toolkits for actionable recourse analysis. Furthermore, Gupta et al. (2019) studies how to mitigale disparities in recourse across populations.
Causal Modeling of Features. flurry of recent papers have demonstrated the importance of under-
slanding causal factors for achieving fairness in machine learning (Wang et. al. 2019 Bhatt. et. al., 2020
Bechavod et al. 2020: Miller et al. 2020 Shavit et al. 2020). Miller et al. 2020) studies distinctions between gaming and improvement from causal perspective. Shavit et al. (2020) provides efficient algorithms for simultaneously minimizing predictive risk and incentivizing decision subjects to improve their outcomes in a linear setting. In addition, Karimi et al.] (2020b) develops methods for discovering recourse-achieving actions with high probability given limited causal knowledge. In contrast to these works, we explicitly separate improvable features from manipulated features when maximizing decision subjects' payoffs. Our work also broadly relates to the concept of intervention in the literature of causal inference (Eberhardt & Scheines 2007)- In our work, the actionability of feature is always factual, mcaning it is always feasible to change those features. This is closely related to the concepl of last trial in causal inference, which refers to the interventions that one could run in the real-world (which would rule out the interventions on age) (Hernán
ct al. 2022
Incentive Design. Like our work, Kleinberg & Raghavan (2020) discusses how to incentivize decision subjects to improve a certain subset of features. Next, Haghtalab et al. (2020) shows that an appropriate projection an optimal lincar mechanism for strategic classification, as well as an approrimate lincar threshold mechanism. Our work complements theirs by providing appropriate linear classifiers that balance accuracy and improvement. Liu et al. (2020) considers the equilíbria of a dynamic decision-making process in which individuals from different demographic groups invest rationally, and compares the impact of two interventions: decoupling the decision rule by group and subsidizing the cost of investment.
Algorithmic Fairness in Machine Learning. Our work contributes to the broad study of algorithmic fairness in machine learning. Most common notions of group fairness include disparate impact Feldman ict al. (2015), demographic parity Agarwal et al. 20018). disparate mistreatment Zafar et al. (2019). equality of opportunity Hardt al. (2016b) and calibration [houldechova) (2017). A Among them, disparities in the recourse fraction can be viewed as equality of false positive rate (FPR) in the strategic classification setting. Disparities in costs and flipsets are also relevant to counterfactual fairness Kusner et al. (2017) and individual fairness Dwork et al. (2012). Similar to our work, von Kügelgen el al. (2020) also consider the intervention cost of recourse in flipping the prediction across subgroups, investigating the fairness of recourse from a causal perspective.
E.1 Agent's Best Response with Partially Actionable Features
Let feature represents those features that should only be non-inereasing, and feature j represents those features that should only be non-decreasing. Then the constraint can be represented as:
y1 50 e000
リソ 22
Assume that there are n_ features that can only be changed negatively, and there are n4 features that can only be changed increasingly. We can further combine those new constraints into matrix form like Ey S O. The other constraint can be re-written as:
T w y 6 66-00004 -w b²,
28

---

Published in Transactions on Machine Learning Research (06/2023)
therefore the optimization problem can be rewritten as:
min
Qy
E
0
8.1.
y
b'
where of the form:
0
no X
A
-In,
0
w
(m+ +1)xm
F Additional Experimental Details and Results
In this section, we provide additional experimental results. In particular, we provide the full results with mean and standard deviation in Table 4
F.1 Basic information of each dataset
Table 3: Basic information of each dataset.
Dataset
Size
Dimension
Prediction Task
credit
20, 000
16
To predict a person can repay their credit card loan.
adult
48, 842
14
To predict whether income exceeds 50K/yr based on census data.
german
1, 0.0
26
To predict whether a person is good or bad credit risk.
spam
4601
57
To predict if an email is spam or not.
F.2 Specific Cost Matrix
We specify the cost matrix as follows:
1. if if and i E
0.2,
if j and j E M
1, if the cost of changing features i and j are negatively correlated
Sty
1, if the cost of changing features i and j are positively correlated 0. otherwise
We use the credit datasct demonstration of how we specify the non-diagonal clement in the cost matrix. For two feature variables that have a positive correlation, e.g., SavingsccounBallcce, we assign -1 to the corresponding elements in the cost matrix S. For two feature variables that have a negative corrclation, c.g., Checking to the correspouding elements in the cost matrix.
and
and MissedPaymentss, we assign +1
F.3 Computing Infrastructure
We conducted all experiments on 3 GHz G-Core Intel Core CPU. All our methods have relatively modest. computational cost. and can be trained within few minutes.
29

---

Published in Transactions on Machine Learning Research (06/2023)
Table 4: Performance metrics for all methods over real data sets with non-diagonal cost matrix. We report the mean and standard deviation for 5-fold cross validation. The constructive adaptation (CA) consistently achieves high accuracy deployment while providing the highest improvement rates across all four datasets.
METHODS
Dataset
Metrics test error deploy error
ST
DF
MP
CA
29.52 0.37
29.66 = 0.40
29.63 0.41
29.60 + 0.44
CREDTT
31.25 0.56
29.66 + 0.40
29.41 + 0.32
29.49 + 0.38
improvement rate
46.35 = 3.81
44.71 = 4.75
36.76 + 0.53
48.27 = 5.50
test error deploy error
23.05 = 0.47
33.55 + 0.73
24.94 + 0.52
27.22 + 0.65
ADULT
38.64 = 4.46
33.55 + 0.73
26.85 + 0.59
29.34 1 0.45
improvement rate
30.92 = 3.31
60.63 = 29.40
36.70 = 1.62
63. + 7.80
test error deploy error improvement. rale
30.85 = 0.82
36.10 + 1.97
33.25 + 1.44
34.70 + 2.15
GERMAN
33.40 = 1.78
36.10 - 1.97
34.60 + 1.94
34.25 + 1.78
41.20 = 5.77
42.10 + 9.07
33.50 2.53
56.10 6.40
test error deploy error
7.11 = 0.52
10.18 + 0.45
11.52 + 0.12
14.37 + 0.24
SPAMBASE
22.40 = 3.14
10.18 = 0.45
12.92 + 0.58
14.70 + 0.36
improvement rule
40.04 + 13.06
32.46 + 14.63
26.42 + 4.80
43.98 + 6.18
F.4 Results for non-diagonal cost matrix
In real life, the specification of the cost matrix might require examining the causal correlations among different features. We consider a non-diagonal cost matrix setup based on common knowledge and describe the rationale as below. For two feature variables that have a positive corrclation, c.g.; CheckingAccount assign -1 to the correspouding elements in the cost matrix. For two feature
and SceringsAccemmmBaaammm. variables that have negative correlation, e.g., Checking.AccountBalar to the corresponding elements in the cost matrix. We also note that the non-diagonal cost matrix must be invertible under our assumption on the cost of modifying features. We provide more detailed results for cach dataset in Table 4 which shows the means and standard deviations of different metrics. Compared to the empirical results using a diagonal matrix, we achieve similar results with respect to the three evaluation criteria across all four mothods.
and WrissedPayments. we assign +1
F.5 Additional Experimental Results for
models
We also work with three-layer neural network to validate the effectiveness of the oracle best response in Algorithm []] We note that the LIME program needs to learn a local linear model for each instance, which is very time-consuming. Therefore, we downsample only 10% of data examples from the credit dataset. We follow the same setting as the lincar classifier experiments. We compare our method with the static classifier in Table 5 We find out for this non-linear model setting, our approach has higher improvement rate while preventing manipulations with the deploy error 27. 27.72% vs. 35.64%.
Table 5: Performance metrics for non-linear models.
METHODS ST
Metrics
CA
test error
30.72%
30.01%
deploy error
27.72% 35.64%
improvement rate
0.99%
2.97%
30

---

Published in Transactions on Machine Learning Research (06/2023)
F.6 Flipsets
We also construct flipsets for individuals in the german datasel using the closed-form solution Eq- under our trained classifier. The individual characterized as a "bad consumer" (-1) is supposed to decrease their missed payments in order to flip their outcome of the classifier with respect to a non-diagonal cost matrix. In contrast, even though the individual improves their loan rate or liable individuals, the baseline classifier will still reject them. We also provide flipsets for conditionally actionable features on the credit dataset Table 7 The individual will undesirably reduce their education level when the classifier unaware of the partially actionable features. In contrast, the individual decreases their total overdue months instead when the direction penalty is imposed during training.
Table 6: Flipset for person denied credit by ManipalateddProot on the german dataset. The red up arrows f represent increasing the values of features, while the red down arrows represent decreasing.
Feature
Type
Original
LightTouch
ManipulatedProof
LoanRate A PercenlOflncome
3
3
2 4
Number OfOther At AtBo
1
1
1
Number Of
1
1
t
Actiringanncouuuuaalalaaa 2
I
0
0
Checking Aaciiggggoooo Aecoonn..aaaannccec....c..
200
T
O
0
Savings Acconntsaacaaaaaaacccce 2 100
I
O
0
Savings A ccounlBalance
500
I
O
0
0
MissedP
Pymments ayments
1
0
4
No CurrentLonn
0
Critical (ooomttrrooomnneeseeeee
0
OtherLonns AtStore
0
Has Caapopillia
I
0
HasGuaranlor
0
Unemployed
I
0
0
LoanDuration
M
48
47
47
Offpo
M
0
0
LoanAmount
M
4308
4307 4
4307
Has Telephone
M
0
0
Gender
U
0
Foreign Worker
U
0
Single
U
0
0
Age
U
24
24
24
YearsAfCurrentHome
U
4
4
4
OunsHouse
U
0
0
RentsHouse
U
1
Years <
U
1
YearsAtCurrentJob
2 4
U
0
Ishilees
U
1
1
GoodConsumer
-1
+11
-1
In this experiment, we implicitly assume that balances reflect the agent's savings.
31

---

Published in Transactions on Machine Learning Research (06/2023)
Table 7: Flipset for an individual on Credit dataset with partially actionable features. The red up arrows f represent any increasing values, while the red down arrows represent any decreasing values.
Feature
Type
dir
Original
0
100
EducationLevel
+1
3
4
TotalOverdue
0
1
1
TotalMonthsSweerdde
I
0
1
1
0
Maa Bow.Blllmmmoutttteeeeaooototttte
0
0
Mazi Wwa.arogggeeed/mmmmooooooooottoo
M
0
Months WithleemoobblanneeeeeerLsstttttr
M
0
Months Wih..oowSpeendiiggoooo///aooooo
M
6
1
6
Months WwthhHHggghSpennnggggeerrrrtttte
M
O
0
0
0
M
0
0
0
MostleeeenddoymmeetAAuue
M
0
O
Married
U
1
Single
U
0
0
Age < 25
U
0
0000
0
0
0
25 S Age S 40
U
0
0
0
40 < Age < 60
U
0
0
0
Age 2 60
Hhistry(OJOveeddeePaammned
1
NoDefandlNeeztMntth
-1
+1
1
+1
32


Reviews:
[{"review_id": "l7Q81niJYI", "reviewer": "Reviewer_5yXo", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n * The results in Section 3 give nice explicit discussion of the implications of allowing a classifier to condition on manipulable features, and the way that correlations can reduce the cost of manipulating a classifier. These results are intuitive and a little unsurprising, but given that they are very clearly presented, they serve as a useful introduction to the challenges of selecting good features in this setting.\n * Nice experimental evaluation.\n\nWeaknesses:\n * I did not understand the condition in Prop 5. How is it ever the case that \"the manipulating best response is more likely to result in a positive prediction than the unconstrained best response\"? If the manipulating best response only changes manipulable features, surely its a more constrained action space, and hence it should always be less likely to result in a positive prediction (assuming the users are optimizing to induce a positive prediction)? Why can't the unconstrained best response always play the manipulating best response if that option is available?\n * I would expect the covariate shift assumption to only hold for improving features and not for manipulating features - so it seems strange to be totally black-box about the way the assumption is stated in Proposition 6. Is there any example of a manipulating feature for which the covariate shift holds? Assuming not - while you may not want to specify a specific DAG, you do have an equivalence class of DAGs that imply your assumption (I think it is the DAGs for which conditional ignorability holds given the improvable features and a subset of the immutable features), and the proposition would be improved by making that explicit.\n * I noticed that you used account balances as improvable features for the `german` data. Surely those are manipulate using the examples you give in the text? (I.e. borrowing money from a relative before the loan)\n\nMinor:\n * Missing table reference on page 10", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper discusses an approach to designing a classifier that incentivizes strategic adaptation of improvable features (i.e. those features for which strategic adaption leads to actual improvements with respect to some target of interest) while avoiding gaming the classifying by allow adaptation with respect to manipulable features (i.e. features which are correlated with the target of interest but can be manipulated without improving the target of interest). They take as input a taxonomy of features that distinguishes improvable, manipulable and immutable features (so they are not attempting to discover this, thereby avoiding the hardness results from causal discover [Miller et al 2020]), and optimize *constructive adaptation* risk which penalizes incorrect answers as a function of the user's best response to manipulable features, and penalizes not setting the classifier to output true as a function of the best response to improvable features. That is: you want a classifier such that the best response to improvable features induces the classifier to output true, while the best response to manipulable feature just induces the classifier to output the label (so it is not more likely to classify true if the true label is false). They study this problem in the context of linear model with costs given by Mahalanobis norm of the changes in features (to account for correlations between features), which enables the analysis to benefit from closed form best responses (at the cost of generality). The results are intuitive and well presented.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "I would like to see the weaknesses outlined above addressed, but otherwise I think that the paper is very well written and ready to be accepted.", "broader_impact_concerns": "Given that this paper explicitly looks to incentivize behaviour, I would add a broader impact statement that considers what negative consequences may occur if the target, y, is poorly chosen or the assumptions are not met (e.g. accidentally including a manipulable feature may result in people who can't afford loans receiving them which is bad for both parties & if the target y is a proxy for what you want - e.g. engagement as a proxy for user happiness - I would suspect many of these notions could lead to bad outcomes?). ", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "eH2j6K2iHh", "reviewer": "Reviewer_EU7Q", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- I don't know enough about the strategic classification space to know exactly what has been done there so far, but the authors' arguments for why the kind of model they're presenting is the right direction make sense to me.\n- The idea of a new risk function that has different components focusing on different best responses is interesting.\n\nWeaknesses:\n- The model is not really handled formally and really should be. The authors claim to model the problem as a Stackelberg game but don't really achieve this, at least in the sense that they don't specify who the players are, their utility functions, the action spaces, etc. (Many of these details can be \"filled in\" by an informed reader, but that's not the goal here.)\n- In particular, the authors never state what the utility function for the system designer is. I think this is a critical question—the central theorem for the work should relate the outcome that is achieved by the authors' methods to the utility function of the designer. We need to know \"how good\" this solution is relative to others if we are going to model this game theoretically.\n- The paper doesn't have enough new stuff in it in my opinion. The authors' chosen setting (linear classifiers) should be tremendously theoretically tractable, so the bar here is somewhat higher—we really should be able to have theorems that relate the things we care about and not rely on empirical results.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studies the strategic classification setting. A classifier designer wishes to create a linear classifier while knowing that each data point is controlled by an agent who can change features of that data point by incurring a cost. Specifically, the paper considers features in two categories: improvable and not, with the former being broken down into two further subcategories: manipulable—i.e., features that, when changed, do not affect the true label of a data point; and improvable—features that, when changed, affect the true label of a data point. The high-level idea is that the designer wishes to discourage the agent from altering their manipulable features, but wants to encourage the agent to alter their improvable features.\n\nThe authors provide some analysis of the dynamics of this problem as a game (i.e., what is the best response function for the agent) under the assumptions of a Mahalonobis distance-based cost function for the agents.\n\nTo fit a model that encourages improvement and discourages manipulation, the authors propose minimizing a new risk function to fit the model. Because the system designer knows which features are manipulable or improvable, they encourage the model to predict the label true label if the agent manipulates but encourage the model to predict the \"qualified\" label if the agent improves.\n\nThey simulate the effectiveness of their model on some standard domains from the literature.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "No", "audience_explanation": "", "requested_changes": "Minor:\n- References are formatted incorrectly in many places\n- The handling of the causal related stuff is somewhat loose. Some example issues: social media presence as an example. As important causal factor A goes up (e.g., income), social media presence may causally increase depending on A—this is sort of the general story we have for why these manipulable factors are correlated with the label. So when causal features are improved, they are likely to change non-causal features as well.\n- The best response function is not defined when it is introduced. Need a utility function for the agent. (change to h = 1 with min cost?)\n- The notion of qualification is used without definition in 2.1\n- “We assume certain features are known to affect the qualification” what do you mean by this, formally?\n- 2.2 and 2.1 contradictory—you say in 2.1 that y always represents true qualification before adaptation, but in 2.2, you say that y can change as a result of adaptation in x\n- Recourse not defined/cited", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "TKAZsxUw0X", "reviewer": "Reviewer_TLHt", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "- The paper is overall well-written\n- The specific setting of the contribution is interesting and it is original as far as I can tell (however I'm not an expert in this particular area).\n- The limitations are explicitly summarized in the conclusion, which provides a fair and clear view on the scope of the work.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper considers the case of a model designer that needs to train a classifier in a way that will make predictions over decision subjects while these subjects themselves have the possibility to alter their features to obtain a specific prediction.\nThe paper assumes that decision subjects know the classifier, and the classifier knows the decision subjects’ cost function.\nIn other words, this is \"the standard setting in strategic classification where the model designer has no strong verification power to verify truthfulness of $x^*$\".\nThe paper explain that existing approaches in strategic classification tackle these issues by training a classifier that is robust to all adaptation. This paper aims at improving current shortcomings that can be summarized as follows: (i) the classifier from current techniques \"still has suboptimal accuracy because y changes as a result of the adaptation in x\" and (ii) existing approaches miss \"the opportunity to encourage a profile x to truly improve to change their y\".", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Critical:\nI have a few requests for change that I rank as critical but they might only require minor modifications and/or clarifications:\n- The minimization of the constructive adaptation (CA) risk is intuitively meaningful but seems to be somewhat arbitrary. For instance, could you justify why you would not have a term (1-\\lambda) in front of the manipulation risk term?\n- Right before Theorem 1, the paper introduces $\\hat S_F := ((S^{−1})_F)^{−1}$ but it is a bit unclear why the double inversion is necessary.\n- The notations with subscripts and superscripts is not always clear. For instance, the superscript $(m)$ is used for the first time in proposition 1 both for $x$ and $\\Delta$ but the meaning could be improved (in particular $\\Delta^{(m)}$ does not seem to be defined).\n- I don't see any proof for Proposition 3, why?\n\nSuggestions to strengthen the work\n- The introduction of actionable features $x_A = [x_I | x_M]$ seems to be defined as either a improvable or a manipulable feature. The terminology makes sense but I'm wondering whether a terminology closer to for instance the causal inference literature would make even more sense (e.g. with the concept of intervention). It could be useful to relate/explain the choice of at least the *actionable* features.\n- The source code for the experiments does not seem to be given. Is that a possibility?\n", "broader_impact_concerns": "No broader impact concerns", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper formalizes the problem that arises when subjects modify their features to influence their classification.  While previous work focuses on the manipulation of features that may degrade classification accuracy, this work focuses on incentivizing subjects to modify their features in a way that aligns with classification accuracy.  This is a research direction that has not received a lot of attention.  The paper provides a formalization in terms of a two-player Stackelberg game and describes suitable algorithms.  This represents an important contribution to the advancement of machine learning.  While the reviewers raised several concerns in their reviews, those concerns were addressed in the author response with suitable changes to the manuscript.  In the end, the reviewers unanimously recommend acceptance.
Decision: Accept (poster)