Individual Fairness In Strategic Classification

Weakness 1: Assumption ii can be relaxed with the following theorem.

Theorem : Consider a $d$-dimensional binary classification problem, suppose the cost function $c(x, x')$ satisfies $0 \leq c(x, x') < \infty$, $c(x, x) = 0$ and Lipschitz continuouity w.r.t. $x$, i.e.

$|c(x_{1}, x') - c(x_{2}, x')| \leq C_{c} ||x_{1} - x_{2}||, \forall x_{1}, x_{2},$

and $\mathcal{F} = \\{f(x; t)|t \in [C, D]\\}$ for randomized classifier $\mathscr{F}$. Denote the best response as $r(x, t)$ and

Assume $\arg\min_{x'}\\{c(x,x') | l(x') \geq t, c(x,x') \leq \tfrac{1}{\lambda}\\}$ has a unique solution when the solution exists, $r(x, t)$ is bounded and the set of points where $r(x, t)$ is discontinuous has measure zero. If $p(t) \leq L_{c}$ with $L_{c} = \frac{M_{c}}{C_{c}(D - C)}$, then for constant $M_{c}$, $\forall x_{1}, x_{2} \in \mathcal{X}$, we have, $|c_{\mathscr{F}}(x_{1}) - c_{\mathscr{F}}(x_{2})| \leq M_{c}||x_{1} - x_{2}||.$

For assumption (iii), we can use the approximated function of $l(x)$ in the classification. And learning the score function is the central task for many applications.

Weakness 2 and Q1: Constraint 20 is not always feasible to enforce. We also mentioned this problem in Line 228 of the problem. In this case, we can relax the constraints to achieve a trade-off between accuracy, individual fairness and statistical parity as we stated in the paper.

Weakness 3 : We will reduce the inline definitions and algebra steps in the next version of the paper.

Weakness 1 and Q1: The assumptions on $l(x)$ (Eqs. 1 and 2) ensure that decisions can be made based on a score function. In theory, any classification problem can be solved by a threshold-based classifier when $l(x)$ is allowed to be an arbitrary function. However, in practice, such a function may not be learnable. The connection between cost function and $l(x)$ can be relaxed with the following theorem.

Theorem : Consider a $d$-dimensional binary classification problem, suppose the cost function $c(x, x')$ satisfies $0 \leq c(x, x') < \infty$, $c(x, x) = 0$ and Lipschitz continuouity w.r.t. $x$, i.e.

$|c(x_{1}, x') - c(x_{2}, x')| \leq C_{c} ||x_{1} - x_{2}||, \forall x_{1}, x_{2},$

and $\mathcal{F} = \\{f(x; t)|t \in [C, D]\\}$ for randomized classifier $\mathscr{F}$. Denote the best response as $r(x, t)$ and

Assume $\arg\min_{x'}\\{c(x,x') | l(x') \geq t, c(x,x') \leq \tfrac{1}{\lambda}\\}$ has a unique solution when the solution exists, $r(x, t)$ is bounded and the set of points where $r(x, t)$ is discontinuous has measure zero. If $p(t) \leq L_{c}$ with $L_{c} = \frac{M_{c}}{C_{c}(D - C)}$, then for constant $M_{c}$, $\forall x_{1}, x_{2} \in \mathcal{X}$, we have, $|c_{\mathscr{F}}(x_{1}) - c_{\mathscr{F}}(x_{2})| \leq M_{c}||x_{1} - x_{2}||.$

Our method of randomization can still be used to improve individual fairness. However, how to get the optimal distribution of $t$ depends on the specific problem.

Weakness 2 and Q2: Since finding an optimal distribution of $p(t)$ is a linear optimization problem, the worst time complexity can be $\mathcal{O}(2^K)$. However, in practice, the worst case does not happen and algorithms such as the simplex method typically solve problems in polynomial time for most cases. We include the following experiments to test the sensitivity against the number of bins, which show that the results are not very sensitive to the number of bins in this case.

Q3: The distribution is usually centered at the optimal deterministic threshold, but the specific shape is affected by the distribution of feature $x$. In terms of accuracy-fairness tradeoff, the best accuracy is achieved when the distribution of a delta function is at the optimal threshold. When the distribution spreads out, we get better fairness, but more misclassifications will happen.

Dear authors, Thank you for your responses and clarifications. Most of my concerns are being addressed. I maintain my score to borderline accept.

Weakness 1 & Q1: Equation 7 captures scenarios where the cost of improving user features depends on the actual improvement achieved by the action. Here, $l(x)$ is not a prediction function but a function related to the ground-truth label (see Eqs. 1 and 2), and the relationship between cost and $l(x)$ is also employed in [1].

For a more general cost function, we can have the following theorem.

Theorem : Consider a $d$-dimensional binary classification problem, suppose the cost function $c(x, x')$ satisfies $0 \leq c(x, x') < \infty$, $c(x, x) = 0$ and Lipschitz continuouity w.r.t. $x$, i.e.

$|c(x_{1}, x') - c(x_{2}, x')| \leq C_{c} ||x_{1} - x_{2}||, \forall x_{1}, x_{2},$

and $\mathcal{F} = \\{f(x; t)|t \in [C, D]\\}$ for randomized classifier $\mathscr{F}$. Denote the best response as $r(x, t)$ and

Assume $\arg\min_{x'}\\{c(x,x') | l(x') \geq t, c(x,x') \leq \tfrac{1}{\lambda}\\}$ has a unique solution when the solution exists, $r(x, t)$ is bounded and the set of points where $r(x, t)$ is discontinuous has measure zero. If $p(t) \leq L_{c}$ with $L_{c} = \frac{M_{c}}{C_{c}(D - C)}$, then for constant $M_{c}$, $\forall x_{1}, x_{2} \in \mathcal{X}$, we have, $|c_{\mathscr{F}}(x_{1}) - c_{\mathscr{F}}(x_{2})| \leq M_{c}||x_{1} - x_{2}||.$

Proof : The individual cost is

Therefore,

Because

we have

With $p(t) \leq \frac{M_{c}}{C_{c}(D - C)}$,

Weakness 2 & Q2: We acknowledge that randomization is a general approach to achieving individual fairness. The motivation of this paper is to investigate individual fairness in the context of strategic classification, where agents may adjust their features. Prior research has shown that many fairness methods effective in static settings fail to extend naturally to strategic scenarios [2, 3, 4]. Moreover, cost, which is intrinsic to strategic classification, has been an important topic in the literature. Therefore, it is both timely and valuable to explore how randomization can be applied to strategic classification.

In non-strategic settings, where no cost is involved, individual fairness with respect to outcomes can be viewed as a special case of Section 4, where $\mathcal{C} = 0$ and $\Delta(x) = x, \forall x$.

Q3: The left-hand side represents the $l$ function evaluated on the adjusted feature, where the original feature is $x$ and the adjustment is determined by the function $f(x, t)$. Thank you for pointing out the inconsistency. To align with (3) and emphasize the threshold used in $f$, it should be written as $l(\Delta x(f(\cdot; t)))$.

Weakness 4 & Q4: As we discussed in the response to weakness 2 & Q2, strategic classification has its own specific property. Smoother baselines, logistic regression, has the problem of how an individual will react to them, which is beyond the scope of this paper.

In our experiments on Law School dataset, we compared our method against a baseline which is very similar to logistic regression where we learn a linear function on $x$ and then find the best thresholds.

In static settings, the randomized logistic regression classifier $\Pr\\{\hat{Y} = 1| X = x\\} = \frac{1}{1 + e^{-w^{T}x + b}}$ can be seen as a special case of our randomized classifier with $l(x) = -w^{T}x + b$ and $\Pr\\{t \leq l\\} = \frac{1}{1 + e^{-l}}$. Therefore, our method can be used to improve individual fairness further based on $l(x)$ learned by logistic regression model. Here we provide a comparison on the Law school dataset in static setting. Our method used 300 bins.

If you have any other smoother baselines that can be used here, we would be very glad to provide a comparison during the discussion.

[1] Milli, Smitha, et al. "The social cost of strategic classification." Proceedings of the conference on fairness, accountability, and transparency. 2019.

[2] Diana, Emily, Saeed Sharifi-Malvajerdi, and Ali Vakilian. "Minimax group fairness in strategic classification." 2025 IEEE Conference on Secure and Trustworthy Machine Learning (SaTML). IEEE, 2025.

[3] Keswani, Vijay, and L. Elisa Celis. "Addressing strategic manipulation disparities in fair classification." Proceedings of the 3rd ACM Conference on Equity and Access in Algorithms, Mechanisms, and Optimization. 2023.

[4] Estornell, Andrew, et al. "Unfairness despite awareness: group-fair classification with strategic agents." arXiv preprint arXiv:2112.02746 (2021).

Weakness 1 and Q1: Our method implements a randomized classifier by sampling from a set of deterministic classifiers. For feature-attribution scores such as SHAP, we can compute them with respect to the expected prediction, $\mathbb{E}[\mathscr{F}(x)]$. While individual predictions may appear less interpretable due to the inherent randomness, the expected prediction across individuals with similar features remains interpretable and meaningful.

From a governance perspective, the governing body can access both the randomly generated threshold and the resulting prediction to verify the correctness of any specific decision. Furthermore, it can monitor the distribution of thresholds $t$ over time to ensure that the randomization behaves as intended and aligns with fairness and performance requirements.

Weakness 2: We do not assume that our base classifiers are differentiable. In Assumption 2.1, $l(x)$ is a score function, such as a default risk score commonly used in finance. Our actual base classifiers are defined as $f(x; t) = \mathbf{1}[l(\Delta x) \geq t]$ (see Eq. 3), which are not differentiable. Moreover, there is substantial literature on using regression models to do financial assessment [1, 2, 3]. The predicted risk scores from such models can naturally be viewed as differentiable functions $l(x)$.

Clarity: The worst-case complexity of linear optimization algorithms can be as high as $2^{K}$. However, in practice, algorithms such as the simplex method typically solve problems in polynomial time for most cases.

Q2: When $l(x)$ itself is not differentiable, e.g., a decision tree, we can apply randomization to every node of the tree. Achieving the optimal randomization policy needs to be considered with the specific application.

Limitations: Thank you for your suggestion. We will elaborate more about the relationship between individual fairness and group fairness in the next version.

[1] Kogan, Shimon, et al. "Predicting risk from financial reports with regression." Proceedings of human language technologies: the 2009 annual conference of the North American Chapter of the Association for Computational Linguistics. 2009.

[2] Valaskova, Katarina, Tomas Kliestik, and Maria Kovacova. "Management of financial risks in Slovak enterprises using regression analysis." Oeconomia copernicana 9.1 (2018): 105-121.

[3] Smita, Mrinalini. "Logistic regression model for predicting performance of S&P BSE30 company using IBM SPSS." International Journal of Mathematics Trends and Technology-IJMTT 67 (2021).