Incentivizing Desirable Effort Profiles in Strategic Classification: The Role of Causality and Uncertainty
Authors: Valia Efthymiou
Chara Podimata
Diptangshu Sen
Juba Ziani
Venue: NeurIPS 2025 poster ()
Keywords: strategic classification
causality
uncertainty
desirable effort
classifier design
Primary area: social_and_economic_aspects_of_machine_learning
TL;DR: This work studies the problem of designing classifiers that can incentivize strategic agents to exert effort in desirable features even when they have incomplete information about the classifier or the causal graph.

Abstract: We study strategic classification in binary decision-making settings where agents can modify their features in order to improve their classification outcomes. Importantly, our work considers the causal structure across different features, acknowledging that effort in one feature may affect other features. The main goal of our work is to understand when and how much agent effort is invested towards desirable features, and how this is influenced by the deployed classifier, the causal structure of the agent's features, their ability to modify them,  and the information available to the agent about the classifier and the feature causal graph. We characterize conditions under which agents with full information about the causal structure and the principal's classifier align with the principal's goals of incentivizing effort mostly in ``desirable'' features, and identify cases where designing such classifiers (from the principal's side) is still tractable despite general non-convexity. Under incomplete information, we show that uncertainty leads agents to prioritize features with high expected impact and low variance, which may often be misaligned with the principal's goals. Finally, using numerical experiments based on a cardiovascular disease risk study, we illustrate how to incentivize desirable modifications even under uncertainty.

Incentivizing Desirable Effort Profiles in Strategic Classification: The Role of Causality & Uncertainty
Valia Efthymiou MIT ORC valia5540mit.eduu
Chara Podimata
MIT Sloan School of Management &
Archimedes/Athena RC, Greece podimata@mit. edu
Diptangshu Sen Georgia Tech ISyE dsen300gatech. edu
Juba Ziani
Georgia Tech ISyE jzi waaatnneeeccch..mmm edu
Abstract
We study strategic classification in binary decision-making settings where agents can modify their features in order to improve their classification outcomes. Impor- tantly, our work considers the causal structure across different features, acknowl- edging that effort in one feature may affect other features. The main goal of our work is to understand when and how much agent effort is invested towards desirable features, and how this is influenced by the deployed classifier, the causal structure of the agent's ss features, their ability to modify them, and the information available the agent about the classifier and the feature causal graph. We characterize conditions under which agents with full information about the causal structure and the principal's s classifier align with the principal's goals of incentivizing effort mostly in "desirable" features, and identify cases where designing such classifiers (from the principal's 's side) is still tractable despite general non-convexity. Under incomplete information, we show that uncertainty leads agents prioritize features with high expected impact and low variance, which may often be misaligned with the principal's s goals. Finally, using numerical experiments based cardiovascu- lar disease risk study, we illustrate how to incentivize desirable modifications even under uncertainty.
Introduction
The widespread adoption of automated decision-making systems has brought significant attention to the issue of strategic classificatin-aa machine learning setting where individuals modify their features to secure favorable outcomes. This phenomenon is common in many domains: students enroll in preparatory courses to enhance their chances at college admission; job seekers tailor their resumes to align them with Al-based hiring algorithms, and individuals adjust their financial behaviors to improve credit scores. Some of these modifications reflect genuine efforts to enhance one's qualifications or financial responsibility (e.g., acquiring new skills or consistently paying off loans), while others effectively game the system, (c.g., artificially boosting credit scores by opening new credit lines or strategically targeting specific keywords in algorithmic resume screening).
The distinction between desirable and undesirable modifications is not always clear-cut. While gaming is typically regarded as problematic, even genuine improvements can vary in how desirable they are. For example, in healthcare, encouraging patients to adopt preventive lifestyle changes (such improved diet and regular exercise) may be preferable to medical interventions like medication or surgery for conditions such as obesity or hyperlipidemia. This highlights the nuanced nature of
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

strategic classification: interventions that lead to real improvements may still not align with preferred or desirable forms of improvement, where desirability is decided by the learner.
Further, a key challenge in strategic classification is that features are often interdependent. That is, modifications one feature have cascading effects on others. For example, increasing the number of credit cards an individual holds will also lower their credit utilization percentage, indirectly influencing their credit-worthiness. Similarly, reducing alcohol consumption or improving dietary habits can mitigate multiple health risks, such as obesity, hyperlipidemia, and cardiovascular diseases. These dependencies are best captured using a causal graph, a framework that has been explored in a limited amount of prior work [5, 26, 32, 40] in the specific context of strategic classification.
Our work builds upon this causal perspective strategic classification, investigating how agents respond to decision-making systems and, in particular, when their strategic behavior aligns with desirable modifications. We adopt framework in which principal (e.g., decision-maker or machine learning classifier) deploys model, and agents (or individuals) strategically adjust their features to maximize their probability of receiving a favorable classification outcome.
Our contributions. Our paper makes the following contributions.
Model. In Section 2, we introduce our model to study incentivizing desirable efforts in the context of causal strategic classification. We distinguish from previous work in two ways: we introduce incomplete information to the study of causality in strategic classification capturing settings where agents do not know the classifier, causal graph, both; and ii) we introduce notion of f3-desirbiliity quantifying the extent to which agents invest effort in features deemed desirable by the principal.
Complete Information. In Section 3, we focus on agents with full knowledge of the classifier and the causal structure, and we characterize their optimal effort profiles under various effort cost structures. We establish theoretical conditions guaranteeing investment in desirable effort profiles by rational agents. We also demonstrate that finding classifiers that induce desirable behavior is, in general, a non-convex problem. However, show that when the principal chooses only one desirable feature to incentivize-a special case that is particularly important in practice-, the problem of finding good classifiers becomes convex. We also provide simple "convexification" heuristic for when the number of desirable features is more than one, ensuring that chosen classifiers do not incentivize more than a certain amount of undesirable feature effort.
Incomplete Information. We extend our analysis to settings where agents lack information about either the classifier or the causal graph (or both) in Section 4; incomplete information is modeled as agents having Gaussian priors about the classifier and the causal graph. We show that in face of uncertainty over both the classifier and the causal graph, investing effort optimally is non-convex problem for the agent. However, the problem becomes tractable under partial uncertainty, and we provide semi-closed-fome
characterizations of optimal effort profiles in some special settings.
Case study. Finally, in Section 5, we complement our theoretical insights in the incomplete infor- mation setting with numerical experiments, basing our experimental setup a medical study from previous work that predicts risk of cardiovascular disease (CVDs) in adults. In the process, we provide insights into how to incentivize changes in desirable features under uncertainty.
Related work. Strategic classification has received significant attention over the past decade (see e.g., [1, 2, 5, 8, 9, 11, 14, 17, 20, 21, 26, 30, 32, 33, 37, 40, 41, 44J). Among this active area of research, perhaps closest our work is the work of [26]. Like us, they focus general causal graphs; however, we highlight several major differences. First, we focus on classification settings, while [26] focus regression and scoring settings. Second, we highlight differences in our agent model, where our agents invest effort to pass the classifier with reasonably high probability, while agents in [26] always exert effort to improve their score. Third, we note that our cost model is strictly more general: where [26] focuses on linear costs, our work considers general f co-sosss' Finally, unlike [26], our study incorporates incomplete information, where agents may not fully understand either the causal graph or the deployed classifier.
Our work is also closely related to the literature on "Algorithmic Recourse" [24, 25, 42, 43) which explores how to provide individuals, who receive adverse decisions from machine learning models,
'Or results show that this choice of cost is important, noting a sharp distinction in agent behavior between the cases of cost and Ep costs for p > 1.
2

---

with feedback (in the form of counterfactual explanations or recommendations) for more favorable future outcomes. From a mathematical standpoint, strategic classification and algorithmic recourse can be seen as flip sides of the same picture: recourse has the learner tell the agent what actions to take to improve their outcomes", while strategic classification sees agents as acting by themselves decide their own actions based on the classifier. A key difference is that much of the recourse literature aims to find a low-cost path between an agent's current features and features that lead to positive classification, often without asking whether this path is "desirable" nor whether it involves gaming the classifier or investing in true improvements. [28] show, in fact, that standard counterfactual recourse algorithms often lead undesirable outcomes, while our work explicitly aims to steer away from those. For a detailed survey on recourse, please refer to [23].
For full discussion of related work, please refer to Appendix A.
2
Model
We consider a binary classification problem, where there is an interaction between a principal and an agent. Roughly, the principal (aka learner), deploys MI model or classifier, which assigns binary decision in {0, 1) to each agent, based on her features. Finally, agents respond to the deployed classifier, potentially changing their features obtain better outcomes, at cost.
Let F be the set of features. Each agent k is defined by a feature vector æg E Id where [F] = d. The set of features F is partitioned into D (the set of desirable features) and 2/ (the set of undesirable features). Informally, desirable features are those that the principal wants to incentivize the agent to change dircetly; e.g., in the health application of the Introduction, "alcohol consumption" would be a desirable feature that the principal (e.g., the agent's ' primary care physician) would like to see lowered. Undesirable features, on the other hand, can be considered features that we would like to disincentivize agents from modifying directly: e.g.. directly intervening to lower an agent's cholesterol level via medication such as statins may be less desirable than promoting lifestyle changes (lower alcohol consumption, improved diet, etc.) that will also lower their cholesterol.
Causal feature interactions. We adopt a causal perspective where different features can impact each other-i.e., a change in a feature (e.g., alcohol consumption or diet) that has a causal relationship with feature j (e.g.. cholesterol) will also induce change in feature j. The chain of causality between the different features can be captured using weighted directed graph g A,, w)., called the causal graph. A represents the set of directed edges on G, where an edge from features i to j indicates that is causal for j. Finally, w AA- + captures the weights of the edges. We make no assumption on the structure of G, other than the fact that it is directed acyclic graph. 3
We represent all necessary information about the graph using an adjacency matrix A E Rddx where A, w(a,)) if dij E A and 0 otherwise. If there is an edge aaj E G, then feature E F causally affects feature j E F directly. The weight of edge aij. given by w(a,)) indicates that if feature improves by a unit amount, then the value of the downstream feature j will improve by w(az))*
Contribution matrix. We define the contribution matrix C E ddd for causal graph G as:
C# = ViE [d], and C.j EmER, w(p) Vi.j E [d], $
where Pty is the set of all directed paths from node i to node j on 9 and wpp) is the weight of path P E Pij with wpp) = Ilee w(a).
In causal graphs, feature may affect another feature j not just directly (in which case there would be an edge of non-zero weight from i to j). but also indirectly through other features; if there is directed path from feature i to feature j through intermediary features i,,...,4x, 4g. where i - i >> i2
is fr, then this can be encoded by the contribution matrix (Figure 1). Given the
'Agents may may not follow the learner's recommendations, depending on how well their incentives aligned with said recommendations.
"This is standard in the causal strategic classification [26. 32).
'Throughout the paper, we assume that causal relationships are linear. This is another common assumption the literature [26, 40].
2x y indicates that is directly causal for y-
3

---

adjacency matrix A, we can also show that the contribution matrix C can be computed efficiently (see Appendix E).
2.1 Principal- Agent Interaction
The principal deploys a linear classifier he E R.. Under this classifier, an agent with feature vector RS is assigned score of s(x) hg x. The classification decision y for said agent is given by ((x) = [<x) 2 r] for a pre-determined threshold 7 E R.
Agent Information Structure. We assume that the agent has Gaussian priors 11, ;= Nu En)
(where jrh E RRLI, En E RIFIXFI) over the deployed classifier ho and Πe == (H Ew) (where Me E RRAA En E AI over the edge weights of the causal graph g The agent knows the topology of the causal graph. We explore two kinds of information structures:
The Complete Information setting (Section 3), where the agent fully knows the classifier ho. i.c, Hb ho and Σn = O and the weights of all edges of G. i.c., Mw and E = 0.
The Incomplete Information setting (Section 4), where i) there is uncertainty over the principal's classifier hg. i.c., 24, may differ from he (bias) and Σn * 0 (variance), and/or ii) there is uncertainty over the edge weights of the causal graph G, i.c., Mww may differ from w (bias) and Ew # 0 (variance).
If yxx) 0, the agent also knows the amount e.g. in loan approval setting, an agent may know their current credit score and be told the threshold credit score that the bank uses to decide who gets approved for a loan.
by which she fell short of passing the classifier;
Agent Best Response. The agent wishes to obtain a positive classification outcome, i.e. y(r) = 1; she attempts to modify her feature vector x by investing some exogenous effort E R!FI, which we call the agent's exogenous effort profile. Importantly, exerting exogeneous effort subset of the features can also lead to other features (particularly those on which no effort was exerted) to change endogenously, due to causality. We call this phenomenon induced endogenous feature change.
Exerting effort comes a cost, modeled through a cost function Cost : Rdd Rzo, where Cost(e) (e) is the cost incurred for effort e. We mainly focus on (weighted) f--norm cost functions for all 2 1:
1/v
Cost(e)
Σ oy lesl) FEJ
where ej 0 V
(I)
where of represents cost multiplier associated with investing unit exogenous effort into feature f.
Let (e) be the agent's modified feature vector after investing effort e, and let Ar(e) x'(e) x be the net change in features due to e. Given the contribution matrix C and exogenous effort e, Ax(e) given by Ar(e) = CTe e. Hence, the agent's ' objective is to choose their optimal effort profile e* that ensures that y (e*)) cost. We call the effort profile e* (I,, Ic) the agent's best response to priors (II, II.). Formally:
with probability at least ō, while incurring the minimum possible
ex (II,, Icc arg min Cost(e)
s.t. PhNMI Tc 2 a] 2 1 111 8.
(2)
Note that the constraint ensures that an agent passes the classifier with probability least 1- 8, with respect to their prior on the causal graph and the classifier. In particular, if they exert effort profile e, their features change by C e, so their score changes by T CT e, and they have to improve their score by at least a to pass the classifier.
2.2 Incentivizing Effort towards Desirable Features
We are interested in the properties of the effort profile that the agent exerts as a result of best- responding to the principal's 's classifier, and in particular understanding the amount of effort they exert towards desirable features in set and undesirable features U. The goal to incentivize effort
"Gaussian priors frequently used model incomplete information [13, 27J.

---

w(a12)
w(ar))((as)) + w(a13) w(223)
C
1
e
0
w(aus
m((s))
fz
fs Ar ce
w(a12) n ((a12)u((23))) + w ((13))
mr(a))
Figure 1: Example of causal graph & with [F] = 3. fi directly affects fa and fa and fo directly affects fs. fi also indirectly affects fa through path 2
towards desirable features and away from undesirable features, i.. to understand when is it in the agent's ss best interest to invest more effort into desirable versus undesirable features?
We define 3-desirability that measures the ratio of investment in features in 'D vs U:
Definition 1 (β-desirable effort profiles), Given 0 < B < 1, an exogenous effort profile e is said be B- "dsiraabe"" " and only if: ||e 2 Al|el1,, i.e., the magnitude of effort towards desirable features is at least 3 3-fraction of the total effort.
From the principal's point of view, incentivizing 3-desirable effort profiles is not straightforward since agents are strategic, and may prefer undesirable features if they are low-cost to manipulate.
3 The Complete Information Setting
In the complete information setting, the agent knows precisely the true classifier ho deployed by the her prior T,, satisfies h. ho (the mean belief matches the true classifier) and the covariance is given by Σ, 0 (there no uncertainty). She also fully knows the causal graph g-i.e., 10 and E 0. Therefore, in the complete information case, the deterministic tuple (ho, C) is enough to fully characterize agent beliefs.
When the agent has no uncertainty about either the classifier or the causal graph, the agent's optimiza- tion problem (2) can be written as:
e ehoho, C) = arg min e20
Cost(e) (e) s.t. (Cho) 2
(3)
Le., the agent must find the minimum-com cost effort profile that passes the (known) classifier hg. Note that it suffices to only focus non-negative efforts for all features (this is without loss of generality as we prove in Proposition 1). Program (3) is convex optimization problem because the objective is convex for cost funetions and all constraints are linear. As such, this program can be solved efficiently. All proofs for this section can be found Appendix
Characterization of Optimal Effort Profiles. We now present the first main result (Theorem where we characterize the structural properties of the optimal effort profile e* for the cost function class outlined in Eq. (1) for > 0 (the case where a is trivial, as we show in Proposition 2). Importantly, we highlight how the structure of the effort profile changes fundamentally when the cost function transitions from the p = the p > 1 regime.
Theorem 1. The optimal effort profile e* of an agent with weighted t--norm costs (p 2 1) has the following structure:
(a) when there always exists optimal effort profile in which the agent needs modify exactly one feature to pass the classifier ba- The optimal feature to modify f is the one which offers the best ratio of contribution to cost, i.e., f arg max (Cho),, with the magnitude of effort invested into feature given by:
cf
e7.
(Chaly-
a
5

---

(b) Further, when > 1, the optimal effort profile invests effort along all non-trivial features (with (Cho)y > 0), with the magnitude of effort invested into feature satisfying:
((cha) 1/(0-1) cf
ej
Conditions for 3-desirability. In this segment, we derive necessary and sufficient conditions under which rational strategic agents have natural incentives to invest only in 3-desirable effort profiles (profiles where a significant amount of effort is exerted on desirable features).
Theorem For any 3 E (0. 1] and n--norm cost function (where p 2 1), the agent's 's best response is always a B-desirable effort profile if and only if:
(a) max (b)
(Cho't es < &maxfED
(Choly
when 1; and
6y
[ESED
(Cho)) of
2/(p-
1/2
Ereu
(Choli os
2/(p-1]] 1)7 1/2
when p > 1,
with 'D and U representing the set of desirable and undesirable features respectively.
The above result finds that, provided the principal designs classifier such that the overall im- portance of desirable features is large enough, desirable behavior can always be incentivized. It also underlines the dependence on the causal graph, which is captured through C. The causal graph characteristics determine the extent to which desirable behavior can be incentivized in any particular setting. This helps us to generate key insights about the design space of desirable classifiers (i.e.. classifiers which can induce 3-desirable effort profiles).
Desirable Classifiers and Where to Find Them. So far, we have provided conditions using which given any classifier hg. we can check whether it incentivizes desirable effort profiles from strategic agents. However, this does not answer the question of how difficult it is to find desirable classifier. Our following result answers this question.
Theorem 3. For any p 2 1. there always exists an instance of the problem (C, hg) and 3 >> 0 such that the space of B-desirable classifiers H. is non-convex set. However, when [D] 1, H can be shown to be convex for any B >> O and any l, en-orrm cost function with p E [1,3].
The first part of the theorem tells us that searching for desirable classifiers that also optimize for accu- racy is expected to be difficult. This is because optimizing over non-convex sets is generally known to be computationally hard. For more detailed formal discussion on hardness, see Appendix C.5.
However, the second part of the theorem argues that under the special case where there is only one desirable feature, the space of desirable classifiers is convex, at least for a limited subclass of f,-norm cost functions. Not only does this circumvent the technical difficulty encountered the general case, it also has other practical benefits. Note that this special case is actually aligned with what expect in real life: indeed, a principal may define for themselves which feature they want to incentivize, and focus one feature where they would really like to see improvements, especially if this is a feature that has historically not been properly leveraged. Not only that, but by targeting a single feature, the principal lowers the agents' cognitive load for best-respon,ing which is always desirable in practice. Note that we do provide a convexification heuristic for cases where [D] > that tries to induce desirable effort by minimizing the importance of undesirable features (See Appendix C.4 for details).
4 Incomplete Information Setting
Recall that for the incomplete information setting, the agent's optimization problem is: e" (II,, arg min Cost(e) s.t.
(4)
Ph- [(Ch) e 2 al 2 21 5 5 (0,1).
Models of Information. Recall that there can be two sources of uncertainty: i) the principal's classifier; and, ii) the edge weights of the causal graph G (the graph topology assumed to be common knowledge). In particular, this leads to the following three incomplete information models:

---

(1) Uncertainty only exists in the principal's 's classifier, the causal graph is fully known;
(2) Uncertainty only exists in the edge weights of the causal graph, the classifier is fully known;
(3) Uncertainty exists over both the classifier and the causal graph.
We refer to models and 2 as models of partially incomplete information while model will be referred to as a model of total incomplete information. The proofs for this section are Appendix D.
Optimal Effort Computation. We note that, unlike the complete information setting, the agent's optimization problem is significantly more involved. Therefore, our first objective here is answer the following question: Under what degree of incomplete information can agents still compute their best response efficiently This crucial because if agents cannot best respond reliably, the question of designing classifiers that incentivize desirable agent behavior is irrelevant.
Theorem 4. For 8 < 1/2, the agent's 's optimization problem (4) is:
(a) always convex, when uncertainty only exists in the classifier (model 1);
(b) convex, when uncertainty only exists in the causal graph and the causal graph has a bipartite structure (i.e., special cases of model 2)
(c) non-convex, for all other cases of model 2 with general causal graph structures and all cases of model 3 with total uncertainty.
In scenarios (a) and (b) above, we have convexity because the overall uncertainty Ch turns out to be multi-variate Gaussian, ie., Ch ~ N (pCE, Ech), in which case, the agent' 's optimization problem reduces to the following convex program:
ex e1I,,, Icc) = min Cost(e) s.t. a- Ps Ve Σcne S O,
(5)
where ps 2 (6) and 4 (-) is the inverse of the standard normal CDF.
The above result highlights that under limited uncertainty, the agent still efficiently solve for an effort profile that helps her to pass the classifier with high probability. Importantly, note that the above result is quite general: any setting where the agent's prior on the feature importance vector Ch is Gaussian is captured by our framework. In particular, we allow for largely different models of incomplete information from the ones have defined so far: for example, the principal may choose to reveal some information about the importance of features to agents, or agents may form priors about the feature importance vector directly through interactions with peers".
We also want to highlight that unlike the complete information case where the agent's optimization problem is always feasible (i.e., the agent can always pass the classifier by choosing effort correctly), under uncertainty, a positive outcome is not guaranteed. We provide a complete characterization of the feasibility of Problem (5) in the Appendix (Proposition 6). The intuition is that there is trade-off between the degree of uncertainty for the agent and the maximum coverage probability (1 - 8) that can be achieved under that uncertainty.
Characterization of Optimal Effort Profiles. We have already identified settings with partial uncertainty where the agent's optimization problem is convex and tractable. While it is much harder compute best responses closed form because of the involved nature of the optimization problem, we still provide insights about structural properties of the optimal effort profile. We identify key differences with the complete information setting, for example, under partial uncertainty, the optimal effort profile for agents with weighted & costs may always involve investment in more than one feature (Proposition 7). In the following result, we focus specifically on the co-cost case where we can actually characterize the best response in semi-closed form:
Theorem 5. For Ey-nrrm cost functions, the effort profile et which is the optimal solution to Problem (5), is of the following form:
= (kg T
PCh:
"One could argue that agents forming priors directly on the feature importance vector is more reasonable in practice because it foregoes the need for agents to reason about how the causal graph and classifier interact. thereby reducing the cognitive load required arrive an optimal decision.
7

---

where 11, X > O. Further, if Ech is diagonal matrix with entry (Ecr) corresponding to feature then
X"HONNS 11 + K2 (EEn)
VFEF.
The special case of Ech being diagonal offers good intuition into how agents with lz costs would exert effort under partial uncertainty. It shows that the agent is expected to invest more effort into features with higher expected contribution (μCa),, Further, the denominator highlights that agents may shy from features they have lot of uncertainty about, thereby leading to lower effort into them.
We also note that diagonal Ech arises in very natural settings. One such setting is scenario (b) in Theorem 4 when the uncertainty is only on the causal graph G and the causal graph is bipartite, i.c., features are either causal (they affect other features, but cannot be affected themselves) or proxy (they are affected by causal features, but cannot affect any other feature). In this case, causal features only have outgoing edges, while proxy features only have incoming edges. We prove this formally in Proposition 8 in Appendix D. Bipartite causal graphs are standard assumptions in much of the strategic classification literature [1, 26].
3-desirability under fg-costs with Incomplete Information. We conclude this section with a discussion on how to induce 3-desirable effort profiles under incomplete information. As see so far, it may be difficult to characterize the agent's 's optimal effort closed form under incomplete information, except for some limited cases. We focus on providing broad insights here, and build on this discussion through numerical experiments in Section 5.
The Interpretable Case of Diagonal Covariance Ech: In this special setting, we can identify con- ditions that guarantee investment in 3-desirable effort profiles by rational agents. We present the following two results:
Corollary 1. Suppose that Ech is a diagonal matrix. In that setting, if all features have the same overall level of uncertainty and the mean feature importance vector pCa satisfies:
3
|| (pck) lla
(pCN)al l12.
VI- g2
then the best response of rational agent with E--norm cost is to invest a 8-desirable effort profile. ((en)) is decreasing in (Ecn) therefore lower levels of uncertainty in
Corollary 2. e Ty too desirable features favors effort profiles with higher degree of desirability 3.
The first corollary follows directly from Theorem and should be intuitive- agents face the same degree of uncertainty about all features, they choose which features to invest effort in based on the mean importance of the features. Therefore, it makes sense that higher the total net importance (measured by the f2-norm) of the set of desirable features, higher the incentive for agents to invest in desirable effort profiles. On the other hand, when different features have different levels of uncertainty, less uncertainty desirable features is good for 3-desirability. This is because having higher degree of uncertainty (higher variance (Ecr)y) about the importance of a feature actively discourages agents from investing effort into said feature.
Non-diagonal Covariance Ech: We explore the non-diagonal Σca case in Section 5, with experiments on real data that consider more general cases of Eoh not being diagonal, specifically covering Model 1, when the classifier is not fully known to an agent. Our experiments suggest that many of the same insights about 3-desirability hold (even withou the assumption that Mes. is diagonal).
5 Numerical Experiments
Our experimental study focuses on setting where the learner is trying to reduce population's 's risk of cardiovaseular disease. To do so, we identify relevant features and build a causal graph based on the recent medical study of [19]. Their study aims to identify the causal links between features such as smoking, diet, or obesity, and whether a patient may develop cardiovascular disease (CVD). We exclude immutable features such age and ethnicity, focusing instead eight modifiable features: alcohol consumption, diet, physical activity, smoking, diabetes mellitus (DM), hyperlipidemia (HPL), hypertension (HPT), and obesity. Among these, we designated desirable
8

---

the features corresponding to lifestyle nnerventions-naneee namely, alcohol, diet, physical activity, and smoking-on those corresponding medical conditions or interventions (DM, HPL, HPT, and obesity). The full experimental setup is detailed in Appendix B.1.
Deployed classifiers: We consider four mean beliefs μ4, the vector h, that denote
DM: There a weight of on the "DM" feature, and on all others.
HPPL: There is weight of the "HPL" feature, and 0 on all others.
HPT: There weight of on the "HPT" feature, and on all others.
Obesity: There is a weight of on the "Obesity" feature, and 0 on all others.
For each of the four classifiers described above, we document the mean contribution of each feature, given by μCa Cju and the E norm of the mean contribution over the set of desirable and undesirable features, given by (D) and (2() respectively. All values are recorded in Table
Classifier
Alcohol
Diet
Activity
Smoking
DM
HPL
HPT
Obesity
(2)
(2
DM
0.1
0.84
0.82
0.52
0
1.28
HPL
0.14
0.84
0.82
0.34
1.23
HPT
0.62
0.84
0.82
0.86
0
0
1.58
Obesity
0.64
0.86
0.82
0
0
1.35
Table I: Mean contribution vector Poc. for the classifiers: DM, HPL, HPT, Obesity
We now make some key observations:
Desirable features can be incentivized even they are never observed. Figures and demon- strate that agents choose to invest significant effort into desirable features even if in our four classifiers of choice, no weight has been put on any of the features in set 'D (see Appendix B.4 for details).
Effeet of total contribution on desirable vs undesirable features: All four classifiers incentivize greater effort the set of desirable features D compared the set of undesirable features 2/ (see Table 1). In Figure 2, we observe that all classifiers achieve 3 > 0.5 under low to moderate uncertainty, which aligns with the prediction of Corollary 2. Furthermore,
find that hypertension (HPT) outperforms Obesity, which outperforms diabetes mellitus (DM), which then outperforms hyperlipidemia (HPL), in terms of effectiveness incentivizing effort on desirable features. This ranking is consistent with the ordering of (D( values across the classifiers and reinforces the theoretical insights provided by the special diagonal covariance case outlined in Theorem
Effect of uncertainty level a. In Figure 2, we plot how 3 varies as function of the uncertainty parameter for different classifiers. Higher indicates a higher degree of uncertainty about the classifier. As a increases, all four classifiers degrade terms of desirability (3). This is intuitive: at higher levels of uncertainty, the contribution of desirable features sees higher variance, as they affect not only themselves but also other features. Undesirable features then become safer to modify.
0.8
0.8
0.8 7V7
DM
0.2
0.2
0.2
HPL
HPT
6.0
0.5
3.0
3.5
2.0
2.5
3.0
0.0
0.3
1.0
1.5
2.0
2.5
3.0
0.9
0.3
1.0
1.5
2.0
2.3
(a) 0.1
(b) 0.3
(c) 0.5
Figure 2: Plot of how 3 varies with at different levels of 6 and for different classifiers.
Effeet of the failure probability 8. At fixed level of uncertainty a, the failure probability d increases, improves across all four classifiers (Figure 3). This is expected
means that the
'We note that all other belief's that only use undesirable, observable features are a linear combination of the four belief' above, so our insights extend to general classifiers.

---

agent is less stringent on the coverage probability requirement and hence has much larger space of feasible effort profiles to choose from- includncu desirable ones with high net contribution.
Trade-off's between a and 8. The failure probability is closely related to the level of uncertainty a. At a fixed level of uncertainty o, there is limit how low failure probability ó can be achieved (Figure 3). Similarly, in order to achieve a given failure rate ó, there maximum amount of uncertainty that can be tolerated (Figure 2); beyond that the problem becomes infeasible. This tracks our theoretical findings Proposition 6. Át = 0.5, uncertainty becomes irrelevant since the agent only needs 50% chance of passing the classifier and can rely solely on the mean belief 14n-
1.
0.2
6.
(a) (a 1,a
(b) (ax 1,0 1)
(c) (a 1,0 0 0.1)
Figure 3: Plots of how 3 varies with for different parameter combinations.
Effect of a represents the amount by which the agent shy of a positive classification outcome. In this case, 3 has no dependence on a (see Figure 5 in Appendix B.3). This is an artifact of the the agent's optimal effort profile is proportional therefore 3 remains unaffected. However, note that a does affect the cost incurred by the agent, the farther she is from the classification boundary (higher a). the higher is the cost incurred.
f2-norm cost function
in each feature and
6 Discussion
In this paper, we adopt causal perspective to the problem strategic classification. The principal deploys a linear classifier which classifies agents "positive" or "negative" based on set of features embedded on a causal graph. Since agents are strategic, they are expected to invest effort "cleverly" to modify their features in the hopes of positive classification outcome while incurring the minimum possible cost. Therefore, understanding how agents respond when they have different levels of access to information about the deployed classifier and the causal graph, is significant to the principal from the perspective of classifier design. We try to answer this central question from the principal's point of view: how design classifier which incentivizes agents to invest in desirable effort profiles?
There are many relevant avenues for future work. Our model uncertainty involves agents with Gaussian priors over the classifier or the edge weights of the causal graph or both, under the assumption that the graph topology is fully known. reality, there may other forms of uncertainty- for example, given large number of features, it may be unreasonable assume that agents have complete knowledge about all causal relationships between features. may be interesting to explore other, more interpretable information structures c.g., instead of independent priors on the classifier and the causal graph, agents may have access to a partial ordering on features by relative importance. Such models may be closer how humans perceive and respond to uncertainty in reality. Finally, different populations with different levels of uncertainty in their priors may have markedly different abilities respond the classifier. The fairness implications of such information asymmetries an important direction for future work.
Acknowledgements
The authors are grateful from support from the US National Science Foundation (NSF) under grants IIS-2504990, IIS 213-233,,36, and an Amazon Research Award. This work has also been partially supported by project MIS 5154714 of the National Recovery and Resilience Plan Greece 2.0 funded by the European Union under the NextGenerationFU Program. Any opinions and findings expressed in this material those of the authors and do not reflect the views of their funding agencies.
10

---

References
[1] Saba Ahmadi, Hedyeh Beyhaghi, Avrim Blum, and Keziah Naggita. The strategic perceptron. In Proceedings of the 22nd ACM Conference on Economics and Computation, pages 6-25, 2021.
[2] Saba Ahmadi, Hedyeh Beyhaghi, Avrim Blum, and Keziah Naggita. On classfficatio of strategic agents who can both game and improve. In 3rd Symposium on Foundations of Responsible Computing, 2022.
[3] Kenneth Arrow. The economics of moral hazard: further comment. The American economic review, 58(3)5537-539 1968.
[4] Kenneth J Arrow. Uncertainty and the welfare economics of medical care. In Uncertainty in economicx, pages 345-375. Elsevier, 1978.
[5] Yahav Bechavod, Katrina Ligett, Steven Wu, and Juba Ziani. Gaming helps! learning from strategic interactions in natural dynamics. In International Conference on Artificial Intelligence and Statistics, pages 1234-1242. PMLR, 2021.
[6] Yahav Bechavod, Chara Podimata, Steven Wu, and Juba Ziani. Information discrepancy in strategic learning. In International Conference on Machine Learning, pages 1691-1715. PMLR, 2022.
[7] Dimitris Bertsimas and John Tsitsiklis. Introduction to linear optimization. 1997.
[8] Mark Braverman and Sumegha Garg. The role of randomness and noise in strategic classification. In Ist Symposium on Foundations of Responsible Computing, 2020.
[9] Yiling Chen, Yang Liu, and Chara Podimata. Learning strategy- aware linear classifiers. Ad- vances in Neural Information Processing Systems, 33:15265-15276, 2020.
[10] Lee Cohen, Saeed Malvaji-aalvajerdi,, Kevin Stangl, Ali Vakilian, and Juba Ziani. Bayesian strategic classification, 2024. URL attps://arxiv: org/ ab/////2//222.2////////// 08758.
[11] 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, pages 55-70, 2018.
[12] Raman Ebrahimi, Kristen Vaccaro, and Parinaz Naghizadeh. The double-edged sword of behavioral responses in strategic classification: Theory and user studies. arXiv preprint arXiv:2410.18066, 2024.
[13] Hadi Elzayn and Zachary Schutzman. Price of privacy in the keynesian beauty contest. In Proceedings of the 2019 ACM Conference on Economics and Computation, pages 845-863, 2019.
[14] Andrew Estornlll, Sanmay Das, Yang Liu, and Yevgeniy Vorobeychik. Group-fair classification with strategic agents. In Proceedings of the 2023 ACM Conference on Fairness, Accountability, and Transparency, pages 389-399, 2023.
[15] Ganesh Ghalme, Vineet Nair, Itay Eilat, Inbal Talgam-Cohen, and Nir Rosenfeld. Strategic classification in the dark. International Conference on Machine Learning, pages 3672-3681.
PMLR, 2021.
[16] Sanford Grossman and Oliver Hart. An analysis of the principal-agent problem. In Foundations of Insurance Economics: Readings in Economics and Finance, pages 302-340. Springer, 1992.
[17] Moritz Hardt, Nimrod Megiddo, Christos Papadimitriou, and Mary Wootters. Strategic classifi- cation. Proceedings of the 2016 ACM Conference on Innovations Theoretical Computer Science, pages 111-122, 2016.
11

---

[18] Keegan Harris, Hoda Heidari, and Steven Z Wu. Stateful strategic regression. Advances in Neural Information Processing Systems, -28741 2021.
[19] Wan Shakira Rodzlan Hasani, Kamarul Imran Musa, Xin Wee Chen, and Kueh Yee Cheng. Constructing causal pathways for premature cardiovascular disease mortality using directed acyclic graphs with integrating evidence synthesis and expert knowledge. Scientific Reports, 14 (1):28849, 2024.
[20] Guy Horowitz and Nir Rosenfeld. Causal strategic classification: A tale of two shifts. In International Conference on Machine Learning, pages 59233-13255 PMLR, 2023.
[21] Lily Hu, Nicole Immorlica, and Jennifer Wortman Vaughan. The disparate effects of strategic manipulation. In Proceedings of the Conference on Fairness, Accountability, and Transparency, pages 259-268, 2019.
[22] Jean Kaddour, Aengus Lyneh, Qi Liu, Matt Kusner, and Ricardo Silva. Causal machine learning: A survey and open problems. arXiv preprint arXiv:2206. 0att:22266.447555 15475, 2022.
[23] Amir-Hossein Karimi, Gilles Barthe, Bernhard Schölkopf, and Isabel Valera. A survey of algorithmic recourse: definitions, formulations, solutions, and prospects. arXiv preprint arXiv:2010.04050, 2020.
[24] Amir-Hossein Karimi, Julius Von Kügelgen, Bernhard Schölkopf, and Isabel Valera. Algorith- mie recourse under imperfect causal knowledge: probabilistic approach. Advances in neural information processing systems, 33:265-277, 2020.
[25] Amir-Hossein Karimi, Bernhard Schölkopf, and Isabel Valera. Algorithmic recourse: from counterfactual explanations interventions. In Proceedings of the 202/ ACM conference on fairness, accountability, and transparency, pages 353-362, 2021.
[26] Jon Kleinberg and Manish Raghavan. How do classifiers induce agents to invest effort strategi- cally? ACM Transactions on Economics and Computation (TEAC), 8(4):1-23, 2020.
[27] Yuqing Kong, Grant Schoenebeck, Biaoshuai Tao, and Fang-Y Yi Yu. Information elicitation mechanisms for statistical estimation. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 2095-2102, 2020.
[28] Gunnar König, Timo Freiesleben, and Moritz Grosse Grosse-Wentrup. Improvement-focuu causal recourse (icr). In Proceedings of the AAAI Conference on Artificial Intelligence, volume 37, pages 11847-11855, 2023.
[29] JaaneJscques Laffont and David Martimort. The theory of incentives: the principal-agent model. In The theory of incentives. Princeton university press, 2009.
[30] Tosca Lechner, Ruth Urner, and Shai Ben-David. Strategic classification with unknown user manipulations. International Conference on Machine Learning, pages 18714-18732. PMLR, 2023.
[31] Harold A Linstone, Murray Turoff, et al. The delphi method. Addison-Weshe Wesley Reading, MA, 1975.
[32] John Miller, Smitha Milli, and Moritz Hardt. Strategic classification is causal modeling in disguise. In International Conference Machine Learning, pages 6917-6926. PMLR, 2020.
[33] Smitha Milli, John Miller, Anca D Dragan, and Moritz Hardt. The social cost of strategic classification. In Proceedings of the Conference on Fairness, Accountability, and Transparency, pages 230-239, 2019.
[34] Panos M Pardalos and Stephen A Vavasis. Quadratic programming with one negative eigenvalue is hprhard. Journal of Global optimization, 1(1):15-22, 1991.
[35] Mark Pauly. The economics of moral hazard: comment. The american economic review, pages 531-537, 1968.
[36] Judea Pearl. Causality: Models, Reasoning, and Inference. Cambridge University Press, 2000.
12

---

[37] Chara Podimata. Incentive-aware machine learning; robustness, fairness, improvement & causality. arXiv preprint arXiv:2505.0521,, 2025.
[38] Stephen A Ross. The economic theory of agency; The principal's problem. The American economic review, 13421133 1973.
[39] David E M Sappington. Incentives in principal-agent relationships. Journal of economic Perspectives, 5(2): 66, 1991.
[40] Yonadav Shavit, Benjamin Edelman, and Brian Axelrod. Causal strategic linear regression. In International Conference on Machine Learning, pages 8676-8686. PMLR, 2020.
[41] Ravi Sundaram, Anil Vullikanti, Haifeng Xu, and Fan Yao. Pac-leaming for strategic classifica- tion. Journal of Machine Learning Research, 24(192):1-38, 2023.
[42] Sohini Upadhyay, Shalmali Joshi, and Himabindu Lakkaraju. Towards robust and reliable algorithmic recourse. Advances Neural Information Prucessing Systems, 14:16696-16937, 2021.
[43] Julius Von Kügelgen, Amir-Hossein Karimi, Umang Bhatt, Isabel Valera, Adrian Weller, and Bernhard Schölkopf. On the faimess of causal algorithmic recourse. In Proceedings of the AAAI conference artificial intelligence, volume 36, pages 9584-9594, 2022.
[44] Xueru Zhang, Mohammad Mahdi Khalili, Kun Jin, Parinaz Naghizadeh, and Mingyan an Liu. Fairness interventions as (dis) incentives for strategic manipulation. In International Conference on Machine Learning, pages 26239 26264. PMLR, 2022.
13

---

NeurIPS Paper Checklist
1. Claims
Question:
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: All claims made in the abstract and introduction are representative of the results discussed the paper.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results
be expected to generalize other settings.
is fine to include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
The paper discusses limitations and scope for future work in Section
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model sell-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
14

---

Answer:
[Yes]
Justification: Yes, all theoretical results have clearly specified assumptions and are thor- oughly backed by proofs.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: Yes, the paper contains all information necessary to reproduce results including detailed Experimental Setup in the Appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, other means that appropriate to the research performed.
also be provided via detailed
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reprodueibility may be tricky in some cases, in which authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
15

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification: Yes, all code will be included as supplementary material before the deadline.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.. cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" an acceptable answer. Papers cannot be rejected simply for including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https:
/ttpp.cccppbllll/// http:ccccpppccccccecceeccccccccc guides/ CCodeSubmiieeeee S ssi ssisssoolooooooooo oonooiiyyyylolooooooooooomiiimii for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: All details pertaining to Experimental Setup have been included in the attached Appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: This does not apply to this particular paper because of the nature experi- mental results.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
16

---

The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time execution) needed to reproduce the experiments?
Question:
Answer: [No]
Justification: This does not apply to this particular paper because the experiments are extremely simple, do not require special computing resources and were run personal computer.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: //nerrip////iss./// cc/public/BBicccccccccc htthh////ehhisuueeleeee.e
Answer: [Yes]
Justification: Yes, the research conducted conforms with the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No. they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: The paper discusses the broader social impact of this work in the introduction to motivate the rest of the paper.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
17

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
This does not apply to this submission.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification:
The paper does not use any such assets and this question does not apply.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website). the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms use in package should be provided. For popular datasets, paperswi wwwode.hcoe...c. com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
18

---

For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer:
[NA]
This question does not apply to this submission since no new assets were introduced.
Justification:
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the datasct/codd/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
For crowdsoureing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Question:
Answer: [NA]
Justification: This question is not applicable for this submission since no human subjects were used during the conduct of this research.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According to the NeurIPS Code Ethics, workers involved in data collection, curation, other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
This question does not apply to this submission.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere the NeurIPS Code of Ethics and the guidelines for their institution.
19

---

For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Justification: This paper does LLMs in any capacity to generate any of the insights or results of this paper.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, or non- non-standard components.
Please refer to LLM policy (https: //tpuriee..p///e/ee wwwc///ceeenne///////////cca /LLM) for what should or should not be described.
20

---

Supplementary Material for paper
"Incentivizing Desirable Effort Profiles in Strategic Classification: The Role of Causality and Uncertainty"
A
Related Work
Strategic classification. Strategic classification has been widely studied recent years. This belongs to a broad class of problems in economics called rincipal-agen problems where agents act strategically in their self-interests which are often misaligned with the principal's interests [16, 29, 38, 39j. Early works in strategic classification focused on scenarios where agents manipulate their observable features to "game" a published classifier, thereby increasing their chances of a favorable label without genuinely improving underlying attributes [1, 8, 9, 11, 17, 30, 41, 44]. [5, 6, 18, 26, 40] move away from this assumption and consider settings where agents can not only game the classifier, but also invest in real improvements. In many cases, actual improvement involves investing effort which not directly observable by the principal - this again has similarities to the notion of moral hazard in insurance markets [3, 35] and other general settings [4]. Fairness in strategic classification [14, 21, 33]) has also been an important avenue of work, but is less related to this work.
Causality. A useful tool to model manipulations as opposed to effective improvement is causal- ity [22, 36]. In strategic classification, few recent studies have incorporated causal modeling to account for interdependencies among features [2. 5, 20, 26, 32, 40]. [32] highlights that in strategic classification, learning a classifier that incentivizes gaming as opposed to improvement is as hard as learning the underlying causal graph between features. [40] and [5] both focus special cases of linear causal graphs, unlike our work that considers general cases of linear graphs. [2] explore strategic classification using different structural framework known "manipulation graphs," where each agent has a fixed set of costly effort profiles that they may choose from, also defining a special case of causal graphs. [20] distinguish among causal, non-causal, and unobserved features, but focus on a different objective: predictive accuracy.
Perhaps closest to is the work of [26]. Like us, they focus on general causal graphs; however, we highlight several major differences. First, we focus on classification settings, while [26] focus on regression and scoring settings. Second, we highlight differences in our agent model, where our agents invest effort to pass the classifier with reasonably high probability, while agents in [26] always exert effort to improve their score. Third, we note that cost model is strietly more general: where [26] focuses on linear costs, our work considers general fp-costs". Finally, unlike [26], our study incorporates incomplete information, where agents may not fully understand either the causal graph or the deployed classifier.
Incomplete Information. A closely related line of work investigates strategic classification under varying models of information available to agents. In many real-world settings, agents may have incomplete information about the classifier- model is proprictary, or the causal relationships governing feature interactions [6. 10, 15]. Or, agents might misperceive the classifier due to behavioral biases [12]. However, the best of our knowledge, we are the first work in the space of strategic classification to incorporate both causal modeling and incomplete information in strategic classification.
because it is too complex, or because the learner's 'ss
Algorithmic recourse. Our work is also closely related to the extensive literature on algorithmic recourse [24, 25, 28, 42, 43]. From a mathematical standpoint, strategic classification and algorithmic recourse can be seen as flip sides of each other: in recourse, the learner tells the agent what actions to take (but the agents may decide to take different action unless properly incentivized) while in strategic classification, the agents decide on their own actions based on the classifier. We note, however, several differences between recourse and strategic classification: a) From practical point of view, recourse requires providing a recommended action to each agent who obtains a negative
Our results show that this choice of cost is important, noting a sharp distinction in agent behavior between the cases of cost and Ep costs for px > 1.
21

---

decision, and is still less common in practice than releasing a single, often not fully transparent, model. Strategic classification, especially with incomplete information, allows us to capture such practical scenarios. b) The addition of the 3-desirability constraint is novel. As we see in many places throughout the paper, this constraint makes the problem significantly more difficult, leading to non-convexities. We expect these issues to also arise when adding desirability to the algorithmic recourse literature, since the optimization problems solved by both fields are similar, and we think that the inclusion of desirability in the recourse literature is an exciting direction for future work. c) To the above point, much of the recourse literature aims to find a low-cost path between an agent's current features and features that lead to positive classification. Importantly, much of the literature does not think specifically about whether that path involves gaming or modifying undesirable features. [28] in fact show that standard counterfactual recourse algorithms often lead to undesirable outcomes such as gaming the system. This is an important limitation: as agents game the classifier, the classifier loses in accuracy and robustness, and must be modified to compensate for this accuracy loss, reducing the effectiveness of the recourse. This includes causal algorithmic recourse, such as [24], where the causality is typically used ensure accuracy of the recourse by taking into account how different features affect each other, whereas previous work that effectively assumed independence of features and could mis-estimate how proposed recourse would translate into feature changes. In much of this literature, however, causality is not introduced to prevent gaming vs improvement or understand desirability.
B Additional Details for Experimental Section 5
B.1 Experimental setup
Identifying Relevant Features We identify a subset of 8 features used in [19] that we focus on in our experimental study. In particular, we did not include features that cannot be changed such as age or ethnicity, and only include the features that can be modified by an individual. The features we identified are: alcohol consumption, diet, physical activity, smoking, diabetes mellitus (DM), hyperlypidia (HPL), hypertension (HPT), and obesity. We normalized features to be between [0, 1]
Among these features, and as noted in our introduction, a principal (i.e., a doctor) would like to in- centivize people to focus on preventative. lifestyle interventions over medical treatment interventions. Hence, we separate them to desirable and undesirable to modify as follows:
Desirable: Alcohol, Diet, Activity, Smoking. Note that desirable means here that these features are desirable to modify, not that, for example, alcohol consumption is desirable.
Undesirable: DM, HPL, HPT, Obesity. Note that these features are not "undesirable" per se, but rather less desirable than lifestyle interventions.
Building the Causal Graph: The study of [19] asked the experts report the likelihood of causation on a Likert scale from 1 to 7, which is then transformed into "fuzzy score" via the Fuzzy Delphi Method [31]. We denote this score 8. A fuzzy score of 0.5 and above indicates that experts at least moderately agree with a relationship being causal, with an increasing score s indicating stronger agreement. A fuzzy score of 0.5 or below indicates that the experts at best disagree with the feature being causal, with the strength of the disagreement increasing as the score goes down.
We follow the expert agreement of [19] to build our causal links. Specifically, we identify link as causal if and only if s > 0.5. Further, since a score of 0.5 denotes that experts are at the boundary of agreeing vs disagrecing on causality, we renormalize our scores to be between 0 and 1: to do so, apply a linear transformation that maps 8 = 0.5 to a causal weight of 0, and s = 1 to a causal weight of 1. We obtain the following graph (Figure 4):
Generating Prior Beliefs We note that our desirable features are generally harder to observe than our undesirable features. First, DM, HPL, HPT, and Obesity are casy-to-quantify features that are also verifiable by a doctor (c.g.. though blood work). On the other hand, lifestyle habits are not only hard to observe, but also often mis-reported to clinicians (i.e., under-reporting alcohol consumption, or
Foro simplicity and wlog, we assume that 0 is the least "healthy" value of the feature, and is the "healthiest" value of the feature. For example, for smoking, 1 maps to not smoking: for activity, 1 maps to high amount of weekly physical activity.
22

---

Obesity
Diet
Smoking
Activity
Alcohol
Figure Causal graph features which affect the output of interest "Risk Cardio-vascular disease (CVD)". There 8 features, all of which causal. The features at the bottom form the set of desirable features DD and those on the top form the set of undesirable features 24 The causal links are indicated the graph. This causal graph has special structure: it is bipartite. The edge weights recorded in Table in Appendix B.
lying about smoking to avoid insurance upcharges). Hence, we generate all our priors of h to have both mean and variance of O for all desirable features (i.e., it is fully known that desirable features are not observed by a clinician, and so not used in the clinician's 's classifier for high risk of CVD), as they are effectively unobservable. We consider four mean beliefs μad the vector h, that denote as follows:
DM: There is weight of 1 on the "DM" feature, and O on all others.
IPL: There is weight of 1 on the "HPL" feature, and 0 on all others.
HPT: There is weight of the "HPT" feature, and all others.
Obesity: There is weight of 1 the "Obesity" feature, and 0 on all others.
We note that all other beliefs that only use undesirable, observable features are linear combination of the four beliefs above, so our insights extend to general classifiers. Also, we demonstrate later that while the classifier does not put any weight on unobserved/ddesirable features, agents may still exert effort on them because they affect the observed/undesiiable features used in the classifier.
The variance of each of the desirable features taken be (there is complete information that no weight is put on these features in the principal's 's classifier). Further, we assume that all undesirable features have the same variance, which parametrized by 0 thus a measure the level of incomplete information. Finally. the covariance matrix of the classifier (E,, is taken to be diagonal for simplicity of exposition and interpretation, i.e., individuals' beliefs do not encode correlations between features in the deployed classifier.
B.2 Supplementary Tables
Features
Alcohol
Diet
Activity
Smoking
DM
HPL
HPT
Obesity
Alcohol
0
0
0
0.10
0.14
0.62
0.64
Diet
0
0
0.84
0.84
0.84
0.86
Activity
0.82
0.82
0.82
0.82
Smoking
0
0
0
0.52
0.34
0.86
0
DM
0
0
0
0
0
0
HPL
0
0
0
HPT
0
0
0
0
0
Obesity
O
0
0
0
0
Table 2: Adjacency matrix which captures the edge weights of the causal graph Figure 4
23

---

B.3 Effect of a on B.
As explained earlier, independent of We demonstrate this below by plotting I's function of 8 for two different values of a:
1 and = 10.
04
0.4
(a) (a
1, 3)
(b) (a 1,0 1)
(c) = 1,0 0.1)
1.0
0.4
34
0.5
0.
(d) (a 10, a 3)
(e) (a 10, = 1)
(1 (a 10, a = 0.1)
Figure 5: Plots of how 3 is invariant with at all levels of uncertainty.
B.4 Further discussion on results
observed. In four classifiers of choice, observe that no weight has been put on any of the features in set 'D because they represent features which cannot be directly observed. However, Figures 2 and 3 demonstrate that agents still choose to invest significant effort into desirable features. This is a direct result of the causal relationship between features. Observe that in the causal graph, the desirable features influence multiple undesirable features simultaneously. This means that an agent obtains a larger improvement in the undesirable features (which actually affect the agent's classification), not by modifying them directly, but by investing effort into desirable features.
Desirable features can be incentivized even if they
C Results & Proofs for the Complete Information Setting
Proposition 1. For the cost functions defined in (1), without loss of generality, assume that: (Cho); 2 0 and that (c) 2 0 F.
Proof. Let e* be the optimal effort profile for the agent, i.e., the profile that corresponds to the solution of (3). First, note that for any feature f E F, (Cho), 0 implies ej 0. Indeed, if feature has contribution towards the classification decision, then effort should be expended on f in the optimal effort profile.
Now, we can focus on features for which (Cho), + O. When (Cho)) < O, we will show that e7 S 0. construct new effort profile e' follows: e' = and o = for all g F.g + f. is easy that e' is still feasible but Cost(e') Cost(e") which contradicts the fact that e* is the optimal solution. Therefore, ej < 0. Similarly, we can show that
Suppose that e; 0. In this case,
when (Cha), > 0, e 2 0.
The above discussion implies that whenever (Cha), * O, then (Ch 2 0 therefore, without loss of generality, it suffices to assume (Cho), > and only search over the space 2 0 (because the optimal solution e* 2 0). This concludes the proof.
Proposition When a S O, then effort change her features.
which means that the agent does not need to invest any
24

---

Proof. Note that the objective value is greater than or equal to zero since ef > 0 for all f E F and 2 0. But, since a I 0, c is feasible the above problem and also achieves an objective value of 0. Therefore, e = 0 must be optimal.
C.1 Proof of Theorem
We complete the proof in parts: first, we prove the p 1 case in Lemma followed by the p 1 case in Lemma 2.
Lemma When modify exactly one feature to pass the classifier hu- The optimal feature to modify f is the one which offers the best ratio of contribution to cost, i.e.,
there exists an optimal effort profile for the agent in which she needs to
(Cho)s
I" E arg max
FEF
of
and the optimal amount of effort to be invested into that feature is given by:
Cft (Cho)
Proof. For p 1, we have the following optimization problem for the agent:
min e20
eee e s.t. (Cho) 2 a.
(6)
The optimization problem in (6) (which we will call the primal problem is linear program whose feasible region is given by the following polyhedron Q {e R (Cha) Te 2 a, e 2 0}. Our first goal is to argue that the optimal solution is a corner point of Q which requires following: i) firstly, Q has at least one corner point, and ii) the optimal solution bounded which would imply that it must be at corner point of Q. Note that the polyhedron Q has no line (because it a subset of the positive orthant) and therefore, it must have least one corner point!! We can now write the dual problem (D) follows:
to prove the
max ST
OU
s.t.
(D)
(Cha) S (e)
π 2 0.
We know that the dual problem (D) is feasible (I 0 is feasible to D) which implies that the optimal solution to (P) cannot unbounded. Hence, we conclude that there must exist a corner point optimal solution to problem (P). Now, note that all corner points of Q are obtained by the intersection of e 2 a with the positive axes. So any corner point of Q must be of the form the hyperplane (Cho) T
where exactly one entry corresponding to some feature f is positive (i.e., takes value (Cha), and all other entries are zero. This implies that there exists an optimal effort profile where the agent needs to modify exactly one feature, proving the first part of the lemma.
For proving the second part, will use the complementary slackness conditions the dual constraints. We already know that there exists an optimal primal solution where there is some feature f* with ey- (Eholy= and Ex- for all f + f Let म* be the optimal dual solution. Using complementary slackness, we know that n (Cho) lz = cf- which implies that:
Cf:
(Cha))-
Since nt must also be feasible to (D), we must have:
Cp
A Vf'+", (Cho)s #0,
(Chu))
which implies that:
(Cho)s
f arg max FEF Cy
This concludes the proof of the lemma.
For more details the polyhedral theory related to linear optimization, please [7].
25

---

When the cost function is the weighted ey-norm of the effort for p > 1, the optimal effort profile for the agent e* satisfies:
Lemma 2.
oj x (Chaly 1/(x-1)
ASEF.
Proof. We solve the constrained optimization problem using Lagrange multipliers. Define the Lagrangian as follows:
- (Erer 1/2 + x-((Chh))
Cie, x)
where ı the Lagrange multiplier associated with the constraint as defined earlier. This gives us the following set of KKT conditions:
vel(e,))= =0,
(-(Cho) Teteetee ae =0
क 2 0,
a- (Cho) e S 0, e 0.
Since our optimization problem is convex, it suffices to find a pair (e",T") that satisfies the KKT conditions and we can automatically conclude that e* is optimal to the primal problem.
First, we show that the constraint (Cho)Te 2 a must active at the optimal solution. We prove this by contradiction. Suppose, if possible that (Cho) T T + a < However, this means that we can obtain the optimal solution e by solving the primal problem as if it were unconstrained. In that case, it must be that ex O, but observe that e = is not even feasible (and hence cannot be optimal), This implies that the constraint must hold at equality. Therefore, we can solve for e and n by solving following system:
-(Cho) e + a 0, Vel(e,
Now,
7L
cp(e,)p-1
(Vel(e,T)), des
1/p p-1 x.
TChh)
Σ c)(e))p fEF
We have already argued that e* * 0. Therefore, n > This implics that for all features f E F. whenever (Cho)s 0, must have:
(Cho)s 1/(p-1)
oz x
cf
and when (Cho), = 0, the condition holds trivially. This concludes the proof of the lemma.
C.2 Proof of Theorem
This proof will again be completed in two parts: first for (Lemma 3) and subsequently for p > (Lemma 4).
Lemma 3. For any 3 (0. 1], the agent's 's best response is always a 3-desirable effort profile if and only if there exists desirable feature f* (f* E such that:
(Cha)s (Cho)s
max fell
Cf
C5-
Proof. We have already shown previously that there exists optimal effort profile for the agent in which she needs invest effort into single feature I where
(Cho)s
f E arg max JEF
Cy
26

---

and the optimal amount of effort that needs to be invested into that feature is given by (Cho)y' We define:
(Cho)s
I' [f EF: f arg max JEF of
Note that I + 1 since (Cho) 0 and have finite number of features. Pick f* arg faX if and only if:
(Chals (f" exists and is in D). Now, the agent's best response is a desirable effort profile
I - + YfEu, f4I
WSEU, (Cho)s
(Cho)s
< max feJ
Cf
cf
(Cho),
(Cho)s
max feu
< mnax
Cf
FEF
Cf
(Cho),
(Cho),
max fell
< max
Cf
FED
(Cho)s
(Cho),
max
FEU
Cf
Cg
This concludes the proof the lemma.
Lemma 4. For norm cost fanction with p > 1, the agent's best response is always a 3-desirable effort profile if and only if:
1/2
2/(0-1) 1/2
2/(x-1)
(Cho)s cf
(Cho)s
Σ JED
2
V1
B2
cf
fEu
Proof. We have already shown that when the agent's cost function is ep-norm with p 1, her optimal effort profile e* satisfies:
((Cho)s) 1/(--1)
ez x
VfEF.
CJ
Now by the definition of B-desirability, ex is 3-desirable if and only if:
|e 12 2 B|e =
1cb112 2
||
12
1 - 82
822
Σ of 2 - 32
ef
FED
FEL
(Cho)s
1/
32
(Cho)s
2/(p-1)
Σ
cJ
B2
Cf
FED
feu
1/2
1/2
(Chols
2/(x-1) 1)
9
(Cho)s
2/(x-1))
Σ
Cf
V1
B
Cf
JED
FEa
This concludes the proof of the lemma.
C.3 Proof of Theorem 3
We will complete the proof in two parts. First, we will show that in the general case, the space of desirable classifiers H can be non-convex (Prop 3), followed by the proof of convexity in the special case of (D) = (Prop 4).
Proposition 3. For any p 2 1, there always exists an instance of the problem (C, ho) and 3 such that the space of 3-desirable classifiers H. is non-convex set.
27

---

Proof. The set of 3-desirable classifiers H. is given as follows:
{ ho E RIA e (ho, C)) is 3-desirable, Cho 2 0)
H =
We define the set 2 (Choo) hg E H}. Suppose that C is full row-rank. This implies that H is convex if and only if 2 is convex Therefore, in order to complete the proof, it suffices to show that the transformed where Z is non-convex and the agents incur nn-mm cost functions with = 1 and > 1. Recall from Theorem that the
Z non-convex the worst case. We now provide instances of problems
given follows:
zf
3 =
2
BERE
R 20
max
max JED Cj
(p (p=1)
SEll
Cf
1/2
1/(
2/(p-1) 1)
2 = 2 E
R
Σ JED
B
(p > 1)
20
Cf
V
B
Cf
fEll
Consider a setting where there are features with D =1,22 and U = {3, 43. Suppose that the cost vector equals c 1. In this case,
Weighted -n-ormm cost function:
2 = {a E 1 max =4) < (2)
Now, choose ;= (4. 7. 6) and z" = 37. Both are clearly points in Z. However, for 0.5, az' + (1 - a)²" = (5.5, 6, Z. Therefore, Z is not convex set.
Weighted norm cost function:
Consider a setting where there are features with D {1,
and 1 (3). Letp = 2, c 1 and
/2 Then 2 given by:
2 =
R 20 V 27 23 23
(0, 1) and (1,0,1) are points in Z, but the point halfway between them, given by (0.5, 0.5, 1) is clearly not in Z. Therefore, Z is not a convex set. This concludes the proof.
Proposition 4. Suppose that there is only single desirable feature, i.e., that [D] 1. Then for any O, the space of B-desirable classifiers H is convex for any ty-norm cost function with p E [1,3].
Proof. We will verify convexity separately for the cases with & --oor and np-n (1 < < 3) cost functions.
The l norr case: When the cost function is a weighted f--nrmm, the set of desirable classifiers is given by
H = { ho E k! Cho > 0, max fell
(Cho)s
(Cho))
max JED
Cf f
Cf
Now, suppose [D] = and there is some feature fa E D. Then, we can rewrite H. as follows:
(Cho)s (Cho)s <0]
H = ho E R! Cho 2 0, max
fEF((fa) Cf
Cfa
In order to show that H. is convex set, suffices to show that the function g(ho) max of maximum of linear functions (which is convex) and a linear function; hence, function g(-) is convex.
(Cha)s (Cho) is convex function. Function g(-) corresponds to the of 6/a
The no-norm case with p 1: For & norm cost functions with p 1. set H. is given by:
1/2
2/(p-1)] 1/2
H. A ho E R F1 Cho
0,
Σ
(Cho)s
2/(p-1)
B
Σ SEU
(Chols
Cj
32
Cf
FED
This is standard result in linear algebra; the proof provided in Appendix for completeness
28

---

Using the fact that [D] 1, we can rewrite H. as follows:
(p-13/2
2/(--1)
(Cho)s
H = hg E RR F1 Cho 2 0, (Cho) 2 K
Σ
cf
FEU
(p-1)
where K = Csa V1- function r(ha) is convex, where r(ho) given by:
>
Now in order to complete the proof, we need to show that the
(p- 1)/2
(Cho))
2/(x-1) 1)
r(ho) K
Σ
Sa
of
FEU
When < S 3, rewrite r(ha) as follows:
r(ha)
K|| Bholl//e-1> - (Cho)
where B E (1((-11))((111-1) Note that //o/Booll/(p-1) is convex function in ho since this is g-norm for q = p-1 2 This makes r(ho) a convex function in hg (sum of convex function and linear function is convex) and concludes the proof.
C.4 Heuristic for Inducing Desirable Effort when [
When [D] > 1, we know that in general, the set H of 3-desirable classifiers is not convex, and difficult to optimize over. However, we propose a convexification heuristic (parameterized by y) where the principal just tries to design classifier such that "the total contribution of undesirable features no more than y":
Proposition 5. Let Hwi(sss (ho I(Chh)ull2//0-1 S 3) Then for any 7 0, Hu is convex for any -y-wrrm cost function with p E [1,3].
The proof is nearly identical to that of Proposition and is omitted to avoid repetition. This result helps the principal guarantee that they can bound the effort exerted undesirable features, even if they are not able to guarantee a certain target level B-desirable effort.
C.5 Hardness Results
In this segment, we to formally characterize hardness of: a) finding any B-desirable classifier, and b) finding the best such classifier, i.e., one which simultaneously 3-desirable and also maximizes classification accuracy. We operate in the limited setting of f2-norm cost functions. We show that while subproblem a) can solved in polynomial time, subproblem b) likely to NP-hard.
a) It is possible to find a 3-desirable classifier for &y-norm cost functions in polynomial time.
Consider the matrices Op and Cu. where Cp zeroes out all rows not corresponding to features in D. and Cy zeroes out all rows not corresponding features in 4, from the contribution matrix C. Theorem 2 shows that the problem of finding desirable classifiers reduces to (when 1,p 2) finding an h such that
||CrAlly CCrllll
g2
32
or equivalently
h hT (CCCDD) hT CT
32
CTT Cuh
82
To find feasible solution, it suffices to find value of h that maximizes the LHS. Because both CD and CJT Cz are positive-semidefintt,,, maximizing the LHS is a known problem with polynomial-tine algorithms; we are maximizing generalized Rayleigh quotient, and the optimal is the eigenvector for the maximum eigenvalue of well-specified function of matrices A and B.
29

---

b) Finding the best such classifier is at least as hard as certifying feasibility of the set of constraints A 2 5 and h Qh 2 0 where Q is diagonal and has both positive and negative eigenvalues.
will focus on the version of the problem where, given observations {(1,, y:) where a is d-dimensional vector and Vi is real-valued label, we aim to find the classifier h that is 3-desirable and minimizes the worst-case error across all data samples, ie., it minimizes
f(h) || Y|
where X is the data matrix and Y the label vector. We make the assumption that C' La is diagonal, i.c., we want to show that our hardness result holds even in the simplest causal graph setting where features do not affect each other. We first prove an intermediate result. Let His be the space of all 3-desirable classifiers.
Lemma 5. Solving the optimization problem: minpeeH f(h) 1 Y at least as hard as checking the feasibility, given any 6 > 0, of a problem of the following problem:
Y 8.8..1 15 XTh,
h QTQ220 0,
where Q' is a diagonal matrix with two distinct eigenvalues X >> 0 and X < O.
Proof. For the given optimization problem, the problem least as hard as deciding for any given 5 > O, whether the optimal solution is 8 or > 8. We can rewrite this as the following feasibility problem:
Given 6, does there exist classifier such that the following conditions hold:
|| h
Y
1o0
S
8,
and
B
||D| 2
huu
v
ga
Note that
| h - 11 88 +
max
x h 31 5
<E[N]
+ | h yil 6 Vie [N]
= -8 8 x 4 ViE [N]
= - y 1.
Y
Now, define ID diag([1|p), 0z(() and Iu = diag(() pp: 11)) Then, for the other constraint we have: bux
19
|/D|| 2
= ||//||| 2
V1 g2
VI
B
82
- hT Iph 2
g2 h" luh (note: 1 ID. 1ul4 lu = lu)
1
h hTQ2Z20 0,
where Q' be the diagonal matrix with entries 1 for features in D, and it all together, we have the following equivalent fcasibility problem:
for features in U. Putting I-
-82
1 1 x x - - and
h TQhh 20 0,
This is at least as hard as solving the feasibility problem on the superset
8 15 X h TQhh 0.
and
(since feasibility on the subset implies feasibility the superset). This concludes the proof.
30

---

According to a classical optimization result, the class of feasibility problems of the form: A 2 b and h J Qh where Q is diagonal but neither positive or negative remi-definite, is NP-hard (see hardness results of this form surveyed in [34]). We do note a small gap here however: while changing X, Y and allows us to generate the entire set of constraints of the form Ar 2 b, Q' cannot be used to generate the set of all diagonal matrices Q because Q' only has two distinct eigenvalues. We technically do not map to the entire NP-hard class of problems of the form x Qx 2 & A 2 b. but we this provides evidence that the problem is likely NP-hard.
Finally, we note that the general consensus in the optimization community is that eigh-dimensiona non-convex optimization problems are considered intractable, and there are no practical/general purpose methods solve them.
D Results & Proofs for the Incomplete Information Setting
D.1 Proof of Theorem
We will complete the proof as follows: first, we will argue that for scenarios (a) and (b), Ch is Gaussian. Then, we will show in Lemma that for Ch Gaussian, Problem (4) is indeed convex program and can be reduced to Problem (5). Finally, we will show in Lemma 7 that for all other scenarios, the problem non-convex.
In scenario (a), when the causal graph G is fully known and there is uncertainty only over the classifier, it is clear that each entry of Ch a linear combination of Gaussian random variables and therefore, Ch is Gaussian. In scenario (b), since the causal graph is bi-partite with all arcs oriented in the same direction, any feature may affect any other feature either directly or not at all. Therefore, entry Ciy is either 0 or w (aig) which is a Gaussian random variable. Since the classifier is fully known, Ch again multi variate Gaussian.
Lemma 6. Under any partially incomplete information model where Ch is multi-variate Gaussian and for cost functions given by Eq. (1), the agent's 's optimization problem to find the optimal effort profile e*, given by (4), is a convex progrum for any 8 < 3/2
Proof. Since the cost functions defined in Eq. (I) are convex, in order to complete the proof, suffices to show that the feasible space of the optimization problem in (4), is convex when Ch is multi-variate Gaussian. Suppose, Ch N(HC,, Ees) for some PCc E R and Eggh E R| This implies,
(Ch) T N (udre, Ecne). This allows us to rewrite the LHS of the probability constraint as follows:
(Ch) E mTAe
a- M
P P(Ch) e 2 = P
VeTech
VeTEcN Ecne
Z a Mone
P
(where Z ~ ~N 1))
Dine
Mehe
Σene
Therefore,
P((Ch)eezal 21-8 &
a P e
2 21-8
Ve T Σcne
mene
+
58
Ve Eone
a More I Ps
(where ps = Tb (6))
V Eche
a Mone - Ps Exne $ 0.
31

---

When d 2' Ps 0 and the above constraint reduces to polyhedral constraint, making the problem trivially convex. On the other hand, note that when 2 Ps < O. Now, since Vea is covariance matrix, it is always symmetric and positive semidefinite and therefore, Zch exists (it is also symmetric and positive semidefinite!). In that case, we can express Ve Eche
T follows:
Eche V
E 1/2211122 cch Ch E (EER e) T e) V VIEE
1| 1/2 e/12.
Now, ΣΣ Eelel is convex function in (because all norms are convex functions). Similarly, Pa C ellz is also a convex function because -Ps > 0. The term a Mcn. e is affine in e and therefore, convex by default. Putting everything together, conclude that Mcs p8 Ve Ecne a convex function in e which makes the constraint:
MCc. ps V Ecne S
convex constraint. This concludes the proof of the lemma.
Lemma 7. Under incomplete information model (3) and general cases of model (2) where the causal graph is not bipartite, the agent's 's optimization problem, given by (4), a non-convex program.
Proof. In order complete this proof, it suffices to provide counter-examples where the program in (4) is non-convex.
Model 3. Consider the simplest possible setting where there can be uncertainty in both the classifier
and the causal graph. Suppose, there is only one feature, i.e., |F] 1. Let w NO0, 1) be random variable that captures the uncertainty in the contribution of the feature (encodes uncertainty in the causal graph) and h (0, 1) the random variable that captures the uncertainty in the classifier weight on the feature. Note that 1. h. We will show that the feasible space given by:
P [[wh)e 2 a] 2-8
is non-convex, which is equivalent to showing that the function f(e) given by:
f(e) = P [(wh)e 2 a]
concave. Below in Figure plot f(e) function one-dimensional effort e. Since there is no closed-form expression for the distribution of the product of two independent standard normal random variables, we obtain empirical estimates for the probability at each using Monte- Carlo simulations. Clearly, f(e) is not concave.
0.20
0.15
0.30
Figure 6: Plot of f(e) with
General Cases of Model with Non-bipertite Graphs. Consider any non-bipartite causal graph. There must exist pair of features and j such that affects indirectly. In that case, the entry Ci of
32

---

the contribution matrix must contain at least one term which is product of multiple independent Gaussian random variables. Therefore, even when the classifier is fully known, by similar argument as Model 3, the optimization problem is again non-convex.
This concludes the proof of the lemma.
D.2
Characterization of Feasibility of Problem 5
Proposition 6. Suppose that Egi is positive definite. Then the oplimization problem (5) is feasible if and only i 4 (- (-1E
1/21/" pex l12). where 4 ( (.) indicates the inverse of the standard normal
CDF
Proof. Recall that the feasible space of the agent's optimization problem in the partially incomplete information case is given by:
MCn e ps | e|12 0.
This feasible space is empty given if we have:
1/2
1/2 e/1 > 0. ell2 > O Ve + min g(e) = a a p6 -112
PCA e
Now consider the convex unconstrained optimization problem: min, g(e). Then,
Ecne
Vg(e) -PCh ps-
1/2 C e
Now there are 2 cases: (e) 0 has solution è: Clearly, è + because the gradient not defined at é = In that case, è satisfies:
Ecrê
P8
JACA-
Ecch
éll2
Now, must be global minimizer of g because g(-) is convex function. We will show that g(è) a:
1 /
g(é) = a - e - Ps
Ecné
a +
ps 1 E|l2
(using the condition from Vg(ê) = 0)
1/2 |//22112 - ps || éll2
= a + p8
Since > 0, the problem is always infeasible for this particular value of ps- Since Eca is positive 1/2 exists, therefore we have:
definite, X-1/2
1/2 pCall2 + 5 --- (-1( pcalla)
Ps = E
Vg(e) = 0 has no solution: This means that either the unique optimal solution is at the point where the gradient does exist, i.e, e O, the solution is unbounded. The first subcase clearly leads to infeasibility as g(0) = a > 0 while the second sub-case leads to non-empty feasible region for Problem (5). We will now try derive conditions on 5 which lead to each subcase.
Suppose that the unique optimal solution is e This means that for any direction d, g(++d) > g()) or equivalently.
a- - - || 1/2
2|I2 > dd + -ps 1 1/2 d|12 > pead V d.
Note that HT d _Te Σー 1/2 d (E MCA)
((=//////00///////// d) < || 1/2 pcx|12- 1/22 1/2 d]la where the
last inequality follows from the Stuchy-Schwartz inequality. In fact, for d' EolucR MCA (which exists
33

---

since Egh is positive definite and hence, invertible), we have equality, But since -ps 1=ch dl12 Mend for all directions d, it must hold for d' well, which implies:
1/2 pca |
- / P8 1
1= d=
which means that Ps |> 1/2 MCM l22 or equivalently, 6 < -- (-1Rish uealla).
ucalla)
Similarly, if the solution is unbounded, there must exist direction d' at 0 such that:
1x1/2 --M ps
d'
a,
or equivalently, -ps cc d' 1l < M.nd'. Using a similar argument as above, we can show that this can happen only when:
6 > x -call))
This concludes the proof the proposition.
D.3 Structure of Optimal Effort Profiles under Weighted ---nrrm Costs
Proposition 7. Under any partially incomplete information setting which leads to the convex optimization problem (5) for the agent, the optimal effort profile et with weighted E--nrrm costs requires investment of effort into more than one feature in the worsl case.
Proof. In order complete the proof, it suffices construct an instance of the problem where the optimal effort profile is not a comner point. Consider setting where |J| = 2, a > 0 and <
Suppose, the features are identical in all respects, i.e., (Hcx)1 = (MCA)2 > 0, Eca = o² 0
o²
and C = C2 = c. Additionally, suppose that μ > -p5a. We first make the following observations:
If e* is not a comer point, it must be symmetric, i.e., ej ez
Since p > 0 and
< 1. must be that e* 2 0 (otherwise, we have infcasibility). 2
Now, there are only two possible corner point solutions: either of the form (e, 0) or (0, In order for either of them to be optimal, the constraint must be active at that point. Solving, obtain:
CO
and Cost
+ P&o
Ā P&T
However, will now construct non-corner point solution (e' e') where the constraint is active and which produces a strictly better objective value. Solving, we obtain:
e'
and Cost
(++ P5
which is strictly smaller than the earlier cost (since Ps < O). This concludes the proof.
D.4 Proof of Theorem
We will use the KKT conditions to obtain the agent's optimal effort profile et. The Lagrangian C(:-) for the above problem is given by:
C(e, A) = ||el|2 + A (a me
|| ellz)
where À is the Lagrange multiplier. We can now write the KKT conditions follows:
e
Eche - pCh = 0,
+ +
-p8-
|el
||2: ell2
ps || ell2 + wene a,
A > 0.
34

---

Since we have convex program, it is sufficient to find pair (e", X*) satisfying the KKT conditions and we can immediately conclude that is an optimal solution to our original problem. Using the first equality above, we infer that the optimal effort e* must be of the following form:
e" = X (k1 1 h2 Ech) M4,
where k
0 and h2
-A 0 (so, the inverse exists). In order to obtain the exact ||
1
expression for ex, need use the other equality condition and solve simultaneously for K1, K2 and X*
The last part of the theorem follows directly by noting that Σca is diagonal matrix. In that case, ( + 12 Ecx) is also a diagonal matrix where the diagonal entry corresponding to feature f is given by 1/(kg + 22 () The final expression follows from simple algebra. This concludes the proof the theorem.
D.5 Scenario where Eeh diagonal matrix
Proposition 8. Suppose G is a bipartite graph with all edges oriented in the same direction; further, suppose the agent only has uncertainty over the weights of the graph (model 2), i.e. En. 0. Then, Ech is diagonal matrix.
Proof. Since G is bipartite graph, the set of nodes (in this case, partitioned into two sets Fout and Fin such that Fin U Fout = F. Fin. O. Fout = and all ares in A are directed from Fout towards Fsn-
set of features) |F] can be
Recall that Mea is the covariance matrix of Ch where uncertainty only over the edge weights of G, it is clear that Eca Cou (Cho). Therefore, in order to show that Ech is a diagonal matrix, it suffices to show that:
Ie and 1l,. However, when there is
fi, F1 # f2, (Cho) (Cho)
ie.. (Cho),, and (Cho),, 12 are independent random variables. Firstly, observe that for any feature Fins must have:
(Cho),
This is because feature has outgoing edges (since f Fin)) and therefore, Cy OT which implies (Cho), = C ho = O. This automatically implies that the covariance of (Cho) with any other random variable is also zero. Therefore, only need to prove that Cov ((Cho) fi (Cho) O when f1, f2 both are Fout. Note that:
(Cho), Shughos and (Cho) =E Ec..hhoof JEF
JEF
Therefore,
Cou (CCho)) Cov
Σ Chuphoot
Σ Clanhhos FeF
FEF
Σ JEF MEF
(ho.r horr) Cou(Crurs Csa.r)
We now argue case by case:
fC ft C 0 because there can be no edges from either fi or fo to f or f' since all of them are nodes in Fout.
S Fout: In this case, Cov(C
f E Fout, I' E Fin: this case, C,. = by the same argument as above. Therefore, the covariance must be 0.
Fouts f Fin: In this case, Cfa.r' which makes the covariance 0.
"f E E Fin: Finally, both f and f' are in Fin. there can be edges from fi and f2 towards / and f'. But those edges are disjoint and therefore, independent which makes the covariance term
This concludes the proof.
35

---

E
Supplementary Proofs
E.1 Computation of the Contribution Matrix C
Proposition 9. Given adjacency matrix A, the contribution matrix of causal graph 9 is given by
[5
C=
A
k==
and therefore can be computed in palynomial time in [F/
The key step complete the proof is show that A captures the influence exerted by feature on feature j through directed path on the graph that is exactly hops long. We will prove by induction.
Proof.
Base case (h: = 0): When = O, there exists no directed path from feature i to feature j unless j. Therefore, all off-diagonal entries are O. The only entries appear on the diagonal because feature i affects itself with a unit positive multiplier. This gives us the identity matrix in [F dimensions which is exactly given by A
General case: Suppose that the induction hypothesis holds for some k > 1. We will now show that also holds for k + 1. Note that:
FF Σ 1==1
A
A
Anj-
Since the induction hypothesis is true, A captures the influence exerted by feature i on feature n through a directed path exactly hops long. Anj represents the direct influence exerted by feature on feature j (in exactly 1 hop). Therefore, the product measures the influence of feature i on feature exerted on a directed path & + hops long. The sum over all features in F captures all such directed paths from i to j. Thus, our induction hypothesis is also true for k + 1.
Finally, to compute C, need to the influences of directed paths of all lengths starting node i and ending in node j. Since G is a directed acyelic graph with [F[ nodes, the length of the maximum directed path from i to is most |F| hops long conservatively |Fl hops long (note that if there are no directed paths of length & from i to j. A O. So, it does not hurt to be conservative). This leads to the final expression of
F
C= 7=>4 A
kmm
To conclude the proof, we need to argue about the time complexity of computing C, given matrix A. Multiplying 2 matrices of size [F] x [F] takes O(FFFs time and need to execute ((F)) such matrix multiplication steps to compute the different powers of A. Therefore, the overall time complexity is polynomial in [Fl.
E.2 Proof of Supporting Result in Proposition 3
We made the following observation in our proof of Proposition 3: Observation. Let X E IR" and M Raxx Define set Y as follows:
Y = ty: 3z E X s.t. y Ma}
When M is full row-rank, set X is convex if and only if set is convex.
We provide a formal proof here. We need to show both directions.
(-) ) Suppose, set X is convex. We need to show that set Y is convex. Let y1,82 E Y such that V1 + y2. Pick any E [0, 1). Then there must exist æι, 22 E X such that y1 = Mxj and y2 = Mx Clearly I1 # z2. Since X is convex set, Ary + (1 A)æz E X. This implies,
Ayi + (1 - A)y2 AMa + (1 (1- 2)M
M (Ax, + (1- \)æ²) EY
36

---

( (=) For the other direction, we assume that set Y is convex and we need to show that set X convex. Pick any two elements 21, 22 x, * I2 and any À [0. Let y1 Mæx and /2 = Mz2. Clearly, y1, 122 E Y (by definition). Note that * y2 (otherwise, we would have MR Maz which implies that 31 - #2 E Nullspace (M). But Nullspace(M)) = 0 as M is full row-rank). Additionally, Ay1 + (1 X)U2 Y since Y is convex set. This implies,
Ar + (1 2)2z AM yı + A)M 1/2 (M exists because rank(M) = n)
M (Ay1 (1 A)U2) E X.
The last part follows from noting that Ay + (1 A)y2 E Y and since M is full row-rank, the pre-image of Ay11 + (1 2)32 must be unique. This concludes both directions the proof.
37


Reviews:
[{"review_id": "9BJb73Uygj", "reviewer": "Reviewer_oibv", "summary": "The authors consider a binary classification with strategic agents. The agents can exert effort to get desired decision. The author also consider a scenario where there are desirable and undesirable features and investigate how the classifier can lead to improving desirable features. \n\nThe authors considers both complete and incomplete information and provide insight on the best response function of the agents.", "questions": "1. In what real world problems, the proposed model can be used?\n\n2. How the design maker should find the optimal classifier? How should we define the optimal classifier? Because we want to have \\beta-desirable outcome, we need to clearly define optimal classifier? \n\n3. In the game theory and economics, there is notion of socially optimality. Why we cannot use this concept instead of Desirable Classfier concept proposed here? \n\n4. How the problem can be extended to non-linear case? \n\n5. What the agents are interdependent (effort of one impact others' utility)", "limitations": "The author have not discussed potential negative societal impact (or I could not find).", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 4, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths: The paper is well written. It is easy to follow and can provide some insight on how strategic classification works.\n\nWeaknesses: \n\n1. The scenario that they consider is very simple. While it is in the context of  machine learning, basically the authors consider a very simple two stage game between decision maker and an agent. The first order condition is used to find the best response. \n\n2. The scenario looks very superficial. A scenario with liner classifier and know causal graph. It is not clear in what real world problem, we can apply this study. \n\n3. In the incomplete information case, still the authors assume the agent knows the distribution over hypothesis space. This still gives a lot of information to agent leading to optimization problem 4.\n\n4. No discussion on how the design maker should find the optimal classifier. The authors discuss that the problem is non-convex for the design maker. But no further insight or algorithm provided for solving that problem. \n\n5. No discussion on how the results can be extended to non-linear case or a scenario where the agents are interdependent.", "was_revised": true, "final_justification": "The authors rebuttal was comprehensive and answered all the questions that I asked them. So I want to increase my score. In particular, they talked about the real world application and social optimality. Other reviewers also want to accept the paper and I agree with them.", "rebuttal": "We thank the reviewer for their comments. Below, we provide detailed responses to the weaknesses identified, followed by answers to the specific questions raised. We look forward to engaging further during the discussion period.\n\n*Weaknesses*\n\n\nW1. We respectfully disagree with the reviewer’s characterization that this is just a simple two-stage game between a decision-maker and an agent in the context of ML. The sequential nature of decision-making in strategic classification makes two-stage games the obvious modeling choice to understand these problems. We clarify that our contribution is not the introduction of a two-stage game model to understand strategic classification – this framework was introduced by Hardt et al (2016). Our main contribution is to study the principal’s problem of incentivizing desirable agent behavior in the context of strategic classification (following the work of Raghavan and Kleinberg (2020)), but under the real-world constraints of causality and uncertainty. We have already provided a detailed breakdown of the major differences of our work with Raghavan and Kleinberg (2020) in Appendix A (Related Work).  \n\nWe clarify that we do not use first order conditions to find the agent’s best response. As demonstrated in our paper, the agent’s decision problem becomes intractable once the agent does not have access to complete information. One of our main results characterizes conditions of partial uncertainty under which the agent problem is still tractable (see Thms 4 and 5 on pages 6 and 7).  \n\nW2. We respectfully disagree that our scenario looks very superficial. Linear classifiers are commonplace across many real-world high-stakes applications due to their simplicity, high degree of interpretability, low training costs and robustness to overfitting; e.g., linear models continue to be used extensively in domains like healthcare (for disease-risk prediction and resource allocation), insurance (for predicting likelihood of claim filing or insurance fraud), and economics. For this specific reason, strategic classification has primarily been studied in literature on linear/binary classifiers (and we adopt the same approach). The question of inducing desirable behavior is also relevant in any real-world context where human beings are “algorithmically scored” and there is scope for strategic behavior – see also Kleinberg and Raghavan (2020) for additional, detailed examples of such settings.  \n\nAs for the known causal graph, we want to clarify that we assume full knowledge only in the complete information setting. In the incomplete information setting, we explicitly allow for agent uncertainty in the weights of the causal graph. The only assumption that we use is that agents always know the causal graph topology fully; this effectively means that the agents know the features and have a rough idea of where edges between features exist. However, note that the most crucial piece of information that agents need in order to make decisions is the overall importance vector of features, given by $Ch$ (it subsumes information about both the classifier and causal graph). Thus, our main theoretical insights would go through even absent the assumption about a fully known graph topology, as long as the agent has some partial information about the importance of individual features. As such, they are, to the best of our knowledge, among the most general assumptions in the strategic classification literature.\n\n\nW3. In the CS and economics literature (specifically (Bayesian) mechanism design), the standard model for agents with incomplete information is priors—probability distributions that capture an agent’s belief over unknown aspects of the environment (Myerson 1981, Kamenica and Gentzkow 2011). We emphasize that there is no distribution over classifiers or causal graphs — the classifier is chosen deterministically by the principal and the causal graph is fixed (by nature). Our prior just reflects the agent’s *belief* about what the deployed classifier and the weights of the causal graph are. Further, the assumption on having priors at the time of deciding how to strategize has been studied in the past in strategic classification (see ``Bayesian Strategic Classification’’ by Cohen et al., 2024) and published in NeurIPS.\n\nW4. We believe that the reviewer means “how to choose the desirable classifier that maximizes accuracy” when they ask “how to choose the optimal classifier”. We clarify that after showing that finding the most accurate desirable classifier is a non-convex optimization problem in the general case, we do provide 2 key ways to circumvent this issue: \n\na) We show that by deciding to incentivize a desirable modification in exactly 1 feature, the principal can make this optimization problem convex and easily tractable (Thm 3). \n\nb) In the general case, we provide a heuristic that encourages searching for the most accurate classifier which cannot put more than a fixed amount of importance on undesirable features (Prop 5 in Appendix C.4). This again makes the search space convex and the optimization problem tractable.  \n\nW5. We argued above why the linear classifier setting is important. Further, we have demonstrated throughout the paper that the problem is non-trivial even for the linear classifier setting with many open questions. Linear classifiers are the first line of attack when it comes to building theoretical models for these settings. Note also that thinking about non-linear classifiers opens a host of other questions about what types of non-linear classifiers we want to focus on, which algorithms are used to produce them etc. The extension to non-linear classifiers is a very interesting direction, but is beyond the scope of the present work.\nIt is indeed interesting to study settings where agents are interdependent and some works have considered this aspect (Hossain et al 2024). However,  studying the interdependent setting meaningfully requires understanding what are the effects of uncertainty, causality, and incentivizing desirable behavior in the independent setting. Otherwise, it is unclear which conclusions are a byproduct of externalities on the agents and which conclusions are truly a byproduct of uncertainty and causality. Lastly, the independent setting is, in fact, the standard setting in strategic classification (Hardt et al. 2016, Ahmadi et al. 2021, 2022, Bechavod et al. 2021, Braverman and Garg 2020, Cohen et al. 2024, Chen et al. 2020, Dong et al. 2018, Ghalme et al. 2023, Harris et al. 2021, Hu et al. 2019, Kleinberg and Raghavan 2020, Miller et al. 2020, Milli et al. 2019, Shavit et al. 2020, Zhang et al. 2022). \n\n*Questions*\n \nQ1. We have already touched upon the aspect of real-world applications of our model. To reiterate, in any real-world setting where human beings are algorithmically scored (in the words of Kleinberg and Raghavan (2020)) and there is scope of strategic human behavior, the question of how to incentivize desirable behavior becomes critical; e.g., in the context of college admissions, a candidate can invest effort in broadly desirable activities, like taking AP classes in high school. Alternatively, they might engage in undesirable behaviors—like signing up for multiple extracurricular activities without meaningful participation in an attempt to appear more well-rounded. Incentivizing the first kind of behavior is a meaningful pursuit in this setting. \n\nQ2. In traditional strategic classification, the optimal classifier is defined as the classifier in the entire hypothesis class which minimizes classification error accounting for the agents’ ability to best-respond; this is also known as the Stackelberg equilibrium classifier. In our setting, the “optimal” classifier would be defined as the classifier which minimizes classification error among all classifiers in the hypothesis class which are guaranteed to induce $\\beta$-desirable effort from rational agents. We use this exact definition in Appendix C.5  Of course, in general, depending on the specific application, the principal may adopt different objective functions to reflect their own notion of what constitutes the \"optimal\" classifier.\n\tPertaining to the question of finding the “optimal“ classifier, we emphasize that we do provide insights about how to find it in the complete information setting. Kindly refer to our response to W4 above. \n\nQ3. Social optimality (aka, maximum social welfare) and $\\beta$-desirability are complementary notions, and not directly exchangeable. Social optimality makes statements about maximizing the sum of the utilities of the agents and does not directly prevent gaming nor agents modifying undesirable features. Consider the following example, inspired by Kleinberg and Raghavan (2020): the learner, here a university professor, deploys a scoring rule that must decide which weight to put on homework assignments versus in-class exams. Each agent can decide to cheat or to study. Cheating has a very low cost, why studying has a significant cost. Further, the causal graph is such that an agent can only cheat on assignments, but not on in-class exams. In this case, the classifier that provides social optimality in that it maximizes agents’ utilities is the one that puts all the weight on assignments, and pushes all students to cheat. In turn, social optimality is obtained, but at the cost of the student “gaming” the system and investing undesirable effort. Arguably, in our example above, a professor may be more interested in preventing cheating than optimizing social welfare (which could be, in this example, seen as a form of grade inflation when students are cheating).\n\tAn interesting direction for future work is to understand the trade-offs between these two complementary notions, one which is utilitarian (social optimality) and one that is normative (desirability). We will add this discussion in the Discussion (Section 6).\n\n\nQ4 & Q5. Please see our responses to W5 above."}, {"review_id": "ZL6EGKEEby", "reviewer": "Reviewer_Mw5J", "summary": "This paper addresses strategic classification under causal interdependencies and incomplete information. It introduces the concept of β-desirable effort profiles and analyzes how rational agents respond to deployed classifiers under different information assumptions. The authors consider both complete and incomplete knowledge settings and provide a combination of theoretical results and simulations based on cardiovascular disease prediction. The model incorporates causal graphs, agent cost functions, and effort optimization, providing insight into classifier design that incentivizes desirable (rather than merely effective) changes.", "questions": "1. Could the authors contrast this work more clearly with the literature on causal algorithmic recourse (e.g., [Mothilal et al., 2020], [Karimi et al., 2021])? The lack of mention is surprising given the shared setting.\n2. Are there cases where the incentive structure leads to undesirable gaming behavior under partial information? A small example would be helpful.\n3. The β-desirability conditions are mathematically clean — could the authors comment on the extent to which principals can reasonably verify them in practice?\n4. Line 90: is it that the features are desirable/undesirable, or changes to/interventions upon those features?\n5. How would the framework handle heterogeneous populations (e.g., different groups with different priors or cost sensitivities)?", "limitations": "No — while section 6 does speak to the methodology's limitations, more explicit discussing regarding the practicality of assuming full causal graph knowledge and cost function specifications, as well as risks tied to fairness, misspecification, and strategic disparity would be welcome.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "### Strengths\n- The problem is important and well-motivated: incentivizing desirable feature change under strategic manipulation is a key issue in responsible ML.\n- Strong theoretical depth with clean characterizations (e.g., β-desirability conditions).\n- Good mix of theory and simulation; the cardiovascular disease application is relevant and realistic.\n- Reasonable modeling assumptions around cost functions, agent behavior, and effort optimization.\n- Good literature coverage (in Appendix) but also in main body when contrasting against most similar work.\n\n### Weaknesses\n- At times, the paper is dense and difficult to read — many sections could benefit from simplification or intuitive summarization of key ideas. E.g., several concepts (e.g., β-desirability, agent best response, contribution matrix) take effort to parse and might deter less technical readers.\n- While the related work is thorough, it lacks direct contrast with causal algorithmic recourse literature — a striking omission given the similarity in goals. Esp. since those works operate on models beyond the linear variants studied here\n- The empirical section is clean, but could benefit from a broader discussion of fairness and real-world risks.", "was_revised": true, "final_justification": "The rebuttal satisfactorily addressed key concerns, including clarifying modeling assumptions, the role of desirability, and connections to related work. While some empirical limitations and assumptions (e.g., linearity, Gaussian priors) remain, they are clearly acknowledged and framed as future directions. The paper makes a strong theoretical contribution to strategic ML under causal and informational constraints, and I believe its strengths justify a positive recommendation.", "rebuttal": "We thank the reviewer for the careful read of our paper, their positive feedback about the strengths of our work, and their insightful comments. \n\nWe also apologize if parts of the paper feel difficult to read. We will provide intuitive explanations/visuals for some of the key concepts (like contribution matrix and desirability definitions); we already have these visuals in the public, extended version of our paper, but cannot add them to the rebuttal because of the formatting restrictions. We will elaborate upon the fairness aspects of our work in Section 6 (see Q5). \n\nBelow we provide answers to the reviewer’s questions:\n\n\nQ1. Thank you for pointing this out! First, recourse is indeed directly related, and we will add a discussion of recourse in the related work. From a mathematical standpoint, strategic classification and algorithmic recourse can be seen as flip sides of each other: in recourse, the learner tells the agent what actions to take (but the agents may decide to take a different action unless properly incentivized) while in strategic classification, the agents decide on their own actions based on the classifier.\nWe note, however, several differences between recourse and strategic classification:\n\na) From a practical point of view, recourse requires providing a recommended action to each agent who obtains a negative decision, and is still less common in practice than releasing a single, often not fully transparent, model. Strategic classification, especially with incomplete information, allows us to capture such practical scenarios.\n\nb) The addition of the $\\beta$-desirability constraint is novel. As we see in many places throughout the paper, this constraint makes the problem significantly more difficult, leading to non-convexities. We expect these issues to also arise when adding desirability to the algorithmic recourse literature, since the optimization problems solved by both fields are similar, and we think that the inclusion of desirability in the recourse literature is an exciting direction for future work.\n\nc) To the above point, much of the recourse literature aims to find a low-cost path between an agent's current features and features that lead to positive classification. Importantly, much of the literature does not think specifically about whether that path involves gaming or modifying undesirable features. [KFG 2023] in fact show that standard counterfactual recourse algorithms often lead to undesirable outcomes such as gaming the system. This is an important limitation: as agents game the classifier, the classifier loses in accuracy and robustness, and must be modified to compensate for this accuracy loss, reducing the effectiveness of the recourse. This includes \\emph{causal} algorithmic recourse, such as [Karimi et al. 2021], where the causality is typically used to ensure accuracy of the recourse by taking into account how different features affect each other, whereas previous work that effectively assumed independence of features and could mis-estimate how proposed recourse would translate into feature changes. In much of this literature, however, causality is not introduced to prevent gaming vs improvement or understand desirability.\n\n\n[KFG 2023] König, Gunnar, Timo Freiesleben, and Moritz Grosse-Wentrup. \"Improvement-focused causal recourse (ICR).\" In Proceedings of the AAAI Conference on Artificial Intelligence, vol. 37, no. 10, pp. 11847-11855. 2023.\n\n\nQ2. Yes, there can indeed be scenarios with partial uncertainty where agents can have incentives to engage in undesirable behavior. In general, if undesirable features are not costly/easy to modify, and if there is a belief that such undesirable features may be prevalent in the classifier, then agents may prefer modifying these undesirable features. Note that this is a realistic assumption in real systems: credit scores rely significantly on credit usage, but credit usage can be improved by opening dummy credit card accounts without lowering actual spending or improving re-payments. In turn in some cases, it may not be possible to induce $\\beta$-desirability due to the incomplete information; the probability with which such an event occurs depends on the prior (see Proposition 6 in the Appendix). \n\nWe are not sure if that is exactly what the reviewer had in mind for this question, but we are very interested in engaging further during the discussion period. \n\n\nQ3. We thank the reviewer for appreciating the definition of $\\beta$-desirability! We note that the $\\beta$-desirability condition is on the agent’s exogenous effort profile $e$. Unfortunately, the principal does not observe $e$ directly, they only observe the change in feature values $\\Delta x(e)$ because of effort $e$. Assuming the principal has complete information about the causal graph, they can infer $e$ by observing $\\Delta x$ only when the contribution matrix $C$ is full rank (and hence invertible). But, in general, $C$ is not full rank because many different effort profiles can amount to the same final feature vector — this implies that in most cases, the principal cannot verify the beta-desirability condition. \n\t\n\nHowever, in our setting, the principal need not directly verify $\\beta$-desirability, so long as the agents are rational. Our classifiers incentivize desirable behavior. This can be seen as a parallel to incentive-compatibility in classical mechanism design where specific actions can be incentivized without seeing an agent's type. \n\t\nThis is a useful point to get across to the reader, and we will add this clarification in Section 6.\n\nQ4. The reviewer is absolutely right that we should have clarified the language in Line 90. What we mean is that investing effort to modify those features directly is desirable or undesirable. We actually clarify this in lines 91-96 through the health example. We thank the reviewer for the insightful observation. \n\nQ5. Our framework is indeed capable of handling heterogeneous populations with different costs/priors. The analysis of the agent problems for different groups goes through unchanged. The principal problem changes in the sense that the goal is now to pick a classifier that satisfies $\\beta$-desirability simultaneously for all groups (we will have $k$ desirability constraints if there are $k$ different groups). However, note that all of our main insights still go through unchanged. For example, if the problem is hard to solve with one constraint, it is definitely harder with multiple constraints. Also, if the feasible space with one group is convex (like, when $|D| = 1$ and $p<= 3$), it will still be convex with multiple groups (since all the group-wise constraints are individually convex and intersection of convex sets is convex).  \n\nHaving multiple groups with different priors, however, has major fairness implications as identified by Bechavod et al (2022). When groups have different priors or different abilities to strategize, this disparately affects their ability to best respond (and in our setting, obtain $\\beta$-desirable effort profiles). We already highlighted the heterogeneous population setting as an exciting future direction, but we will add the above discussion in Section 6 too."}, {"review_id": "uR44ssDI2I", "reviewer": "Reviewer_sN5p", "summary": "The paper proposes a causal framework for strategic classification in which agents invest effort to modify features that influence others, and a principal wants to steer that effort toward desirable attributes. It introduces $\\beta$-desirability to quantify the share of effort on preferred features, characterizes agents’ optimal effort under $\\ell_p$ costs, and derives sufficient conditions on linear classifiers that guarantee desirable behavior under full information. The authors show finding such classifiers is generally non-convex but becomes convex when one feature is targeted, and they analyze partial-information settings, providing closed-form responses and numerical experiments on cardiovascular-risk data to validate their theory.", "questions": "- Your model presumes agents know the entire causal-graph topology. How would the guarantees change if this topology were uncertain or misspecified?\n\n- How does the proposed method scale as the number of features $d$ grows large?\n\n- The empirical study uses only one eight-feature CVD graph. Can you provide additional experiments on public strategic-behaviour datasets (e.g., credit scoring, résumé screening) to demonstrate external validity?", "limitations": "Yes", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "## Strengths\n\n* Well-structured paper.  Clear separation of complete vs. incomplete information.\n  \n* Combines causal modelling with strategic classification under uncertainty—areas that had largely been studied separately.\n  \n* Good intuitive explanations. After each theorem the authors add discussion.\n  \n* All main results are formally stated with complete assumptions and full proofs in the appendix.\n  \n\n## Weaknesses\n\n* **Causal Structure**:  The entire DAG topology is assumed common knowledge; in practice, agents seldom know the full graph structure.\n  \n* **Feature Dynamics**: The framework relies on linear causal relations encoded in a contribution matrix $C$, whereas real-world effects are often non-linear or state-dependent.\n  \n* **Finite Sample**: The paper does not address how estimation error in the DAG would affect the results.\n  \n* **$\\beta$-Desirable**: just only large amount of $\\beta$-desirable provied gurantee to use desirable faetures instead of undesireable feature\n  \n* **Classifier Family**: Analysis is limited to linear classifiers with a fixed threshold, while non-linear models (trees, neural nets) dominate many real applications.\n  \n* **Agent information**: Agents’ beliefs over $h$ and edge weights are assumed Gaussian, yet empirical priors are often multi-modal or heavy-tailed.\n  \n* **Non-convex design problem.** The desirable-classifier search is non-convex except when $|D| = 1$ and $p \\le 3$; the paper provides only a heuristic with no guarantees in the general case.\n  \n* **Agent optimisation hardness.** Under full uncertainty the best-response program is non-convex (they show even the simple 2-feature toy becomes non-concave) , but no algorithmic remedy is proposed.\n  \n* **Algorithmic Recourse**: Despite close ties, the paper does not reference the algorithmic recourse literature.\n  \n* **Simulation**: The only experiment uses one expert-elicited CVD DAG with eight features; no cross-domain validation, no real behavioural data, and no statistical uncertainty.", "was_revised": true, "final_justification": "**Clarified in rebuttal:**\n\n* **Graph knowledge:** Agents need beliefs over **$Ch$** (importance vector), not full DAG; main insights persist.\n* **$\\beta$ feasibility:** Achievable $\\beta$ is **instance-dependent**; as $\\beta \\to 1$ feasibility shrinks (clear example provided).\n* **Assumptions:** Will explicitly justify linear models/Gaussian priors and explain why broader regimes are intractable.\n* **Recourse link & clarity:** Added positioning vs. recourse; plan to streamline theorem statements and add intuition.\n\n**Key limitations (remain):**\n\n* **Empirics:** Single 8-feature CVD DAG; no cross-domain baselines or stress tests.\n* **Design guarantees:** Principal’s problem is **non-convex**; only heuristics, no performance guarantees.\n* **Scope:** Linear $C$, linear classifiers, Gaussian beliefs; limited guidance on scalability/misspecification.\n\n\nThe primary remaining concern is empirical evaluation. The authors argue that the CVD study is the only suitable dataset, but they do not assess their method on standard synthetic benchmarks or public datasets with ground-truth structural equations commonly used in the causal community. During the rebuttal, they chose not to add such tests. This materially weakens the empirical case and, accordingly, lowers my overall recommendation.", "rebuttal": "We thank the reviewer for the careful read of our paper, their positive feedback about the strengths of our work, and their insightful comments. Below, we reply to the weaknesses and reviewers’ questions:\n\n*Weaknesses*\n\nW1. Kindly refer to Q1 below. \n\nW2. We highlight that much of the strategic classification literature that models causal effects only considers linear causal relationships (which is the same approach we adopt here) (Kleinberg and Raghavan (2020), Shavit et al (2020)). Our main goal in this work is to take a first step towards studying the problem of incentivizing desirable agent behavior when agents have uncertainty not only in the classifier, but also in the causal graph. We have already seen that the problem is already non-trivial under the linearity assumption, which hints at the fact that it is likely to be intractable under general non-linear causal structures. \nWe do agree with the reviewer that there are real-world instances where causal relationships are non-linear. This is an exciting avenue of future research. Another avenue is to understand how more general causal graphs can be linearized and at what cost to accuracy. We will include this short discussion in Section 6.\n \nW3. There are several ways an agent can possibly learn the environment. One is peer-learning—agents may interact with other agents which can help them learn C over time, similarly to (Bechavod et al. 2022). From a technical point of view, agents do not need to learn $C$ directly—all their decisions depend only on the vector $Ch$ - the agent learning problem is that of learning a $n$-dimensional vector. Under i.i.d., noisy samples of effort profiles and resulting features from peers, this is well-understood and follows standard concentration inequalities—we did not include those to keep the paper to the point. Under non-noisy, perfect samples, we can learn $Ch$ fully.\n\nW4. We are not exactly sure we understand the statement. We would be happy to address it during the discussion if the reviewer could clarify their comment.\n\nW5. Linear classifiers are commonplace across many real-world high-stakes applications due to their *simplicity*, *high degree of interpretability*, *low training costs* and *robustness to overfitting*. Ex: linear models continue to be used extensively in domains like healthcare (for disease-risk prediction and resource allocation), insurance (for predicting likelihood of claim filing or insurance fraud), and economics. For this reason, strategic classification has primarily been studied in literature on linear/binary classifiers (and we adopt the same approach). Inducing desirable behavior is also relevant in any real-world context where humans are “algorithmically scored” and there is scope for strategic behavior—see Kleinberg and Raghavan (2020) for additional, detailed examples of such settings.  \n\nW6. While unimodal priors do not necessarily arise in *every* setting, they are still natural and relevant to many. In bank loans or credit scoring applications, agents typically have a sense of which features are relevant, but may have some uncertainty exactly on how much each feature matters. E.g., agents understand that lowering credit usage or re-paying loans most consistently will improve their score. Such settings are typically well approximated by unimodal distributions. Beyond strategic classification, Gaussian priors are used commonly in the ML, CS, and economics literature to model incomplete information for agents (see Elzayn et al at EC 2019, Kong et al at AAAI 2020, Acharya et al. at SATML 2023 to only name a few examples).\n\nSecond, we want to refer the reviewer to Jagadeesan et. al (2021) which establishes alternative microfoundations for strategic classification that also uses a Gaussian noise model. Other recent papers in the context of strategic classification have also used similar Gaussian assumptions (e.g., Braveman and Garg at FORC 2020, Avasarala et al. at AIES 2025).\n\nW7. Our main contribution is to understand how easy/difficult the principal’s problem of incentivizing desirable agent behavior is, when the agent has different levels of access to information. Providing algorithms with provable guarantees is a key future direction that we are actively pursuing. \nWe want to highlight some key aspects of classifier design under uncertainty. We have seen that even under partial uncertainty, characterizing agent effort profiles in closed form is difficult. So, the intuition is to use the structural property of the optimal effort profile (Thm 5 - agents under uncertainty invest effort in features with high expected importance and low uncertainty) to design good approximation algorithms for finding the optimal classifier. Finally, greedy algorithms that pick and optimize over one desirable feature at a time do seem to be a natural choice for the principal. \n\nW8. Under general uncertainty (incomplete info over classifier + causal graph), we show that the agent problem itself is not tractable. Τhis suggests that the agent may attempt to best-respond approximately, rather than optimally. Modeling such approximate best-responses opens up new avenues for future research, particularly in understanding the behavioral dynamics and outcomes when agents operate under bounded rationality or limited information. \n\nW9. As the reviewer notes, recourse is directly related, and we will add a discussion of recourse in the related work. From a mathematical standpoint, strategic classification and algorithmic recourse can be seen as flip sides of each other: in recourse, the learner tells the agent what actions to take (but the agents may decide to take a different action unless properly incentivized) while in strategic classification, the agents decide on their own actions based on the classifier.\nWe note, however, several differences between recourse and strategic classification:\n\na) Practically, recourse requires providing a recommended action to each agent who obtains a negative decision, and is still less common in practice than releasing a single, often not fully transparent, model. Strategic classification, with incomplete information, allows us to capture such practical scenarios.\n\nb) The addition of the beta-desirability is novel. As we show, this constraint makes the problem significantly more difficult, leading to non-convexities. We expect these issues to also arise when adding desirability to the algorithmic recourse literature, since the optimization problems solved by both fields are similar, and we think that the inclusion of desirability in the recourse literature is an exciting direction for future work.\n\nc) Much of the recourse literature aims to find a low-cost path between an agent's current features and features that lead to positive classification. Importantly, much of the literature does not think specifically about whether that path involves gaming or modifying undesirable features. König et al. \"Improvement-focused causal recourse (ICR).\"’s paper at AAAI 2023 show that standard counterfactual recourse algorithms often lead to undesirable outcomes such as gaming the system, an important limitation: as agents game the classifier, the classifier loses in accuracy and robustness, and must be modified to compensate for this accuracy loss, reducing the effectiveness of the recourse. This includes causal algorithmic recourse, such as [Karimi et al. 2021], where the causality is typically used to ensure accuracy of the recourse by taking into account how different features affect each other, whereas previous work that effectively assumed independence of features and could mis-estimate how proposed recourse would translate into feature changes. In much of this literature, however, causality is not introduced to prevent gaming vs improvement or understand desirability.\n\n\nW10. Kindly refer to the Q3 below. \n   \n\n*Questions*\n\nQ1. Recall, we show in Theorem 4 that the agent’s optimization problem under uncertainty is tractable when their priors over the importance vector $Ch$ is gaussian — an important contribution of our paper involves microfounding this using more primitive models of incomplete information (priors over the classifier and the graph weights while fully knowing the topology). However, note that the most crucial piece of information that agents need in order to make decisions is the overall importance vector of features, given by $Ch$ (it subsumes information about both the classifier and causal graph). Therefore, our main theoretical insights would go through even absent the assumption about fully knowing the graph topology, as long as the agent has some partial information about the overall importance of individual features.   \n\nQ2. As the number of features $d$ grows, the agent’s cognitive load for best-responding increases (as they now have to consider much larger contribution matrices). We touch upon this aspect in detail in Section 6 Discussion. However, all of our theoretical results go through irrespective of the value of $d$. Note that all non-convexity results remain; the size of all vectors used in the desirability constraint hence the complexity of the problem in the convex case scale linearly in $d$. \n\nQ3. We want to highlight that there are some challenges with the publicly available datasets highlighted by the reviewer. Note that a key requirement for conducting numerical experiments in our setting is the availability of the corresponding causal graph. However, the data contained in these public datasets is purely observational and does not contain interventions or counterfactuals which can be used to recover the true causal graph. The issue with using such data is that causal graphs cannot be point identified and resulting graphs are often severely misaligned with reality, in particular increasing the risk of societal harm due to misinformed decisions. The primary reason we use the CVD-risk study is that the causal graph for that study is publicly available."}, {"review_id": "KKRzKTH4rs", "reviewer": "Reviewer_RF8Z", "summary": "This paper proposes a new formulation of SC based on a causal perspective. Specifically, the causal effects of investing efforts are captured by a contribution matrix $C$ and the decision maker publishes a linear classifier $h$. The cost is formulated as the weighted $L_p$ norm of the effort. The paper first characterized the optimal effort profiles when agents best respond under a complete information setting, and pointed out that space of desired classifiers is non-convex/convex when the set of desirable features has cardinality $>1$/$1$. Finally, the paper discussed two settings of incomplete information and gave explicit expressions of the optimal effort profile under when the cost is $l_2$.", "questions": "1. Are there efficient algorithms to learn an optimal classifier to incentivize desirable efforts in your problem setting, especially when there is incomplete information?\n2. Can you discuss with learning the contribution matrix $C$ in practice?", "limitations": "yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "> Strengths\n- The problem formulation is reasonable and the theoretical results seem to be solid.\n- The consideration of incomplete information is interesting.\n- The writing is clear.\n\n> Weaknesses\n- The formulation of the causal structure is still similar to [23] although [23] did not mention \"causal\". The causal effects are still characterized by the multiplication of $C$ and $e$. But the causal effects in reality can be more complex (e.g., non-linear)\n- Getting the contribution matrix $C$ may be difficult in practice, so it may be worthwhile adding such a discussion on the practical usage.\n- Some highly related works are not mentioned. For example, [1] discussed long-term genuine improvement in SC settings, while [2] discussed the externalities of SC.\n\n[1] Xie, T., Tan, X., & Zhang, X. (2024, October). Algorithmic decision-making under agents with persistent improvement. In Proceedings of the AAAI/ACM Conference on AI, Ethics, and Society (Vol. 7, pp. 1672-1683).\n\n[2] Hossain S, Micha E, Chen Y, et al. Strategic classification with externalities[J]. arXiv preprint arXiv:2410.08032, 2024.", "was_revised": true, "final_justification": "- Thanks for pointing me to Appendix A. The discussion of this work and [23] makes sense. I still think his work has similar settings to [23], but it is slightly more general, and this extension may be non-trivial. \n\n- For the related work, I did not mean to say your work is similar to those, but just hope most works closely related are referred. \n\n- I encourage the authors to add more discussions on algorithm design.\n\nOverall, I think the paper has merit and will retain the positive score.", "rebuttal": "We thank the reviewer for the careful read of our paper, their positive feedback about the strengths of our work, and their insightful comments. Below, we reply to the weaknesses and questions noted by the reviewer:\n\n*Weaknesses*\n\nW1. We want to highlight that much of the strategic classification literature that models causal effects only considers linear causal relationships (which is the same approach we adopt here) (Kleinberg and Raghavan (2020), Shavit et al (2020)). Our main goal in this work is to take a first step towards studying the problem of incentivizing desirable agent behavior when agents have uncertainty not only in the classifier, but also in the causal graph. Linear causal graphs are the first natural point of attack for understanding the effects of causality and incentivizing certain types of behavior in strategic classification; the reason being that when it comes time to generalize to non-linear settings, we will be able to disentangle the effects of (non)-linearity in the causal structure from the conclusions. Additionally, we have already seen that the problem is already non-trivial under the linearity assumption, which hints at the fact that it is likely to be intractable under general non-linear causal structures. However, we do agree with the reviewer that there are real-world instances where causal relationships are complex/non-linear. Considering non-linear causal relationships could be an exciting avenue for future research.\n\nWe agree that Kleinberg and Raghavan [23] also consider causal relationships between features. We have highlighted in Appendix A (Related Work) that our work differs from [23] in the following main aspects: \n\na) We consider more general cost functions and show that the nature of the cost function significantly affects the best response effort profile and consequently, the principal’s problem of designing desirable classifiers.\n\nb) We consider incomplete information where the agent can have uncertainty in both the classifier and causal graph. [23] does not consider uncertainty at all.  \n\nc) In our work, we introduce a general and flexible notion of desirability of effort parametrized by $\\beta$: we say a profile is desirable if the total effort on desirable features is at least a $\\beta$-fraction of the total effort. This is in sharp contrast to [23] where desirability of an effort profile is pre-determined by the principal. \n\nW2. Please refer to the response to Q2 below. \n\nW3. We provide a summary of how our work differs from the two works referenced by the reviewer: \n\nWhile the high-level setting introduced in Xie et al (2024) is also about improvement of agents, we highlight some key differences: i) firstly, their main goal is to understand the temporal aspects of agent behavior (where change in behavior materializes slowly over a long period of time), while we try to understand how agents best-respond to a classifier under incomplete information—our settings and goals are therefore orthogonal—, ii) our work considers causality in features, introducing inter-dependencies across features, but Xie et al (2024) operates in a simpler independent feature setting, iii) in their work, the principal has a fixed desirable vector ‘d’ and all agent behaviors are measured with respect to d (alignment <q,d>)---this is in sharp contrast to our work where we introduce a general, more flexible concept of beta-desirability that can evaluate a wider range of human behavior more meaningfully, iv) finally, because of their simple evaluation rule, Xie et al (2024) have a single-variable decision problem for the principal (designing the threshold value that separates gaming from improvement). However, our work captures most real-world strategic classification settings where the principal actually tries to design a high-dimensional classifier in order to incentivize “desirable behavior”. We can add a short discussion about this in the revised version of the paper.\n\nThe main focus of Hossain et. al (2024) is fundamentally different from ours, as it centers on externalities arising from interdependence between agents. Beyond the difference in the main question, their tools and modeling are completely different—there is no notion of causality or improvement, and they use game-theoretic modeling and solution concepts. We are happy to add a discussion of this paper. \n\n\n*Questions*\n\nQ1. Our main contribution in this paper is to understand how easy/difficult the principal’s problem of incentivizing desirable agent behavior is, when the agent has different levels of access to information; in some sense, we take an information theoretic point-of-view, rather than a prescriptive one.  \n\nSince the problem is generally non-convex, we have thought about efficient algorithm design by providing some heuristics (see e.g., Appendix C.4). We find it useful to highlight some key aspects of efficient algorithm design in this setting: \n\ni) first, desirability does not come for free; in particular, there is a trade-off between \\beta-desirability and accuracy. So, the first step for algorithm design is to characterize the pareto-front of this trade-off. This would provide us with a baseline (best achievable accuracy under $\\beta$-desirability, given $\\beta$). \n\nii) We have seen that even under partial uncertainty, characterizing agent effort profiles in closed form is difficult. So, the intuition is to use the structural property of the optimal effort profile (Thm 5 - agents under uncertainty invest effort in features with high expected importance and low uncertainty) to design good approximation algorithms for finding the optimal classifier. \n\niii) Finally, greedy algorithms do seem to be a natural choice for the principal when it comes to classifier design. We will add this discussion on Section 6 Discussion.\n\n\nQ2. Thanks for this very insightful question. There are several ways an agent can possibly learn the environment. One way could be through peer-learning—agents may interact with other agents which can help them learn $C$ over time—, similarly to (Bechavod et al. 2022). From a technical point of view, note that agents do not need to learn $C$ directly—all their decisions depend only on the vector $Ch$. In turn, the agent learning problem is that of learning a $d$-dimensional vector. Under i.i.d., noisy samples of effort profiles and resulting features from peers, this is a well-understood problem that follows standard concentration inequalities—we did not include those to keep the paper to the point. Under non-noisy, perfect samples, we can learn $Ch$ fully. These are great questions and will be very important for future work."}]

Author rebuttal:

Meta-review: The paper studies strategic behavior by agents who can modify their features in settings where binary decisions are made.  Such agents may wish to invest effort modify their features to obtain a better outcome for themselves.  Such investment may also provide benefit to the principal. The resulting game has complex behavior. The paper analyzes this behavior, extracts insights, and presents a numerical example.

Strengths
- Interesting and novel setting
- Reasonable model
- Theory is strong 

Weakness
- Reviewers were mixed on the relevance to practice. The paper does contain a numerical study of cardiovascular disease (e.g., Mw5J writes "the cardiovascular disease application is relevant and realistic.") but reviewers felt that a tighter connection to reality would help the paper 

- Reviewers oibv and sN5 expressed concerns about real-world details not present in the model (e.g., the classifiers are linear). On the one hand, as I see it, the paper studies a parsimonious model in which (we hope) the core interesting dynamics of reality are also present. While some real-world complications are not modeled, this enables core insights to be extracted. This might not be possible in a model weighed down by more detail. On the other hand, if the model could handle more aspects of the real world, that would be better.

- Reviewers expressed concerns that the paper is dense.  I did not find this to be an extreme problem but I see where they are coming from.  The page limit at NeurIPS can present challenges to a paper like this.

- Some concerns about gaps in the literature review that can be addressed in a final version.

I am recommending acceptance because I feel the strengths outweight the weaknesses.
Decision: Accept (poster)