Thanks for the comments. We address your questions point by point as follows.

While the conclusions of the paper help understand the impact of human strategic behavior on ML systems, many of these conclusions are somewhat intuitive and straightforward.

We believe the theoretical results are not intuitive. In section 3, we show that although the decision-maker keeps retraining the classifier, the increasing $a_t$ and decreasing $q_t$ demonstrate the model becomes more biased (Theorem 3.3 - 3.5). In section 4, we not only display the fairness dynamics of the retraining process but also research the influence of fairness interventions. In particular, Theorem 4.2 reveals that fairness intervention can even prohibit the disadvantaged group from becoming advantaged, which is also counter-intuitive.

The paper primarily focuses on linear models and specific distributions. The research conclusions might not fully apply to non-linear models and complex data distributions.

• Note that the linearity of the decision model is standard setting in strategic classification (e.g., [1,6,7,11,12,17,25,31,35] in the main paper). In practice, one can first use a non-linear feature extractor to learn the embeddings of agents' preliminary features and then apply a linear model to the newly generated embedded features. Given the knowledge of both feature extractor and model, agents will best respond with respect to new features, and all our results still hold. The generalization to non-linear settings is also discussed in [13,28] in the main paper and [Levanon and Rosenfeld, 2021].

• To further validate the above arguments, we provide an additional case study using ACSIncome data [Ding et al., 2022], which contains information on more than $150K$ agents. In this study, the goal is to predict whether a person has an annual income $> 50000$ based on $53$ features such as education level and working hours per week. Specifically, we consider a decision-maker who first learns 2-D embeddings from $53$ original features using a neural network and then regards the embedding as the new feature. A linear decision model is trained and used on these new features to make predictions. We divide the agents into 2 groups based on their ages. Similar to the credit approval data, we then fit Beta distributions on the 2 groups and then verify the monotonic likelihood assumption (Figure 1,2 in the attached pdf). We then plot the dynamics of $a_t, q_t, \Delta_t$ for both groups when the systematic bias is either positive or negative. The results show that similar trends still hold for this large dataset (Figure 3 in the attached pdf).

• Finally, it is an interesting direction to extend our setting into non-linear decision policy while the agents can only respond to the classifier with the original features (not the embedding). This setting can be highly intricate because both the decision boundary and the agent best response will vary. We hope our paper can be a starting point and a solid foundation of more future work.

The scale of the datasets used in experiments is relatively small, which may not fully capture the complexity of system dynamics in large-scale data environments.

• Our paper focuses on strategic classification settings [1,6,7,11,12,17,25,31,35]. According to the previous literature, human strategic behaviors are prevalent in high-stakes domains such as hiring, lending, and college admission, where humans have more incentives to improve their features for favorable outcomes. We believe the datasets adopted in our experiments are sufficiently representative and cover well-known data widely used in strategic classification literature.

• The additional case study illustrated in the above answer uses a larger dataset.

References

Ding, F., Hardt, M., Miller, J., & Schmidt, L. (2021). Retiring adult: New datasets for fair machine learning. Advances in neural information processing systems, 34, 6478-6490.

Thanks for the comments. We address your questions point by point as follows.

Assumptions of the theoretical results and the generalizability

• Our paper focuses on strategic classification settings [1,6,7,11,12,17,25,31,35]. According to the previous literature, human strategic behaviors are prevalent in high-stakes domains such as hiring, lending, and college admission, where humans have more incentives to improve their features for favorable outcomes. We believe the datasets adopted in our experiments are sufficiently representative and cover well-known data widely used in strategic classification literature. While the Gaussian, German Credit, and Credit Approval datasets violate some conditions, the experimental results still show similar trends as the theoretical results, demonstrating the robustness and practical value of the theory.

• The linearity assumption of the decision model is standard setting in strategic classification. In practice, one can first use a non-linear feature extractor to learn the embeddings of agents' preliminary features and then apply a linear model to the newly generated embedded features. Given the knowledge of both feature extractor and model, agents will best respond with respect to new features and all our results still hold. The generalization to non-linear settings is also discussed in [13,28] in the main paper and [Levanon and Rosenfeld, 2021].

• To further validate the above arguments, we provide an additional case study using ACSIncome data [Ding et al., 2022], which contains information on more than $150K$ agents. In this study, the goal is to predict whether a person has an annual income $> 50000$ based on $53$ features such as education level and working hours per week. Specifically, we consider a decision-maker who first learns 2-D embeddings from $53$ original features using a neural network and then regards the embedding as the new feature. A linear decision model is trained and used on these new features to make predictions. We divide the agents into 2 groups based on their ages. Similar to the credit approval data, we then fit Beta distributions on the 2 groups and then verify the monotonic likelihood assumption (Figure 1,2 in the attached pdf). We then plot the dynamics of $a_t, q_t, \Delta_t$ for both groups when the systematic bias is either positive or negative. The results show that similar trends still hold for this large dataset (Figure 3 in the attached pdf).

Organize the experiments section of the main paper

Thanks for the suggestion. We will move the content of App F.3 to the main paper.

The study primarily examines binary classification scenarios with only two outcome classes (e.g., admitted/not admitted).

• Similar to most studies in strategic classification [1,6,7,11,12,17,25,31,35], we focus on binary classification which is a standard setting in strategic classification and has many real applications (e.g., hiring, admission, loan approval) that involve binary decision-making on humans. Compared to existing works, ours is the first that examines the long-term impact of automating data annotation under strategic human agents.

• Although the theoretical modeling and analysis under binary classification is already non-trivial, we may extend the analytical framework and insights to multi-class classification. Specifically, consider strategic agents with categorical labels $Y\in \mathcal{Y}$. Instead of improving features toward one specific favorable outcome (e.g., acceptance in lending/hiring, as given in Eq. (1)), each agent may have its own target $y^*\in \mathcal{Y}$ and they may best respond based on $x_t = argmax_z {Pr(f_{t-1}(z)=y^*)-c(z,x)}$. For the decision-maker, the model retraining process remains the same, i.e., it augments training data with model-annotated samples and human-annotated samples at every round. Under this broader setting, we may consider two scenarios: (i) all agents have the same target $y^*$; (ii) agents have different target $y^*$. For case (i), because agents move toward one class, the result is similar to a binary setting: instead of having the acceptance rate (resp. qualification rate) increasing (resp. decreasing) over time, the probability $P(f_t(X)=y^*)$ (resp. $P(Y=y^*)$) increases (resp. decreases) under certain conditions. For case (ii), the results will be more complicated because different targets could induce highly diverse agent behavior that disrupts the monotonicity change of distributions $P(f_t(X))$ and $P(Y)$. This is an interesting future direction.

• Last, we agree with the reviewer that it is interesting to extend our work to multi-class classification or ranking, which we hope to study in the future. Indeed, such extension is non-trivial and has been an ongoing effort of the community. For example, [Liu et al., 2022] consider competition among strategic agents and is the first work studying strategic ranking to the best of our knowledge. We hope our paper can provide insights and shed light on future works.

References

Ding, F., Hardt, M., Miller, J., & Schmidt, L. (2021). Retiring adult: New datasets for fair machine learning. Advances in neural information processing systems, 34, 6478-6490.

Liu, Lydia T., Nikhil Garg, and Christian Borgs. "Strategic ranking." International Conference on Artificial Intelligence and Statistics. PMLR, 2022.

Levanon, S., & Rosenfeld, N. (2021, July). Strategic classification made practical. In International Conference on Machine Learning (pp. 6243-6253). PMLR.

Thanks for the comments. We address your questions point by point as follows.

Theorem 3.3

The result in Theorem 3.3 (i.e., $a_t > a_{t-1}$) does not require $N >> K$ but only needs $N > 0$. Condition $N >> K$ is only used in Proposition 3.4, under which the acceptance rate converges to $1$ as $t \to \infty$ (i.e., all agents are admitted in the long run). For general cases with arbitrary positive $N$, we believe the increasing trend of the acceptance rate (Theorem 3.3) under complex dynamics between retrained model and strategic agents is not straightforward, rigorously proving requires non-trivial efforts by induction (see detailed proof in Appendix).

Theorem 3.5 beyond linear classifiers?

• Note that the linearity of the decision model is standard setting in strategic classification (e.g., [1,6,7,11,12,17,25,31,35]). In practice, one can first use a non-linear feature extractor to learn the embeddings of agents' preliminary features and then apply a linear model to the newly generated embedded features. Given the knowledge of both feature extractor and model, agents will best respond with respect to new features, and all our results still hold. The generalization to non-linear settings is also discussed in [13,28] in the main paper and [Levanon and Rosenfeld, 2021].

• To further validate the above arguments, we provide an additional case study using ACSIncome data [Ding et al., 2022] with information on more than $150K$ agents. The goal is to predict whether a person has an annual income $> 50000$ based on $53$ features such as education level and working hours. Specifically, we consider a decision-maker who first learns 2-D embeddings from $53$ original features using a neural network and then regards the embedding as the new feature. A linear decision model is trained and used on these new features to make predictions. We divide the agents into 2 groups based on their ages. Similar to the credit approval data, we then fit Beta distributions on the 2 groups and then verify the monotonic likelihood assumption (Figure 1,2 in the attached pdf). We then plot the dynamics of $a_t, q_t, \Delta_t$ for both groups when the systematic bias is either positive or negative. The results show that similar trends still hold for this large dataset (Figure 3 in the attached pdf).

In what situations can the convexity assumption in Theorem 3.5 be validated in practice?

• In lines 236-238 we discussed the situations where the conditions of Theorem 3.5 hold theoretically (e.g. when $P_X$ belongs to Uniform distribution, Beta distribution, or Gaussian distribution when the first decision policy admits 50% or more agents). In practice, the decision-maker can fit the empirical distribution of the real data to get $F_X$ and then verify the convexity. Particularly, if the cdf does not have analytical form, we can verify the convexity empirically by sampling the points from the domain and check the convexity inequality $\forall x_1, x_2 \in J , \lambda \in (0,1), f(\lambda x_1 + (1 - \lambda) x_2) \leq \lambda f(x_1) + (1 - \lambda) f(x_2)$.

• The assumptions are sufficient but not necessary, i.e., Theorem 3.5 may still hold even when assumptions are violated. This is mentioned in lines 238-239 and validated in experiments. Among all datasets adopted in experiments, only the "uniform-linear" dataset satisfies all assumptions in Theorem 3.5, while the Gaussian dataset satisfies Theorem 3.5 only if the initial qualification rate of agents is larger than 0.5. The German Credit and Credit Approval dataset only satisfies the linear classifier assumption and the monotonic likelihood assumption. However, the empirical results on all datasets demonstrate the validity of Theorem 3.5. Thus, we believe the phenomenon in Theorem 3.5 should exist in reality even when some assumptions are not strictly satisfied.

Cumulative density function

$F_X$ can have a large domain such as $\mathbb{R}$, but Theorem 3.5 only needs it to be convex in a subset $J$ of its domain. Formally, $\forall x_1, x_2 \in J , \lambda \in (0,1), f(\lambda x_1 + (1 - \lambda) x_2) \leq \lambda f(x_1) + (1 - \lambda) f(x_2)$. As an example, consider a 1-d Gaussian distribution $X \sim N(\mu, \sigma^2)$, we know it is convex if $J = (-\infty, \mu)$.

Continuity of $P(Y|X)$

$P_{Y|X}(y|x)$ (where $y$ can be $0,1$) is the conditional probability for an agent with feature $x$ to have label $y$. This is a function of $x$ and we assume it is continuous in $x$. For example, the logistic function $P_{Y|X}(1|x) = \frac{1}{1+exp(-\beta^Tx)}$ is continuous when $x \in \mathbb{R}$.

$S_{m, t-1}$ in lines 187-188

Yes, your understanding is correct. Because $S_{m, t-1}$ includes the model-annotated samples at $t-1$, the actual qualification of each sample is unobserved and is annotated using the pseudo-label generated by the model. In this sense, the "qualification rate" of $S_{m, t-1}$ is in fact the "acceptance rate." The reason we used "qualification rate" is because from the decision-maker's perspective, when updating its model using empirical risk minimization, it doesn't distinguish model-annotated samples from human-annotated ones and would regard pseudo-label as the actual qualification. In other words, the dataset the decision-maker uses to update the model has more and more fractions of people with positive labels (regardless of whether labels are acquired from humans or model), i.e., qualification rate of $S_{t}$ (augmented by $S_{m, t-1}$) is higher than that of $S_{t-1}$. We will add more clarification to the paper.

References

Levanon, S., & Rosenfeld, N. (2021, July). Strategic classification made practical. In International Conference on Machine Learning (pp. 6243-6253). PMLR.

Ding, F., Hardt, M., Miller, J., & Schmidt, L. (2021). Retiring adult: New datasets for fair machine learning. Advances in neural information processing systems, 34, 6478-6490.

Thanks for your reply. We apologize that our previous response regarding the high-dimensional case has some inaccurate statements. We present the precise analysis regarding all situations from 1-dimensional to high-dimensional ones and answer your questions.

Theorem 3.5

1. All our previous statements are precise for the 1-dimensional setting where Gaussian, Beta, and Uniform distributions satisfy the conditions in Theorem 3.5;

2. Theorem 3.5 itself is precise for the high-dimensional settings. However, you are correct that the convexity of CDF for $X$ and $Y$ does not ensure the convexity of the joint CDF $(X, Y)$. Consider the simplest independent 2-dimensional distribution setting where $F_X, F_Y$ are convex in 1-d space, we can derive the Hessian of the joint CDF as:

$\begin{bmatrix} F’’_X \cdot F_Y & F’_X \cdot F’_Y \\\ F’_X \cdot F’_Y & F_X \cdot F''_Y \end{bmatrix}$

The Hessian is PSD if $F_X''(x) \cdot F_X(x) \ge F_X’(x)^2$ and $F_Y''(y) \cdot F_Y(y) \ge F_Y’(y)^2$ hold for any $(x,y) \in J$, which is equivalent to say $log(F_X)$ and $log(F_Y)$ are convex functions. Thus, features with log-convex CDFs will satisfy the conditions in Theorem 3.5 such as the Uniform CDF and any CDF in the form of $F(x) = \lambda e^{\lambda x}$ if $\lambda \ge 1$.

3. However, as we stated, Theorem 3.5 is a sufficient condition. In the proof of Theorem 3.5 under high-dimensional distribution settings with feature $(X_1, ..., X_d)$, we can derive the same results if the joint CDF $F$ is convex w.r.t each coordinate $X_i$ in the full domain of $X_i$. This means a multivariate feature distribution will result in a decreasing qualification rate if each feature has convex CDF and they are independent. This is to say, If each variable satisfies Beta distributions with $\alpha \ge \beta, \beta = 1$, the results in Theorem 3.5 still hold.

4. Regarding the situation where multiple features are dependent, the analysis can be increasingly challenging. However, in practice, the decision-maker often uses domain expertise and dimension-reduction methods (e.g., PCA) to do feature selection first, preventing severe violations of independence.

The FICO score example

Theorem 3.3 and 3.5 in the FICO score example can be interpreted as follows: the decision-maker sets the score threshold to give loans, but the qualification means whether they can repay the loans and this is hidden. Theorem 3.3 illustrates that the decision-maker will set a lower score threshold when retraining goes on (e.g., from 700 to 600), but the qualification rate (i.e., the proportion of agents who will repay the loans) decreases. “An applicant’s score is above the threshold but they are not qualified for the loan” happens since the decision-maker lowers the acceptance threshold due to the misleading information it gets during the retraining. This phenomenon is one of our main discoveries that has not been studied in previous literature.

Proposed modifications of the manuscript

Taking all the discussions together, we are happy to make the following modifications to the content related to Theorem 3.5: (i) add the convexity condition w.r.t each coordinate $X_i$ as mentioned above; (ii) add the FICO example in the appendix to illustrate the use cases in practice; (iii) Add more detailed discussions on whether different distributions in high-dimensional space satisfy Theorem 3.5.

Thanks for the comments. We address your questions point by point as follows.

Empirical evidence or case studies to support the validity of the assumptions

• The monotonic likelihood ratio property (MLRP):

This property is rather standard and has been widely used in literature (e.g., [11,12] in the main paper; Jung et al., 2020; Khalili et al., 2021; Barman et al., 2020); it means that each feature dimension is a good indicator of the target variable and an individual is more likely to be qualified when his/her feature value increases.

Regarding the empirical evidence, we demonstrate the distribution of each of the two features in the Credit Approval dataset in Figure 10, where the fitted beta distribution satisfies the monotonic likelihood distribution. Moreover, [11] referred to in the main paper used FICO credit data and verified the monotonic likelihood assumption holds for people's FICO scores in Figure 15 of [11]. FICO has been widely used in the United States to assess people's creditworthiness and is a good practical example. In addition to the lending domain, MLRP has been studied in many other contexts, e.g., research has shown that higher wealth levels are often associated with higher likelihoods of certain favorable economic behaviors (like investment and consumption patterns), empirical data on insurance claims shows that higher levels of risk factors (like age, smoking status) are monotonically associated with higher likelihoods of claims.

• The perfect information about agent distributions

We want to clarify that the knowledge of agent distributions is only used when deriving theorems. In all the experiments, the decision-maker updates models by running empirical risk minimization on training data without knowing agent distribution $P_X$. To verify whether the conditions/assumptions in theorems hold, the decision-maker in practice may fit $P_X$ using the initial training set (e.g., Figure 10 for credit approval data).

Last, we emphasize that the assumptions made in the theoretical analysis are sufficient but not necessary, i.e., the results may still hold even when assumptions are violated. This is validated in our experiments, where only the "uniform-linear" data satisfies all assumptions in the paper but all results are consistent with theorems.

Diverse/larger datasets and other domains

• Our paper focuses on strategic classification settings [1,6,7,11,12,17,25,31,35]. According to the previous literature, human strategic behaviors are prevalent in high-stakes domains such as hiring, lending, and college admission, where humans have more incentives to improve their features for favorable outcomes. We believe the datasets adopted in our experiments are sufficiently representative and cover well-known data widely used in strategic classification literature.

• We want to emphasize that our theoretical findings do not have any restriction on the dataset and are broadly applicable to other domains such as recommendation systems, fraud detection, etc., as long as they involve human strategic behavior and the decision-maker uses a linear model to make decisions. Note that the linearity of the decision model is a standard setting in strategic classification. In practice, one can first use a non-linear feature extractor to learn the embeddings of agents' preliminary features and then apply the linear model to the newly generated embedded features. Given the knowledge of both feature extractor and model, agents will best respond with respect to new features, and all our results still hold. The generalization to non-linear settings is also discussed in [13,28] in the main paper and [Levanon and Rosenfeld, 2021].

• To further validate the above arguments, we provide an additional case study using ACSIncome data [Ding et al., 2022], which contains information on more than $150K$ agents. In this study, the goal is to predict whether a person has an annual income $> 50000$ based on $53$ features such as education level and working hours per week. Specifically, we consider a decision-maker who first learns 2-D embeddings from $53$ original features using a neural network and then regards the embedding as the new feature. A linear decision model is trained and used on these new features to make predictions. We divide the agents into 2 groups based on their ages. Similar to the credit approval data, we then fit Beta distributions on the 2 groups and then verify the monotonic likelihood assumption (Figure 1,2 in the attached pdf). We then plot the dynamics of $a_t, q_t, \Delta_t$ for both groups when the systematic bias is either positive or negative. The results show that similar trends still hold for this large dataset (Figure 3 in the attached pdf).

Conclusion

While our theoretical analysis relies on some assumptions and the results are mainly evaluated in domains of lending and admission, the assumptions and datasets are mostly standard and commonly used in strategic classification literature. Nonetheless, we want to emphasize that our results are broadly applicable to other datasets and applications that involve human strategic behavior.

References

Christopher Jung, Sampath Kannan, Changhwa Lee, Mallesh Pai, Aaron Roth, and Rakesh Vohra. Fair prediction with endogenous behavior. In Proceedings of the 21st ACM Conference on Economics and Computation, pages 677–678, 2020.

Mohammad Mahdi Khalili, Xueru Zhang, Mahed Abroshan, and Somayeh Sojoudi. Improving fairness and privacy in selection problems. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 8092–8100, 2021.

Barman, S. and Rathi, N. Fair cake division under monotone likelihood ratios. In Proceedings of the 21st ACM Conference on Economics and Computation, pp. 401–437, 2020.

Ding, F., Hardt, M., Miller, J., & Schmidt, L. (2021). Retiring adult: New datasets for fair machine learning. Advances in neural information processing systems, 34, 6478-6490.