Incentivizing Desirable Effort Profiles in Strategic Classification: The Role of Causality and Uncertainty

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:

Weaknesses

W1. 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.

We 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:

a) 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.

b) We consider incomplete information where the agent can have uncertainty in both the classifier and causal graph. [23] does not consider uncertainty at all.

c) 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.

W2. Please refer to the response to Q2 below.

W3. We provide a summary of how our work differs from the two works referenced by the reviewer:

While 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.

The 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.

Questions

Q1. 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.

Since 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:

i) 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$).

ii) 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.

iii) 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.

Q2. 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.

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:

Weaknesses

W1. Kindly refer to Q1 below.

W2. 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. We 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.

W3. 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.

W4. 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.

W5. 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.

W6. 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).

Second, 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).

W7. 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. We 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.

W8. 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.

W9. 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. We note, however, several differences between recourse and strategic classification:

a) 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.

b) 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.

c) 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.

W10. Kindly refer to the Q3 below.

Questions

Q1. 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.

Q2. 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$.

Q3. 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.

We thank the reviewer for their thoughtful response and for giving us a chance to answer their questions.

Q1. [Clarification on $\beta$-desirability] The reviewer is correct; higher $\beta$ indicates a higher degree of desirability. This makes desirability harder to satisfy, reducing the size of the space of desirable classifiers. When $\beta = 1$, the requirement becomes extreme: it requires that the entire effort is put on desirable features, with none on undesirable features. This is mostly impossible—this needs the RHS of our expression to be 0, which only happens when agent has no benefit to modify any undesirable feature.

A natural way to upper-bound $\beta$ is to find the limiting value of $\beta$ beyond which the desirability constraint is infeasible. This gives us an instance-specific bound—such bounds will depend on the causal graph. As mentioned above, $\beta = 1$ can be reached when$(C h)_{U} = 0$. This can be achieved, for example, when all features are independent ($C = I_d$), by setting classifier weights of all undesirable features = 0.

Now, consider the following example: there are 2 features, feature 1 (undesirable) causally affects feature 2 (desirable). Suppose the edge weight is 1. In this case, we can show that when searching over classifiers $h \geq 0$, the best achievable $\beta$ is $\frac{1}{\sqrt{2}} = 0.707$ (for agents with unweighted $\ell_2$-costs). Proof: For this graph, $C = \begin{bmatrix}1 & 1 \\\ 0 & 1 \end{bmatrix}$. The desirability constraint is: $h_2 \geq \frac{\beta}{\sqrt{1-\beta^2}} (h_1 + h_2)$ where $h_1, h_2 \geq 0$. Clearly, when $\frac{\beta}{\sqrt{1-\beta^2}} > 1 \iff \beta > \frac{1}{\sqrt{2}}$, no feasible non-trivial classifier $h$ exists.

We hope that these examples drive the point that the best achievable $\beta$ depends on the graph characteristics.

Q2. [Role of Simplifying Assumptions] Thank you for recognizing and appreciating that our contribution is primarily aimed at advancing the theory of strategic classification. We fully agree with your point that in a theory paper, it is important to convey the challenges that arise in a general setting so that readers understand the value of the assumptions and what it adds to the analysis in terms of tractability. We will add more concrete discussions about the assumptions in the final version. We thank you for pointing this out to improve the broad appeal and readability of our work.

Q3. [Partial Knowledge of Causal Graph] There are 2 parts to this question. Firstly, our framework can seamlessly handle the scenario where there are errors in the agent’s partial information pertaining to the graph; this incorrect prior will just be replaced in optimization problem (4) (see next paragraph). The agent’s prior is meant to model their belief, which may or may not match the ground truth. None of our results depend on whether agents have a correct prior about the environment or not, so long as the principal can infer said prior.

That being said, an agent having an erroneous prior might make it more difficult to elicit desirable behavior---for example, if an agent believes that investing in undesirable features is cheap and can have a significant impact on other features, there may not be a way for the learner to steer the agent away from undesirable effort. This would be seen in a reduction of the achievable beta at the specific, instance level.

Q4. [Experiments and Alternative datasets] We received an email from NeurIPS on 27 July, with instructions for the discussion period. Quoting: “For authors, please refrain from submitting images in your rebuttal with any “tricks”.....For reviewers/ACs/SACs, please do not expect the authors to submit updated results with images or any type of rich media. Instead, please discuss the current merits of the paper and clarify any misunderstanding based on textual communications.”

We interpreted this email to mean that submitting additional results is not advised since conveying new results often requires uploading a pdf document or using images (ways to circumvent the character limit). We were also advised against submitting external URLs for anonymity issues.

Q5. [Balance between theory and empirics] We agree that cross-validating our numerical results on multiple different settings is only going to bolster our paper. One of our goals in the last response was to illustrate some of the real challenges we faced while looking to obtain datasets/causal graphs for our setting.

That being said, we note that contributions in the area of strategic classification have been largely theoretical, and one major goal of our work was to propose new frameworks and paradigms that help take the theory one step closer to reality (by incorporating causality and uncertainty). We understand that there is still a gap between theory and practice, but we believe our contribution helps close this gap and actually sets the tone for more empirical work.

We thank the reviewer for the careful read of our paper, their positive feedback about the strengths of our work, and their insightful comments.

We 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).

Below we provide answers to the reviewer’s questions:

Q1. 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. We note, however, several differences between recourse and strategic classification:

a) 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.

b) 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.

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. [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 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.

[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.

Q2. 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).

We 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.

Q3. 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.

However, 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.

This is a useful point to get across to the reader, and we will add this clarification in Section 6.

Q4. 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.

Q5. 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).

Having 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.

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.

Weaknesses

W1. 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).

We 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).

W2. 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.

As 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.

W3. 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.

W4. 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:

a) 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).

b) 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.

W5. 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. It 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).

Questions

Q1. 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.

Q2. 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. Pertaining 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.

Q3. 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). An 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).

Q4 & Q5. Please see our responses to W5 above.