As machine learning (ML) models are increasingly used in social domains to make consequential decisions about humans, they often have the power to reshape data distributions. Humans, as strategic agents, continuously adapt their behaviors in response to the learning system. As populations change dynamically, ML systems may need frequent updates to ensure high performance. However, acquiring high-quality human-annotated samples can be highly challenging and even infeasible in social domains. A common practice to address this issue is using the model itself to annotate unlabeled data samples. This paper investigates the long-term impacts when ML models are retrained with model-annotated samples when they incorporate human strategic responses. We first formalize the interactions between strategic agents and the model and then analyze how they evolve under such dynamic interactions. We find that agents are increasingly likely to receive positive decisions as the model gets retrained, whereas the proportion of agents with positive labels may decrease over time. We thus propose a refined retraining process to stabilize the dynamics. Last, we examine how algorithmic fairness can be affected by these retraining processes and find that enforcing common fairness constraints at every round may not benefit the disadvantaged group in the long run. Experiments on (semi-)synthetic and real data validate the theoretical findings.

§ DYNAMICS OF THE AGENTS AND MODEL

In this section, we examine the evolution of qualification rate $q_t$, acceptance rate $a_t$, and classifier bias $\Delta_t$. We aim to understand how applicant welfare (Sec. <ref>), social welfare (Sec. <ref>), and decision-maker welfare (Sec. <ref>) are affected by the retraining process in the long run. We first introduce some assumptions used for the theorems.

Because the acceptance rate $a_t:=\E_{\mathcal{S}_t}\left[A(f_t,P^t)\right]$ and qualification rate $q_{t}:=\E_{\mathcal{S}_{t-1}}[Q(P^t)]$ depend on agent post-best-response distribution $P^t_{XY}$ and the classifiers, we can first identify all sources that affect the evolution of these quantities (details are in App. <ref>):

* $\overline{q}_t$: Expected qualification rate of agents in training set.

* $\delta(D^t,\mathcal{F})$ : Algorithmic bias that measures how well hypothesis class $\mathcal{F}$ can approximate the training data distribution $D^t_{Y|X}$. It universally exists in the PAC learning framework.

* $\delta^t_{BR}$: Strategic shift caused by agents' best responses to $f_{t-1}$ at $t$. what does it mean; why do we need to introduce these sources. Can we express algorithmic bias mathematically

Note that $\delta^t_{BR}$ and $\overline{q}_t$ closely affect each other and cannot be decoupled quantitatively. Meanwhile, $\delta(D^t,\mathcal{F})$ only depends on how well the hypothesis class $\mathcal{F}$ fits $P^t_{Y|X}$. Since $\mathcal{F}$ is pre-determined, we ignore $\delta(D^t,\mathcal{F})$ in our theoretical analysis (Assumption <ref>).

Hypothesis class $\mathcal{H}$ can perfectly learn the training data distribution $D^t_{Y|X}$, i.e., $\exists h^*_t\in\mathcal{H}$ such that $h_t^*(x) = D^t_{Y|X}(1|x)$.

With Assumption <ref>, we avoid the effects of learning error on the system dynamics; this allows us to focus on the dynamic interactions between strategic agents and ML system.
Although the theoretical analysis relies on the assumption, our experiments in Sec. <ref> and App. <ref> show consistent results with theorems. We further assume the monotone likelihood ratio property holds for $D^o_{XY}$ and $P_{XY}$.

Let $x[m]$ be the $m^{th}$ dimension of $x\in\mathbb{R}^d$, then $D^o_{Y|X}(1|x)$ and $P_{Y|X}(1|x)$ are continuous and monotonically increasing in $x[m],~\forall m=1,\cdots,d$ while other dimensions are fixed.

Note that the Assumption <ref> is mild and widely used in previous literature [Zhang et al., 2022, Raab and Liu, 2021]. It can be satisfied by many distributional families such as exponential, Gaussian, and mixtures of exponential/Gaussian. It implies that agents are more likely to be qualified as feature value increases.

§.§ Applicant welfare: dynamics of acceptance rate

We first examine the dynamics of $a_t=\E_{\mathcal{S}_t}\left[A(f_t,P^t)\right]$.
Intuitively, under Assumption <ref>, all classifiers can fit the training data well. Then the model-annotated samples $\mathcal{S}_{m,t-1}$ generated from post-best-response agents would have a higher qualification rate than the qualification rate of training data $\mathcal{S}_{t-1}$. As a result, the training data $\mathcal{S}_{t}$ augmented with $\mathcal{S}_{m,t-1}$ has a higher proportion of qualified agents than the qualification rate of $\mathcal{S}_{t-1}$, thereby producing a more "generous" classifier $f_t$ with a larger $a_t$. This reinforcing process can be formally stated in Thm. <ref>.

Under the retraining process, the acceptance rate of the agents that join the system increases over time, i.e.,  $a_t > a_{t-1}$,  $\forall t\geq 1$.

Increasing acceptance rate from $a_t$ to $a_{t+1}$. Unqualified/qualified agents are shown as circles/squares, while the admitted/rejected agents are shown in red/blue. New agents coming at $t+1$ are shown in hollow. The left plot shows the training set $\mathcal{S}_t$ containing 2 unqualified (red circle) and 2 qualified agents (blue square) and $a_t$ is 0.5. The middle plot shows the agents coming at $t$ best respond to $f_{t-1}$. After the responses, 3 of 4 agents are qualified (blue square) and 1 is still unqualified (blue circle). However, all 4 agents are annotated as "qualified" (blue). The right plot shows the training set $\mathcal{S}_{t+1}$ containing all points of the left and middle plot, plus two new human-annotated points (hollow points). All blue points are labeled as 1 and the red points are 0. So the qualification rate of $\mathcal{S}_{t+1}$ gets larger and $f_{t+1}$ accepts a higher proportion of agents ($a_{t+1}$ is 0.58).

We prove Thm. <ref> by mathematical induction in App. <ref> and Fig. <ref> illustrates the theorem. When agents best respond, the decision-maker tends to accept more agents. We can further show that when the number of model-annotated samples $N$ is large compared to the number of human-annotated samples $K$, the classifier will ultimately accept all agents in the long run (Prop. <ref>).

For any $P_{XY}, D^o, B$, there exists a threshold $\lambda > 0$ such that $\lim_{t \to \infty}a_t = 1$ whenever $\frac{K}{N} < \lambda$.

The specific value of $\lambda$ in Prop. <ref> depends on $P_{XY}, D^o, B$, which is difficult to find analytically. Nonetheless, we illustrate in Sec. <ref> that when $\frac{K}{N} = 0.05$, $a_t$ tends to approach $1$ in numerous datasets. Since the human-annotated samples are often difficult to attain (due to time and labeling costs), the condition in Prop. <ref> is easy to satisfy in practice.

§.§ Social welfare: dynamics of qualification rate

Next, we study the dynamics of qualification rate $q_t=\E_{\mathcal{S}_{t-1}}[Q(P^t)]$. Unlike the acceptance rate $a_t$ which always increases during the retraining process, the evolution of $q_t$ is more complicated and depends on agent prior-best-response distribution $P_{XY}$.

Specifically, let $q_0 = Q(P) = \E_{(x,y) \sim P_{XY}}[y]$ be the initial qualification rate, then the difference between $q_t$ and $q_0$ can be interpreted as the amount of improvement (i.e., increase in label) agents gain from their strategic behavior at $t$. This is determined by (i) the proportion of agents that decide to change their features at costs (depends on $P_X$), and (ii) the improvement agents can expect upon changing features (depends on $P_{Y|X}$). Thus, the dynamics of $q_t$ depend on $P_{XY}$.
Despite the intricate nature of dynamics, we can still derive a  condition under which $q_t$ decreases monotonically.

Let $F_X(x)$ be the cumulative density function corresponding to $P_X$. Denote $\mathcal{J} = \{x | f_0(x) = 0\}$  as the half-space in  $\mathbb{R}^d$ determined by the classifier $f_0$ trained  with $\mathcal{S}_{o,0}$. Under the retraining process, if $F_X$ and $P_{Y|X}(1|x)$ are convex on $\mathcal{J}$, then $q_{t+1} < q_{t}$, $\forall t \ge 1$.

Note that $q_{t+1}<q_t$ in Thm. <ref> holds only for $t\geq 1$. Because agent behavior can only improve their labels, prior-best-response
$q_0$ always serves as the lower bound of $q_t$. The half-space $\mathcal{J}$ in Thm. <ref> specifies the region in feature space where agents have incentives to change their features. The convexity of $F_X$ and $P_{Y|X}(1|x)$ ensure that as $f_t$ evolves from $t=1$: (i) fewer agents choose to improve their features, and (ii) agents expect less improvement from feature changes. Thus, $q_t$ decreases over time. Conditions in Thm. <ref> can be satisfied by common distributions $P_X$ (e.g., Uniform, $\text{Beta}(\alpha,\beta)$ with $\alpha>\beta$) and labeling functions $P_{Y|X}(1|x)$ (e.g., linear function, quadratic functions with degree greater than 1). The proof and a more general analysis are shown in App. <ref>. We also show that Thm. <ref> is valid under diverse experimental settings (Sec. <ref>, App. <ref>, App. <ref>).

§.§ Decision-maker welfare: dynamics of classifier bias

Sec. <ref> and <ref> show that as the classifier $f_t$ gets updated over time, agents are more likely to get accepted ($a_t$ increases). However, their true qualification rate $q_t$ (after the best response) may actually decrease. It indicates that the decision-maker's misperception about agents varies over time. Thus, this section studies the dynamics of classifier bias $\Delta_t = |a_t - q_t|$. Our results show that the evolution of $\Delta_t$ is largely affected by the decision-maker's systematic bias $\mu(D^o,P)$ as defined in Def. <ref>.

Under the retraining process and the conditions in Thm. <ref>:

* If $\mu(D^o,P)=0$, i.e., the systematic bias does not exist, then $\Delta_t$ increases over time.

* If $\mu(D^o, P) > 0$, i.e., the decision-maker overestimates agent qualification, then $\Delta_t$ increases over time.

* If $\mu(D^o, P) < 0$, i.e., the decision-maker underestimates agent qualification, then $\Delta_t$ either monotonically decreases or first decreases but then increases.

Thm. <ref> highlights the potential risks of the model retraining process and is proved in App. <ref>. Originally, the purpose of retraining the classifier was to ensure accurate decisions on the targeted population. However, when agents behave strategically, the retraining may lead to adverse outcomes by amplifying the classifier bias. Meanwhile, though systematic bias is usually an undesirable factor to eliminate when learning ML models, it may help mitigate classifier bias to improve the decision-maker welfare in the retraining process, i.e., $\Delta_t$ decreases when  $\mu(D^o, P) < 0$.

§.§ Intervention to stabilize the dynamics

Sec. <ref>- <ref> show that as the model is retrained from strategic agents, $a_t, q_t, \Delta_t$ are unstable and may change monotonically over time. Next, we introduce an effective approach to stabilizing the system.

From the above analysis, we know that one reason that makes $q_t$, $a_t$, $\Delta_t$ evolve is agent's best response, i.e.,   agents improve their features strategically to be accepted by the most recent model, which leads to a higher qualification rate of model-annotated samples (and the resulting training data), eventually causing $a_t$ to deviate from $q_t$. Thus, to mitigate such deviation, we can improve the quality of model annotation. Our method is proposed based on this idea, which uses a probabilistic sampler [Taori and Hashimoto, 2023] when producing model-annotated samples.

Specifically, at each time $t$, instead of adding $\mathcal{S}_{m-1,o} = \{x_{t-1}^i,f_{t-1}(x_{t-1}^i)\}_{i=1}^N$ (samples annotated by the model $f_{t-1}$) to training data $\mathcal{S}_t$ ((<ref>)), we use the probabilistic model $h_{t-1}(x)$ to annotate each sample according to the following: For each sample $x$, we label it as $1$ with probability $h_{t-1}(x)$, and as 0 otherwise. Here $h_{t-1}(x)\approx D^{t-1}_{Y|X}(1|x)$ is the estimated posterior probability learned from $\mathcal{S}_{t-1}$ (e.g., using logistic model). We call the procedure refined retraining process if model-annotated samples are generated in this way based on a probabilistic sampler.

Fig. <ref> also illustrates the above idea: agents best respond to $f_{t-1}$ (middle plot) to improve and $f_t$ will label both as $1$. By contrast, a probabilistic sampler $h_t$ only labels a fraction of them as $1$. This alleviates the influence of agents' best responses to stabilize the dynamics of $a_t, q_t, \Delta_t$. Prop. <ref> and App. <ref> provide proofs and more experiments for the refined retraining process.

§ IMPACTS ON ALGORITHMIC FAIRNESS

In this section, we further consider agents from multiple social groups and investigate how group fairness can be affected by the model retraining process. Similar to prior studies in fair ML [Zhang et al., 2020, Zhang et al., 2022, Liu et al., 2020], we assume the decision-maker knows the group identity of each agent and uses group-dependent classifiers to make decisions. WLOG, we present the results for any pair of two groups $i,j$. Among the two groups, we define the group with a smaller acceptance rate under unconstrained optimal classifiers as disadvantaged group.

§.§ Impacts of systematic bias & model retraining
We first consider the situation where two groups have no innate difference: they have the same prior-best-response feature distribution and the same cost matrix $B$ to change features. However, the decision-maker has a systematic bias in favor of group $i$ more than group $j$, making $i$ the advantaged group and $j$ the disadvantaged group. We consider the fairness metric demographic parity () [Feldman et al., 2015], which measures unfairness as the difference in acceptance rate across two groups.  Extension to other fairness metrics such as equal opportunity [Hardt et al., 2016] is discussed in App. <ref>. Thm. <ref> below shows the long-term impacts of refined retraining process (i.e., model-annotated samples generated with probabilistic sampler $h_t$) and original model retraining process (i.e., model-annotated samples generated with model $f_t$) on group unfairness.

When groups $i,j$ have no innate difference, but $j$ is disadvantaged due to systematic bias: (i) If applying original retraining process to both groups with $\frac{K}{N}$ satisfying Prop. <ref>, then group $j$ will stay disadvantaged until all agents in both groups are accepted to achieve perfect fairness; (ii) If applying  refined retraining process to both groups, then group $j$ will stay disadvantaged and the unfairness remains the same in the long run; (iii) If applying refined retraining process to group $i$ but the original process to group $j$ with $\frac{K}{N}$ satisfying Prop. <ref>, then unfairness first decreases after certain rounds of retraining until group $j$ becomes advantaged, then unfairness increases.

Unfairness () when the refined retraining process is applied to both groups (left), original retraining process is applied to both groups (middle), refined retraining process is only applied to group $i$ (right) under dataset 2.

Thm. <ref> shows that original and refined retraining processes impact differently on group fairness as proved in App. <ref>. Specifically, the original retraining process ultimately attains "trivial" perfect fairness by accepting all agents, whereas the refined retraining process stabilizes the dynamics but unfairness always exists. Interestingly, applying disparate retraining strategies to two groups may result in perfect fairness in the middle of retraining process. This suggests that it may be beneficial for the decision-maker to monitor the fairness measure during the retraining and execute an early stopping mechanism to attain almost perfect  fairness, i.e., stop retraining models early once unfairness reaches the minimum. As shown in the right plot of Fig. <ref>, when refined retraining is only applied to group $i$, unfairness is minimized at $t=5$.

§.§ Impact of short-term fairness intervention

Sec. <ref> proposed a solution of "disparate retraining with early stopping" to mitigate unfairness. A more common method to maintain fairness throughout the retraining process is to enforce certain fairness constraints every time when updating the models. Next, we consider this method where refined retraining process is applied to both groups (to stabilize dynamics) and a fairness constraint is imposed at each round of model retraining. Unlike Sec. <ref>, we consider a general setting where two groups may have different feature distributions and different cost matrices $B$, but feature-label relation $P_{Y|X}(1|x)$ is the same across groups.

Finding fair models. For each group $s$, we use superscript $s$ to denote the group-specific distributions/metrics listed in Sec. <ref> (e.g., $P_{XY}^{s,t}$). At each round $t$, the decision-maker first trains a linear model $f_t^s = \mathbf{1}(h_t^s(x) \ge \theta)$ for group $s$. According to Assumption <ref> and Prop. <ref>, $h_t^s$ is expected to be $D^{o,s}_{Y|X}(1|x) = P^s_{Y|X}(1|x) + \mu_s$, where $\mu_s$ is the systematic bias towards group $s$. Denote $\theta_t^s$ as the original optimal threshold at $t$ without the fairness intervention, and let $a_t^s$ be the acceptance rate for group $s$ under $\theta_t^s$, then the decision-maker can tune the thresholds to get fair-optimal thresholds $\widetilde{\theta}_t^s$ (a pair of thresholds satisfying the fairness constraint with the largest aggregated accuracy).

Noisy agent best response. To ensure there always exists a pair of thresholds that satisfy  fairness constraint (i.e., equal acceptance rate), each group's post-best-response distribution needs to be continuous. However, when agents modify their features based on (<ref>), the
aggregate response
necessarily exhibits discontinuities [Jagadeesan et al., 2021]. To tackle this issue, we consider the noisy best response model proposed by Jagadeesan et al., 2021, which assumes the agents only have imperfect and noisy information of decision threshold. Formally, given decision threshold $\theta$, each agent best responds to $\theta + \epsilon$ where $\epsilon$ is a noise independently sampled from a zero mean distribution with finite variance $\sigma^2$. Under noisy best response, we investigate the impacts of fairness intervention.

Suppose group $j$ is disadvantaged from round $0$ to $t$, i.e., group $j$ has a smaller acceptance rate than group $i$ under unconstrained optimal thresholds $\{\theta_\tau^i, \theta_\tau^j\}$, $\forall \tau\leq t$. Let $\sigma_t^2$ be the variance of the noisy best response at $t$. We have the following:

(i) Without fairness intervention, $\forall \sigma_t$, always there exists feature distributions and cost matrices under which group $j$ switches to be advantaged at $t+1$

(ii) With fairness intervention, if $\sigma_t < (\theta_t^j - \widetilde{\theta}_t^j)\sqrt{a_0^i - a_t^j}$, then group $j$ always remains disadvantaged at $t+1$.

Thm. <ref> shows that without fairness intervention, the originally disadvantaged group $j$ can flip to be advantaged. In contrast, the fairness intervention helps maintain the disadvantaged and advantaged groups when the agent's perception of the decision rule is sufficiently accurate.

Note that the bound on $\sigma$ is well-defined. Since group $j$ is disadvantaged, $a_0^i > a_0^j$ always holds. If $\sigma_t < (\theta_t^j - \widetilde{\theta}_t^j)\sqrt{a_0^i - a_t^j}$ holds, then it is guaranteed that $a_0^i > a_{t+1}^j$ (see App. <ref> for details).

This result implies that the disadvantaged group, by losing their chance to become advantaged, may not benefit from fairness intervention in the long run.

§ EXPERIMENTS

We conduct experiments on two synthetic (Uniform, Gaussian), one semi-synthetic (German Credit [Hofmann, 1994]), and one real dataset (Credit Approval [Quinlan, 2017]) to validate the dynamics of $a_t, q_t, \Delta_t$ and the unfairness. Note that only the Uniform dataset satisfies all assumptions and the conditions in our theoretical analysis, while the Gaussian and German Credit datasets violate the conditions in Thm. <ref>. The Credit Approval dataset violates all assumptions and conditions of the main paper. The decision-maker trains logistic regression models for all experiments using stochastic gradient descent (SGD) over $T$ steps. We present the experimental results of the Gaussian and German Credit datasets to illustrate the dynamics of $a_t, q_t, \Delta_t$ in this section, while the results for Uniform and Credit Approval data are similar and shown in App. <ref>.

Gaussian Dataset Setting

$P_{X_k}(x_k)$      $P_{Y|X}(1|x)$     $n,r,T,q_0$

$\mathcal{N}(0,0.5^2) $     $(1+\exp(x_1+x_2))^{-1}$     $100,0.05,15,0.5$

Gaussian data. We consider a synthetic dataset with Gaussian distributed $P_{X}$. $P_{Y|X}$ is logistic and satisfies Assumption <ref> but not the conditions of Thm. <ref>. We assume agents have two independent features $X_1, X_2$ and are from two groups $i,j$ with different sensitive attributes but identical joint distribution $P_{XY}$. Their cost matrix is $B = \begin{bmatrix}
5 & 0\\
0 & 5
\end{bmatrix}$ and the initial qualification rate is $q_0 = 0.5$. We assume the decision-maker has a systematic bias by overestimating (resp. underestimating) the qualification of agents in the advantaged group $i$ (resp. disadvantaged group $j$), which is modeled as increasing $D^o_{Y|X}(1|x)$ to be 0.1 larger (resp. smaller) than $P_{Y|X}(1|x)$ for group $i$ (resp. group $j$). For the retraining process, we let $r = \frac{K}{N} = 0.05$ (i.e., the number of model-annotated samples $N = 2000$, which is sufficiently large compared to the number of human-annotated samples $K = 100$). Table <ref> summarizes the dataset information, and the joint distributions are visualized in App. <ref>.

We verify the results in Sec. <ref> by illustrating the dynamics of $a_t, q_t, \Delta_t$ for both groups (Fig. <ref>). Since our evolution results are in expectation, we perform $n=100$ independent runs of experiments for every parameter configuration and show the averaged outcomes. The results are consistent with Thm. <ref>, <ref> and <ref>: (i) acceptance rate $a_t$ (red curves) increases monotonically; (ii) qualification rate $q_t$ decreases monotonically starting from $t= 1$ (since strategic agents only best respond from $t=1$); (iii) classifier bias $\Delta_t$ evolves differently for different groups and it may reach the minimum after a few rounds of retraining.

We further test the robustness of system dynamics against agent noisy response, where we assume agents estimate their outcomes as $\widehat{f}_t(x) = f_t(x) + \epsilon$ with $\epsilon \sim \mathcal{N}(0,0.1)$. We present the dynamics of $a_t, q_t, \Delta_t$ for both groups in Fig. <ref> which are similar to Fig. <ref>, demonstrating the robustness of our theorems.

German Credit dataset [Hofmann, 1994]. This dataset includes features for predicting individuals' credit risks. It has 1000 samples and 19 numeric features, which are used to construct a larger-scaled dataset. Specifically, we fit a kernel density estimator for all 19 features to generate  19-dimensional features, the corresponding labels are sampled from the distribution $P_{Y|X}$ which is estimated from data by fitting a logistic classifier with 19 features. Given this dataset, the first 10 features are used to train the classifiers. The attribute "sex" is regarded as the sensitive attribute. The systematic bias is created by increasing/decreasing $P_{Y|X}$ by $0.05$. Other parameters $n,r,T,q_0$ are the same as Table <ref>. Since $P_{Y|X}$ is a logistic function, Assumption <ref> can be satisfied easily as illustrated in App. <ref>.

We verify the results in Sec. <ref> by illustrating the dynamics of $a_t, q_t, \Delta_t$ for both groups (Fig. <ref>). The results are consistent with Thm. <ref>, <ref> and <ref>: (i) acceptance rate $a_t$ (red curves) always increases; (ii) qualification rate $q_t$ (blue curves) decreases starting from $t =1$ (since strategic agents only best respond from $t=1$); (iii) classifier bias $\Delta_t$ (black curves) evolve differently for different groups. Finally, similar to Fig. <ref>, Fig. <ref> demonstrates the results are still robust under the noisy setting.

Gaussian: group $i$ (left) and $j$ (right)

German: group $i$ (left) and $j$ (right)

Dynamics of $a_t, q_t,\Delta_t$ under the perfect information setting

Gaussian: for group $i$ (left) and $j$ (right)

German: group $i$ (left) and $j$ (right)

Dynamics of $a_t, q_t,\Delta_t$ under the noisy setting

Additional experiments. We provide more results in App. <ref> to: (i) verify Thm. <ref> and Thm. <ref>; (ii) Visualize the influence of each factor including training rounds, cost matrices, the ratio between human-annotated and model-annotated samples, and whether the agents are strategic; (iii) visualize the evolution of unfairness when different retraining strategies are applied to different groups.

§ CONCLUSION & LIMITATIONS

This paper studies the dynamics where strategic agents interact with an ML system retrained over time with model-annotated and human-annotated samples. We rigorously studied the evolution of applicant welfare, decision-maker welfare, and social welfare. Such results highlight the potential risks of retraining classifiers when agents are strategic. The paper also provides a comprehensive analysis on the fairness dynamics associated with the retraining process, revealing that the fairness intervention may not bring long-term benefits. To ease the negative social impacts, we provide mechanisms to stabilize the dynamics and an early stopping mechanism to maintain fairness. However, our theoretical results rely on certain assumptions and we should first verify these conditions before adopting the results of this paper, which may be challenging in real-world applications.

[Hardt et al., 2016]
Moritz Hardt, Nimrod Megiddo, Christos Papadimitriou, and Mary Wootters.
Strategic classification.
In Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science, page 111–122, 2016a.

[Levanon and Rosenfeld, 2022]
Sagi Levanon and Nir Rosenfeld.
Generalized strategic classification and the case of aligned incentives.
In International Conference on Machine Learning, ICML 2022, 17-23 July 2022, Baltimore, Maryland, USA, pages 12593–12618, 2022.

[Taori and Hashimoto, 2023]
Rohan Taori and Tatsunori Hashimoto.
Data feedback loops: Model-driven amplification of dataset biases.
In Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pages 33883–33920, 2023.

[Adam et al., 2022]
George Alexandru Adam, Chun-Hao Kingsley Chang, Benjamin Haibe-Kains, and Anna Goldenberg.
Error amplification when updating deployed machine learning models.
In Proceedings of the Machine Learning for Healthcare Conference, Durham, NC, USA, pages 5–6, 2022.

[Dong et al., 2018]
Jinshuo Dong, Aaron Roth, Zachary Schutzman, Bo Waggoner, and Zhiwei Steven Wu.
Strategic classification from revealed preferences.
In Proceedings of the 2018 ACM Conference on Economics and Computation, page 55–70, 2018.

[Ahmadi et al., 2021]
Saba Ahmadi, Hedyeh Beyhaghi, Avrim Blum, and Keziah Naggita.
The strategic perceptron.
In Proceedings of the 22nd ACM Conference on Economics and Computation, pages 6–25, 2021.

[Chen et al., 2020]
Yiling Chen, Yang Liu, and Chara Podimata.
Learning strategy-aware linear classifiers.
Advances in Neural Information Processing Systems, 33:0 15265–15276, 2020a.

[Guldogan et al., 2022]
Ozgur Guldogan, Yuchen Zeng, Jy-yong Sohn, Ramtin Pedarsani, and Kangwook Lee.
Equal improvability: A new fairness notion considering the long-term impact.
In The Eleventh International Conference on Learning Representations, 2022.

[Zrnic et al., 2021]
Tijana Zrnic, Eric Mazumdar, Shankar Sastry, and Michael Jordan.
Who leads and who follows in strategic classification?
Advances in Neural Information Processing Systems, pages 15257–15269, 2021.

[Kleinberg and Raghavan, 2020]
Jon Kleinberg and Manish Raghavan.
How do classifiers induce agents to invest effort strategically?
page 1–23, 2020.

[Zhang et al., 2022]
Xueru Zhang, Mohammad Mahdi Khalili, Kun Jin, Parinaz Naghizadeh, and Mingyan Liu.
Fairness interventions as (Dis)Incentives for strategic manipulation.
In Proceedings of the 39th International Conference on Machine Learning, pages 26239–26264, 2022.

[Raab and Liu, 2021]
Reilly Raab and Yang Liu.
Unintended selection: Persistent qualification rate disparities and interventions.
Advances in Neural Information Processing Systems, pages 26053–26065, 2021.

[Zhang et al., 2020]
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, pages 18457–18469, 2020.

[Liu et al., 2020]
Lydia T Liu, Ashia Wilson, Nika Haghtalab, Adam Tauman Kalai, Christian Borgs, and Jennifer Chayes.
The disparate equilibria of algorithmic decision making when individuals invest rationally.
In Proceedings of the 2020 Conference on Fairness, Accountability, and Transparency, pages 381–391, 2020.

[Feldman et al., 2015]
Michael Feldman, Sorelle A Friedler, John Moeller, Carlos Scheidegger, and Suresh Venkatasubramanian.
Certifying and removing disparate impact.
In proceedings of the 21th ACM SIGKDD international conference on knowledge discovery and data mining, pages 259–268, 2015.

[Hardt et al., 2016]
Moritz Hardt, Eric Price, Eric Price, and Nati Srebro.
Equality of opportunity in supervised learning.
In Advances in Neural Information Processing Systems, 2016b.

[Jagadeesan et al., 2021]
Meena Jagadeesan, Celestine Mendler-Dünner, and Moritz Hardt.
Alternative microfoundations for strategic classification.
In Proceedings of the 38th International Conference on Machine Learning, pages 4687–4697, 2021.

[Hofmann, 1994]
Hans Hofmann.
Statlog (German Credit Data).
UCI Machine Learning Repository, 1994.
DOI: https://doi.org/10.24432/C5NC77.

[Quinlan, 2017]
Quinlan Quinlan.
Credit Approval.
UCI Machine Learning Repository, 2017.
DOI: https://doi.org/10.24432/C5FS30.

[Capers IV et al., 2017]
Quinn Capers IV, Daniel Clinchot, Leon McDougle, and Anthony G Greenwald.
Implicit racial bias in medical school admissions.
Academic Medicine, 920 (3):0 365–369, 2017.

[Alvero et al., 2020]
AJ Alvero, Noah Arthurs, Anthony Lising Antonio, Benjamin W Domingue, Ben Gebre-Medhin, Sonia Giebel, and Mitchell L Stevens.
Ai and holistic review: informing human reading in college admissions.
In Proceedings of the AAAI/ACM Conference on AI, Ethics, and Society, pages 200–206, 2020.

[Bareinboim and Pearl, 2012]
Elias Bareinboim and Judea Pearl.
Controlling selection bias in causal inference.
In Artificial Intelligence and Statistics, pages 100–108, 2012.

[Brock and De Haas, 2023]
J Michelle Brock and Ralph De Haas.
Discriminatory lending: Evidence from bankers in the lab.
American Economic Journal: Applied Economics, 150 (2):0 31–68, 2023.

[Ben-Porat and Tennenholtz, 2017]
Omer Ben-Porat and Moshe Tennenholtz.
Best response regression.
In Advances in Neural Information Processing Systems, 2017.

[Braverman and Garg, 2020]
Mark Braverman and Sumegha Garg.
The role of randomness and noise in strategic classification.
CoRR, abs/2005.08377, 2020.

[Izzo et al., 2021]
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, pages 4641–4650, 2021.

[Tang et al., 2021]
Wei Tang, Chien-Ju Ho, and Yang Liu.
Linear models are robust optimal under strategic behavior.
In Proceedings of The 24th International Conference on Artificial Intelligence and Statistics, volume 130 of Proceedings of Machine Learning Research, pages 2584–2592, 13–15 Apr 2021.

[Eilat et al., 2022]
Itay Eilat, Ben Finkelshtein, Chaim Baskin, and Nir Rosenfeld.
Strategic classification with graph neural networks, 2022.

[Liu et al., 2022]
Lydia T. Liu, Nikhil Garg, and Christian Borgs.
Strategic ranking.
In Proceedings of The 25th International Conference on Artificial Intelligence and Statistics, pages 2489–2518, 2022.

[Lechner and Urner, 2022]
Tosca Lechner and Ruth Urner.
Learning losses for strategic classification.
arXiv preprint arXiv:2203.13421, 2022.

[Horowitz and Rosenfeld, 2023]
Guy Horowitz and Nir Rosenfeld.
Causal strategic classification: A tale of two shifts, 2023.

[Harris et al., 2021]
Keegan Harris, Hoda Heidari, and Steven Z Wu.
Stateful strategic regression.
Advances in Neural Information Processing Systems, pages 28728–28741, 2021.

[Bechavod et al., 2022]
Yahav Bechavod, Chara Podimata, Steven Wu, and Juba Ziani.
Information discrepancy in strategic learning.
In International Conference on Machine Learning, pages 1691–1715, 2022.

[Jin et al., 2022]
Kun Jin, Xueru Zhang, Mohammad Mahdi Khalili, Parinaz Naghizadeh, and Mingyan Liu.
Incentive mechanisms for strategic classification and regression problems.
In Proceedings of the 23rd ACM Conference on Economics and Computation, page 760–790, 2022.

[Chen et al., 2020]
Yatong Chen, Jialu Wang, and Yang Liu.
Strategic recourse in linear classification.
CoRR, abs/2011.00355, 2020b.

[Haghtalab et al., 2020]
Nika Haghtalab, Nicole Immorlica, Brendan Lucier, and Jack Z Wang.
Maximizing welfare with incentive-aware evaluation mechanisms.
arXiv preprint arXiv:2011.01956, 2020.

[Alon et al., 2020]
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:0 1774–1781, 2020.

[Bechavod et al., 2021]
Yahav Bechavod, Katrina Ligett, Steven Wu, and Juba Ziani.
Gaming helps! learning from strategic interactions in natural dynamics.
In International Conference on Artificial Intelligence and Statistics, pages 1234–1242, 2021.

[Miller et al., 2020]
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.

[Shavit et al., 2020]
Yonadav Shavit, Benjamin L. Edelman, and Brian Axelrod.
Causal strategic linear regression.
In Proceedings of the 37th International Conference on Machine Learning, ICML'20, 2020.

[Harris et al., 2022]
Keegan Harris, Dung Daniel T Ngo, Logan Stapleton, Hoda Heidari, and Steven Wu.
Strategic instrumental variable regression: Recovering causal relationships from strategic responses.
In International Conference on Machine Learning, pages 8502–8522, 2022.

[Yan et al., 2023]
Tom Yan, Shantanu Gupta, and Zachary Lipton.
Discovering optimal scoring mechanisms in causal strategic prediction, 2023.

[Perdomo et al., 2020]
Juan Perdomo, Tijana Zrnic, Celestine Mendler-Dünner, and Moritz Hardt.
Performative prediction.
In Proceedings of the 37th International Conference on Machine Learning, pages 7599–7609, 2020.

[Hardt et al., 2022]
Moritz Hardt, Meena Jagadeesan, and Celestine Mendler-Dünner.
Performative power.
In Advances in Neural Information Processing Systems, 2022.

[Rosenfeld et al., 2020]
Nir Rosenfeld, Anna Hilgard, Sai Srivatsa Ravindranath, and David C Parkes.
From predictions to decisions: Using lookahead regularization.
In Advances in Neural Information Processing Systems, pages 4115–4126, 2020.

[Hall et al., 2022]
Melissa Hall, Laurens van der Maaten, Laura Gustafson, and Aaron Adcock.
A systematic study of bias amplification.
arXiv preprint arXiv:2201.11706, 2022.

[Adebayo et al., 2022]
Julius Adebayo, Melissa Hall, Bowen Yu, and Bobbie Chern.
Quantifying and mitigating the impact of label errors on model disparity metrics.
In The Eleventh International Conference on Learning Representations, 2022.

[Shirali et al., 2022]
Ali Shirali, Rediet Abebe, and Moritz Hardt.
A theory of dynamic benchmarks.
In The Eleventh International Conference on Learning Representations, 2022.

[Leino et al., 2018]
Klas Leino, Emily Black, Matt Fredrikson, Shayak Sen, and Anupam Datta.
Feature-wise bias amplification.
arXiv preprint arXiv:1812.08999, 2018.

[Dinan et al., 2019]
Emily Dinan, Angela Fan, Adina Williams, Jack Urbanek, Douwe Kiela, and Jason Weston.
Queens are powerful too: Mitigating gender bias in dialogue generation.
arXiv preprint arXiv:1911.03842, 2019.

[Wang et al., 2019]
Tianlu Wang, Jieyu Zhao, Mark Yatskar, Kai-Wei Chang, and Vicente Ordonez.
Balanced datasets are not enough: Estimating and mitigating gender bias in deep image representations.
pages 5310–5319, 2019.

[Zhao et al., 2017]
Jieyu Zhao, Tianlu Wang, Mark Yatskar, Vicente Ordonez, and Kai-Wei Chang.
Men also like shopping: Reducing gender bias amplification using corpus-level constraints.
arXiv preprint arXiv:1707.09457, 2017.

[Sculley et al., 2015]
David Sculley, Gary Holt, Daniel Golovin, Eugene Davydov, Todd Phillips, Dietmar Ebner, Vinay Chaudhary, Michael Young, Jean-Francois Crespo, and Dan Dennison.
Hidden technical debt in machine learning systems.
Advances in neural information processing systems, 28, 2015.

[Ensign et al., 2018]
Danielle Ensign, Sorelle A Friedler, Scott Neville, Carlos Scheidegger, and Suresh Venkatasubramanian.
Runaway feedback loops in predictive policing.
In Conference on fairness, accountability and transparency, pages 160–171. PMLR, 2018.

[Mansoury et al., 2020]
Masoud Mansoury, Himan Abdollahpouri, Mykola Pechenizkiy, Bamshad Mobasher, and Robin Burke.
Feedback loop and bias amplification in recommender systems.
In Proceedings of the 29th ACM international conference on information & knowledge management, pages 2145–2148, 2020.

[Adam et al., 2020]
George Alexandru Adam, Chun-Hao Kingsley Chang, Benjamin Haibe-Kains, and Anna Goldenberg.
Hidden risks of machine learning applied to healthcare: Unintended feedback loops between models and future data causing model degradation.
In Proceedings of the 5th Machine Learning for Healthcare Conference, volume 126 of Proceedings of Machine Learning Research, pages 710–731. PMLR, 2020.

[Schmit and Riquelme, 2018]
Sven Schmit and Carlos Riquelme.
Human interaction with recommendation systems.
In International Conference on Artificial Intelligence and Statistics, pages 862–870, 2018.

[Sinha et al., 2016]
Ayan Sinha, David F Gleich, and Karthik Ramani.
Deconvolving feedback loops in recommender systems.
Advances in neural information processing systems, 29, 2016.

[Jiang et al., 2019]
Ray Jiang, Silvia Chiappa, Tor Lattimore, András György, and Pushmeet Kohli.
Degenerate feedback loops in recommender systems.
In Proceedings of the 2019 AAAI/ACM Conference on AI, Ethics, and Society, page 383–390, 2019.

[Gupta et al., 2019]
Vivek Gupta, Pegah Nokhiz, Chitradeep Dutta Roy, and Suresh Venkatasubramanian.
Equalizing recourse across groups, 2019.

[Liu et al., 2019]
Lydia T. Liu, Sarah Dean, Esther Rolf, Max Simchowitz, and Moritz Hardt.
Delayed impact of fair machine learning.
In Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence, IJCAI-19, pages 6196–6200, 2019.

[Dua and Graff, 2017]
Dheeru Dua and Casey Graff.
UCI machine learning repository, 2017.
URL <https://archive.ics.uci.edu/ml/datasets/credit+approval>.

§ THE RETRAINING PROCESS

retraining process

[1]
Joint distribution $D^o_{XY}$ for any $\mathcal{S}_{o,t}$, Hypothesis class $\mathcal{F}$, the number of the initial training samples and agents coming per round $N$, the number of decision-maker-labeled samples per round $K$.
Model deployments over time $f_0, f_1, f_2, \ldots$
$S_0 = S_{o,0} \sim D^o_{XY} = \{x_0^i\}_{i=1}^{N}$
At $t=0$, deploy $f_0 \sim \mathcal{F}(\mathcal{S}_0)$
$t \in \{1,\ldots \infty \}$
$N$ agents gain knowledge of $f_{t-1}$ and best respond to it, resulting in $\{x_{t}^{i}\}_{i=1}^{N}$
$\mathcal{S}_{m,t} = \{x_{t-1}^{i}, f_{t-1}(x_{t-1}^{i})\}_{i=1}^{N}$ consists of the model-labeled samples from round $t-1$.
$\mathcal{S}_{o,t} \sim D^o_{XY}$ consists of the new $K$ decision-maker-labeled samples.
$\mathcal{S}_t = \mathcal{S}_{t-1} \cup  \mathcal{S}_{m,t} \cup \mathcal{S}_{o,t}$
Deploy $f_t \sim \mathcal{F}(\mathcal{S}_t)$ on the incoming $N$ agents who best respond to $f_{t-1}$ with the resulting joint distribution $P^t_{XY}$.

§ MOTIVATING EXAMPLES OF THE SYSTEMATIC BIAS

Def. <ref> highlights the systematic nature of the decision-maker's bias. This bias is quite ubiquitous when labeling is not a trivial task. It almost always the case when the decision-maker needs to make human-related decisions. We provide the following motivating examples of systematic bias with supporting literature in social science:

* College admissions: consider experts in the admission committee of a college that obtains a set of student data and wants to label all students as "qualified" or "unqualified". The labeling task is much more complex and subjective than the ones in computer vision/natural language processing which have some "correct" answers. Therefore, the experts in the committee are prone to bring their "biases" towards a specific population sharing the same sensitive attribute into the labeling process including:

* Implicit bias: the experts may have an implicit bias they are unaware of to favor/discriminate against students from certain groups. For instance, a famous study [Capers IV et al., 2017] reveals admission committee members at the medical school of the Ohio State University unconsciously have a "better impression" towards white students; Alvero et al., 2020 finds out that even when members in an admission committee do not access the sensitive attributes of students, they unconsciously infer them and discriminate against students from the minority group.

* Selection bias: the experts may have insufficient knowledge of the under-represented population due to the selection bias [Bareinboim and Pearl, 2012] because only a small portion of them were admitted before. Thus, experts may expect a lower qualification rate from this population, resulting in more conservative labeling practices. The historical stereotypes created by selection bias are difficult to erase.

* Loan applications: consider experts in a big bank that obtains data samples from some potential applicants and wants to label them as "qualified" or "unqualified". Similarly, the experts are likely to have systematic bias including:

* Implicit bias: similarly, Brock and De Haas, 2023 conduct a lab-in-the-field experiment with over 300 Turkish loan officers to show that they bias against female applicants even if they have identical profiles as male applicants.

* Selection bias: when fewer female applicants are approved historically, the experts have less knowledge on females (i.e., whether they will actually default or repay), thereby tending to stay conservative.

§ RELATED WORK

§.§ Strategic Classification

Strategic classification without label changes. Our work is mainly based on an extensive line of literature on strategic classification [Hardt et al., 2016, Ben-Porat and Tennenholtz, 2017, Dong et al., 2018, Jagadeesan et al., 2021, Levanon and Rosenfeld, 2022, Braverman and Garg, 2020, Izzo et al., 2021, Chen et al., 2020, Ahmadi et al., 2021, Tang et al., 2021, Zhang et al., 2020, Zhang et al., 2022, Eilat et al., 2022, Liu et al., 2022, Lechner and Urner, 2022, Horowitz and Rosenfeld, 2023]. These works assume the agents are able to best respond to the policies of the decision-maker to maximize their utilities. Most works modeled the strategic interactions between agents and the decision-maker as a repeated Stackelberg game where the decision-maker leads by publishing a classifier and the agents immediately best respond to it. The earliest line of works focused on the performance of regular linear classifiers when strategic behaviors never incur label changes [Hardt et al., 2016, Ben-Porat and Tennenholtz, 2017, Dong et al., 2018, Chen et al., 2020], while the later literature added noise to the agents' best responses [Jagadeesan et al., 2021], randomized the classifiers [Braverman and Garg, 2020] and limited the knowledge of the decision-maker [Tang et al., 2021]. Levanon and Rosenfeld, 2022 proposed a generalized framework for strategic classification and a strategic hinge loss to better train strategic classifiers, but the strategic behaviors are still not assumed to cause label changes.

Strategic classification with label changes. Several other lines of literature enable strategic behaviors to cause label changes. The first line of literature mainly focuses on incentivizing improvement actions where agents have budgets to invest in different actions and only some of them cause the label change (improvement) [Kleinberg and Raghavan, 2020, Harris et al., 2021, Bechavod et al., 2022, Jin et al., 2022, Chen et al., 2020, Haghtalab et al., 2020, Alon et al., 2020, Bechavod et al., 2021, Raab and Liu, 2021]. The other line of literature focuses on causal strategic learning [Miller et al., 2020, Shavit et al., 2020, Horowitz and Rosenfeld, 2023, Harris et al., 2022, Yan et al., 2023]. These works argue that every strategic learning problem has a non-trivial causal structure which can be explained by a structural causal model, where intervening on causal nodes causes improvement and intervening on non-causal nodes means manipulation.

Performative prediction. Several works consider performative prediction as a more general setting where the feature distribution of agents is a function of the classifier parameters. Perdomo et al., 2020 first formulated the prediction problem and provided iterative algorithms to find the stable points of the model parameters. Izzo et al., 2021 modified the gradient-based methods and proposed the  algorithm. Hardt et al., 2022 elaborated the model by proposing performative power.

Retraining under strategic settings

Most works on learning algorithms under strategic settings consider developing robust algorithms that the decision-maker only trains the classifier once [Hardt et al., 2016, Tang et al., 2021, Levanon and Rosenfeld, 2022, Jagadeesan et al., 2021], while Performative prediction[Perdomo et al., 2020] focuses on developing online learning algorithms for strategic agents. There are only a few works [Horowitz and Rosenfeld, 2023, Rosenfeld et al., 2020] which permit retraining the Strategic classification models. However, all these algorithms assume that the decision-maker has access to a new training dataset containing both agents' features and labels at each round. There is no work considering the dynamics under the retraining process with model-annotated samples. Also, few works [Liu et al., 2020, Zhang et al., 2020] discussed the long-term fairness issues under sequential strategic settings. Liu et al., 2020 modeled strategic behaviors in a completely different way where each individual decides whether or not (a binary choice) to acquire the desired qualification based on a cost drawn from a fixed distribution. Moreover, they assumed the decision maker has perfect knowledge of the agent distribution, i.e., can draw infinitely many examples from the agent population. Instead, our work focuses on a practical setting where the decision maker must learn from samples and acquiring human-annotated samples is quite expensive, motivating the use of model-annotated samples as well. Zhang et al., 2020 also simplified the modeling of the qualification changes of agents by using fixed transition matrices.

§.§ Bias amplification during retraining

There has been an extensive line of study on the computer vision field about how machine learning models amplify the dataset bias, while most works only focus on the one-shot setting where the machine learning model itself amplifies the bias between different groups in one training/testing round [Hall et al., 2022, Adebayo et al., 2022]; Another work theoretically studies dynamic benchmarking [Shirali et al., 2022] to propose a retraining scheme to increase model accuracy with adversarial human-annotation. In recent years, another line of research focuses on the amplification of dataset bias under model-annotated data where ML models label new samples on their own and add them back to retrain themselves[Leino et al., 2018, Dinan et al., 2019, Wang et al., 2019, Zhao et al., 2017, Adam et al., 2022, Sculley et al., 2015, Ensign et al., 2018, Mansoury et al., 2020, Adam et al., 2020]. These works study the bias amplification in different practical fields including resource allocation [Ensign et al., 2018], computer vision [Wang et al., 2019], natural language processing [Zhao et al., 2017] and clinical trials [Adam et al., 2020]. The most related work is [Taori and Hashimoto, 2023] which studied the influence of retraining in the non-strategic setting. Also, there is a work [Adam et al., 2022] touching on the data feedback loop under performative setting, but it focused on empirical experiments under medical settings where the feature distribution shifts are mainly caused by treatment and the true labels in historical data are highly accessible. Besides, the data feedback loop is also related to recommendation systems. where extensive works have studied how the system can shape users' preferences and disengage the minority population [Schmit and Riquelme, 2018, Sinha et al., 2016, Jiang et al., 2019, Mansoury et al., 2020]. However, previous literature did not touch on the retraining process.

§.§ Machine learning fairness in strategic classification

Several works have considered how different fairness metrics [Feldman et al., 2015, Hardt et al., 2016, Gupta et al., 2019, Guldogan et al., 2022] are influenced in strategic classification [Liu et al., 2019, Zhang et al., 2020, Liu et al., 2020, Zhang et al., 2022]. The most related works [Liu et al., 2020, Zhang et al., 2022] studied how strategic behaviors and the decision-maker's awareness can shape long-term fairness. They deviated from our paper since they never considered retraining and the strategic behaviors never incurred label changes.

§ ADDITIONAL DISCUSSIONS

§.§ The source of Human-annotated samples

As stated in footnote 1, for the source of human-annotated samples, we consider natural settings where the human-annotated samples are drawn from fixed $P_X$ and the process is independent of the decision-making process, i.e., the agents who best respond to $f_{t-1}$ are classified by model $f_t$ and the decision-maker never confuses them with human annotations. Instead, human annotation is a separate process for the decision-maker to obtain additional information about the whole population (e.g., by first acquiring data from public datasets or third parties, and then labeling them to estimate the population distribution $P_{XY}$). Here we provide an additional **example**: In a university admission scenario, the admission office uses the model $f_t$ to assign decisions at $t$ and obtain model-annotated samples for $t+1$. But for human-annotated samples, the admission committee hopes to acquire a more objective knowledge of "what kinds of students are successful" from the whole student population. Thus, in the hope of avoiding additional sampling/selection bias, the committee seeks human annotations from third-party education researchers/experts. The experts can provide qualifications of the public/historical student samples drawn from the whole student population including students who are not applicants for this specific university or even do not attend a university.

In this section, we additionally consider the situation where all human-annotated samples at $t$ are drawn from the post-best-response distribution $P_X^t$. This will change (<ref>) to the following:

\begin{equation}\label{eq:dtp}
\textstyle  \overline{q'}_t = \frac{tN+(t-1)K}{(t+1)N+tK}\cdot \overline{q'}_{t-1} + \frac{N}{(t+1)N+tK} \cdot a'_{t-1}\ + \frac{K}{(t+1)N+tK} \cdot q^{*}_{t-1}
\end{equation}

where $q'$ and $a'$ denote the new qualification rate and acceptance rate, and $q^{*}_{t-1}$ stands for the qualification rate of the human annotations on features drawn from $P_X^{t-1}$. Note that the only difference lies in the third term of the RHS which changes from $\overline{q}_0$ to $q^{*}_{t-1}$. Our first observation is that $q^{*}_{t-1}$ is never smaller than $\overline{q}_0$ because the best response will not harm agents' qualifications. With this observation, we can derive Prop. <ref>.

$a'_{t} \ge a_{t}$ holds for any $t \ge 1$. If Prop. <ref> further holds, we also have $a'_{t} \to 1$.

Prop. <ref> can be proved easily by applying the observation stated above. However, note that unlike $a_t$, $a'_{t}$ is not necessarily monotonically increasing.

§.§ Additional discussions on fairness

Other fairness metrics. It is difficult to derive concise results considering other fairness metrics including equal opportunity and equal improvability because the data distributions play a role in determining these metrics. However, Theorem <ref> states the true qualification rate of the agent population is likely to decrease, suggesting the retraining process may do harm to improvability. Meanwhile, when the acceptance rate $a_t$ increases for the disadvantageous group, the acceptance rate of the qualified individuals will be likely to be better, but it is not guaranteed because the feature distribution of the qualified individuals also changes because we assume the strategic behaviors are causal which may incur label changes.

Visualization of distribution: Uniform data (left) and Gaussian data (right)

§.§ Additional Discussion on the training dataset $\mathcal{S}_t$

$\mathcal{S}_t$ reuses the accumulated data instead of only fine-tuning the model using the available data at the current round. This is more reasonable because: (i) The distribution shifts caused by agent best responses are not known by the decision maker, only using current data may result in forgetting the previous samples that may still be useful. Since agents' best responses will change $Y$ and will not break $P_{Y|X}$, previous samples can provide useful information, especially on the feature domain that current samples do not cover; (ii) the sample size at a single round may be too small even for fine-tuning (e.g., for a college admission example, if we only have tens of people applying during some application round).

Moreover, only using current data does not qualitatively change the theoretical results. Since the theoretical results demonstrate monotonic trends of $a_t, q_t$, only using the most recent data will not alter the trends.  We perform an additional set of simulations where the decision maker only uses samples from the most recent round ($S_{m,t-1}, S_{o,t-1}$) on Gaussian Data and Uniform-linear Data with the experimental setups same as the ones in the paper (Section 5 for Gaussian Data and App. <ref> for Uniform-linear Data), and report the average of $a_t, q_t$. Dynamics of $a_t, q_t$ are still similar.

Uniform-linear: group $i$ (left) and $j$ (right)

Gaussian: group $i$ (left) and $j$ (right)

Dynamics of $a_t, q_t,\Delta_t$ when $\mathcal{S}_t$ only contains the most recent samples

§.§ Additional Discussions on refined retraining process

We provide the following proposition to illustrate how the refined retraining process leverages a probabilistic sampler to stabilize the dynamics.

If the decision-maker uses a probabilistic sampler $h_{t-1}(x) = D^{t-1}_{Y|X}(1|x)$ to produce model-annotated samples at $t$, then $D^t_{Y|X} = D^o_{Y|X}$.

The proof details are in App. <ref>. Prop. <ref> illustrates the underlying conditional distribution $D^t_{Y|X}$ is expected to be the same as $D^o_{Y|X}$, meaning that the classifier $f_t$ always learns the distribution of human-annotated data, thereby only preserving the systematic bias. However, there is no way to deal with the systematic bias in refined retraining process.

§ MAIN EXPERIMENTS FOR OTHER DATASETS

We provide results on a Uniform dataset and a real dataset [Quinlan, 2017] with settings similar to Sec. <ref>.

Uniform data. All settings are similar to the Gaussian dataset except that $P_X$  and $P_{Y|X}(1|x)$ change as shown in Table <ref>.

Gaussian Dataset Setting

$P_{X_k}(x_k)$      $P_{Y|X}(1|x)$     $n,r,T,q_0$

$\mathcal{U}(0,1) $     $0.5\cdot(x_1+x_2)$     $100,0.05,15,0.5$

We first verify the results in Sec. <ref> by illustrating the dynamics of $a_t, q_t, \Delta_t$ for both groups (Fig. <ref>). Since our analysis neglects the algorithmic bias and the evolution results are in expectation, we perform $n=100$ independent runs of experiments for every parameter configuration and show the averaged outcomes. The results are consistent with Thm. <ref>, <ref> and <ref>: (i) acceptance rate $a_t$ (red curves) increases monotonically; (ii) qualification rate $q_t$ decreases monotonically starting from $t= 1$ (since strategic agents only best respond from $t=1$); (iii) classifier bias $\Delta_t$ evolves differently for different groups and it may reach the minimum after a few rounds of retraining.

$a_t$, $q_t$, $\Delta_t$ for group $i$ (left) and $j$ (right)

Description of credit approval dataset

Settings      Group $i$     Group $j$

$P_{X_1|Y}(x_1|1)$     $Beta(1.37, 3.23)$     $Beta(1.73, 3.84)$

$P_{X_1|Y}(x_1|0)$     $Beta(1.50, 4.94)$    $Beta(1.59, 4.67)$

$P_{X_2|Y}(x_2|1)$     $Beta(0.83, 2.83)$     $Beta(0.66, 2.50)$

$P_{X_2|Y}(x_2|0)$     $Beta(0.84, 5.56)$    $Beta(0.69, 3.86)$

$n,r,T,q_0$     $50, 0.05, 15, 0.473$    $50, 0.05, 15, 10$

Next, we present the results of a set of complementary experiments on real data [Quinlan, 2017] where we directly fit $P_{X|Y}$ with Beta distributions. The fitting results slightly violate Assumption <ref>. Also $D^o_X$ is not equal to $P_X$. More importantly, logistic models cannot fit these distributions well and produce non-negligible algorithmic bias, thereby violating Assumption <ref>. The following experiments demonstrate how the dynamics change when situations are not ideal.

Credit approval dataset [Quinlan, 2017]. We consider credit card applications and adopt the data in UCI Machine Learning Repository processed by Dua and Graff, 2017. The dataset includes features of agents from two social groups $i,j$ and their labels indicate whether the credit application is successful. We first preprocess the dataset by normalizing and only keeping a subset of features (two continuous $X_1, X_2$) and labels, then we fit conditional distributions $P_{X_k|Y}$ for each group using Beta distributions (Fig. <ref>) and calculate prior-best-response qualification rates $q_0^i, q_0^j$ from the dataset. The details are summarized in Table <ref>. All other parameter settings are the same as the ones of synthetic datasets in Sec. <ref>.

We first illustrate the dynamics of $a_t, q_t, \Delta_t$ for both groups under different $r$. The results are shown in Fig. <ref> and are approximately aligned with Thm. <ref>, <ref> and <ref>: (i) acceptance rate $a_t$ (red curves) has increasing trends; (ii) qualification rate $q_t$ (blue curves) decreases starting from $t =1$ (since strategic agents only best respond from $t=1$); (iii) classifier bias $\Delta_t$ (black curves) evolve differently for different groups.

Next, we illustrate situation (iii) of Thm. <ref> on this dataset, where the evolutions of unfairness and $\Delta_t$ are shown in Fig. <ref>. Though the dynamics are still approximately aligned with the theoretical results, the changes are not smooth. However, this is not surprising because several assumptions are violated, and the overall trends still stay the same.

Visualization of distribution for Credit Approval dataset.

Group $i$ in Credit Approval data: $r = 0.1$ (left), $0.05$ (middle) and $0$ (right)

Group $j$ in Credit Approval data: $r = 0.1$ (left), $0.05$ (middle) and $0$ (right)

Dynamics of $a_t, q_t, \Delta_t$ for Credit Approval dataset

Dynamics of unfairness in Credit Approval data: $r = 0.1$ (left), $0.05$ (middle) and $0$ (right)

Dynamics of $\Delta_t$ in Credit Approval data: $r = 0.1$ (left), $0.05$ (middle) and $0$ (right)

Dynamics of unfairness and $\Delta_t$ for Credit Approval dataset

§ ADDITIONAL RESULTS ON SYNTHETIC/SEMI-SYNTHETIC DATASETS

In this section, we provide comprehensive experimental results conducted on two synthetic datasets and one semi-synthetic dataset mentioned in Sec. <ref> of the main paper. Specifically, App. <ref> gives the details of experimental setups; App. <ref> demonstrates additional results to verify Theorem <ref> to Theorem <ref> under different $r$ (i.e., ratios of human-annotated examples available at each round). The section also gives results on how $a_t, q_t, \Delta_t$ change under a long time horizon or when there is no systematic bias; App. <ref> further demonstrates the results under refined retraining process; App. <ref> provides fairness dynamics under various values of $r$ on different datasets; App. <ref> illustrates how the results in the main paper still hold when strategic agents have noisy best responses; App. <ref> compares the situations when agents are non-strategic with the ones when they are strategic, demonstrating how agents' strategic behaviors produce more extreme dynamics of $a_t, q_t, \Delta_t$.

§.§ Additional Experimental Setups

Generally, we run all experiments on a MacBook Pro with Apple M1 Pro chips, memory of 16GB and Python 3.9.13. All experiments are randomized with seed 42 to run $n$ rounds. Error bars are provided in App. <ref>. All experiments train $f_t$ with a logistic classifier using SGD as its optimizer. Specifically, we use  with  to fit models.

Synthetic datasets. The basic description of synthetic datasets $1$ and $2$ is shown in Sec. <ref> and App. <ref>. We further provide the visualizations of their distributions in Fig. <ref>.

German Credit dataset. There are 2 versions of the German Credit dataset according to UCI Machine Learning Database [Hofmann, 1994], and we are using the one where all features are numeric. Firstly, we produce the sensitive features by ignoring the marital status while only focusing on sex. Secondly, we use  to normalize all features. The logistic model itself can satisfy Assumption <ref> with minimal operations: if feature $i$ has coefficients smaller than 0, then just negate it and the coefficients will be larger than 0 and satisfy the assumption.

§.§ Additional Results to Verify Thm. <ref> to Thm. <ref>

Dynamics under different $r$. Although experiments in Sec. <ref> and App. <ref> already demonstrate the validity of Thm. <ref>, Prop. <ref> and Thm. <ref>, the ratio $r$ of human-annotated examples is subject to change in reality. Therefore, we first provide results for $r \in \{0, 0.05, 0.1, 0.3\}$ in all 3 datasets. $r$ only has small values since human-annotated examples are likely to be expensive to acquire. Fig. <ref> shows all results under different $r$ values. Specifically, Fig. <ref> and <ref> show results for synthetic dataset 1, Fig. <ref> and <ref> show results for synthetic dataset 2, while Fig. <ref> and <ref> show results for German Credit data. On every row, $r = 0.3, 0.1, 0.05, 0$ from the left to the right. All figures demonstrate the robustness of the theoretical results, where $a_t$ always increases and $q_t$ decreases starting from $t = 1$.  $\Delta_t$ also has different dynamics as specified in Thm. <ref>.

Dynamics under a long time horizon to verify Prop. <ref>. Prop. <ref> demonstrates that when $r$ is small enough, $a_t$ will increase towards $1$. Therefore, we provide results in all 3 datasets when $r=0$ to see whether $a_t$ increases to be close to $1$. As Fig. <ref> shows, $a_t$ is close to $1$ after tens of rounds, validating Prop. <ref>.

Dynamics under a different $B$. Moreover, individuals may incur different costs to alter different features, so we also provide the dynamics of $a_t, q_t, \Delta_t$ when the cost matrix $B = \begin{bmatrix}
3 & 0\\
0 & 6
\end{bmatrix}$ in two synthetic datasets. Fig. <ref> shows the differences in costs of changing different features do not affect the theoretical results.

Dynamics when all samples are human-annotated. Though this is unlikely to happen under the Strategic Classification setting as justified in the main paper, we provide an illustration when all training examples are human-annotated (i.e., $r=1$) when humans systematically overestimate the qualification in both synthetic datasets. Theoretically, the difference between $a_t$ and $q_t$ should be relatively consistent, which means $\Delta_t$ is only due to the systematic bias. Fig. <ref> verifies this.

§.§ Additional Results on refined retraining process

In this section, we provide more experimental results demonstrating how refined retraining process stabilizes the dynamics of $a_t, q_t, \Delta_t$ but still preserves the systematic bias. Specifically, we produce plots similar to Fig. <ref> in Fig. <ref>, but the only difference is that we use probabilistic samplers for model-annotated examples. From Fig. <ref>, it is obvious the deviations of $a_t$ from $q_t$ have the same directions and approximately the same magnitudes as the systematic bias.

§.§ Additional Results on Fairness

In this section, we provide additional results on the dynamics of unfairness and classifier bias under different $r$ (the same settings in App. <ref>). We aim to illustrate situation (iii) in Thm. <ref> where the refined retraining process is applied on the advantaged group $i$ while the original process is applied on the disadvantaged group $j$. From Fig. <ref>, <ref> and <ref>, we can see unfairness reaches a minimum in the middle of the retraining process, suggesting the earlier stopping of retraining brings benefits. From Fig. <ref>, <ref> and <ref>, we can see $\Delta_t$ for the disadvantaged group $j$ reaches a minimum in the middle of the retraining process, but generally not at the same time when unfairness reaches a minimum.

§.§ Additional Results on Noisy Best Responses

Following the discussion in Sec. <ref>, we provide dynamics of $a_t, q_t, \Delta_t$ of both groups under different $r$ similar to App. <ref> but when the agents have noisy knowledge. The only difference is that the agents' best responses are noisy in that they only know a noisy version of classification outcomes: $\widehat{f}_t(x) = f_t(x) + \epsilon$, where $\epsilon$ is a Gaussian noise with mean $0$ and standard deviation $0.1$. Fig.<ref> shows that Thm. <ref> to Thm. <ref> are still valid.

§.§ Comparisons between Strategic and Non-strategic Situations

In this section, we show the absence of strategic behaviors may result in much more consistent dynamics of $a_t, q_t, \Delta_t$ as illustrated in Fig. <ref>.

Uniform data when $r=0$ and $T$ is large: Group $i$ (left), Group $j$ (right)

Gaussian data when $r=0$ and $T$ is large: Group $i$ (left), Group $j$ (right)

German Credit data when $r=0$ and $T$ is large: Group $i$ (left), Group $j$ (right)

Dynamics when all data is human-annotated (i.e, $r=1$): Uniform data (left), Gaussian data (right).

Dynamics of $a_t,q_t,\Delta_t$ on all datasets when $r=0$ and $T$ is large or when all examples are annotated by humans.

Uniform data with a different $B$ : Group $i$ (left), Group $j$ (right)

Gaussian data with a different $B$ : Group $i$ (left), Group $j$ (right)

Dynamics of $a_t,q_t,\Delta_t$ on synthetic datasets. Except $B$, all other settings are as same as in Sec. <ref>.

Group $i$ in Uniform data : $r = 0.3,0.1,0.05,0$ from the leftmost to the rightmost

Group $j$ in Uniform data : $r = 0.3,0.1,0.05,0$ from the leftmost to the rightmost

Group $i$ in Gaussian data : $r = 0.3,0.1,0.05,0$ from the leftmost to the rightmost

Group $j$ in Gaussian data : $r = 0.3,0.1,0.05,0$ from the leftmost to the rightmost

Group $i$ in German Credit data : $r = 0.3,0.1,0.05,0$ from the leftmost to the rightmost

Group $j$ in German Credit data : $r = 0.3,0.1,0.05,0$ from the leftmost to the rightmost

Dynamics of $a_t,q_t,\Delta_t$ on all datasets.

refined retraining process for Group $i$ in Uniform data: $r = 0.1$ (left), $0.05$ (middle) and $0$ (right)

refined retraining process for Group $j$ in Uniform data: $r = 0.1$ (left), $0.05$ (middle) and $0$ (right)

refined retraining process for Group $i$ in Gaussian data: $r = 0.1$ (left), $0.05$ (middle) and $0$ (right)

refined retraining process for Group $j$ in Gaussian data: $r = 0.1$ (left), $0.05$ (middle) and $0$ (right)

refined retraining process for Group $i$ in German Credit data: $r = 0.1$ (left), $0.05$ (middle) and $0$ (right)

refined retraining process for Group $j$ in German Credit data: $r = 0.1$ (left), $0.05$ (middle) and $0$ (right).

Illustrations of refined retraining process on all 3 datasets.

Dynamics of unfairness in Uniform data : $r = 0.1$ (left), $0.05$ (middle) and $0$ (right)

Dynamics of $\Delta_t$ in Uniform data : $r = 0.1$ (left), $0.05$ (middle) and $0$ (right)

Dynamics of unfairness in Gaussian data : $r = 0.1$ (left), $0.05$ (middle) and $0$ (right)

Dynamics of $\Delta_t$ in Gaussian data : $r = 0.1$ (left), $0.05$ (middle) and $0$ (right)

Dynamics of unfairness in German Credit data : $r = 0.1$ (left), $0.05$ (middle) and $0$ (right)

Dynamics of $\Delta_t$ in German Credit data : $r = 0.1$ (left), $0.05$ (middle) and $0$ (right)

Dynamics of unfairness and $\Delta_t$ of all datasets.

Noisy retraining process for Group $i$ in Uniform data: $r = 0.1$ (left), $0.05$ (middle) and $0$ (right)

Noisy retraining process for Group $j$ in Uniform data: $r = 0.1$ (left), $0.05$ (middle) and $0$ (right)

Noisy retraining process for Group $i$ in Gaussian data: $r = 0.1$ (left), $0.05$ (middle) and $0$ (right)

Noisy retraining process for Group $j$ in Gaussian data: $r = 0.1$ (left), $0.05$ (middle) and $0$ (right)

Noisy retraining process for Group $i$ in German Credit data: $r = 0.1$ (left), $0.05$ (middle) and $0$ (right)

Noisy retraining process for Group $j$ in German Credit data: $r = 0.1$ (left), $0.05$ (middle) and $0$ (right)

Illustrations of noisy retraining process on all 3 datasets.

Nonstrategic retraining process for Group $i$ in Uniform data

Nonstrategic retraining process for Group $j$ in Uniform data

Nonstrategic retraining process for Group $i$ in Gaussian data

Nonstrategic retraining process for Group $j$ in Gaussian data

Nonstrategic retraining process for Group $i$ in German Credit data

Nonstrategic retraining process for Group $j$ in German Credit data

Illustrations of nonstrategic retraining process on all 3 datasets: $r = 0.1$ (left), $0.05$ (middle) and $0$ (right)

§ DERIVATIONS AND PROOFS

§.§ Dynamics of the Expected Qualification Rate of $\mathcal{S}_t$

Let us begin by defining $\overline{q}_t:= \E_{\mathcal{S}_t}[Q(\mathcal{S}_t)]$ which is the expected qualification rate of the training dataset at $t$. While it is difficult to derive the dynamics of $a_t$ and $q_t$ explicitly, we can first work out the dynamics of $\overline{q}_t$ using the law of total probability (details in App. <ref>), i.e.,

\begin{equation}\label{eq:dt}
\textstyle  \overline{q}_t = \frac{tN+(t-1)K}{(t+1)N+tK}\cdot \overline{q}_{t-1} + \frac{N}{(t+1)N+tK} \cdot a_{t-1}\ + \frac{K}{(t+1)N+tK} \cdot \overline{q}_0
\end{equation}

To derive $\overline{q}_t:= \E_{\mathcal{S}_t}[Q(\mathcal{S}_t)]$, we first refer to (<ref>) to get $|\mathcal{S}_t| = (t+1)N+tK$. Then, by the law of total probability, the expected qualification rate of $\mathcal{S}_t$ equals to the weighted sum of the expected qualification rate of $\mathcal{S}_{t-1}$, $S_{o,t-1}$ and the expectation of $f_{t-1}(x)$ over $\mathcal{S}_{m,t-1}$ as follows:

\begin{equation}
\nonumber\resizebox{.95\hsize}{!}{$\frac{tN+(t-1)K}{(t+1)N+tK}\E_{\mathcal{S}_{t-1}}[Q(\mathcal{S}_{t-1})] + \frac{N}{(t+1)N+tK} + \E_{\mathcal{S}_{t-1}}[A(f_{t-1}, P^{t-1})] + \frac{K}{(t+1)N+tK}\E_{\mathcal{S}_{o,t-1}}[Q(\mathcal{S}_{o,t-1})]$}
\end{equation}

The second expectation is exactly the definition of $a_{t-1}$. Moreover, note that $Q(\mathcal{S}_{o,t-1}) = Q(\mathcal{S}_{o,0}) = Q(\mathcal{S}_{0}) = \overline{q}_0$ for any $t > 0$, the third expectation is exactly $\overline{q}_0$, so the above equation is exactly (<ref>).

§.§ Derivation of factors influencing $a_t, q_t$

As stated in Sec.<ref>, we can get the factors influencing the evolution of $a_t$, $q_t$ by finding all sources affecting $P^t_{XY}$ and the expectation of $f_t(x)$ over $P^t_{X}$.

We first work out the sources influencing $f_t$ and the expectation of $f_t(x)$ over $P^t(X)$:

* $\overline{q}_t$: since $f_t$ is trained with $\mathcal{S}_t$, $\overline{q}_t$ is a key factor influencing the classifier.

* $h_t$ may not model $D^t_{Y|X}$ accurately enough. However, we ignore this by Assumption <ref>, where realizability is a common assumption in theoretical proof, while the experiments do not ignore this source.

* $\delta^t_{BR}$: we now know factors influencing the expectation of $f_t(x)$ over $D^t_X$, then the only left factor is the ones accounting for the difference between $D^t_X$ and $P^t_X$. Note that only the best responses of agents can change the marginal distribution $P_X$. We then denote it as $\delta^t_{BR}$.

Then, with $P_{XY}$ known, $P^t_{XY}$ is only influenced by $f_{t-1}$ (i.e., the agents' best responses to the classifier at $t-1$). $f_{t-1}$ is also dependent on the above factors. So we get all factors.

§.§ Proof of Theorem <ref>

proving the following lemma:

Assume $t \ge 2$ and the following conditions hold: (i) $\overline{q}_t > \overline{q}_{t-1}  \ge \overline{q}_{t-2}$; (ii) $\forall x \in X$, $D^t_{Y|X}(1|x) \ge D^{t-1}_{Y|X}(1|x)$; (iii) $\forall x, \overline{f}_{t-1}(x) \ge \overline{f}_{t-2}(x)$. Let $\overline{f}_{t-1} = \E_{\mathcal{S}_{t-1} \sim D^{t-1}_{XY}}[f_{t-1}], \overline{f}_{t} = \E_{\mathcal{S}_t \sim D^{t}_{XY}}[f_t]$, we have the following results:

* $\forall x,~\overline{f}_t(x) \ge \overline{f}_{t-1}(x)$.

* There exists a non-zero measure subset of $x$ values that satisfies the strict inequality.

Proof. We first prove (i). Note that we assume $h_t$ models $D^t_{Y|X}$ well in Assumption <ref>, so $\overline{f}_{t-1}$ (resp. $\overline{f}_t$) outputs 1 if $D^{t-1}_{Y|X}(1|x)$ (resp. $D^{t}_{Y|X}(1|x)$) is larger than some threshold $\theta$. Then, according to the above condition (ii), $\forall \theta$, if $D^{t-1}_{Y|X}(1|x) > \theta$, $D^{t}_{Y|X}(1|x) \ge D^{t-1}_{Y|X}(1|x) > \theta$. This demonstrates that $\overline{f}_{t-1}(x) = 1$ implies $\overline{f}_{t}(x) = 1$ and (i) is proved.

Next, according to (<ref>), if $\overline{q}_t > \overline{q}_{t-1}$, this means $\E_{y \sim D^t_{Y}}[y] > \E_{y \sim D^t_{Y}}[y]$. Since $D^t_Y = D^t_{X} \cdot D^t_{Y|X}$, either there exists at least one non-zero measure subset of $x$ values satisfying $D^t_{Y|X}(1|x) > D^{t-1}_{Y|X}(1|x)$ or $D^{t}_X$ is more "skewed" to the larger values of $x$ (because of monotonic likelihood assumption <ref>). For the second possibility, note that the only possible cause for the feature distribution in the training dataset $D^{t}_X$ to gain such a skewness is agents' strategic behaviors. However, since $\overline{f}_{t-1}(x) \ge \overline{f}_{t-2}(x)$ always holds, $\overline{f}_{t-1}$ sets a lower admission standard where some $x$ values that are able to best respond to $\overline{f}_{t-2}$ and improve will not best respond to $\overline{f}_{t-1}$, thereby impossible to result in a feature distribution shift to larger $x$ values while keeping the conditional distribution unchanged. Thus, only the first possibility holds.

Then we prove Theorem <ref> using mathematical induction to prove a stronger version:

When $t > 1$, $\overline{q}_t > \overline{q}_{t-1}$, $D^t_{Y|X}(1|x) \ge D^{t-1}_{Y|X}(1|x)$, $\overline{f}_t(x) \ge \overline{f}_{t-1}(x)$, and finally $a_t > a_{t-1}$.

Proof. $t$ starts from 2, but we need to prove the following claim: $\overline{q}_1$ is "almost equal" to $\overline{q}_0$, so are $D^1_{Y|X}$ and $D^0_{Y|X}$.

Firstly, according to the law of total probability, we can derive $\overline{q}_1$ as follows:

\begin{eqnarray}\label{eq:claim1}
\overline{q}_1 = \frac{N}{2N+K}\cdot \overline{q}_0 + \frac{N}{2N+K} \cdot a_0 + \frac{K}{2N+K} \cdot \overline{q}_0
\end{eqnarray}

The first and the third element are already multiples of $\overline{q}_0$. Also, we know $D^o_{X} = P_X$. Then, since $D^t_{Y|X}(1|x)$ falls in $\mathcal{H}$ and agents at $t=0$ have no chance to best respond, we have $a_0 = \E_{X \sim P_X}[D^o_{Y|X}(1|x)] = \overline{q}_0$. Thus, $a_0$ is also equal to $\overline{q}_0$, and the claim is proved. Still, as Assumption <ref> assumes realizability of $h_t$, $\overline{f}_1$ is the same as $\overline{f}_0$.

Next, we can prove the lemma by induction:

* Base case: Similar to Eq.<ref>, we are able to derive $\overline{q}_2$ as follows:

\begin{eqnarray}
\overline{q}_2 = \frac{2N+K}{3N+2K}\cdot \overline{q}_1 + \frac{N}{3N+2K} \cdot a_1 + \frac{K}{3N+2K} \cdot \overline{q}_0
\end{eqnarray}

Based on the claim above, we can just regard $\overline{q}_0$ as $\overline{q}_1$. Then we may only focus on the second term. Since $\overline{q}_1$ and $\overline{q}_0$ are "almost equal" and both distributions should satisfy the monotonic likelihood assumption <ref>, we can conclude $\overline{f}_0, \overline{f}_1$ are "almost identical". Then the best responses of agents to $\overline{f}_0$ will also make them be classified as 1 by $\overline{f}_1$, and this will directly ensure the second term to be $A(f_1, P^1) > A(f^1, P) = A(f^0,P)$. The "larger than" relationship is because strategic best responses at the first round will only enable more agents to be admitted. Thus, the first and the third term stay the same as $\overline{q}_1$ while the second is larger, so we can claim $\overline{q}_2 > \overline{q}_1$. Moreover, the difference between $D^2_{XY}$ and $D^1_{XY}$ are purely produced by the best responses at $t=1$, which will never decrease the conditional probability of $y = 1$. Thus, $D^2_{Y|X}(1|x) \ge D^1_{Y|X}(1|x)$. Together with $\overline{f}_1 = \overline{f}_0$, all three conditions in Lemma <ref> are satisfied. we thereby claim that for every $x$ admitted by $\overline{f}_1$, $\overline{f}_2(x) \ge \overline{f}_1(x)$ and there exists some $x$ satisfying the strict inequality. Note that $P^1$ is expected to be the same as $P^2$ since $f_1 = f_0$. Thus, $A(f_2, P^2) > A(f_1, P^2) = A(f_1, P^1)$, which is $a_2 > a_1$. The base case is proved.

* Induction step: To simplify the notion, we can write:

\begin{eqnarray}\label{eq: dataset_dynamics_t}
\nonumber \overline{q}_t &=& \frac{tN+(t-1)K}{(t+1)N+tK}\cdot \overline{q}_{t-1} + \frac{N}{(t+1)N+tK} \cdot a_{t-1} + \frac{K}{(t+1)N+tK} \cdot \overline{q}_0 \\
\nonumber &=& A_t \cdot \overline{q}_{t-1} + B_t \cdot a_{t-1} + C_t \cdot \overline{q}_0
\end{eqnarray}

Note that $\overline{q}_{t-1}$ can also be decomposed into three terms:

\begin{eqnarray}\label{eq: dataset_dynamics_t1}
\nonumber \overline{q}_{t-1} &=& \frac{(t-1)N+(t-2)K}{tN+(t-1)K}\cdot \overline{q}_{t-2} + \frac{N}{tN+(t-1)K} \cdot a_{t-2} + \frac{K}{tN+(t-1)K} \cdot \overline{q}_0 \\ \nonumber &=& A_{t-1} \cdot \overline{q}_{t-1} + B_{t-1} \cdot a_{t-2} + C_{t-1} \cdot \overline{q}_0
\end{eqnarray}

Since the expectation in the second term is just $a_{t-1}$, and we already know $a_{t-1} > a_{t-2}$, we know $ B_t \cdot a_{t-1} + C_t \cdot \overline{q}_0 > B_t \cdot a_{t-2} + C_t \cdot \overline{q}_0$. Note that $\frac{B_t}{B_{t-1}} = \frac{C_t}{C_{t-1}}$, we let the ratio be $m < 1$. Then since $B_{t-1} \cdot a_{t-2} + C_{t-1} \cdot \overline{q}_0 > (B_{t-1} + C_{t-1})\cdot \overline{q}_{t-1}$ due to $\overline{q}_{t-1} > \overline{q}_{t-2}$, we can derive $B_t \cdot a_{t-1} + C_t \cdot \overline{q}_0 > m \cdot (B_{t-1} + C_{t-1})\cdot \overline{q}_{t-1} = (B_t + C_t) \cdot \overline{q}_{t-1}$. Then $\overline{q}_t > (A_t + B_t + C_t) \cdot \overline{q}_{t-1} = \overline{q}_{t-1}$. The first claim is proved. As $a_{t-1} > a_{t-2}$ and $D^o$ stays the same, any agent will not have a less probability of being qualified in $\mathcal{S}_t$ compared to in $\mathcal{S}_{t-1}$, demonstrating $D^t_{Y|X}(1|x) \ge D^{t-1}_{Y|X}(1|x)$ still holds. And similarly, we can apply Lemma <ref> to get $\overline{f}_t(x) \ge \overline{f}_{t-1}(x)$ and $a_t > a_{t-1}$.

Now we already prove Lemma <ref>, which already includes Theorem <ref>. We also want to note here, the proof of Theorem <ref> does not rely on the initial $\overline{q}_0$ which means it holds regardless of the systematic bias.

§.§ Proof of Proposition <ref>

We prove the proposition by considering two extreme cases:

(i) When $\frac{K}{N} \to 0$, this means we have no decision-maker annotated sample coming in each round and all new samples come from the deployed model. We prove $\lim_{t \rightarrow \infty} a_t = 1$ by contradiction: firstly, by Monotone Convergence Theorem, the limit must exist because $a_t > a_{t-1}$ and $a_t < 1$. Let us assume the limit is $\overline{a} < 1$. Then, since $K = 0$, when $t \to \infty$, $\overline{q}_t$ will also approach $\overline{a}$, this means the strategic shift $\delta_{BR}^{t}$ approaches $0$. However, this shift only approaches $0$ when all agents are accepted by $f_{t-1}$ because otherwise there will be a proportion of agents benefiting from best responding to $f_{t-1}$ and result in a larger $\overline{q}_{t+1}$ Thus, the classifier at $t+1$ will admit more people and the stability is broken. This means the only possibility is $lim_{t \to \infty} a_{t-1} = 1$ and produces a conflict.

(ii) When $\frac{K}{N} \to \infty$, the problem shrinks to retrain the classifier to fit $D^o_{XY}$, this will make $a_t = a_0$.

Thus, there exists some threshold $\lambda$, when $\frac{K}{N} < \lambda$, $lim_{t \to \infty} a_{t} = 1$. In practice, the $\lambda$ could be very small.

§.§ Proof of Theorem <ref>

Firstly, since $P^t_{XY}$ differs from $P_{XY}$ only because agents' best respond to $f_t$, we can write $q_t = q_0 + r_t$ where $r_t$ is the difference of qualification rate caused by agents' best responses to $f_t$. Qualitatively, $r_t$ is completely determined by two sources: (i) the proportion of agents who move their features when they best respond; (ii) the increase in the probability of being qualified for each agent. Specifically, each agent that moves its features increases its probability of being qualified from its initial point to a point at the decision boundary of $f_t$. For an agent with initial feature $x$ and improved feature $x^{*}$, its improvement can be expressed as $U(x) = P_{Y|X}(1|x^{*}) - P_{Y|X}(1|x)$.

Next, denote the Euclidean distance between $x$ and the decision boundary of $f_t$ as $d_{x,t}$. Noticing that the agents will best respond to the decision classifier if and only if the Euclidean distance between her feature vector and the decision boundary is less than or equal to some constant $C$ no matter where the boundary is (Lemma 2 in [Levanon and Rosenfeld, 2022]) and what the cost matrix $B$ is, we can express the total improvement at $t$ as follows:

\begin{equation}\label{eq:qt_express}
I(t) = \int_{d_{x,t} \le C} P_{X}(x) \cdot U(x) \,dx
\end{equation}

According to the proof of Theorem <ref>, all agents with feature vector $x$ who are admitted by $f_0$ will be admitted by $f_t$ ($t > 0$), making all agents who possibly improve must belong to $\mathcal{J}$. Since $F_X$ and $P_{Y|X}(1|x)$ are both convex and non-decreasing in $\mathcal{J}$, $P_{X}(x), U(x)$ are non-decreasing in $\mathcal{J}$. Then note that $f_t$ always lies below $f_{t-1}$, therefore, for each agent who improves at $t$ having feature vector $x_{i,t}$, we can find an agent at $t-1$ with corresponding $x_{i,t-1}$ such that both $P_{X}(x_{i,t-1}) >P_{X}(x_{i,t})$ and $U(x_{i,t-1}) >U(x_{i,t})$. This will ensure $I(t) < I(t-1)$. Thus, $q_t$ decreases starting from 1.

Generally, (<ref>) reveals that if $P_{X}(x) \cdot U(x)$ is convex in $\mathcal{J}$,$q_t$ decreases. This illustrates Prop. <ref> gives a sufficient condition which is much easier to verify.

§.§ Proof of Theorem <ref>

* $\mu(D^o, P) \ge 0$: according to Def. <ref>, $a_0 = \E_{P_X}[D^o_{Y|X}(1|x)] > \E_{P_X}[P_{Y|X}(1|x)] = Q(P) = q_0$. Now that $a_0 - q_0 \ge 0$. Based on Thm. <ref> and Thm. <ref>, $a_t$ is increasing, while $q_0$ is decreasing, so $\Delta_t$ is always increasing.

* $\mu(D^o, P) < 0$: similarly we can derive $a_0 - q_0 < 0$, so $\Delta_0 = |a_0 - q_0| = q_0 - a_0$. So while $a_0 - q_0$ is still increasing, $\Delta_t$ will first decrease. Moreover, according to Prop. <ref>, if $\frac{K}{N}$ is small enough, $\Delta_t$ will eventually exceed 0 and become larger again. Thus, $\Delta_t$ either decreases or first decreases and then increases.

§.§ Proof of Proposition <ref>

Firstly, $\mathcal{S}_0 = \mathcal{S}_{o,0}$ and $\mathcal{S}_1 = \mathcal{S}_{0} \cup \mathcal{S}_{o,1} \cup \mathcal{S}_{m,0}$. Obviously, the first two sets are drawn from $D^o_{XY}$. Consider $\mathcal{S}_{m,0}$, since it is now produced by labeling features from $P_X = D^o_X$ with $D^o_{Y|X}$, $\mathcal{S}_{m,0}$ is also drawn from $D^o_{XY}$. Thus, $D^1_{Y|X} = D^o_{Y|X}$.

Then we prove the cases when $t > 1$ using mathematical induction as follows:

* Base case: We know $\mathcal{S}_2 = \mathcal{S}_{1} \cup \mathcal{S}_{o,2} \cup \mathcal{S}_{m,1}$. The first two sets on rhs are drawn from $D^o_{XY}$. The labeing in the third set is produced by $h_1(x) = D^1_{Y|X} = D^o_{Y|X}$. Thus, the base case is proved.

* Induction step: $\mathcal{S}_t = \mathcal{S}_{t-1} \cup \mathcal{S}_{o,t} \cup \mathcal{S}_{m,t-1}$. Similarly, we only need to consider the third set. But Note that
$h_t(x) = D^{t-1}_{Y|X} = D^o_{Y|X}$, the induction step is easily completed.

§.§ Proof of Proposition <ref>

At round $t$, we know $A_{\theta_t^i}^{it} > A_{\theta_t^j}^{jt}$. To reach demographic parity, the acceptance rates need to be the same, so at least one of the following situations must happen: (i)  $\widetilde{\theta}_t^i > \theta_t^i$ and $\widetilde{\theta}_t^j > \theta_t^j$; (ii) $\widetilde{\theta}_t^i < \theta_t^i$ and $\widetilde{\theta}_t^j < \theta_t^j$; (iii) $\widetilde{\theta}_t^i < \theta_t^i$ and $\widetilde{\theta}_t^j < \theta_t^j$. Next we prove that (i) and (ii) cannot be true by contradiction.

Suppose (i) holds, then we can find $\overline{\theta}_t^j < \theta_t^j$ such that $\ell(\overline{\theta}_t^j, \mathcal{S}_t^j) \in \bigl (\ell(\theta_t^j, \mathcal{S}_t^j), \ell(\widetilde{\theta}_t^j, \mathcal{S}_t^j) \bigr)$ and $A_{\overline{\theta}_t^j}^{jt} \in \bigl (A_{\theta_t^j}^{jt},  A_{\theta_t^i}^{it}  \bigr)$. We can indeed find this $\overline{\theta}_t^j$ because $\ell, A$ are continuous w.r.t. $\theta$. Now noticing that $A_{\widetilde{\theta}_t^i}^{it} = A_{\widetilde{\theta}_t^j}^{jt} > A_{\theta_t^j}^{jt}$ but $A_{\overline{\theta}_t^j}^{jt} < A_{\theta_t^j}^{jt}$, we will know we can find $\overline{\theta}_t^i \in \bigl ( \theta_t^i,  \widetilde{\theta}_t^i \bigr )$ to satisfy demographic parity together with $\overline{\theta}_t^j$. Since $P_{Y|X}(1|x)$ satisfies monotonic likelihood and $\theta_t^i$ is the optimal point, $\ell(\overline{\theta}_t^i, \mathcal{S}_t^i) < \ell(\widetilde{\theta}_t^i, \mathcal{S}_t^i)$ must hold. Thus, $(\overline{\theta}_t^i, \overline{\theta}_t^j)$ satisfy demographic parity and have a lower loss than $(\widetilde{\theta}_t^i, \widetilde{\theta}_t^j)$. Moreover, the pair satisfies (iii), which produces a conflict.

Similarly, we can prove (ii) cannot hold by contradiction, thereby proving (iii) must hold.

§.§ Proof of Theorem <ref>

Situation (i) is directly derived from Thm. <ref>, where we can just regard the trajectory of the acceptance rate of group $j$ as moving the one of group $i$ vertically downward; Situation (ii) is derived from Prop. <ref>, where the systematic bias causes unfairness and it keeps stable; Situation (iii) can be derived from Thm. <ref>, where the acceptance rate of group $i$ stays stable, while the one for $j$ monotonically increases.

§.§ Proof of Theorem <ref>

The first fact is that both $\theta_t^i, \theta_t^j$ stay stable as $0.5 - \mu_i$ and $0.5 - \mu_j$ when we use accuracy as the metric. Therefore, to understand which group is disadvantaged/advantaged at $t+1$, we just need to track the agents who best respond to $\widetilde{\theta}_t^i, \widetilde{\theta}_t^j$. First, we need the following proposition which is proved in App. <ref>:

If $P^{ti}_{XY}, P^{tj}_{XY}$ are continuous, then $\widetilde{\theta}_t^i \ge \theta_t^i$ and $\widetilde{\theta}_t^j \le \theta_t^j$.

Since we want to sacrifice the least accuracy to reach demographic parity. Since the agent best response will never make them worse off, we will know $a_t^i$ corresponding to the acceptance rate of group $i$ under the optimal threshold $\theta_t^i$ is always larger than or equal to $a_0^i$. Thus, it suffices to show that under the condition of Thm. <ref>, $a_t^j < a_0^i$.

Suppose $a_t^j < a_0^i$, then we can use Chebyshev's Inequality to bound the probability that an unadmitted agent $z$ in group $j$ reaches $\theta_t^j$ after its best response. Denote this event as $E$ and the threshold agent $z$ feels is $I_z$, where $E(I_z) = \widetilde{\theta_t^j}$. Then we can write $\mathbb{P}(E) < \mathbb{P}(I_z - E(I_z) \ge \theta_t^j - \widetilde{\theta}_t^j) < \frac{(\theta_t^j - \widetilde{\theta}_t^j)^2}{\sigma_t^2}$. Thus, when $\sigma_t < \frac{\theta_t^j - \widetilde{\theta}_t^j}{\sqrt{a_0^i - a_t^j}}$, we know $\mathbb{P}(E) < a_0^i - a_t^j$, and from the simple fact $a_{t+1}^j < a_t^j + \mathbb{P}(E)$, we know $j$ will stay disadvantaged at $t+1$.

However, when we do not add the fairness intervention, just consider the situation where all unadmitted agents in group $j$ at $t = 0$ improve, while no one in group $i$ can improve. This will flip the disadvantaged/advantaged group.

§ ALL PLOTS WITH ERROR BARS

Uniform data with a different $B$ : Group $i$ (left), Group $j$ (right)

Gaussian data with a different $B$ : Group $i$ (left), Group $j$ (right)

Error bar version of Fig. <ref>.

Error bar version of Fig. <ref>

$a_t$, $q_t$, $\Delta_t$ for group $i$ (left) and $j$ (right)

unfairness (left) and classifier bias $\Delta_t$ (right)

Error bar version of Fig. <ref>

$a_t$, $q_t$, $\Delta_t$ for group $i$ (left) and $j$ (right)

unfairness (left) and classifier bias $\Delta_t$ (right)

Error bar version of Fig. <ref>

Gaussian: $a_t$, $q_t$, $\Delta_t$ for group $i$ (left) and $j$ (right)

German: $a_t$, $q_t$, $\Delta_t$ for group $i$ (left) and $j$ (right)

Error bar version of Fig. <ref>

Uniform-linear: group $i$ (left) and $j$ (right)

Gaussian: group $i$ (left) and $j$ (right)

Error bar version of Fig. <ref>.

Uniform data when $r=0$ and $T$ is large: Group $i$ (left), Group $j$ (right)

Gaussian data when $r=0$ and $T$ is large: Group $i$ (left), Group $j$ (right)

German Credit data when $r=0$ and $T$ is large: Group $i$ (left), Group $j$ (right)

Dynamics when all data is human-annotated (i.e, $r=1$) on synthetic datasets.

Error bar version of Fig. <ref>

Group $i$ in Credit Approval data: $r = 0.1$ (left), $0.05$ (middle) and $0$ (right)

Group $j$ in Credit Approval data: $r = 0.1$ (left), $0.05$ (middle) and $0$ (right)

Error bar version of Fig. <ref>

Group $i$ in Uniform data : $r = 0.3,0.1,0.05,0$ from the leftmost to the rightmost

Group $j$ in Uniform data : $r = 0.3,0.1,0.05,0$ from the leftmost to the rightmost

Group $i$ in Gaussian data : $r = 0.3,0.1,0.05,0$ from the leftmost to the rightmost

Group $j$ in Gaussian data : $r = 0.3,0.1,0.05,0$ from the leftmost to the rightmost

Group $i$ in German Credit data : $r = 0.3,0.1,0.05,0$ from the leftmost to the rightmost

Group $j$ in German Credit data : $r = 0.3,0.1,0.05,0$ from the leftmost to the rightmost

Error bar version of Fig. <ref>.

refined retraining process for Group $i$ in Uniform data: $r = 0.1$ (left), $0.05$ (middle) and $0$ (right)

refined retraining process for Group $j$ in Uniform data: $r = 0.1$ (left), $0.05$ (middle) and $0$ (right)

refined retraining process for Group $i$ in Gaussian data: $r = 0.1$ (left), $0.05$ (middle) and $0$ (right)

refined retraining process for Group $j$ in Gaussian data: $r = 0.1$ (left), $0.05$ (middle) and $0$ (right)

refined retraining process for Group $i$ in German Credit data: $r = 0.1$ (left), $0.05$ (middle) and $0$ (right)

refined retraining process for Group $j$ in German Credit data: $r = 0.1$ (left), $0.05$ (middle) and $0$ (right).

Error bar version of Fig. <ref>

Dynamics of unfairness in Uniform data : $r = 0.1$ (left), $0.05$ (middle) and $0$ (right)

Dynamics of $\Delta_t$ in Uniform data : $r = 0.1$ (left), $0.05$ (middle) and $0$ (right)

Dynamics of unfairness in Gaussian data : $r = 0.1$ (left), $0.05$ (middle) and $0$ (right)

Dynamics of $\Delta_t$ in Gaussian data : $r = 0.1$ (left), $0.05$ (middle) and $0$ (right)

Dynamics of unfairness in German Credit data : $r = 0.1$ (left), $0.05$ (middle) and $0$ (right)

Dynamics of $\Delta_t$ in German Credit data : $r = 0.1$ (left), $0.05$ (middle) and $0$ (right)

Error bar version of Fig. <ref>

Noisy retraining process for Group $i$ in Uniform data: $r = 0.1$ (left), $0.05$ (middle) and $0$ (right)

Noisy retraining process for Group $j$ in Uniform data: $r = 0.1$ (left), $0.05$ (middle) and $0$ (right)

Noisy retraining process for Group $i$ in Gaussian data: $r = 0.1$ (left), $0.05$ (middle) and $0$ (right)

Noisy retraining process for Group $j$ in Gaussian data: $r = 0.1$ (left), $0.05$ (middle) and $0$ (right)

Noisy retraining process for Group $i$ in German Credit data: $r = 0.1$ (left), $0.05$ (middle) and $0$ (right)

Noisy retraining process for Group $j$ in German Credit data: $r = 0.1$ (left), $0.05$ (middle) and $0$ (right)

Error bar version of Fig. <ref>

Nonstrategic retraining process for Group $i$ in Uniform data: $r = 0.1$ (left), $0.05$ (middle) and $0$ (right)

Nonstrategic retraining process for Group $j$ in Uniform data: $r = 0.1$ (left), $0.05$ (middle) and $0$ (right)

Nonstrategic retraining process for Group $i$ in Gaussian data: $r = 0.1$ (left), $0.05$ (middle) and $0$ (right)

Nonstrategic retraining process for Group $j$ in Gaussian data: $r = 0.1$ (left), $0.05$ (middle) and $0$ (right)

Nonstrategic retraining process for Group $i$ in German Credit data: $r = 0.1$ (left), $0.05$ (middle) and $0$ (right)

Nonstrategic retraining process for Group $j$ in German Credit data: $r = 0.1$ (left), $0.05$ (middle) and $0$ (right)

Error bar version of Fig. <ref>

Dynamics of unfairness in Credit Approval data: $r = 0.1$ (left), $0.05$ (middle) and $0$ (right)

Dynamics of $\Delta_t$ in Credit Approval data: $r = 0.1$ (left), $0.05$ (middle) and $0$ (right)

Error bar version of Fig. <ref>

Although all our theoretical results are expressed in terms of expectation, we provide error bars for all plots in the main paper, App. <ref> and <ref> if randomness is applicable. All following figures demonstrate expectations as well as error bars ($\pm$ 1 standard deviation). Overall, the experiments have reasonable standard errors. However, experiments in the Credit Approval dataset [Quinlan, 2017] (Fig. <ref>) incur larger standard errors, which is not surprising because the dataset violates several assumptions. Finally, note that we conduct 50-100 randomized trials for every experiment and we should expect much lower standard errors if the numbers of trials become large.