Learning under Imitative Strategic Behavior with Unforeseeable Outcomes
Authors: Tian Xie
Zhiqun Zuo
Mohammad Mahdi Khalili
Xueru Zhang
Venue: Accepted by TMLR ()

Abstract: Machine learning systems have been widely used to make decisions about individuals who may best respond and behave strategically to receive favorable outcomes, e.g., they may genuinely improve the true labels or manipulate observable features directly to game the system without changing labels. Although both behaviors have been studied (often as two separate problems) in the literature, most works assume individuals can (i) perfectly foresee the outcomes of their behaviors when they best respond; (ii) change their features arbitrarily as long as it is affordable, and the costs they need to pay are deterministic functions of feature changes. In this paper, we consider a different setting and focus on imitative strategic behaviors with unforeseeable outcomes, i.e., individuals manipulate/improve by imitating the features of those with positive labels, but the induced feature changes are unforeseeable.  We first propose a Stackelberg game to model the interplay between individuals and the decision-maker, under which we examine how the decision-maker's ability to anticipate individual behavior affects its objective function and the individual's best response. We show that the objective difference between the two can be decomposed into three interpretable terms, with each representing the decision-maker's preference for a certain behavior. By exploring the roles of each term, we further illustrate how a decision-maker with adjusted preferences can simultaneously disincentivize manipulation, incentivize improvement, and promote fairness.

Published in Transactions on Machine Learning Research (10/2024)
Learning under Imitative Strategic Behavior with Unforesee- able Outcomes
Tian Xie
rie. 1de.1390@suueel
Deportment of Computer Science and Engineering the Olio State Universily
Zhiqun Zuo
zuo. 167 edu
Department Computer Science and Engineering the Ohio State University
Mohammad Mahdi Khalili
khaliti, 1 170osu edu
Department of Computer Science and Engineering the Ohio State University
Xueru Zhang
shang. 128070osu. edu
Department of Computer Science and Engineering the Olio State Universily
Reviewed on OpenReview: https: // openreview. net/ net/ forum? id= 82bNZGNNZa
Abstract
Machine learning systems have been widely used to make decisions about individuals who may behave strategically to receive favorable outcomes, c.g., they may genuinely improve the true labels manipulate observable features directly to game the system without chang- ing labels. Although both behaviors have been studied (often as two separate problems) in the literature, most works assume individuals can (i) perfectly foresee the outcomes of their behaviors when they best respond; (ii) change their features arbitrarily as long as it affordable, and the costs they need to pay are deterministic functions of feature changes. In this paper, we consider a different setting and foeus on imiiaative strategic behaviors with unforeseeable outcomes, i.e. individuuls manipulate/ /imprrive by imitating the features of those with positive labels, but the induced feature changes unforeseeable. We first pro- posc Stackelberg game to model the interplay between individuals and the decision-maken under which we examine how the decision-maker's ability to anticipate individual behavior affects its objective function and the individual's best response. We show that the objective difference between the two can be decomposed into three interpretable terms, with each preference for certain behavior. By exploring the roles
representing the decision-makee of each term, we theoretically illustrate how decision-maker with adjusted preferences may simultaneously disincentivize manipulation, incentivize improvement, and promote fairness. Such theoretical results provide a guideline for decision-malke makers to inform better and socially responsible decisions in practice.
1 Introduction
Individuals subject to algorithmic decisions often adapt their behaviors strategically to the decision rule to receive a desirable outcome. As machine learning is increasingly used to make decisions about humans, there has been a growing interest to develop learning methods that explicitly consider the stralegic behavior of human agents. A line research known as strategic classification studies this problem, in which individuals can modify their fcatures costs to receive favorable predictions. Depending on whether such feature changes are to improve the actual labels genuinely (i.e., improvement) or game the algorithms maliciously (i.e., manipulation), existing works have largely focused learning classifiers robust. against manipulation

---

Published in Transactions on Machine Learning Research (10/2024)
Hardt et al.
2016a or designing incentive mechanisms to encourage improvement (Kleinberg & Raghavan
2020 Bechavod et al. 2022 Xie et al. 2024). A few studies (Miller et al. 2020 Shavit et al. 2020 Horowitz
& Rosenfeld 2023) also consider the presence of both manipulation and improvement, where they exploit
the causal structures of features and use structural causal models to capture the impacts of feature changes
on labels.
To model the interplay between individuals and decision-maker, most existing works adopt (or extend basod on) a Sluckelbery game proposed by Hardt et al. (2016a), i.e., the deeision-maker publishes its policy, following which individuals best respond to determine the modified features. However, these models (implicitly) rely on the following two assumptions that could make them unsuitable for certain applications: (i) individuals can perfectly foresee the outcomes of their behaviors when they best respond; (ii) individuals can change their features arbitrarily at costs, which are modeled as deterministic functions of the feature.
In other words, existing studies assune individuals know their exact feature values before and after strategic behavior. Thus, the cost. can be computed precisely based on the feature changes (e.g., using functions such as fy-norm distance). However, these may not hold in many important applications.
Consider example of college admission, where the students' exam scores are treated as features in admission decisions. To get admitted, students may increase their scores by either cheating exams (manipulation) or working hard (improvement). Here (i) individuals do not know the exact values of their original features (unrealized scores) and the modified features (actual scores received in an exam) when they best respond, but they have a good idea of what those score distributions would be like from their past experience; (fi) the cost of manipulation/ camiipllation/mmpvvementt imposter to take the exam and the cost of such behavior is more or less fixed). As the original feature was never realized, we cannot compute the feature change precisely and measure the cost. based on it. Therefore, the existing models do not fit for these applications.
/improvement not a function of feature change (e.g., students may cheat by hiring an
Motivated by the above (more examples are also given in App. B.2 this paper studies strategic classification with unforeseeable outcomes. We first propose a novel Stackelbery game to model the interactions between individuals and the decision-maker. Compared to most existing models (Jagadcesan et al.] 2021 Levanon & Rosenfeld 2022). ) ours is a probabilistic frumework that models the outcomes and costs of strategic behavior
as random variables. Indeed, this framework is inspired by the models proposed in Zhang et al.) (2022):
Liu et al. 22000), which only considered either strategic manipulation (Zhang et al. 2022 or improvement [Liu et al. 2020). In contrast, our model significantly extends their works by considering both manipulation and improvement behaviors, investigating agents' choices between them, and providing theoretical results and practical guideline for socially responsible decision making in the new setting. Importantly, we focus on imitative stratogic behavior where individuals manipulate/ ciniiullac//mproee /improve by imitating the features of those with positive labels, due to the following:
It is inspired by imitative learning behavior in social learning, whereby new behaviors are acquired by copying social models' behavior. It has been well-supported by literature in psychology and social science (Bandura, 1962 1978). Recent works (Heidari et. al. 2019 Raab & Liui 2021 in ML. also model individuals' behaviors as mmnitating/replicatee the profiles of their social models to study the impacts of fairness interventions.
Docision-makers can detect easy-to- masy-la-manipulate features (Bechavod et al. 2021 and stop using them when making decisions, so individuals can barcly manipulate their features by themselves without changing labels. A better option for them is to mimic others' profiles. Such imitation- manip- ulative behavior is very common in the real world (e.g., cheating, identity theft) and even becomes increasingly worrying during recent years!]
Additionally, our model considers practical scenarios by permitting manipulation to be detected and im- provement to be failed at certain probabilities, as evidenced in auditing (Estornell et al. 2021 and social
LAs COVID-19 hit the world, candidates more commonly permitted to take exams/assesssuuee or online assessments of companies) remotely. Although many institutions diligent in designing novel challenges to prevent candidates from directly finding the answers on the internet, the remote nature makes it casier to hire qualified imposters to take the assessments instead of them. Talha 2024 illustrated how students can let. others take the GRE instead of them when the test is permitted be taken at home.
(e.g.. GRE, TOEFL,
2

---

Published in Transactions on Machine Learning Research (10/2024)
A provides more related work and differences with existing models are discussed in App. B.1
learning Bandura 1962).
App.
Under this model, we first study the impacts of the decision maker's ability to anticipate individual behavior. Simílar to Zhang et al. (2022) we consider two types of decision-makers: non-strategic and strategic. We say a decision-man makerr (and its policy) is strategic if it has the ability to anticipate strategic behavior and accounts for this determining the decision policies, while a non-strategic decision-males ignores strategic behavior in determining its policies. Importantly, we find that the difference between the decision-maker's learning objectives under two settings can be decomposed into three interpretable terms, with each term representing the docision-maker's preference for certain behavior. By exploring the roles of cach term on the decision policy and the resulting individual's best response, we further show that strategic decision- maker with adjusted preferences (i.e., changing the weight of each term in the learning objective) can disincentivize manipulation while incentivizing improvement behavior.
We also consider settings where the strategic individuals come from different social groups and explore the impacts of adjusting preferences on algorithmic fairness. We show that the optimal policy under adjusted preferences may result in faircr outcomes than non-strategic policy and original strategic policy without ad- justment. Moreover, such fairness promotion can be atlained simullaneously with the goal of disincentivizing manipulation. Our contributions are summarized as follows:
1. We propose a probabilistic model to capture both improvement and manipulation; and establish a novel Stackelberg game to model the interplay between individuals and decision-maker. The individual's best response and decision-maker's (non-)strateggic policies are characterized (Sec. 2
2. We show the objective difference between non-strategic and strategic policies can be decomposed into three terms, each representing the decision-maker's preference for certain behavior (Sec.
3. We study how adjusting the decision-maker's preferences can affect the optimal policy and its fairness property, as well as the resulting individual's best response (Sec. 4 We also illustrate how the decision- maker can adjust preferences to disincentivize manipulation, incentivize improvement and promote fair- ness in practice (Sec. and App. B.5)
4. We conduct experiments on both synthetic and real data to validate the theoretical findings (Sec. 5
2 Problem Formulation
Consider a group of individuals subject to some ML decisions. Each individual has an observable feature X E R. and a hidden label Y E {0, 1} indicating its qualification state ("0" being unqualified and "1" being qualified) P Let a = Pr(Y = 1) be the population's qualification rate, and Pxly (x/1), Pxly (z)0) be the feature distributions of qualified and unqualified individuals, respectively. A decision- maker makes binary decisions D E 10 ("O' being reject and "1" being accept) about individuals based on a threshold policy with acceptance threshold 0 R: T(x) (1)x 1(x 2 0). To receive positive decisions, individuals with information of policy π may behave strategically by either manipulating their features or improving the actual qualifications Formally, let M E {0, 1} denote individual's action, with M = 1 being manipulation and M = 0 being improvement.
Outcomes of strategic behavior. Both manipulation and improvement result in the shifts of feature distribution. Specifically, for individuals who choose manépulate, we assume they manipulate by "steal- ing" the features of those qualified (Zhang et al., 2022), e.g., students cheat on exams by hiring qualified imposters. Moreover,
assume the decision-maker can identify the manipulation behavior with probability E [0, 1] (Estornell et al.) 2021). Individuals, once getting caught manipulating, will be rejected directly. For
those who decide to improve, they work hard to imitate the features of those qualified (Bandura) 1962 Raabl
"Similar to prior work (Zhang et al. 2022 Liu et al. 2 we present our model in one-dimensional feature space. Note that our model and results are applicable to high dimensional space, in which individusls imitate and change all features whole based the joint conditional distribution Pxiy regardless of the dimension of X. The custs be regarded the of indiviual's 's cffort to change leatures all dimensions..
We assumic all unqualihed individuals who stay the docision-making system either mampulate improve, In other words, they already have sufficiently large initial utility by staying the system and trying to be qualified. We discuss the
details in App. H.3
3

---

Published in Transactions on Machine Learning Research (10/2024)
& Liu 2021 Heidari et al. 2019 With probability E [0, 1], they improve the label successfully (overall a increases) and the features conform the distribution Pxly(11) (z|1); with probability 1 - q. they slightly improve the features but fail to change the labels, and the improved features conform a new distribution ((().. Throughout the paper, we make the following assumption on feature distributions.
Assumption 2.1. Px (x]1), (x))) (x) are contivuous; distribulion puirs (P P((x)) and ('(x) and (xll
Pxj) (a(0)) satisfy the strict monotone likelihood rotio property, i.c. Pxir(100) increasing in R.
P(()
are
Assumption 2.1 is relatively mild and has been widely used (e.g., [Tiirtsis et al. 2019 Zhang et al. 2020b)
It can be satisfied by wide range of distributions (e.g., exponential, Gaussian) and the real data (c.g., FICO data used in Sec. 5). It. implies that an individual is more likely to be qualified as leature value increases. Meanwhile, compared to the unqualified individuals, the individuals who improve but fail also tend to have higher feature values. Individuals have good knowledge of their true qualifications by observing their peers or previous individuals who received positive decisions Raab & Liu (2021), and only unqualified individuals have incentives take action Dong al. (2018) since (x|1 is always the best attainable outcome (as manipulation and improvement only bring additional cost but no benefit to qualified individuals).
2.1 Individual's best response.
An individual incurs random cost CM 2 0 when manipulating the features ZZang et al. 2022). while incurring random cost C₁ 2 O when improving the qualifications (Liu et al.) 2020). The realiza realizations of these random costs are known to individuals when determining their action M; while the decision-maker only knows the cost distributions. Thus, the best response that the decision-maker expects from individuals is the probability patppplaattoommmoeeeeennt Figure illustrates the strategic interaction between them.
New population resulting from individuals taking different actions
Adinit or reject
Feature distribution and labels change
Feature distribution changes while labels remein
Yes
No
Take action
Being detected
Being rejected
Decision maker
Succeed
Yes-
Improve
Manipulate
Publiish threshold
Qualified
Unqualified
Original
population
Figure 1: Illustration of the strategic interaction
Formally, given a policy (④Φ) = 1(x 2 8) with threshold 8, an individual chooses to manipulate only if the expected utility attained under manipulation UM outweighs the utility under improvement U7))). from the acceptance, and 0 from the rejection. Given that cach
Suppose an individual benefits w individual only knows his/her label y E (0, and the conditional feature distributions Pxjy but not the exact values of the feature x, the expected utilities (!) and (0) can be computed the expected benefit minus the cost of action, as given below.
(m) Fx (0 Fxiy (0 E(1 Fx (011)) -CM
(0) Exiy (010) q Fxir (0(1) - (1 q) Fl F(( C1
4

---

Published in Transactions on Machine Learning Research (10/2024)
where (x)1 (x)r(2)0), (x) are cumulative density function (CDF) of (x)r (xjr(2)0), (x). respectively. Given the threshold 0, the decision-maker can anticipate the probability that unqualified individual chooses to manipulate as (0) = Pr (Um( > Ur(0)), which can further be written as follows (derivations and more explanation details in App. D.1
Po) = Pr ((1-g) q)- (F) (F) Fx]r - c(1 (((1-Fxxee Fxir 2 CM - -c1)
(1)
The above formulation captures the imitative strategic behavior with unforeseeable outcomes (e.g., college admission example in Sec. 1]: individuals best respond based on feature distributions but not the realizations, and the imitation costs (egg. hiring an imposter) for individuals from the same group follow the same distribution (Liu et al.) 2020), as opposed to being a function of feature changes. equation | above can further be written based on CDF of Cм - C₁, ie., the difference between manipulation and improvement costs. We make the following assumption on its PDF.
Assumption 2.2. The PDF PCn-Ci (x) is continuous with (c) > 0 for x E (-c,1 -0)-
Assumption 2.2 is mild only to ensure the manipulation is possible under all thresholds 0. Under the Assumption, we can study the impact of acceptance threshold 0 on manipulation probability PM(().
Thcorem 2.3 (Manipulation Probability). Under Assumption 2.2. (0) continuous and satisfies the following: (i) If q + 2 1, then (0) striclly increases. (ti) If q + < 1, then Pws(0) first increases and then decreases, thereby cristing unique mazimizer 0max. Moreover, marimizer fmaz increases in q and e.
Thm. 2.3 shows that an individual's best response highly depends on the success rate of improvement q and the identification rate of manipulation 6. When q + c 2 (i.e., improvement can succeed or/and manipulation is detected with high probability), individuals are more likely to manipulate as 0 increases. Note that although individuals are generally more likely to benefit from improvement than manipulation, as 0 increases to the maximum (ie., when the decision-maker barely admits anyone), the 'net benefit' of improvement compared to manipulation will finally diminish to 0 because both actions are uscless. Thus, more individuals tend to manipulate under larger 0, making (o)(O) strictly increasing and reaching the maximum. When q t < 1, more individuals are incentivized to improve as the threshold gets farther away from 0maz. This is because the manipulation in this case incurs a higher benefit than improvement at Omaz. As the threshold increases/ decreases from mez to the minimum/ /maximum (i.e., the docision-make either admits almost, everyone or one), the 'net benefit. of manipulation compared to improvement decreases to 0 or -. Thus, (!) decreases as 0 increases decreases from Omaz.
2.2 Decision-makers optimal policy
Suppose the miision-maaer receives benefit u (resp. penalty uu) when accepting a qualified (resp. unqual- ified) individual, then the decision-maker aims to find an optimal policy that maximizes its expected utility E E)), where utility is R(1, u, R) u, R(O, 1) R(0, 0) 0.
As mentioned in Sec. ! we consider strategic and non-strategic decision makers. Because the former can anticipate individual's strategic behavior while the latter cannot, their learning objectives E[R(D, Y)] are different. As result, their respective optimal policies are also different.
Non-strategic optimal policy. Without accounting for strategic behavior, the non-strategic decision- maker's learning objective (TT) under policy x is given by:
(()) = / (uxX w(1 (0l1-a)PP -ul
(x))) dr
(2)
Under Assumption 2.1 it has been shown in Zhang et al. (2020b) that the optimal non-strategic policy that
maximizes (T)) is threshold policy with threshold 0- satisfying
Pxjy (0'1100'1) 1-a
Pxix (0
Strategic optimal policy. Given cost and feature distributions, strategic decision-maker can anticipate individual's 's best response (equation I and incorporate it in determining its optimal policy. Under
5

---

Published in Transactions on Machine Learning Research (10/2024)
threshold policy T2²) = (z 2 0), the objective UTt)) can be written function of 8, i.c.,
U(0) a + - (1 Pv)(0)a)) (1 -1-PAy Ex(x((11)) - u(1 - a) (a1 -c) PM - -1- (xx
+ (1 - PM (0)) (1 -1--8 21 - ( (()))
(3)
The policy that maximizes the above objective function (() is the strategic optimal policy. We denote the corresponding optimal threshold as 0" Compared to non-strategic policy, U()) also depends q, e, Par (0) and is rather complicated. Nonetheless, we will show in Sec. 3 that U(O) can be justified and decomposed into several interpretable terms.
3
Decomposition of the Objective Difference
In Sec. 2.2 we derived the learning objective functions of both strategic and non-strategic decision- makers (expocted utilitics U and Ù). Next, explore how the individual's choice of improvement or manipulation affects decision-maker's utility. Define (0) = (0) (0) as the objective difference between strategic and non-strategic decksion-makers, we have:
2 = u(1 - a) (01(0)-02(0) - x2(0)= os(())
(4)
where
(0) (1 (-)) 9- (1 Fxir 1 FxIr
(2 = (1 - Pas (0)) (1 (1-9)) g) (Fx]r (010) - F' (0)
(0( =
- (1- - Fxjy (010))
As shown in equation 4 the objective difference + can be decomposed into three terms Φ1, 02, Φ3. It turns out that each term is interpretable and indicates the impact of certain type of individual behavior on the decision-maker's utility. We discuss these in detail as follows.
1. Benefit from the successful improvement Φ1: additional benefil the decision-maker gains due to the successful improvement of individuals (as the successful improvement causes label change). In the college admission example, di stands for the utility gain caused by students studying hard to be qualified.
2. Loss from the failed improvement Φ2: additional loss the failure to improve; this occurs because individuals who fail to improve only experience feature distribution shifts from Px|x(x100) to pd (xx) but labels remain. In the college admission example, Φ2 stands for the utility loss caused by students who seem to try but fail to be qualified.
suffers due the individuals'
3. Loss from the manipulation Φs: additional loss the decision-maker suffers due to the successful manipulation of individuals; this occurs because individuals who manipulate successfully only change (x(0) to (x]( but the labels remain unqualified. In the college admission example, Φ3 stands for the utility loss caused by students who cheat/hire imposters.
Note that in Zhang et al. [002]], the objective difference ((0) has only one term corresponding to the additional loss caused by strategic manipulation. Because our model further considers improvement behavior, the impact of an individual's 's strategic behavior on the docision-maket 's utility gets more complicated. We have illustrated above that in addition to the loss from manipulation Φs, the improvement behavior also affects decision-maker"s utility. Importantly, such an effect can be either positive (if the improvement is succossful) or negative (if the improvement fails).
The decomposition of the objective difference (()) highlights the connections between three types of policies: 1) non-strategic policy without considering individual's behavior; 2) strategic policy studied in Zhang et al. (2022) that only considers manipulation, 3) strategic policy studied in this paper that considers both ma- nipulation and improvement. Specifically, by removing Φi, $2, da (resp. Ø2) from the objective function (0), the strategic policy studied in this paper would reduce to the non-strategic policy (resp. strategic policy studied in ZZhang et al. (2022)) ). Based on this observation, we regard d1, d2 Φ3 each as the decision- maker's preference to certain type of individual behavior, and define a general strategic meeiisonn-mkaer with adjusted preferences.

---

Published in Transactions on Machine Learning Research (10/2024)
3.1 Strategic Dacision-maker with adjusted preferences
We consider general strategic decision-makers who find the optimal decision policy by maximizing ((0) ((0, A1, 22, ka) with
$(0, k1, k2 kis) = k1 01 - 22 x2(0) R3 (3)
(5)
where kn, ki, k3 ences of the decision-maker. We give some examples below:
weight parameters; different combinations of weights correspond to different prefer-
1. Original strategic decision-maker: the with kn = l2 k3 u(1 a) whose learning objective function U follows equation it considers both improvement and manipulation.
2. Improovement-encourrggggg decision-maker: the one with b > 0 and k2 K3 it only considers strategic improvement and only values the improvement benefit while ignoring the loss caused by the failure of improvement.
3. Manipulation-proot decision-maker: the one with ka > 0 and kn k2 0; it only concerned with strategic manipulation, and the goal is to prevent manipulation.
4. Improvement-pree docision-maker: the one with l2 > 0 and h kz improvement but. the goal is to avoid loss caused by the failed improvement.
0; it only considers
The above examples show that decksion-maker, by changing the weights ky kz, k3 could find a policy that encourages certain types of individual behavior (as compared to the original policy 0*). Although the decision-maker can impact an individual's behavior by adjusting its preferences via kg k2 k3, we emphasize that the actual utility it receives from the strategic individuals is always determined by U()) given in equation 3. Indeed, we can regard the framework with adjusted weights (equation as a regularization method. We discuss this in more detail in App. B.4
4 Impacts of Adjusting Preferences
Next, we investigate the impacts of adjusting preferences. We aim to understand how a decision-maker can adjust preferences (i.e., changing k,, k2 k3) to affect the optimal policy (Sec. 4.1 and fairness property (Soc. 4.3,, as well as the resulting individual's best response (Scc.
4.1 Preferences shift the optimal threshold
We will start with the original strategic decision-maker (with k = b2 k u(1 - a))) whose objective function follows equation and then investigate how adjusting preferences could affect the decision-maker's optimal policy.
Complex nature of original strategic decision-maker Unlike the non-strategic optimal policy, the analytical solution of strategic optimal policy that maximizes equation is not easy to find. In fact, the utility function (0) of the original strategic decision-maker is highly complex, and the optimal strategic threshold 6" may change significantly as a, Fx CM, Cr,e,q vary. In App. C.2 we demonstrate the complexity of (0), which may change drastically as a, 6,6, vary. Although we cannot find the strategic optimal threshold precisely, we may still explore the impacts the drecision-maker" anticipation of strategic behavior on its policy (by comparing the strategic threshold 0* with the nan-sirategic 0*), as stated Thm. below.
Theorem 4.1 (Comparison of strategic and non-strategic policy). If ming (M)(0) S 0.5, then there crists @ T 1) such that 4q 2 T. the strategic optimal 0* is always lower than the non-strutegic 0+
Thm. 4.1 identifies a condition under which the strategic policy over-accepls individuals compared to the non-strategic one. Specifically, ming (0) < 0.5 ensures that there exist policies under which the ma- jority of individuals prefer improvement over manipulation. Intuitively, under this condition, a strategic decision-maker by lowering the threshold (from Ø*) may encourage more individuals to improve. Because q is sufficiently large, more improvement brings more benefit. to the mecision-maker.
7

---

Published in Transactions on Machine Learning Research (10/2024)
0.6
PM curve
0.5
PM(0*) )
0.5
Increase Kg
0
(kz)
0.4
increase
PM
(K(1)
PM
0.4
0.3
Pm curve
0.3
PM
0.2
PM(0")
0.2
-4
-2
2
4
-2
2
0
Figure 2: Illustration of scenario 1 (left) and scenario 2 (right) in Thm. 4.5 adjusting preferences decreases
manipulation probability Par(O).
Optimal threshold under adjusted preferences. Despite the intricate nature of (0), the optimal strategic threshold may be shifled by adjusting the decision-maker" preferences, i.e. changing the weights k1, k2, k3 assigned to Φ1, 62, d3 in equation 5 Next, we examine how the optimal threshold can be affected compared to the original strategic threshold by adjusting the decision-maker's preferences. Denote 0" (k₃) as the strategic optimal threshold attained by adjusting weight k,, {1, of the original objective function (0).. The results are summarized in Table [ Specifically, the threshold gets lower as k increases (Prop. 4.2 Adjusting 22 or 3a may result in the optimal threshold moving toward both directions, but we identify sufficient conditions when adjusting lyg ky pushes the optimal threshold to move toward one direction (Prop.
4.3 and 4.4
Table 1: The impact of adjusted preferences on 8 (k;) compared to the original stratogic threshold #*
Adjusted weight
Preference
Threshold shift
Increase kı Encourage improvement
(k1) 0"
Increase kg
Discourage improvement
(*2k) $ l"
Increase lig
Discourage manipulation
0r (*(aa) $
Proposition 4.2. Increasing kn results in lower optimal threshold 0 (k1) < 0-. Moreover, when kn is sufficiently large, (k1) < f"
Proposition 4.3. When a S 0.5 (the majorily of the population is unqualified), increasing ko results in a higher optimal threshold 0" (k2) 0* Moreover, when ka is sufficienlly large, 0 0*22) > Ō- Proposition 4.4. For any feature distribution Pxly, there exists an E (0,1) such that whenever 2 E, increasing K3 results in lower optimal threshold 0 (*kk)) <
Prop. 4.2 to reveal that adjusting preferences may lead to predictable changes of optimal strategic thresholds under certain conditions. So far we have shown how the optimal threshold can be shifted as the decision maker's preferences change. Next, we explore the impacts of threshold shifts on individuals' behaviors and show how decision-male with adjusted preferences can (dis)incentivize manipulation and influence fairness.
4.2
Preferences as (dis)incentives for manipulation
In Thm. 2.3 explored the impacts of threshold 0 on individuals' best responses Py) Combined with our knowledge of the relationship between adjusted preferences and policy (Sec. 4.1]. we can further analyze how adjusting preferences affect individuals' responses. Next, we illustrate how a decision-maker may disincentivize manipulation (or equivalently, incentivize improvement) by adjusting its preferences.
Thcorem 4.5 (Preferences serve as inietinnc Compared to the original strategic policy 8", decision- makers can adjust preferences disincentivize manipulation (i.e., Par(8) decreases) under certain scenarios. Specifically,
8

---

Published in Transactions on Machine Learning Research (10/2024)
1. When either of the following is satisfied, and the decision-maker adjusts preferences by increasing ky
( _
1-
(0) cc221:
(8).
Pi
1- -
2. When both of the followings are satisfied, and the decision- maker adjusts preferences by increasing kz:
Px 1- and Pax(0') Fc
()) gettr < and a < 0.5;
(ti).
P((
1-9-6
Moreover, when kn (for scenario 1) 22 (for scenario 2) are sufficiently large, adjusting preferences also disincentivize the manipulation compared to the non-strategic policy 0"
Thm. 4.5 identifies conditions under which decision-maker can disincentivize manipulation directly by adjusting its preferences. The condition q+ e determines whether the best response Pw is strictly (x
increasing or single-peakedd (Thm. 2.3 the condition (T(0)) $ - implies that 6 is lower/ than Omaz in Thm. 2.3 In Fig. 2 we illustrate Thm. where the left (resp. right) plot corresponds to scenario (resp. scenario 2). Because increasing h1 (resp. k2) results in lower (resp. higher) threshold than l*, the resulting manipulation probability PM is lower for both scenarios. The detailed experimental setup and more illustrations are in App.
4.3 Preferences shape algorithmic fairness
The threshold shifts under adjusted preferences further allow to compare these policies against certain fairness measure. In this section, we consider strategic individuals from two social groups Go. Go distinguished
by some protected attribute S E {a. (e.g., race, gender). Similar to Zhang et al. (2019 2020b 2022). we assume the protected attributes are observable and the decision-maker uses group-dependent threshold policy [x( = 1(x 2 0z) to make decisions about Ge, E {a, 6}. The optimal threshold for each group can be found by maximizing the utility associated with that group: maxg, E[R(D, (T){(D))SS=.. s].
Fairness measure. We consider class of group fairness notions that can be represented in the following form ZZang et al. 2020a Zhang & Liu 2021):
Ex~ (Ta (X)] = Ex Pg [X)]
where PC is some probability distribution over X associated with fairness metric C. For instance, under oqual opportunity (EqOpt) fairness (Hardt al. 2016b). P. PEqupt (x) (xlrs(a|L,s)) under demographic
parity (DP) fairness (Barocas al., 2019). P (x) Pxis(rls).
For threshold policy with thresholds (0a, 0b), we mcasure the unfairness as pg [1 2 0.)] - Px Z
0.]]| Define the advantaged group as the group with larger Ex~pe[1(X [1(X 2 0:)] under non-strategic optimal policy 02, i.e. the group with the larger true positive rate (resp. positive rate) under EqOpt (resp. DP) fairness, and the other group as disadvantaged group.
Mitigate unfairness with adjusted preferences. Next, compare the unfairness of different policies and illustrate that fecision-makee with adjusted preferences may result in fairer outcomes, as compared to both the original strategic and the non-strategic policy.
Theorem 4.6 (Promote fairness while disincentivizing manipulation). Without loss of generality, let Ga be the advantaged group and Go disadvantaged. A strategic decision-maker con always simultaneously disincen- livize manipulation and promole jairness in any of the following scenarios:
1. When condition 1.(1) or (ii in Thm. 4.5 holds for both groups, and the decision-maker adjusts the preferences by increasing kn for both groups
2. When condition 2i( and 2. (ii) in Thm. preferences by increasing k2 for both groups.
4.5 hold for both groups and the decision-maker adjusts the
3. When condition (i) or 1.(0i) holds for Ga, condition (1 and 2. (bi) hold for Go, and the ceatision-makes adjusts preferences by increasing kn for Ga and ko for Go-
9

---

Published in Transactions on Machine Learning Research (10/2024)
Corollary 4.7. If none of the three scenarios in Thm. 4.6 holds, adjusting preferences is not guaranteed to promole fairness and disincenlivize manipulation simullaneously
Thm. 4.6 identifies all scenarios under which a decision-maker can simultaneously promote fairness and disincentivize manipulation by simply adjusting k2. Otherwise, it is not guaranteed that both objectives can be achieved at the same time, as stated in Corollary 4.7
A practical guideline for socially responsible decisions. The theoretical results in Thm. 4.5 give con- ditions under which the trrision-make can adjust preferences to disincentivize manipulation and encourage improvement, while the ones in Thm. 4.6 further sheds light on how the decision-maker can make explainable and socially responsible decisions under the unforeseeable strategic individual behavior: instead of adding separate regularizers to prevent manipulation or promote fairness, we show that the decision-maker may adjust their preferences in an interpretable way to disincentivize manipulation, incentivize improvement and promote fairness the same time.
However, applying our theoretical results in practice needs access to several model parameters such g,e, CMr, Cr, F' which can be estimated empirically. In App. B.5 we assume the decision-maker needs to estimate all paramcters except the fcature distribution for the qualified individuals Pxly (x|1) and the quali- fication rate a. Then we provide an estimation procedure for the parameters using controlled experiments on an experimental population P With the model parameters, the decision-maker can derive accurate ex- pressions for the decompositions 1 Ø2, d3 and verify whether any condition in Thm. 4.5 and 4.6 holds. This enables the decision-mant maker to design a policy by adjusting preferences. For example, if estimated probabili- ties q é 2 1, then the decision-maker may train policy with increased k to disincentivize manipulation behavior (by Thm. 4.5 case 1).
5 Experiments
We conduct experiments on both synthetic Gaussian data and FICO score data Hardt et al. 2016b
FICO data (Hardt et al., 2016b). FICO scores are widely used in the US to predict people's 's credit worthiness. We use the preprocessed dataset containing the CDF of scores [x]s(a)s), qualification likelihoods (r]xs(1|22, (1)221))))) s), and qualification rates as for four racial groups (Caucasian, African American, Hispanic, Asian). All scores are normalized to [0, 1]. Similar to Zhang et al. (2022), we use these estimate the conditional feature distributions (x]ys s) using beta distribution Beta Beta(ays: bys). The results are shown in Fig. We assume the improved feature distribution (xx) Beta (# bractbba)) and Ca C2 N(00 0.25) for all groups, under which Assumption 2.2 and 2.1 are satisfied (see Fig. 8). We also considered other feature/co /cosure//ostttaae distributions and observed similar results. Note that for each group 8, the mecision-maker finds its own optimal threshold (0; or (ks) or Ō;) by maximizing the utility associated with that group, i.., maxe, E[R(D, Y)JS = s].
We first examine the impact of the mecisisn anticipation of strategic behavior on policies. In Fig. 21 (App. C.I), the strategic 0 and non-strategic optimal threshold 0= are compared for each group under different and e. The results are consistent with Thm. Ø; when g is sufficiently large.
4. i.e., under certain conditions, 0r is lower than
We also examine the individual best responses. Fig. 3 shows the manipulation probability Par (0) as a function of threshold 0 for Caucasians and Asians (blue) versus African Americans and Hispanic (orange) when q 0.3, c 0.5. For all groups, there cxists a unique manr that maximizes the manipulation probability. These are consistent with Thm. 2.3 We also indicate the manipulation probabilities under original strategic optimal thresholds ; The results indicate that original strategic optimal thresholds may cause the disadvantagod groups to have higher manipulation probabilities.
Note that the scenario considered in Fig. 3 satisfies the condition (.t in Thm. 4.5 because the original stratogic 03 < 6max for both groups. We further conduct experiments in this setting to evaluate the impacts of adjusted preferences. We first adopt EqOpt as the fairness metric, under which Ex-ps [1(X 0)
Miller ct al. (2000) already argued that designing policy for any stratogic classification problem is non-trivial causal modeling problem, thereby making the controlled experiments necessary for applications in practice.
5 Scode available https::/ htips://gtthun httpss//gtthubb.c///omsmmm/// http://mm//nnneeeebeee/e//eeeee
10

---

Published in Transactions on Machine Learning Research (10/2024)
Table 2: Comparison between three types of optimal thresholds (FICO data). For Utility and PM values, the left value in parenthesis is associated with the advantaged group (Caucasian, Asian), while the right is for the disadvantaged group (African American, Hispanic). The first tabular is for Aaaucaiian/fficcaa American while the second is for Asian Asian/Hispant Hisspanic.
Threshold
Utility
PM
Unfairness (Eq0pt)
Non-strategic
(0.698, 0.171)
(0.331, 0.513)
0.136
Original strategic
(0.704 0.203)
(0.211, 0.278)
0.055
Adjusted strategic
(0.701, 0.189)
(0.140, 0.5)
0.028
Threshold category
Utility
PM
Unfairness (EqOpt)
Non-strategic
(0.726, 0.427)
(0.115, 0.322)
0.089
Original strategic
(0.734, 0.448)
(0.055, 0.161)
0.047
Adjusted strategic
(0.726, 0.431)
(0.023, 0.070)
0.022
0.6
0.6
0.5
PM(e") )
0.4
pM(0')
0.4
PM (Caucasian) Pu (African American) Pul0,)) Pw(B
0.3
Pμ curve for Asian
0.2
Pi curve for Hispanic Pm(0)) Pw(0))
0.2
0.1
0.0
0.0
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.6
0.8 1.0
0
Figure 3: (0) of Caucasian and African American (left plot)) and of Asian and Hispanic (right plot).
(0 and the unfairness measure of group Ga, Go can be reduced to | Experiments for other fairness metrics are in App. C.1 The results are shown in Fig. | where dashed red and dashed blue curves manipulation probabilities under non-strategic 0* and strategic 0" (Kx), respectively. Solid red and solid blue curves are the actual utilities U(O') and U (k1)) received by the decision-maker. The difference between the two dotted green curves measures the unfairness between Caucasians/ African Americans Asians/ Hispanics. All weights are normalized such that λ corresponds to the original strategic policy, and k 1 indicates the policies with adjusted preferences. Results show that when condition 1(88) in Thm. 4.5 is satisfied, increasing k can simultancously disincentivize manipulation (PM
Y (0) b)).
decreases with ki) and improve fairness. These validate Thm. 4.5 and 4.6
Caurasian
African American
Asian
Hispanic
0.4
stutogic uti ky
0.6
0.4
valuue
stratttrttgicccccc Pulk")
0.4
0.3
Statesic stily Frralii.a1
3 0.2
0.2
0.2
0.2
0.1
0.0
0.0
0.0
0.0
1.0
1.5
2.0
1.0
1.5
2.0
1.0
1.5
2.0
1.0
1.5
2.0
nomalized
Xt normalized by
normalized by uil
k) normalized
Figure 4: Impact of adjusted preferences: Caucasian and African American (left plot), Asian and Hispanic (right plot)
11

---

Published in Transactions on Machine Learning Research (10/2024)
Caucasian
African American
Coucasion
Arrican American
0.6
0.4
ligit Facalt
0.6-
0.4
0.4
g 0.4
sprdtroppp..t LERy
0.2
Pult
0.2
0.2
0.2
0.0
0.0
0.0
1.0
1.5
2.0
1.0
1.5
2.0
1.0
1.5
2.0
1.0
1.5
2.0
normalized
normalized by ull c)
normalized by u(l
normalized by
Figure 5: Impact of adjusted preferences (FICO data) when there is a Gaussian noise on q. The noises have O mean, and 0.05, 0.1 standard deviation from the left two plots to the right two plots.
Caucasian
African American
Caurasian
African American
0.6
Puli Vilt
Jal Hye Strrekk sallyy SetSaal
0.4
0.4
0.4
0.4
0.2
0.2
0.0
0.0
0.0
0.0
1.0
1.5
2.0
1.0
1.5
2.0
1.0
1.5
2.0
1.0
1.5
2.0
k1 normalized by 012 00
normalized by uEl
normalized by ucl
kt normalized by oll
Figure 6: Impact of adjusted preferences (FICO data) when there is a Gaussian noise on e. The noises have mean, and 0.05, 0.1 standard deviation from the left two plots to the right two plots.
Tab. 2 compares the non-strategic O-, original strategic 0*, and adjusted strategic 0 (k:) when ki,c 1i.0a = 1.5. It shows that decision-makers makers by adjusting preferences can significantly mitigate unfairness and disincentivize manipulation, with only slight decreases in utilities.
Robustness of results when q. c are noisy. We also present experiments to relax the assumption that the decision-maker knows g, 6 exactly on the Caucasian/ African groups. Instead, they only know q + 8 or 6 where 6 is a Gaussian noise. We do 10 rounds of simulations and produce plots with expectation and error bars similar to Fig, 4 (Fig. shows the results with noisy q, while Fig. G shows the results with noisy c). The results show adjusting l still works under noisy 9 and e.
Gaussian Data. We also validate our theorems on synthetic data with Gaussian distributed PxlYs in App. C.2 Specifically, we examined the impacts of adjusting preferences on decision policies, individual's best response, and algorithmic fairness. As shown in Fig. 19 and Tab. 5 7 these results are consistent with theorems, i.e., adjusting preferences can effectively disincentivize manipulation and improve fairness. Notably, we considered all thrce scenarios in Thm. 4.5 when condition (i) or 1.(W) or is satisfiod. For each scenario, we illustrate the individual's best response PM in Fig. 19 and show that manipulation can be disincentivized by adjusting preferences, i.e., increasing hn under condition 1.(1) 11()),, or increasing ho under condition 2.
6 Conclusions & Limitations
This paper proposes novel probabilistic framework and formulates Stackelberg game to tackle imitative strategic behavior with unforesccable outcomes. Morcover, the paper provides an interpretable decomposition for the decision-maker to incentivize improvement. and promole fairness sinultaneously. The theoretical results depend on some (mild) assumptions and are subject to change when e, q, CM, C2 change. Although we provide a practical ostimation procodure to estimate the model parameters, it still remains a challenge to estimate model parameters accurately due to the expensive nature of doing controlled experiments. This may bring uncertainties in applying our framework accurately in real applications.
12

---

Published in Transactions on Machine Learning Research (10/2024)
Broader Impact Statement
We believe proposed framework promote socially responsible machine learning under strategic clas- sification scttings since the outcomes of strategic behaviors in many real-world settings are imitative and un unforeseeable, thereby being more appropriately caplured by our model. However, as mentioned in Sec. G we need certain assumptions and an estimation procedure to apply the model in practice, which may bring unexpected social outcomes.
Acknowledgement
This material is based upon work supported by the U.S. National Science Foundation under award I1S- 2202699 and IIS-2416895, by OSU President's Research Excellence Accelerator Grant, and grants from the Ohio State University's Translational Data Analytics Institute and College of Engineering Strategic Research Initiative.
References
Saba Ahmadi, Hedyeh Beyhaghi, Avrim Blum, and Keziah Naggita. The strategic perceptron. In Proceedings of the 22nd ACM Conference on Economics and Computation, pp. 6-25, 2021.
Saba Ahmadi, Hedych Beyhaghi, Avrim Blum, and Keziah Naggita. On classification of strategic agents who can both game and improve. orXiv preprinl arXiv:2203.0111 001224 2022a.
Saba Ahmadi, Hedych Beyhaghi, Avrim Blum, and Keziah Naggita. Setting fair incentives to maximize improvement. arXiv preprint or 2rXin:2003.00 2022b.
Tal Alon, Magdalen Dobson, Ariel Procaccia, Inbal Talgam-Cohen, and Jamie Tucker-Foltz. Multiagent evaluation mechanisms, Proceedings of the AAAI Conference on Artificial Intelligence, 34:1774-172 2020.
Albert Bandura. Social learning through imitation. 1962.
Albert Bandura. Social learning theory of aggression. Journal of communication, pp. 12 29, 1978.
Solon Barocas, Moritz Hardt, and Arvind Narayanan. Fairness and Machine Learning: Limitotions and Opportunities. 2019.
Flavia Barsotti, Ruya Gokhan Kocor, and Fernando P. Santos. Transparcncy, detection and imitation strategic classification. In Proceedings of the Thirly- First International Joind Conference on Arlificial Intelligence, 1JCAI-22, pp. 67-73, 2022.
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, pp. 1234-1242, 2021.
Yahav Bechavod, Chara Podimata, Steven Wu, and Juba Ziani. Information discrepancy in strategic learning. In International Conference on Machine Learning, pp. 1691-1715, 2022.
Omer Ben-Porat and Moshe Tennenholuz. Best response regression. In Advances in Newral Information Processing Systems, 2017.
Daniele Bracale, Subha Maity, Moulinath Banerjee, and Yuekai Sun. Learning the distribution map in reverse causal performative prediction. arXie preprint ar11v:2,05.15172, 2024.
Mark Braverman and Sumegha Garg. The role of randomness and noise in strategic classification. CoRR, abs/2005.08877, 2020.
Micah D Carroll, Anca Dragan, Stuart Russell, and Dylan Hadfield-Mencll Estimating and penalizing induced preference shifts in recommender systems. In International Conference on Machine Learning, pp. 2686-28 2708. PMLR, 2022.
13

---

Published in Transactions on Machine Learning Research (10/2024)
Yatong Chen, Jialu Wang, and Yang Liu. Strategic recourse in linear classification. CoRR, abs/2011 2011.0035,, 2020a.
Yatong Chen, Jialu Wang, and Yang Liu. Learning incentivize improvements from strategic agents. Transactions on Machine Learning Research, 2023.
Viling Chen, Yang Liu, and Chara Podimata. Learning strategy-aware linear classifiers. Advonces in Neural Information Processing Systems, 33:15265 15276, 2020b.
Jinshuo Dong, Aaron Roth, Zachary Schutzman, Bo Waggoner, and Zhiwei Steven Wu. Strategic clas- sification from revcaled preferences. In Proceedings of the 2018 ACM Conference on Economics and Compulation, pp. 55 70, 2018.
Itay Eilat, Ben Finkelshtein, Chaim Baskin, and Nir Rosenfeld. Strategic classification with graph neural networks, 2022.
Andrew Estornell, Sanmay Das, and Yevgeniy Vorobeychik. Incentivizing truthfulness through audits strategic classification. In Proceedings of the AAAI Conference on Artificial Intelligence, number 6, pp. 5347-5354, 2021.
Michael Feldman, Sorelle A Friedler, John Moeller, Carlos Scheidegger, and Suresh Venkatasubramannia. Certifying and removing disparate impact. In proceedings of the 21th ACM SIGKDD international con- ference on knowledge discovery and data mining, pp. 259-268, 2015.
Vivek Gupta, Pegah Nokhiz, Chitradeep Dutta Roy, and Suresh Venkatasubramanian. Equalizing recourse across groups, 2019.
Nika Haghtalab, Nicole Immorlica, Brendan Lucier, and Jack Z Wang. Maximizing welfare with incentive- aware evaluation mechanisms. arXie preprint arX:v:0011.01956, 2020.
Moritz Hardt, Nimrod Megiddo, Christos Papadimitrion, and Mary Wootters. Strategic classification. Tn Proceedings of the 2016 ACM Conference on Innovations in Theoreticol Computer Science, pp. 111 122, 2016a.
Moritz Hardt, Eric Price, Eric Price, and Nati Srebro. Equality of opportunity supervised learning. Advances Neural Information Processing Systems, 2016b.
Moritz Hardt, Meena Jagadecsan, and Celestine Mendler-Dünneer Performative power. In Advances in Newral Information Processing Systems, 2022.
Keegan Harris, Valerie Chen, Joon Kim, Ameet Talwalkar, Hoda Heidari, and Steven Z Wu. Bayesian persuasion for algorithmic recourse. Advances in Newral Information Processing Systems, 35:11131-11 11144, 2022a.
Koegan Harris, Dung Daniel Ngo, Logan Stapleton, Hoda Heidari, and Steven Wu. Stratogic instrumental variable regression: Recovering causal relationships from strategic responses. In International Conference on Machine Learning, pp. 8502 0522, 2022b.
Hoda Heidari, Vedant Nanda, and Krishna Gummadi. On the long-term: impact of algorithmic decision policies: Effort unfairness and feature segregation through social learning. In 36th International Conference on Machine Learning, pp. 2692 2701, 2019.
Guy Horowitz and Nir Rosenfeld. Causal strategic classification: tale of two shifts, 2023.
Guy Horowitz, Yonatan Sommer, Moran Koren, and Nir Rosenfeld. Classification under strategic self- selection. Xiv preprint arXic:2402. 15274, 2024.
Zachary Izzo, Lexing Ying, and James Zou. How to learn when data reacts to your model: Performative gradient descent. In Proceedings of the 38th International Conference on Machine Learning, pp. 4641-4650 2021.
14

---

Published in Transactions on Machine Learning Research (10/2024)
Meena Jagadecsan, Celestine Mendler-Dünnee and Moritz Hardt. Alternative microfoundations for strategic classification. In Proceedings of the 38th International Conference on Machine Learning, pp. 4687-4697, 2021.
Kun Jin, Xueru Zhang, Mohammad Mahdi Khalili, Parinaz Naghizadeh, and Mingyan Liu. Incentive mech- anisms for strategic classification and regression problems. In Proceedings of the 23rd ACM Conference on Economics and Compulation, pp. 760-790, 2022.
Kun Jin, Tongxin Yin, Zhongzhu Chen, Zeyu Sun, Xueru Zhang, Yang Liu, and Mingyan Liu. Performative lederated learning: A solution to model-dependent and heterogeneous distributiin shifts. In Proceedings of the AAAI Conference Artificial Intelligence, volume 38, pp. 19938-12944 2024.
Musre-osseein Karimi, Gilles Barthe, Bernhard Schölkopf, and Isabel Valera. A survey of algorithmic recourse: contrastive explanations and consoquential recommendations. ACM Computing Surveys, 55(5):1-29, 2022.
Jon Kleinberg and Manish Raghavan. How do classifiers induce agents to invest effort strategically? pp. 1 23, 2020.
Tosca Lechner and Ruth Urner. Learning losses for strategic classification. arXiv preprint arXiv:2203.1342 13422, 2022.
Sagi Levanon and Nir Rosenfeld. Generalized strategic classification and the case of aligned incentives. International Conference on Machine Learning, ICML 2022, 17-23 July 2022, Baltimore, Maryland, USA, 2022.
pp.
Lydia T Liu, Sarah Dean, Esther Rolf, Max Simchowitz, and Moritz Hardt. Delayed impact of fair machine learning. In International Conference on Machine Learning, pp. 3150 3158. PMLR, 2018
Lydia T Liu, Ashia Wilson, Nika Haghtalab, Adam Tauman Kalai, Christian Borgs, and Jennifer Chayes. The disparate equilibria of algorithmic decision making when individuals invest rationally. In Proceedings of the 2020 Conference on Fairness, Accounlabilily, and Transparency, pp- 381-33 381-391, 2020.
Lydia T. Liu, Nikhil Garg, and Christian Borgs. Strategic ranking. In Proceedings of The 25th International Conference Artificial Intelligence and Stalistics, pp. 2489-2518, 2022.
Jie Lu, Anjin Liu, Fan Dong, Feng Gu, Joao Gama, and Guangquan Zhang. Learning under concept drift:
A review. IEEE Transactions on Knowledge and Data Engineering, 31(12):2346 2363, 2018
John Miller, Smitha Milli, and Moritz Hardt. Strategic classification is causal modeling in disguise. In Proceedings of the 37th International Conference on Machine Learning, 2020.
Juan Perdomo, Tijana Zrnic, Celestine Mendler-Dinner, and Moritz Hardt. Performative prediction. In Proceedings of the 37th International Conference on Machine Learning, pp. 7599-7609, 2020.
Reilly Raab and Yang Liu. Unintended selection: Persistent qualification rate disparitics and interventions.
Advances in Newral Information Processing Systems, pp. 26053 26065, 2021.
Nir Rosenfeld, Anna Hilgard, Sai Srivatsa Ravindranath, and David C Parkes. From predictions to docisions: Using lookahead regularization. In Advances in Neural Information Processing Systems, pp. 2020.
Yonadav Shavit, Benjamin L. Edelman, and Brian Axelrod. Causal strategic linear regression. In Proceedings of the 37th International Conference on Machine Learning, ICML '0, 2020.
Scamus Somerstep, Yuekai Sun, and Ya'acov Ritov. Learning in reverse causal strategic environments with ramifications on two sided markets. ar preprint arxiv:2404. 13240, 2024.
Omer Talha. Cheating is rampant on gre at home, 2024. URL
htt.:p/pw.................o..a.. 200o//00a//20aakk///2/0001ee..
15

---

Published in Transactions on Machine Learning Research (10/2024)
Wei Tang, Chien-Ju Ho, and Yang Liu. Linear models are robust optimal under strategic behavior. In Proceedings of The 24th International Conference Artificial Intelligence and Statistics, volume 130 of Proceedings of Machine Learning Research, pp. 2584 2592, 13 15 Apr 2021.
Stratis Tsirtsis, Behzad Tabibian, Moein Khajehnejad, Adish Singla, Bernhard Schölkopf, and Manuel Gomcz-Rodriguez. Optimal decision making under strategic behavior, 2019.
Tian Xie and Xueru Zhang. Automating data annotation under strategic human agents: Risks and potential solutions. arXi preprint arXi::405.08802, 2024a.
Tian Xie and Xueru Zhang, Non-linear welfare-aware strategic learning. arXiv preprint arXiv:2/05.01810, 2024b.
Tian Xie, Xuwei Tan, and Xueru Zhang. Algorithmic decision-making under agents with persistent improve- ment. Xir preprint 205:2240500107,, 2024.
Tom Yan, Shantanu Gupla, and Zachary Lipton. Discovering optimal scoring mechanisms in causal stralegic prediction, 2023.
Xueru Zhang and Mingyan Liu. Fairness in learning-based sequential decision algorithms: survey. Tn Handbook of Reinforcement Learning and Control, pp. 525 555. 2021.
Xueru Zhang, Mohammad Mahdi Khalili, Cem Tekin, and Mingyan Liu. Group retention when using machine lcarning in sequential decision making: the interplay between user dynamics and fairness. Advances in Newral Information Processing Systems, 32, 2019.
Xueru Zhang, Mohammad Mahdi Khalili, and Mingyan Liu. Long-term impacts of fair machine learning. ergonomics in design, 28(3):7-11, 2020a.
Xueru Zhang, Ruibo Tu, Yang Liu, Mingyan Liu, Hedvig Kjellstrom, Kun Zhang, and Cheng Zhang. How do fair decisions fare in long-term qualification? In Advances in Neural Information Processing Systems, pp. 18457-18469, 2020b.
Xueru Zhang, Mohammad Mahdi Khalili, Kun Jin, Parinaz Naghizadeh, and Mingyan Liu. Fairness inter- ventions as (Dis) for strategic manipulation. In Proceedings of the 39th International Conference on Machine Learning, pp. 26239 26264, 2022.
16

---

Published in Transactions on Machine Learning Research (10/2024)
A Related Work
A.1 Strategic classification
Generally, strategic behaviors can cause feature and label distribution of individuals to shift, which have long been closely related to concept drift (Lu et al.} 2018), preference shift (Carroll et al., 2022] and algorithm recourse (Karimi et al. 2022). Strategic classification has been extensively studied since (Hardt ct al. 2016a) formally modeled the interaction between individuals and a decision maker as a Stackelberg Game, and proposed a framework for strategic classification. While taking the individuals' best response into account, the decision maker can make the optimal decision by anticipating sateggi manipulation. During recent years, more complex models on strategic classification have been proposed (Ben-Porat & Tennenholtz
2017
Dong et al.
2018 Braverman & Garg 2020
Jagadccsan et al.
2021
Izzo al. 2021 Ahmadi et al.
2021
lang et al.
2021
Zhang et al. 2020b
2022 bilal et al. 2022] Liu el al. 2022 Lechner & Urner 2022:
Chen et al. 2020b
Xie & Zhang. 2024a). Ben-Porat & Tennenholtz (2017 7) developed best response linear
regression predictor where two players compete and each gets a payoff depending on the proportion of the
points he/she predicts more accurately than the other player. Dong et al. (2018) focused on the online version of the strategic classification algorithm. Chen et al. (2020b) developed a strategic-aware linear classifier to minimize the Stacelberg regret. Tang et al. (2021) considered the setting where the decision maker only knew a subset of individuals' actions. Levanon & Rosenfeld (2022) generalized strategic classification to situations
where individuals and the decision maker have aligned interests. Lechner & Urner 2022 proposed novel loss function considering both the accuracy of the prediction rule and its vulnerability to strategic manipulation. Eilat et al. (2022) relaxed the assumption that individual best responses are independent of each other and proposed a robust learning framework based on a Graph Neural Network. Horowitz et al. (2024) considered the self-selection problem in strategic classification where agents decide whether to participate in the system.
Xie & Zhang (2024b) proposed a welfare-aware optimization framework in strategic learning scttings.
Regarding randomness, Braverman & Garg (2020) proposed that randomized linear classifiers can be more robust to strategic behaviors. Morcover, Jagadecsan et al. (2021) added noise to standard strategic classi- fication and modified the slandard microfoundation into allernative microfoundations to let a portion of individuals be irrational and not have perfect knowledge about the decision maker's policy. However, they just consider directly adding noise to the best response without modeling the unforeseeable and imitative nature of human agents' behavior.
A.2
Improvement with label change
Another line of rescarch takes improvement into account(Liu et al. 2018 Zhang et al.
2020b
Liu et al.
2020
Rosenfeld el al. 2020 Chen et al.) 2020a;
Haghtalab el al. 2020 K Kleinberg & Rag havan
2020 Alon
et al.
2020 Miller et al.
2020; Shavit et al.
2020: Bechavod et al. 2021 Jin et al. 2022
Barsotti et al.
2022
A Ahmadi et al. 2022a
Raab & Liu 2021
Heidari et al. 2019 Somerstep et al. 2024). Liu et al. (2018)
2020
;
Zhang et al. [2020b] Rosenfeld et al.
(020); Ahmadi et al. (002bb) studied the conditions under
which individuals will choose to improve their qualifications. Specifically, Liu et al.] (2018) investigated how
different decision rules (e.g. maxutil, fair) influence population qualification. Liu et al. (2020) modeled the
improvement cost as random variable and further pointed out that subsidizing mechanism for individual costs can be beneficial for improving behaviors. Zhanng et al. (2020b) studied the dynamic of population qualification under a partially observed Markov decision problem setting, where improvement probability is given as a parameter. Rosenfeld et al.] (2020) proposed a Look-ahead regularization to directly penalize the drop of population qualification. Ahmadi et al.] (2022b) proposed a common improvement capacity model and a individualized improvement capacity model to optimize social welfare and fairness while considering individual improvement. JJin et al. (2022); Chen ct al. (2023) focused on designing subsidy mochanisms to incentivize improvement.
A.3
Studies considering both behaviors
There are other studies considering both strategic manipulation and improvement, but most. of them modeled manipulation and improvement in a similar way[Cher et al.] 2020a Haghtalab et al.) 2020 Kleinberg &
Raghavan 2020 Alon et al. 2020) Miller et al.) 2020 Shavit et al. 2020 Bechavod ct al.) 2021 Jin et al.
2022
Barsotti et al.] [022 Ahmadi et al. [022a Harris et al., 2022b
Horowitz & Rosenteld 2023 Yan
et al.
2023 Chen et al.] 2023). Specifically, illustrated in the abstract, the above-listed works all assume
17

---

Published in Transactions on Machine Learning Research (10/2024)
the agents can foresce the outcomes of their actions and they can change their features arbitrarily long as the cost. function permits. Moreover, these works modeled improvement and manipulation by assigning causal/non-cauu /e///oooncaussss features, which may not cover the practical cases in our paper such as college admission and job application. We further compare the differences between our model and causal strategic learning in App. B.1 Additionally, Perdomo et al. (2020); Izzo et al. (202T): ; Hardt el al. (2022; : Jin et al. (2024) proposed and claborated the concept of performative prediction where predictive decisions can influence the outcomes predict. In general, this framework can model both manipulation and improvement but lacks
interpretability.
There are only few works considering both actions while incorporating randomness (Harris et al. 2022a Bracale et al. 2024). Harris et al. (2022a) mainly focused on the situation where the decision-maker can choose from disclosing partial information of the model (namely, persuasion) and the agents estimate the best response using the partial information. Since the randomness completely comes from the information revealed by the decision-maker, this setting is different from ours where the randomness comes from the unforeseeable and imitative nature of agent improvement and manipulation. As a concurrent work, [Baccae et al. 2024) considered general setting where different actions incur random costs and lead to different leature-labe distributions. However, they only focused on estimating the distribution map generally, which is iangential to our focus on disincentivizing manipulation, incentivizing improvement, and promoting fairness. Their contribution to estimating the distribution map may further facilitate the practical applications of our model.
A.4 Machine learning fairness
While machine learning algorithms are able to achieve high accuracy in different tasks, they are likely to be unfair to individuals from different ethnic groups. To measure the fairness of algorithms, various metrics have been proposed including demographic parily (Feldman et. al. 2015). equal opportunity (Hardt et al. 2016b), equalized odds (Hardt et al. 2016b and equal resource (Gupta et al. 2019).
More importantly, several works have studied how strategic behaviors impact fairness (Liu et al. 2018 Zhang et al., 2020b Liu et al., 2020; Zhang et al. 2022). Specifically, Liu et al. (2018) considered one-step feedback
where static fairness does not promote dynamic fairness. Zhhang et al. (2020b) analyzed the long-torm impact of static fairness metries based on dynamics of population qualification. Liu et al. (2020) studied how hetero- geneity across groups and the lack of realizability can destroy long-term fairness in strategic classification. Zhang et al. (2022) has proposed a probabilistic model to demonstrate strategic manipulation well the fairness impacts of strategic behaviors, where the individuals shift their feature distribution instead of directly changing their features. The work also assumed randomness in manipulation cost. Meanwhile, it explored influences on different fairness metrics when strategic manipulation is present[Barocas Barocas et al. 2019
Hardt et al. 2016b).
B Additional discussions
B.1 The comparison between our model and causal strategic learning
Previous works in causal strategic learning model every strategic classification problem as structural causal model (SCM). SCM is a graphic model depicting the causal relationships between different features and the label, where features can be classified as causal or non-causal after a causal discovery process (Miller et al., 2020). Strategic manipulation means intervening in the non-causal nodes and improvement corresponds to intervening in the causal nodes. Though the model takes both behaviors into account and can accommodate complex causal structures, it has the following weaknesses: (i) The individuals can intervene in any feature node arbitrarily with a deterministic outcome to any value once their budgets permit, which is not practical as ratust in D. (ii) In most real-world cases, individuals are not able to intervene the observable features directly. Instead, they intervene in other unobserved features (causal or non-causal) to change the observable features. So is somctimes meaningless to distinguish whether an observable feature is causal or non-causal, because the root causes of its value change may be diverse.
We illustrate (ii) more clearly in Fig. 7 causal graph where U, are unobserved. However, U is non-cansal and V is causal. It is easy to see only X is observable and correlated to Y, but its change can be either "causall or "non-causal" with respect. to Y.
18

---

Published in Transactions on Machine Learning Research (10/2024)
By contrast, our probabilistic framework does not classify X as causal or non-causal. It models both ma- nipulation and improvement as imitating qualified individuals and incorporates the randomness of outcomes and costs. With limited control over their features, individuals can only expect a distribution shift and may even fail when they take certain actions. We believe the concise yet effective design of our model is more suitable for many practical situations nowadays, while the causal stralegic models sometimes assign too much power to individuals.
U
V
Figure 7: An example causal graph where only X is observable and U, V are unobserved.
B.2 More practical examples fitting to model
In Sec. and Appendix B.T we already explain the motivation of model in detail. Here provide more motivating examples besides college admission:
1. Loon application:
(a) Manipulation: an unqualified applicant may "steal" the features from qualified ones by purchasing a social security card (SSN) from the hackers. The "stolen' features are still random when the applicant decides to purchase an SSN because the card is often randomly drawn from many stolen cards of qualified individuals.
(b) Improvement: an unqualified applicant may observe the qualified individuals' profiles and strive imitate their behaviors. However, the applicant never knows the realization of his/her features before trying improve. The applicant only try their best mimic qualified individuals and expects the successful imitation will cause his/ his/her feature distribution to shift.
2. Job application:
(a) Manipulation: an unqualified applicant may "steal" the features from qualified ones by hiring an imposter to take the interview instead of him/her (especially when remote interviews are prevalent today). Similar to previous examples, the applicant docs not know the exact feature realization when making the decision to manipulate.
(b) Improvement: an unqualified applicant may still observe the features of qualified ones by reading their interview preparation tips looking at their technical portfolios. Then they may try hard to imitate the qualified individuals. Similar to previous examples, the applicant still has no idea of the exact outcome when he/she decides to improve.
B.3 The option of "doing nothing"
Our model implicitly includes the action of "doing nothing". Specifically, our model assumes improvement only succeeds with probability q and the improvement cost differs among agents which is modeled as a random variable C,- For agents who do nothing, we may consider them as those who take improvement action at zero costs but fail to improve. Because no cost is incurred and the improvement fails, the resulting features remain the same and the outcome is equivalent to 'doing nothing".
Although may be intuitive to model 'doing nothing" as separate action, we argue that it is more realistic in practice for individuals to always take action. As pointed out by Horowitz et. al. (2024) agents who decide
19

---

Published in Transactions on Machine Learning Research (10/2024)
to participate in system will pay an unavoidable cost, and the cost is a part of the 'improvement cost'. On the contrary and we argued before, unqualified individuals in our model are not given explicit option of "doing nothing" with a deterministic 0 cost and 0 utility in the first place. In our framework where improvement is modeled as the imitative behavior in social learning (the third paragraph on page 2); all unqualified individuals staying the system are influenced by the desire to be qualified and must do something to imitate the qualified profiles because they know they are unqualified. Otherwise, they will just quit the system and are not in our interest. In the college admission example, all unqualified students who do not give up applications and do not cheat are doing similar things: striving to learn more courses, take tests, and prepare for application packages. The only difference is the realization of the improvement outcomes (some students really improve, some do not). To concretely answer your question of Cm, C,, we slightly modily the "budget' to "utility" in footnole 3: For all agents already in the decision-making system, they already have a sufficiently large initial utility exceeding CM, This means if they choose to quit, they lose the initial utility.
B.4 Discussion on adjusted preferences
Utility loss from the adjusted preferences. Although adjusting preferences a simple yet effective way to promote fairness and disincentivize manipulation, the actual utility received by the decision-maker inevitably diminishes as ly or l2 changes (as the actual utility the decision-maker receives always do- termined by the original function (0) in equation
3 Nonetheless, such diminished utilities may still be higher than the utility under non-strategic policy 0" This is illustrated empirically in Sec. and Appendix
Adjusted preference as a regularizer to promote fairness. We have shown that adjusting weights ki, k2, ki in learning objective (equation 5) can control the individual behavior and algorithmic fairness. Indeed, we can view this adjustment mechanism as a regularization method: by adjusting weights, we are essentially changing the objective U() by adding a regularizer, i.c.,
((0)+ + (0,,, k1 k2 k2) (0) + 11,
regularizer
with the regularizer (4 k2, 12, ky) defined as follows:
(0, k1, k2, ka) - (0, u(1 - a), a(1-a),,ut u(l-(a))))
Weights ki, h2, ha are the regularization parameters. The analysis Sec. 4.2 and 4.3 suggests that to learn optimal policies that satisfy certain constraints such as bounded fairness violation and/or bounded individual's manipulation,
may transform this constrained optimization into regularized unconstruined optimization. This view, by incorporating fairness and strategic classification in simple unifidd framework, may provide insights for researchers from both commintiies.
B.5 Estimate Model Parameters
A complete estimation procedure. With only the knowledge of conditional distribution of qualified in- dividuals Px y (x:[1) and the population's qualification rate a, we introduce complete procedure to estimate P (x)0) q, P! e, Pcs- Pes--o,6o (ar) sequentially. Specifically, we need to do controlled intervention experiments on an experimental population as follows.
1. Estimate (x/0)) Set the lowest decision threshold 0 0 to estimate Px (z/0). Since all un-
qualified individuals will be accepted, the resulting distribution is the original mixture distribution (1 a) (x(0) + a (x)). Thus, with minor assumptions on the feature distribution fami- lies, we can estimate (x)))
2. Estimate q: Apply the strictest auditing procedures (e.g., audit everyone in [26]) to the population disable manipulation. With manipulation disabled and arbitrary decision threshold appliod, all unqualified people choose to improve, and the resulting qualification rate is (1 a)q + a. Thus, by examining the qualification rate after the intervention we can get the estimation of q.
20

---

Published in Transactions on Machine Learning Research (10/2024)
3. Estimate Pl: Apply arbitrary decision threshold 0 to the population, the resulting population prob- ability density distribution will be mixture of (1 a1 - g) + [(1 a.g + al Pxi1- Similarly, with minor assumptions on the distribution family of Pl, we can estimate pt
4. Estimate e: With q, Pf known, the decision-male maker can first apply another arbitrary 0 to new samples from the population and observe the resulting new population. This gives the new qualification rate Op- Because Op = a + (1-a) a) (m)())) where (0) is the probability of manipulation under 0, we can then compute the value of (0). Note that the prcision-maker also knows how many individuals (among all individuals) are discovered to manipulate (cheat), and let this proportion be c then can estimate the manipulation detection probability as (0)
5. Finally, with all previous parameters known, we can apply different 0 to the population several times to obtain data points of PM- Then since PM corresponds to points of FCM- -Cr, with minor assumptions on the distribution family of Par, we can directly fit the distribution and get Pcx-Cr-
It is worth noting that all the above steps can be more robust by doing multiple intervention experiments, and controlled experiments are necessary Miller et al. (2020). We will add the above discussion to the paper to improve its significance. Finally, with all the parameters, the decision-makes maker can first apply Thm. 4.6 to see how to adjust its preferences, and then perform a grid search to find the best k.
Robustness of results when q, are noisy. We also present an experiment to relax the assumption that the decision-maker knows q, c exactly on FICO data. Instead, they only know g 5 or + 8 where 8 is a Gaussian noise. Table 3 show the results with noisy q, while Table 4 show the results with noisy c). The results show adjusting k still works under noisy and although inconsistency exists.
Table 3: Comparison between three types of optimal thresholds (FICO data) when there is a Gaussian noise on g with standard deviation 0.1 and k = ki,aa = 1.25. For utility and PM. the left value in parenthesis is for Group a, while the right for Group b. The fairness metric is egopt.
Threshold category
Utility
PM
Unfairness
Non-strategic
(0.698, 0.171)
(0.331, 0.513)
0.136
Original average noisy strategic
(0.703, 0.201)
(0.212, 0.284)
0.057
Adjusted average noisy strategic
(0.700, 192)
(0.170, 0.220)
0.043
Table 4: Comparison between three types of optimal thresholds (FICO data) when there is Gaussian noise on e with standard deviation 0.1 and other settings stay the same.
Threshold category
Utility
PM
Unfairness
Non-strategic
(0.698, 0.171)
(0.331, 0.513)
0.136
Original average noisy strategic Adjusted average noisy strategic
(0.700, 0. 195)
(0.192, 0.251)
0.050
(0.698, 0. 0.185)
(0.158, 0.194)
0.037
C Additional empirical results
C.1 Additional results on FICO score
Firstly, Fig. ! shows the conditional distribution PxlYs and pl of each ethnic group. Fig. demonstrates Assumption 2.1 is satisfied. Fig. 21 the (non)-strategic optimal thresholds under different combinations of q, for each ethnic group. All four plots demonstrate the correctness of Thm. 4.1
Experiments with demographic parity as a new fairness metric.
We also reconducted the above experiments with demographic parity (DP) as the new fairness metric. As illustrated in Sec. 4.3] puP (z) (x)s( Similar to Fig. and Fig. we produce Fig. 11 based on DP, which demonstrate the same patterns the figures based on Eqopt.
21

---

Published in Transactions on Machine Learning Research (10/2024)
s1 Par. (00,.)
Pax.ate[1
P(a)
1013
1013
1023
Caucasian
Caucasian
Caucasian
African-American
AfricanAmmercan
Arrican-American
Hispanic
Hispanic
Hispanic
Asian
Asian
Asian
10
10a
10
0.0
0.2
0.4
0.6
0.8
1.0
0.2
0.4
0.6
1.0
0.0
0.2
0.6
0.8
1.0
Score
Score
Score
Figure 8: Illustration of Assumption
2.1
FICO Data
Caucasian
Mircan-Ameeican
Hispanic
Asian
10.0
Fall to Improve
10.0
Fail to improve
10.0
Fall to improve
10.0
Fail to improve
repay
repay default
replay
repay default
7.5
default
7.5
7.5
default
7.5
5.0
2.5
2.5
2.5
Score
Score
Score
Score
Figure 9: Manipulation curve and manipulation probability for both groups under optimal non-strategic thresholds
C.2 Results for Gaussian Data Assune there are two groups For E {a, we both have:
Px|rs(a(0,5) 8)
NNO, 1)
pd N(0.5,1 1)
(x)rs(a(1,s)
N(1,1)
CM-Oi
N(0,0.25)
(6)
We first illustrate the conditional feature distributions for Gaussian data in Fig, 10 With these parameters pre-determined, we still need to vary a, e, to obtain 0-0 8" under different parameter combinations.
(Non)-strategic optimal threshold and utility
To illustrate the complex nature under different permutations of parameters, with the pre-determined pa- rameters in equation 0 and 0.6, we vary q and plot both non-strategic optimal thresholds and regular strategic ones with respect to different e as shown in the bottom plot of Fig. 12 where the lower graphs illustrate Thm. i.c. the red line always under the blue line.
We also demonstrate the strategic utility under different combinations of with pre-determined parameters in equation 0 and a = 0.3 or a = 0.6. Fig. 13 and 14 suggest the complicated nature regular strategic utility under different parameter combinations. is possible to have 0,1 or extreme points.
Illsttation of threshold shifts while adjusting k
To illustrate 4.5 we demonstrate the effects of adjusting each of ki, k2, kg- According to Fig. 15 and 16
we can see when ki is large enough, the optimal strategic threshold is definitely lower than the optimal non-stratogic ones. However, when a small, we need larger k to pull 0" downward. According to Fig. I7 and 18 we can see when the population is majority qualified, adjusting by is guaranteed to shift ø* upward (Fig. 18
22

---

Published in Transactions on Machine Learning Research (10/2024)
0.4
1.0
unqualified
unqualified
fail improve qualified
fail improve qualified
0.8
0.3
0.6
pdf
0.2
cdf
0.4
0.1
0.2
0.0
0.0
Figure 10: Illustration of equation 6
Caucasian
Asian
0.6
0.6
Pwtt IKx))
Putl Put8"(ki) (Ik))
valuue
0.4
strategic utility Fxs(6(s)
value
strategic utility
0.4
1x)
non straterat utility Pu(0")
non-strategic utility
0.2
Pwt0 ")
0.2
0.0
1.00
1.25
1.50
1.75
2.00
1.0
1.2
1.4
1.6
1.8
2.0
k1 normalized by u(1 a)
ki normalized by u(1 a)
African American
Hispanic
(k,)) strategic utility Fxs(B|ss
0.4
0.4
non con-strategic utility
value
Pu(0") )
value
0.2
Pwte (Ku)) strategic utility Fxi (011,
0.2
non-strategic Utility Pw(0")
0.0
1.00
1.25
1.50
1.75
2.00
1.4
1.6
normalized by u(1 a)
k1 normalized u(1
Figure 11: Ilussraaioon of Thm. Caucasian and African American, while the right is for Asian and Hispanic
4.5 and Thm. 4.6 in FICO Data with fairness metric DP. Left figure is for
Illustration of condition 1.(i), Thm. 4.5
We first show parameter setting satisfying condition 1.(i) in Thm. 4.5 With pre-determined parameters in equation we set = 0.5 and a, 0.2, o5 = 0.25. This matches the notation tradition in Sec. 4.3 where group the disadvantaged group with a lower qualified percentage. Also, because + 2 1, the setting satisfies condition 1.(1) in Thm. 4.5 We first illustrate the manipulation probability under optimal original stratogic threshold 0 as in Fig. From Fig. [00 we can set j₁a k2. 1.25 to let the strategic utility still be larger than the one under str-strategic optimal threshold(i.c. the solid blue line is above the solid red line), while lower the cumulative density dramatically (i.e. the dotted green line) to admit
23

---

Published in Transactions on Machine Learning Research (10/2024)
0.00
q 0.30
0.00
0.25
-2
-0.50
-0.75
8
-1.00-
0.0
0.5
1.0
0.0
0.5
1.0
E
E
0.60
q = 1.00
0-
-2
-2
0*
0*
-4
-4
0.0
0.5
1.0
0.0
0.5
1.0
Figure 12: straeestr optimal threshold. We regularize y-axis to be [-5,5] to prevent numerical issues.
qualified individuals and disincentivize manipulaation (i.e. the dashed blue line). The details of comparisons are shown in Table 0
Illustration of condition 1iii,,, Thm. 4.5
With pre-determined parameters in equation we set 4 0.25 and aa = 0.4, on = 0.6. This matches the notation tradition Sec. 4.3 where group the disadvantaged group with lower qualified percentage. We first illustrate the manipulation probability under optimal original strategie threshold 0 is satisfied because the orange and green points are both located before the extreme large point of PM (). Thus, we could increase kıs to disincentivize manipulation while improving fairness as shown in Fig.
in Fig. 19 Fig. 19 reveals that 1.(H) in 4.5
20 From Fig. 20 we can set kia = hza = 1.25 to let the strategic utility still be larger than the one under non-strategic optimal threshold(i.e. the solid blue line is above the solid red line), while lower the cumulative density dramatically (i.e. the dotted green line) to admit more qualified individuals and disincentivize manipulation (i.e. the dashed blue line). In Table We summarize the comparison between non-stralegic 0-, original strategic 0*, and adjusted strategic 0" (ki)) (when k1,c = 01.00 = 1.25). It shows that Docision-maker by adjusting preferences can significantly mitigate unfairness and disincentivize manipulation, with only slight decreases in utilitics.
Illustraioon of condition 2, Thm. 4.5
Besides, we also show one more parameter setting satisfying condition 2 in Thm. 4.5 With pre-determined parameters in equation t we also set q
0.2 and a2 0.3, 0.35. This matches the notation tradition in Sec. 4.3 where group is the disadvantaged group with a lower qualified percentage. Also, based on Fig. 19 q + é < 1 and aa as < 0.5, the setting satisfies condition 2 in Thm. [.3] We first illustrates the manipulation probability under optimal original strategic threshold 0r and non-strategic threshold 0 as in Fig. 19 As shown in Fig. 20 for both groups, we demonstrate the manipulation probability for 0*,0" and (k1) when hj varies, (ntatestrategic utility and cunulative density conditioned on Y = 1 (i.e. this measures the unfairness based on equal opportunity). This plot suggests we can find suitable l2. and hz disincentivize manipulation and promote fairness, while also making the utility higher than the one under non-strategic optimal threshold. From Fig. 20 we set both k2a and las at 1.25 to let the strategic utility
24

---

Published in Transactions on Machine Learning Research (10/2024)
0.4
0.4
Strategic utility
Strategic utility
0.3
0.3
0.2
0.2
0.1
0.1
0.0
0.0
4
-2
0
2
-4
-2
2
4
0
Figure 13: Regular strategic utility when a = 0.6. The left figure has = 0, q
0.5 and the right has
0.75, = 0.25
0.00
0.08
Strategic utility
Strategic utility
0.06
0.02
0.04
-0.04
0.02
0.00
-0.06
00.02
-0.0
-0.04
4 -2
4
0
0
Figure 14: Regular strategic utility when a 0.3. = 0.75, 0.25
The left figure has == 0,
0.5 and the right has
3
-1-
-5
-5
0
-9
0 (k:
10.00)
-9
0' (k:
10.00)
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.6
0.8
1.0
Figure 15: Strategic optimal threshold (k(k)) after increasing k while keeping k2, k3 fixed. Left figure has g 0.01 and right figure has q = 0.99, while both figures have a 0.6
still be larger than the utility under non-strategic optimal threshold (i.c. the solid blue line is above the solid red line), while keeping the cunulative density function closer (i.e. the green dotted line) to mitigate unfairness, and also disincentivize manipulation (i.e. the blue dashed line). The details of comparisons are shown in Table 7
25

---

Published in Transactions on Machine Learning Research (10/2024)
3
3
-1
0
0
(k; 100.00)
-
(k, 100.00)
-9-
-9
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.6
0.8
1.0
E
Figure 16: Strategic optimal threshold (k1) after increasing kı while keeping k2, k3 fixed. Left figure has 0.01 and right figure has 0.99, while both figures have a 0.3. We regularize y-axis to be [-5,5] to prevent numerical issues.
5
5
0*
3
.e (k2 = 100.00)
3
0 (k2 100.00)
-1
-1
-3
-3
-
-5
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.6
0.8
1.0
E
E
Figure 17: Strategic optimal threshold 0" (k2) after increasing k2 while keeping k1, ka fixed. Left figure has =
0.01 and right figure has 0.99, while both figures have a 0.3. We regularize y-axis to be [-5,5] to prevent numerical issues.
5
5
e" (k2 100.00)
3
0 (k2 100.00)
1
-1-
-1
-3
3
-5
-5
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.6
0.8
1.0
E
E
Figure 18:
Strategic optimal threshold 8" (k2) after increasing k2 while keeping k1, Ky fixed. Left figure has 0.01 and right figure has = 0.99, while both figures have a = 0.6
26

---

Published in Transactions on Machine Learning Research (10/2024)
0.5
0.6
Pi curve
Pa curve
0.4
Pw(0))
0.5
Pu(o))
0.5
0.3
Px(0[]
Pute
0.4
Pulo))
Pw10
Pu curve Pu(e'))
0.4
0.2
0.3
Pu(82)
0.1
0.3
Putd"")
Pu(8.")
0.0
-4
-2
0
2
-2
2
4
-4
0
2
4
6
0
0
Figure Manipulation probability Pas (0): from left to right are plots for condition 1. 1.(1), 1. 1.(6),,
Group
Group a
Group a
0.4
Pale (tu))
0.5
Puld (k,D)
1.0
strategic utility
strategic utility
Far (l)
Fan 5001.
0.8
0.3
non strategic utility
non-strategp utiliyy
value
Pud6 1
value
0.3
Pu(6") 1
value
0.6
0.2
0.2
0.4
Pul8 (kg1)
strategic utility
0.1
0.1
0.2
Fay 1011. s) non-strategic utility
0.0
0.0
0.0
Pu(l"))
1.00
1.25
1.50
1.75
2.00
1.00
1.25
1.50
1.75
2.00
2
8
normalized u(1 a)
k1 normalized u(1 -
normalize lized oll
Group
Group b
Group b
0.4
0.4
1.0
Pwi0 (ka))
strategic utility
0.3
0.3
0.8
Far S18
Pel0 (hi))
Putl ((x)))
non-strategic uiility
strategic utility (8)
value
strategic utility
valuee
0.6
PHIl")
0.2
0.2
Fay st
non-strategic utility
non-stratogic utility Pu(8")
0.4
Pa(8
0.1
0.1
0.2
0.0
0.0
1.00
1.25
1.50
1.75 2.00
1.00
1.25
1.50
1.75
2.00
4
8
10
k normalized by u(1 a)
k normalized by u(1 a)
kg normalized by ofl - a)
Figure 20: Illustration of Thm.
4.5 and Thm.
4.6
From left to right are illustrations for condition
1. (1),2
Table 5: Comparison between three types optimal thresholds for Gaussian data satisfying condition 1. 1.(1). For utility and PM, the left value in parenthesis for Group a, while the right is for Group b. The fairness metric is egopt.
Threshold category
Utility
PM
Unfairness
Non-strategic
(0.054, 0.327)
(0.519, 0.368)
0.280
Original strategic
(0.081, 0.384)
(0.266, 0.168)
0.073
Adjusted stratogic
00.088, 0.385)
(0.176, 0.159)
0.008
27

---

Published in Transactions on Machine Learning Research (10/2024)
0.000
0.30
Q 0.20
- 0.30
0.25
strtogicc optimal
0.8
strotogic eptina
nar-strategic optimal
non-strategl
0.20
0.6-
0.15
0.20
0.4-
0.10
0.15
0.05
strategic
0.4
0.2-
strotoglc
0.00
optimal
0.0
0.0
0.2
0.4
0.6
0.8
1.5
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.6
0.6
1.0
0.0
0.2
0.4
0.6
0.8
1.0
Q- 3.60
q
1.00
Q 0.50
Q-
0.20-
0.20
0.20
0.15
0.15-
siretegit optimal
strerggle optimw
0.10
0.10
non-strategr rptimal
0.30
0.10
non-strategi- oprimal
0.05
strategii optimal
0.05
0.05
stritegic oprimal
0.05
0.00
non strottio optimal
0.00
0.00
non ton-stratooic optimll
0.00
0.0
0.2
0.4
0.6
0.8
1.0
1.0
0.3
0.2
0.4
0.6
0.8
1.0
3 0.00
q- 0.30
q - 0.00
Q 0.30
0.25
0.20
0.20
0.25
0.35
0.15
0.10
0.30
0.10
strategic notimal
0.05
strategk opt mai
0:15
stritegic oprimal
0.05
strieegc totimaal
non-stratogce optinal
strotgiic optinal
stratggic optinal
0.00
non-strtogic optmal
0.0
0.4
0.6
0.0
1.0
0.2
1.0
0.0
0.6
1.0
1.00
0.60
1.00
0.20
0.20-
0:25
0.25
0.20
0.15
0.15
0.10
non-shateeii oprimal
stratagic optmal
0.10-
non-erntegic optimal
stratogic opt mal
0.15
0.15
0.30
non-thategl optimal
strutogs ootimal
0.05
0.05
Strategic optimal
0.05
0.00
0.00
0.00
stw.sgic optma
0.00
0.0
0.2
0.4
0.5
0.8
100
0.0
0.2
0.4
0.6
0.0
1.
0.0
02
0.4
0.6
08
1.0
0.0
0.2
0.4
0.6
0.8
100
Figure 21: -trateetrateggic optimal thresholds under different q, for different ethnic groups (top left: Cau- casian; top right: African American; bottom left: Asian; bottom right: Hispanic)
Table 6: Comparison between three lypes of optimal thresholds for Gaussian data satisfying condition 1.(1)). For utility and Pas, the left value in parenthesis is for Group a, while the right is for Group b. The fairness metric is egopt.
Threshold category
Utility
PM
Unfairness
Non-strategic
(0.029, 0.060)
(0.434, 0.393)
0.086
Original strategic (0.204, 0.251)
(0.046, 0.040)
0.019
Adjusted stratogic
(0.191, 0.241)
(0.023, 0.023)
0
Table 7: Comparison between three types of optimal thresholds for Gaussian data satisfying condition 2. For utility and Pas, the left value in parenthosis is for Group a, while the right is for Group b. The fairness metric is egopl.
Threshold category
Utility
PM
Unfairness
Non-strategic
(- 0.0366 -0.014)
(0.674, 0.686)
0.088
Original strategic
(0.001, 0.004)
(0.508, 0.547)
0.084
Adjusted strategic
(0, 0)
(0.500, 0.500)
0.002
28

---

Published in Transactions on Machine Learning Research (10/2024)
D Derivations and Proofs
D.1 Derivations of equation [
(0) is the expected utility gain of an unqualified agent if choosing to manipulate: i. If the manipulation is not exposed, the probability of admission is 1 - (011) because the manipulation leads the agents to get his/her new fealure from Pxjr=1, which happens at a probability - ii. If the manipulation is exposed, the probability of admission is O, which happens at a probability e; iii. If the agent does not manipulate, the probability of admission is 1 - Fx (0(0) because now his/he feature is from the unqualified population, and keep in mind that the agents will never know the exact values of his/her feature when he/she makes decisions; Then according to the total probability theorem, the expectation of utility gain (0) (1 -) c) (1 (01)) + 0 (1 (010) Car-
(r) is the expected utility gain of an unqualified agent if choosing to improve: i. If the improvement succeeds, the probability of admission is 1 - 1'jxixx(00 (011) because the improvement leads the agents to get his/her new feature from PxIr=I: which happons at a probability q: ii If the manipulation is exposod, the probability of admission is - F' (0), which happens at a probability 1 - qi iii. If the agent does not manipulate, the probability of admission is 1 (010).
Then according to the total probability theorem, we can derive Ur(0) as well. Finally, substitute above two terms into (0) Pr (0) Uy)) and get equation
D.2 Proof of Thm. 2.3
Assumption 2.2 ensures that Pon-CC, > when in its domain. Thus, we can directly take the derivative inside equation we can get (1 - q) (0) (1 - q (Pxxx(0)))) To get its sign, we only need to consider
(1 9) (1 q (011) (T(
Thus, if 1 - e < O, the derivative is always larger than 0 (since q < 1). So under this situation, Pas is always increasing. Otherwise, since (011 is increasing according to Assumption 2.1 it will first increase [6]
and then decrease, with (0mezl 1-9
P!(mma))
I-
Since Pxiv(mmez is monotonically increasing and 1-4 = 1+ --q-c: when g increases 1+ 1-g-r increases, p!(0
1-q-c making fmaz increases. The same also holds when e increases. Note that while or e increases, we still need 11
D.3 Proof of Thm. 411
Assume O E b). When q -> 1, improvement will always succeed. Also, Thm. 2.3 reveals PM (f) reaches its minimum when 0 + a, so Par(a) < 0.5. Thus, improvement will always bring benefit that is larger than manipulation to the strategic decision-male maker (since improvement always succeeds). Thus, the decision maker may set a threshold as low as possible (-> a) to maximize its utility, which will always be lower than the non-strategic optimal threshold.
D.4 Proof of Prop. 4.2
Assume 0 E (a, b). Consider the situation when l k3 both stay fixed and Ki + o0, U = = is dominated by k1Φ1. Noticing é1 reaches its maximum when 0 + a, we will also have the new optimal 8 (k()) - a. Since a is the minimum possible value of the threshold, the optimal threshold when ki is large enough will definitely be smaller than the optimal non-strategic threshold as well as the original optimal strategic threshold.
D.5 Proof of Prop. 4.3
Assume A E (a, Consider the situation when hi, ks both stay fixed and 22 + oo, U = + Ô is dominated by -k202 dh2 + 0 both when 0 - or a (i.e. d2 reaches its minimum). However, the non-strategic utility should be when 0 + 6 but smaller than when 0 + a if not majority of people are qualified. This will make the new optimal l² (k2) + b. Since b is the maximum possible value of the threshold, the optimal threshold when 22 is large enough will definitely be larger than the optimal non-strategic threshold as well the original optimal strategic threshold.
29

---

Published in Transactions on Machine Learning Research (10/2024)
D.6 Proof of Prop. 4.4
Assume 8 E (a, b). Consider the situation when k1, 22 both stay fixed and ky b, ++Ū is dominated by kgd3- Take the derivative of (1-c)- (1- (x(xx((1)))))))))))) - (01)) (the term multiplied by PM in Φs), we get 1 (1- P (x(D) This suggests the term will first increase and then decrease. Thus, the maximizer of Px
- -3-003 PM (1-(1- (1- Pxi((10)) will locate before the root of (1-e)-(1-F)) (0 (1-)))((1PPp) (0(0). Then noticing that increasing will lower the value of the root, we can confirm the existence of ? to make the root small enough, thereby making the maximizer of -k3 03 smaller enough. Then because U is dominated by -ky03, 0" (kg) will also be small enough.
(xx(()))
D.7 Proof of Thm. 4.5
Assume 0 E b). Then: Under condition 1.(0). Thm. 2.3 shows PM((0) strictly increases. Because increasing & will cause (ka) to left shift until approaching a, PM PM (ki)) will keep decreasing its minimum value.
2. Under condition (i)), Thm. 2.3 shows (0) strictly increases before maax where Px P (0mazl1) 1-9.. pi(Omaz) = 1-q-e" (xlr(011) is increasing, would know 0* 0mar- Because increasing kn will cause 0 (Ia) to left shift Since (T(0)
until approaching a, (6 will keep decreasing to its minimum value.
Px (( (!(mmar) T-q-e-
3. Under condition 2, Thm. 2.3 shows Pas (0) strictly decreases after 6maz. where
Since (011 is incrcasing, we would know > 0max. Because incrcasing ho when I 0.5 will cause (T())
(kg) to right shift until approaching Pas (0r(00()))) will keep decreasing to FC (0), which is smaller
than (f*).
D.8 Proof of Thm. 4.6
Define R as some cumulative density function (CDF) associated with fairness metric C. The unfairness E Ex-rgl1(z 2 0.]l - xx [1x 2 0,)]| can also be written as (0.) - (06).
1. Under situation 1, Thm. 4.5 already reveals increasing k can disincentivize strategic manipulation. Mcanwhile, (k)) will decrease for both groups because (% decrcases for both group. Thus, there must exist kin kis to miligate the difference between Fg (kI)) and (0 which promoting the fairness at the same time of disincentivizing manipulation.
2. Under situation 2, Thm. 4.5 already reveals increasing by can disincentivize strategic manipulation. Meanwhile, F (02 will increase for both groups because (% increases for both group. Thus, there must exist k2a, h2s to mitigate the difference between Fg (k2))) and (k2)),, which is promoting the fairness at the same time of disincentivizing manipulation.
3. Under situation 3, Thm. 4.5 already reveals increasing y for group a and increasing by for group b can disincentivize strategic manipulation. Meanwhile, (k)))) will decrease for a and (07 increase for b. Thus, because a is already the disadvantaged group, the difference between (k)))())) and (0) (k2)) will be mitigated, which is promoting the fairness at the same time of disincentivizing manipulation.
D.9 Proof of Corollary 4.7
Corollary 4.7 can be derived directly from Thm. 4.5 and Thm. 4.6 To recap, Thm. 4.5 identifies all scenarios under which manipulation is guaranteed to be disincentivized via adjusting preferences; Theorem foftheorem:fairness finds all scenarios when promoting fairness and disincentivizing manipulation can be attained simultaneously; Corollary 4.7 emphasizes all scenarios where disincentivizing manipulation does not guarantee fairness improvement.
In Corollary 4.7 to ensure the manipulation to always be disincentivized, both groups a, should satisfy either scenario identified Thm. 4.5] This results in four possible combinations, and three out of these four are the scenarios found in Thm. 4.6 The left one situation the case Corollary 4.7 (group a satisfies condition 2 and group b satisfies condition 1). In this case, group can be disincentivized only by
30

---

Published in Transactions on Machine Learning Research (10/2024)
increasing 222 However, increasing ly can only make the decision threshold 0g higher, which will exacerbate the unfairness (since group a has Oa < 0.5, by condition (.))-
31


Reviews:
[{"review_id": "4Rfm3wEFX2", "reviewer": "Reviewer_xoU9", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- The model extends the strategic classification problem by limiting the knowledge and action space of the individuals so that the benefit of manipulation is not observable a priori. This setting is often more realistic in practice and is well motivated.\n- The content is overall well presented and readable, with clean notations.\n- The theoretical results are complemented with empirical evidence from both simulated and real world data. Robustness of the assumptions is also addressed in some of the experiments.\n\nWeaknesses:\n- I find the results overall quite straightforward. Given the similarity to the existing setting of strategic classification in the literature, I do not find the formulation truly novel. The theoretical results are standard once the assumptions are established; in particular, several results (e.g., Thm 4.1, Prop 4.2) are existential and non-quantitative.\n- I am not sure how significant the results are regarding real world problems, as the setting seems overly simplifying (specifically, regarding the underlying distribution and the knowledge of type, but not the feature).", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper presents a variant of the strategic classification problem, formulated as a Stackelberg game between a decision maker (e.g., college admission) and a population of individuals (e.g., students). The novel piece in the formulation is that individuals's manipulation of their profiles may lead to unforeseeable outcomes. The authors decompose the difference between strategic and non-strategic decision-makers' utilities into three interpretable terms that describes the individuals qualification improvement (or the lack thereof) and manipulation. By further adjusting the decision policy function, the authors claim that the decisions can better improve fairness and disincentivize manipulation. Both theoretical analysis and empirical simulations are provided.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "- To highlight the significance of the contribution, the authors should be more specific with what their main take-aways are. E.g., the current summary of contribution names \"how adjusting .. preferences can affect ... fairness\". If there is any real insights for practitioners here, they are worth explicitly describing upfront.\n- While I like the decomposition of $\\Phi$ into the three components and the interpretation of them, I believe it can be beneficial to explain further with a concrete motivating example what each terms mean. This can be important since few, if any, of the terms in the expression are directly observable; some sort of statistical estimation or model fitting is required. While this estimation aspect may seem tangential to the main purpose of the paper, it is central to any applications of the results. (If I understand correctly, in the FICO experiment, these quantities are again computed from certain distributions of the authors' choice, rather than estimated from data.)\n- [Minor] Further proofreading can be useful (e.g., formatting issues with quotation marks).", "broader_impact_concerns": "The topic studied in this paper is related to the fairness in algorithmic decisions. I believe the discussion in this paper may contribute to better understanding of how to battle manipulation (e.g., cheating) in real world scenarios. No additional concerns noticed.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "R8zzc8WYyd", "reviewer": "Reviewer_FRV2", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Overall, the paper tackles a central problem in the interface of machine learning and game theory concerning strategic classification and naturally continues a long line of research on the subject; the topic is certainly of interest to the TMLR audience. In particular, the paper introduces a new model that is able to provide insights concerning important considerations in the context of actual applications, most notably the presence of unforeseeable outcomes; this differentiates the paper from much of the prior work. I also found the motivating examples the authors provide quite convincing (although it would be nice if the authors could include the examples in the appendix to the introduction, space limitations notwithstanding). The model is overall cleanly presented in a self-contained manner, without assuming familiarity with prior related papers. Moreover, the decomposition derived by the authors is quite informative, and cleanly conveys several insights about the problem, in particular concerning the impact of different preferences from the side of the decision maker, which the authors discuss in detail. All of the mathematical statements are informative and are discussed and explained in detail. A particularly interesting result is Theorem 4.6, which shows how fairness properties are affected by adjusting preferences. All statements appear to be sound, and I did not find any notable issues. The experiments are also quite thorough and support the theoretical findings.\n\nIn terms of weaknesses, the authors could do a better job of explaining the novelty of the introduced model in relation to prior work. That is, to explain clearly all aspects of the model that were introduced in prior work, and everything that is new. My understanding is that the model builds on, among others, Zhang et al. (2022), with some additions. I believe the authors can make this more clear in the revision. Besides this issue, one weakness is that all of the mathematical derivations are very straightforward, suggesting that the results are not too deep. Although the paper draws some interesting conclusions, one wonders whether those conclusions are fundamental or are just an artifact of the modeling assumptions. Finally, discussion regarding related literature is oftentimes lacking. For example, in the introduction it is claimed that prior work assumes that \"individuals can perfectly foresee the outcomes of their behaviors when they best respond\", but I believe that there are certain exceptions to that. For example, see Harris et al. (\"Bayesian persuasion for algorithmic recourse\"). Moreover, in the related work section in the appendix, I expected to see a more detailed discussion regarding certain related papers, in particular about the papers cited after \"there are other studies considering both strategic manipulation and improvement\" since they seem very much related.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper introduces a new model to capture improvement and manipulation (in the context of strategic classification) based on a Stackelberg game between the decision maker and the participants. It provides a characterization of the best response policies, and decomposes the objective between non-strategic and strategic policies in terms of certain interpretable and natural terms that provide several insights. Based on this, the authors study how the preferences of the decision maker affects the optimal policy and its fairness properties. Finally, the theoretical results are validated through a series of experiments.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "I expect to see the following changes:\n\n- A more clear explanation regarding the novelty of the model, clarifying which components were introduced in prior work and what is new.\n- A more detailed discussion about some of the related work (see above).\n\nI also have the following minor comments:\n\n- Page 17: strategic manipulation means intervening -> Strategic manipulation means intervening\n- The citations format is often used incorrectly: when using parenthesis, the citation should not be syntactically part of the sentence.", "broader_impact_concerns": "The paper adequately addresses concerns regarding the ethical implications of the work.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "ReX2vgAqiI", "reviewer": "Reviewer_69Tp", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "I think the paper is well-written, the problem setup is clear, and the results are interesting. I did not fully check the proofs, but the theorem statements and experimental results both seem reasonable to me.\n\nAs someone who does not work in the space of strategic classification, I am not well-placed to judge the novelty of the work; I will leave that to the other reviewer(s) who might have more problem-specific knowledge.\n\nMy main criticism is that some of the assumptions of the paper seem to be not sufficiently justified:\n\n1. In Footnote 3/Appendix B.3 it states that agents will always choose to either manipulate or improve. But this does not seem true to me, even in the model studied in the paper: for example, if $C_M, C_I > 1$ then clearly the agent should choose to do neither. If the assumption is that $C_M$ and $C_I$ are always small enough that at least one of the two actions is preferable to doing nothing, this should be stated (and perhaps analyzed---for example, in what regime of $C_M, C_I$ is this the case?)\n2. Why aren't agents allowed to know their own feature $x$? In real situations, it seems logical for e.g. students to be able to know roughly how well they will do on an exam, e.g., by taking practice exams. Similarly, it is strange to me that the agents' ability to improve is completely decoupled from their current feature. For example, higher-feature agents ought to be able to improve either a larger amount (i.e., have better posterior features given success), and/or improve at lower cost (i.e., $C_I$ should be negatively correlated with $x$). \n3. Is it reasonable to assume that the decision-making policy $\\pi$ is deterministic? Especially when discussing fairness, where pure classifiers often cannot achieve certain fairness guarantees, randomized policies might be able to do better.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studies a model of strategic binary classification of agents using a threshold-based classifier, in which unqualified (negative-label) agents can choose to either attempt to *manipulate* their features (succeeding and imitating a qualified candidate), or to *improve* their features (thereby actually becoming a qualified candidate). Each action has a probability of failure: failing to manipulate results in immediate rejection, and failure to improve results in the agent's label not changing (but possibly the features changing, according to a known distribution). The paper then presents various results about how the decision-maker's choice of threshold is related to various other quantities.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "The most crucial change (critical to securing my recommendation) is that I would want to see more discussion of the various assumptions made by the paper and either (1) why they are justified or (2) some analysis of what happens in the case where they are broken (or both).\n\nRelatively minor notes, questions, and nitpicks, in no particular order, that I would like clarification on:\n1. Some of the plots (Figs 14, 19, and 20) exhibit very strange \"jumpy\" behavior in $\\theta$ as a function of the given parameter. It seems reasonably likely to me that this behavior is nothing but a function of \"numerical precision\"-type issues when dealing with thresholds that are 6+ standard deviations away from the means. Perhaps it would be more instructive/illuminating to, for example, set the bounds of the $\\theta$ axis at a reasonable range like $[-5, +5]$, to remove these numerical issues.\n2. Regarding the assumptions of continuity of various distributions (2.2 and parts of 2.1): are these assumptions made for clarity/simplicity of exposition, or are they somehow technically vital to the results? Phrased another way, could you obtain the same or similar results without these continuity assumptions?\n3. In Section 3, what is the use of specifying a number $u$ for the decision-maker's utility of making a correct decision? Isn't it WLOG to assume $u=1$?", "broader_impact_concerns": "none", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper tackles the problem of machine learning under strategic behavior of participants who may manipulate their features to try and game the system. The paper relaxes common assumptions in prior literature on this topic with a proposed model where participants cannot easily guess the outcomes of counterfactual features, and instead, imitate other participants with positive labels as a proxy. This model and associated results are certainly of interest to a non-trivial subset of TMLR's audience. The reviewers have provided thorough reviews and are convinced of the correctness of the results, thereby meeting TMLR's criteria.
Decision: Accept (poster)