Individual Fairness In Strategic Classification
Authors: Zhiqun Zuo
Mohammad Mahdi Khalili
Venue: NeurIPS 2025 poster ()
Keywords: Individual Fairness
Strategic Classification
Group Fairness
Primary area: social_and_economic_aspects_of_machine_learning
TL;DR: We present a method using randomized classifiers to improve individual fairness in the strategical classification setting and an algorithm finding the optimal threshold distribution.

Abstract: Strategic classification, where individuals modify their features to influence machine learning (ML) decisions, presents critical fairness challenges. While group fairness in this setting has been widely studied, individual fairness remains underexplored. We analyze threshold-based classifiers and prove that deterministic thresholds violate individual fairness. Then, we investigate the possibility of using a randomized classifier to achieve individual fairness. We introduce conditions under which a randomized classifier ensures individual fairness and leverage these conditions to find an optimal and individually fair randomized classifier through a linear programming problem. Additionally, we demonstrate that our approach can be extended to group fairness notions. Experiments on real-world datasets confirm that our method effectively mitigates unfairness and improves the fairness-accuracy trade-off.

Individual Fairness In Strategic Classification
Zhiqun Zuo zuo 167 edu
Mohammad Mahdi Khalili khalili. 17w.17..eeee. edu
Department of Computer Science and Engineering The Ohio State University Columbus, OH 43210
Abstract
Strategic classification, where individuals modify their features to influence chine learning (ML) decisions, presents critical fairness challenges. While group fairness in this setting has been widely studied, individual fairness remains un- derexplored. We analyze threshold-based classifiers and prove that deterministic thresholds violate individual fairness. Then, we investigate the possibility of using a randomized classifier to achieve individual faimesss. We introduce conditions under which randomized classifier ensures individual fairness and leverage these conditions to find an optimal and individually fair randomized classifier through a linear programming problem. Additionally, we demonstrate that our approach can be extended to group fairness notions. Experiments on real-world datasets confirm that our method effectively mitigates unfairness and improves the fairness- accuracy trade-off.
Introduction
As machine learning (ML) becomes increasingly popular in decision-making systems, the interaction between individuals and AI agents emerges as critical issue. Al-aided applications, such as automated lending [1 resume screening [2), and college admissions [3], significantly influence people's ' opportunities and outcomes. fundamental issue these applications is fairness-ensuring that ML-based decisions do not systematically disadvantage certain individuals or groups. Various fairness notions, including tier balancing 44. lookahead counterfactual fairness (5), and long-term fairness [6] have been proposed to address fairness issues arising from interactions between human and AI.
major challenge in ML-based decision-making process is strategic behavior-whert individuals adjust their features to obtain more favorable outcomes on predefined decision criteria, they are inherently vulnerable to such gaming. For example, students may participate in specific extracurricular activities if they believe doing so will improve their college admissions prospects. The field of strategic classification seeks to address these challenges by designing classifiers that account for individuals' ability to adjust their features (7]. Prior work has examined diverse aspects of strategic classification, including heterogeneous strategic behavior [10), incentive-award awaee risk minimization [II) and performative prediction, where data distributions evolve
Because ML models operate based
in response to decision rules [12.
Fairness in MI has been widely studied, leading to the development of multiple fairness criteria such 17]. and individual fairness [18). However, fairness in strategic settings introduces new complexities. While some research has explored how strategic behavior may mitigate or exacerbate unfairness [19], much of the
as statistical parity [3] [4), equal opportunity [15], counterfactual fairness [76
focus has been on group fairness (20 2T. Less attention has been given individual fairness even as strategic behavior amplifies disparities near decision thresholds.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Beyond faimess in prediction outcomes, strategic classification raises concerns about faimess in
social burden (i.e., the cost individuals must pay to meet decision criteria) 22 Since different individuals face varying levels of difficulty in modifying their features, strategic decision-making can lead unfair cost disparities. Prior work has examined the trade-off between social cost and institutional utility [22] and proposed group-specific thresholds to mitigate cost disparities [23]. However, ensuring individual fairness with respect to individual cost remains an open problem. For instance, two individuals with similar underlying qualifications may be forced to pay different costs to receive the same decision simply because one lies just below the decision threshold.
In this work, we analyze binary strategic classification and demonstrate that deterministic threshold- based classifiers inherently violate individual faimess. To address this, we propose a randomized thresholding approach, proving that individual fairness can be achieved if the threshold distribution satisfies certain conditions. Furthermore, we show that the optimal threshold distribution can be efficiently computed via linear programming, Finally, we investigate the challenge of simultaneously achieving individual and group fairness, proving that this can be accomplished by adding constraint to the threshold Distributionwhiln still preserving the linear programming formulation.
Our results provide principled framework for fair decision-making in strategic classification, ensuring equitable treatment both in terms of predictions and the costs individuals must bear to adapt. By addressing fairness from both an individual and group perspective, our approach offers a practical and computationally efficient solution to mitigate unfaimess in real-world strategic decision-make -aaiin systems.
2 Notations and Preliminaries
2.1 Strategic Classification
In this paper, we consider a binary classification problem in a strategic environment. The goal is to find a classifier ʃ X + +' to predict binary label Y from the observed features X with X E X and Y E E' (0. 3. In strategic setting. I is being used by a decision maker/institution to identify qualified individuals for job or position, and individuals can improve their features æ to get better result]] ! When an individual adjust feature x to x', a cost will be incurred which is represented by cost function e: X' x X + E U {0} with c(x, x) = 0, Vr E X. The institution and individuals aim at maximizing their utility functions. The utility function of the institution is the accuracy on the improved/adjusted features, i.e., (fs Pr(f(X') = Y).
The individuals need to consider both the gain from the classification and the cost they need to pay
for the feature improvement. So, their utility is defined as follows, Undii (f) = [f(x') - fx)]
Ac(a, x'), where is a positive constant measuring the relative importance the cost to people. The
best response of person is x' such that Vindio (f) is maximized. We denote the best response to classifier f as Az()) = arg max. Windio (f)-
In this paper, we will analyze the strategic classification problem where x is general d-dimensional feature vectors. The following definition and assumption will be used throughout this paper.
Definition 2.1 (d-dimensional binary classification problem). A d-dimensional binary classification problem is a problem of finding a classifier f : X + y with X C Idd and y = =(, 13. Assumption 2.1. In d-dimensional binary classification problem, we assume there is a function 1(x): : R2d + TR, such that
((x1) 2 ((22) if Pr(Y = 1|X 31 2 Pr(Y = 1|X = =x2).
(1)
and
(x11) & ((22) If Pr(Y = 1|X = m1 & Pr(Y = 1|X = 22). We further assume that ((x) is continuous and differentiable function and 1(X) E [C, D).
(2)
Note that we adopt Assumption 2.1 as it is commonly used in the literature 22 The existence of l(x) ensures that the problem can be addressed using threshold- based classifiers on ((x). In many real-world scenarios (for example, when bank decides whether issue a loan based on an applicant's 's credit score) 1(z) could simply be since a higher credit score typically indicates
'Capital letters are being used for random variables, and small letters are being used for realizations.

---

a lower risk of default. When æ lies in high- digh-dimensional space, a reasonable choice for ((x) is
((x) = 1
In this paper, we focus on threshold classifiers. A deterministic threshold classifier in a d-dimensional binary classification problem is given by,
f(x:t) 1 ((Ax(f)) 2|
where is a fixed threshold associated with classifier f'a;; t), and 1(-) is an indicator function [24].
Note that Ar is used in because the classifier is applied to adjusted features rather than original features.
2.2 Randomized Classifier
We denote a randomized classifier # as a random mapping from X' to V. Each randomized classifier associated with function family F and probability distribution P over F. Given z, the output distribution is,
Pr (r( =
Σ
P()-
fE(M(N())
randomized threshold classifier is associated with a distribution over F (f(x; E T), where T is the of possible thresholds. Let p(t) be probability density function over T. Then, for F associated with p(t), we have,
Pr( = f) = -aa0=---rrttiie Jeetrotttltee)>=ol dtt)d
(5)
Note that deterministic classifier [(; tu) can be regarded as a special randomized classifier with 5(t ta), where 8(-) is the unit impulse function (also referred to Dirac delta function
p(t)
25
For the rest of the paper, we are focusing on randomized and deterministic threshold classifiers.
2.3
Best Response Cost
Since in this paper we consider strategic setting, the individuals always choose the best response to the classifier announced by the institution/decisionn maker. We define the Best Response Cost (BRC) associated with an individual with feature x as follows, cf(x) = cxx, Ar(f)).
For randomized classifier F. BRC is
c5 (x)
= B(c(,, An()))
(6)
JEF
We assume that cost function c(x,x') depends on the distance between ((x) and l(x'). More precisely, we consider the following cost function,
c(x, - [9(((x')- ((x))
1(x') 2 1(x), I(x') < 1(z).
where g : IR + RR is differentiable and is strictly increasing function satisfying g(0) 0. When 1(x) < 1(x'), the cost is infinite because we are considering a threshold-based classifier, and decreasing ((z) will decrease the probability of being positively classified. Therefore, we have the following best response function.
(A(f(=;)))) ( ((x)) ((x) <())< (t)g<t1--1(
1(x) 24 1 <i(0) <1(x)< <1))) <t
For notational convenience, we denote the constant - -1(+) as C. When ((x) < (. L the individual cannot benefit from increasing ((x:) due to the high cost. When 1(x:) 2 1, the individual does not need to change the feature to change the outcome. Only when C S 1(x) < (, increasing ((x: to L will
result in positive utility V Undii (f).
3

---

2.4 Individual Fairness
Dwork el al. (26) proposes the notion individual fairnsss that requires people with similar features to be treated similarly. We can adopt similar definition for strategic setting. Mathematically, individual fairness with respect to (W.r.t.) the expectation of outcome/decision & a strategic setting is defined as follows.
(x)))) - B{ & ||= - x2ll
where Mp is a predefined constant, || 22 is the Euclidean distance between 21 and 22. We can also adopt individual fairness with respect to BRC. In particular, we say the individual fairness with respect BRC is satisfied if the following holds,
(c c S Me |2 x2ll2
(10)
3 Individual Fairness with Repspect to BRC
In this section, we show for certain (2)), a classifier with a deterministic threshold can never satisfy individual faimess with respect to BRC. Then, we identify conditions under which a randomized classifier satisfies individual fairness. We also discuss how to find fair optimal randomized classifier.
Consider a deterministic classifier f(;; fo). Note that if to < +++CC C, then all the individuals after choosing the best response will be assigned label 1, and f(z;ty) cannot distinguish between qualified and unqualified individuals. Therefore, in the following theorem, we focus in case where to E (C + C, D).
Theorem 3.1. Consider d-dimensional binary classification problem with deterministic classifier f f(;; fo) with to E (C' +C, D). If is reverse Lipschitz continuous, i.e.
((x1 1(x2)) 2 L || - .zll2- L1 < 00, Vx1, 22:
(11)
then for any constant Mc. there exist æı, T2 X such that (cy(21) (x(22) > Mc 1|2 - r2ll2-
Condition [II ensures that the change in x can effectively change ((x) to affect the classification
result. From the proof of Theorem [3 in Appendix A. BRC is not continuous Zo where 1(zn) = to - C, and individual fairness does not hold. Therefore, we relax a deterministic threshold and consider randomized threshold. The following theorem implies that we can achieve individual fairness with respect to BRC by adding constraints on distribution p(t).
Theorem 3.2. Consider a d-dimensional binary classification problem, and let Ct maxxex V 1 Cg maxie[o.c] (!),,, and F = (f(x; (C + C, D)) for random- ized classifier F. p() S Le with Le = mint AM, C. c,C,ch. then for constant Mos Van, x2 X,
we have,
(cx(x1) cg (x2)) S Ma | x2l12-
Theorem 3.2 shows that by relaxing the hard threshold, the individuals with feature vector an such that ((xp) to C (e is a positive constant) now also have the opportunity change the classification result by paying a certain cost.
3.1 Fair Optimal Randomized Classifier
Theorem demonstrates the existence of randomized classifiers that can achieve individual fairness. However, not all threshold distributions yield high accuracy, so it is necessary to identify one that achieves the highest possible accuracy. In this section, our goal is to find a randomized classifier that minimizes the error rate while satisfying individual fairness. Let e(t) denote the error rate of f(:t). Then, we have,
e(t) = f.e PP(Y 1[((X
(X(Y=1[((>>>) ()pz + ["" Pr(Y 0|((X) ()))(()
(12)
where (!) is the probability density function of L = 1(X). Note that Pr(4i S 1(X) S 12) = Sh (()dd For notational convenience, we denote (o( Pr(Y 0I((X) ()p((() and

---

Pi(1) Pr(Y 1[( = (1). Hence, to find the optimal classifier F we need to solve the following optimization problem.
[ e(t)p(t)dt
pe(t) arg min p( [e(t)] p(t)
arg min p(t) C+C
s.t. { Joce p(t)dt= - 0 0 p(t) Lc
(13)
In the above optimization problem, Le is a constant that controls the fairness level. Smaller Le leads better fairness level. Solving problem| 13 is difficult because p(t) general function, and convex or linear optimization techniques cannot be directly used. To tackle the challenge, we consider an approximated solution where Pe(t) piecewise constant function. Given a hyper-parameter K, we assume that (C + C, D) can be divided into K bins with the k-th bin corresponding to CC+C+ (6-1XD-C-C) C-C) C C+ kDDCC-C) and Pe(() has constant value in each bin. We denote A these constant values as {Pet, Pe2, m. Pck and for simplicity, we denote the start point of the k-th
K
bin 8k, i.e. 8k C++ (k-1)(D-O0 1110---00) C-C Then, the average error rate for randomized classifier given by,
D Jo e(t)p(t)dt=
Σ I
K
(fo pi(()dl S.- po(()a( dt.
Pok
(14)
k=1
Define Ack
[ 8k41
(10- pi(1)dl+
[- po(()a)) dt.
Ack
(15)
Because Ack is a constant and determined solely by the distribution of 1(X), the optimization problem 13 can be translated as the following linear optimization problem,
s.l. Σ PeelD -C =1, 0 Pck Pek S Tuc-
min
AckPPkk
(16)
K
The above problem can be efficiently solved using linear programming techniques (e.g., simplex method (27)). Algorithm[aand shows how to find the optimal randomized classifier and use it to make a prediction.
Algorithm 1 Finding optimal randomized classifier satisfying individual fairness w.r.t. BRC
Input: Training data = {zi, 3: - X, Mc, function g, /
1: C- g))) Tue min ( AM M
C.C.C
2: Estimate Ask from data with Eq. 15
3: Solve the following optimization problem,
Pek (D C 10-O) 1, 0 Pek S Le
Pek arg min
AckPak s.t.
Output: Pek
Individual Fairness with Respect to Outcome
In this section, we show that our proposed randomized classifier can also be used to improve individual fairness with respect to decision/outcome. Given a randomized classifier F we define the average prediction outcome as follows, Y (x) = E₁er f()) = -x)}
Individual fairness with respect outcome with constant M, requires (x) - < Mpl |1 ø2/12, Vx,, 22 E X. For certain I(x), we can prove any deterministic classifier canmot satisfy this constraint.
We use SK-1 to denote the end point of the last bin though there is actual (K 1)-th bin.
5

---

Algorithm 2 Inference with a randomized classifier
Input: Data point 2, threshold distribution Pok. intervals (5R, Sk41), {l, Kj, function !
1: Sample k from distribution Pr(K k) = -t-1 Pek
2: t + + 7 is random noise sampling from a uniform distribution on [0, 8k+1 sk)
y + 1[(()) 2 t]
Output: !)
Theorem 4.1. Consider a d-dimensional classification problem and a randomized classifier & with p(t) = ō(to) and to & (C+ C, D). ((x) is reverse Lipschitz continuous, i.e..
[(x11) 1(x2)1 2 L 1 x2ll2: La < o0, Va1, 222
(17)
then for any constant Mp. there exists I1, 22 X. such that ( so
>
Mp || x2l12-
Similar to Theorem 3.1 Theorem 4.1 shows that the expected outcome is not continuous at zo satisfying (200 to C. When use a randomized classifier, of which the distribution of thresholds has no impulse component, the individual fairness with respect to outcome can be satisfied. The following theorem illustrates this point.
Theorem 4.2. Consider d-dimensional binary classification problem, and let Ct max, [+)))) and F (z;;;))) t)]t (C CC+ p(t) S Top with Tnp Mp then for C
constant Mg. we have, (11) (x2) $ Mp |m x2 22l22- V21.
Now we that the requirement for individual fairness fairness w.r.t. BRC. To find the optimal distribution of p(t) for individual fairness w.r.t. outcome, we solve similar optimization problem (13 by replacing p(t) S The constraint with p(t) s Tep Our theorem also provides the possibility of achieving individual fairness w.r.t. BRC and outcome at the same time by using constraint S p(t) < min(Le,4p).
outcome is very similar individual
5 Extension to Group Fairness
The analysis of our paper demonstrates the potential usage of randomized classifiers when pursuing individual fairness. real-world applications, people are often concerned not only with individual fairness, but also with fairness across different groups (28) There are several methods used to achieve group fairness in the literature (20 29 30 However, individual fairness and group fairness can conflict in some situations 311. This proposes the question that whether an individually fair randomized classifier can achieve group fairness. To answer this question, we extend the binary
classification problem in Section 2 to multi-group case. The following definition and assumptions will be used in this section.
Definition 5.1 (Multi-group d-dimensional binary classification problem). A d-dimensional binary classification problem is a problem of finding classifier J X x A with X' C Rd, where A is the domain of sensitive altribute which is often discrete set. We denote the features from group a E A as Xa-
Assumption 5.1. In a multi-group d-dimensional binary classification problem, we assume there are functions La (x) for each group such that
la(x1) 2 (a(22) iff Pr(Y = 1|X x A = 2 Pr(Y = 1|x = x2, A=
and
(ta iff Pr(Y = 1|X x1, A= Pr(Y = 1|8 x2, A = a} We further assume that lx) are continuous differentiable functions and I(X.) ) E IC.. Dal.
For multi- group cases, assume the cost function g(.) is different for each groups, which denoted as 9.).). For simplicity, we denote the constants -1a))1(( as C.. An important group

---

faireess metric is statistical parity, which requires that the classifier has the same positive outcome rate over all groups, i.e., Pr( 1/A a} Px( 1|A= Va, A.
In this part, our goal is to find one classifier for each group to ensure statistical parity. We use Pa()) to denote the distribution of threshold for group A a. Denote the probability density function of la (z) pf (1). Given (t),, the overall distribution of Pr(.F(X)
1|A = a} is given by,
J Sctte.
Da
(Leo L-C
D= Pf. (t)dz Pa (t)dt.
Pr( = 1|4 = a)
(18)
Denote the group-specifie error rate ea(1) which is calculated as follows,
Ca
L. I.c.
Do
(t) Pr(Y=1440 (()d
Pr(Y (X) ()22())l
(19)
we can find optimal (t) by solving the optimization problem
Palt) arg min
Σ
(a(t)pa(t)dt Pr(A-
(f()) aEA Cutc.
Da
s.t.
Pa(t)= =1, 0 pat Va E A,
C4Cc
foo Imm ( (2 ) Sentees (Frre Dt (1())))) Pa (t)de, Va, a' E A.
(20)
The objective function is the weighted average of error rate across different groups To solve this problem, we consider an approximated solution where all (t) are piecewise constant functions. Given a K, we assume that (C. Ca, D.) can be divided into K bins with the k-th bin corresponding to
where L could be Le or Lp from Theorem 3.2 or Theorem
(Ca + CC. + (D- C. C.), Co + Cu + k(D. C. Co2] and Pt(t) has a constant value each bin. K m. Pak J. and for simplicity, we denote the start point (D-1)(D-CooCC of the k-th bin as Sak. i.e. 8ak = Co + Ca + (k-1)(D.- Co -Ca The last constraint in (20 can be re-written as follows.
K We denote these constant values as (Pa1 Pa2r ..
K
K
(__ dt
Patk (raeett
(fec) Pa (aa dt, Va, d' A. (21)
Pak
Jack
k=1
k=1 = Seackte) (i()dt)))) and similarly define
Define
Bak
Agk
( (Se- p9(1)dl + P. - ((())dt) dt, where (1) = Pr(Y = 0)la(X) = (1),
Pb(1) = Pr(Y = 0(la(X) = (f). Then problem (0) can re-written as,
DDa C.
Ca)Pak 1, 0 Pak S L, Va A,
min
AakPak Pr(A a}, s.t.
acA, OSKSK
K
OEAR
K BakPak Σ
BalkPo' Ya,d' E
(22)
k=
k=1
In practice, the statistical parity constraint can be too strong such that the optimization problem
has no solution. Therefore, it can be relaxed as ===1 BaNDas Ek Barka S Ω Va, a' E A.
The value of Ω can be used to control the extent of statistical parity.
Apart from statistical parity, equal opportunity and equalized odds are also commonly used group fairness metrics. For prediction, equal opportunity [15] requires that
Pr S (X) = 1 = 1, A = a) = Pr $ (X) = 1 = 1-A=a} Va, E.A.
(23)
Equalized Odds 32 implies that
Px) = 1|Y y, a} (x( = 1|L y, A = Va,a' A,y
(24)
The optimization problem (2) can be slightly modified to satisfy equal opportunity or equalized odds.
7

---

Experiment
Dataset and Implementation. In this section, conduct experiments two real-workd datasets to evaluate the effectiveness of our proposed methods. The first dataset is the FICO dataset, pre- processed by [15]. This dataset provides the cumulative distribution of credit scores across different racial groups. In our experiments, we generate 5,000 data points according to the distributions for the racial groups Black and Non-Hispanne denotes the credit score and a represents the individual's race. We assume (xx) K., and define the
White. Each feature vector is defined as := [Ks, a], where
individual utility function as Windin (J) = (xx'') [(r) 100(((=') (xx))² with the associated cost function given by c(z, = 100(((x²) (())
The second dataset is the Law School Dataset (33, which contains 18,692 student records. We use the same pre-processed version employed in the experiments of [[6]. The prediction task is to determine whether student will pass the bar exam. In our experiment, we include all features excluding zgpa and the target variable bar_pass in the feature vector x. The zgpa variable, representing a student's final law school GPA, is used ((x) To estimate (xx) in practice, train a linear regression model using the remaining features x to predict zgpa. When evaluating group fairness, we consider race as the sensitive attribute. We define the individual utility function Vindio (f) [f(x') - [[))] (I(x') - 1xx))², with the corresponding cost function c(x, = (1(x') (xx))
We split the dataset into train/validation//et datasets randomly with a ratio of 20%/20/%20. The baseline model for individual fairness experiment (Tables | and 2 is the best deterministic classifier. For the group fairness experiments (Tables 3 and 4 the baseline model consists of two deterministic thresholds (one for each group). We find the deterministic thresholds using grid search on all possible combinations which will maximize the macro average F1 score while satisfying group fairness constraints. For the Law School dataset, we set the number of bins K to 80 and set it to 200 for FICO dataset. Apart from using F1 score to evaluate the accuracy, we use IF ratio for evaluating individual fairness, Statistical Disparity (S-DP), Equal Opportunity Disparity (EO-DP) and Equalized Odds Disparity (ED-DP) for evaluating group fairnsss Assume the dataset is {a;, yi 2 (sensitive attribute h--%1 a, is included in x,), IF ratio is defined as maX , For the deterministic classifier, % is the predicted outcome or the BRC for data Z,. For the randomized classifier, %/4 is the expected outcome or expected BRC. S-DP is [Pr = 1/0 = 1} Pr(ū: = l|; = 0) EO- DP is defined as [Pr is estimated as the ratio in the dataset, and ED-DP is the maximum conditional disparity across both positive and negative classes [P
1/a,- 1, 3/ 1}- Pr(ü: 0; 1/a; = 0, y/ = 1}. where the probability
l|a: = 1, = 13 Pr(s- = =1/a; = 0, y/ 1}1,
[Pr(0 = 1/a;- = 1, y: = 0} - Pr(u = 1 la: 0, yı 0}1}.
Results. Table and Table SablleSshon show the results when using randomized classifiers for the two datasets with different upper bounds on the distributions. IF ratio is measured w.r.t. the prediction For the
Table 1: Results on FICO dataset applying our randomized classifier
Randomized Classifier
Method
Deterministic Classifier
Lp =
Lp = 0.5
Lp = 0.25
Lp = 0.1
F1 score
0.986 + 0.001
0.986 0.001
0.986 = 0.001
0.984 + 0.002
0.975 = 0.003
IF ratio
4.421 = 0.691
1.000 + 0.000
0.500 = 0.000
0.250 + 0.000
0.100 = 0.000
S-DP
0.355 1 0.020
0.009
0.356 1 0.018
0.352
0.017
0.355 1 0.015
EO-DP
0.016 1 0.011
1.061000010
0.019 0.010
0.016
0.026 + 0.011
ED-DP
0.016 + 0.011
0
0.019 + 0.010
0.016 1
0.026 + 0.011
FICO dataset, we can improve individual fairness for a large extent (4.421 to 0.100) with only a small accuracy drop. The IF ratio is equals to the upper bounds Lp. which is consistent to Theorem 4.2 For the Law School dataset, we observe that with larger Lp. we have a smaller IF ratio with smaller F1 score. IF ratio is not equal to I.p because of the gradient introduced by the linear regression model as discussed in Theorem [.2 We also measure the group fairness metrics, which shows that there is no direct relationship between individual faimnsss and group fairness. Therefore, it is possible that we improve individual fairness with a randomized classifier while not exacerbating group unfairness.
Figure I in Appendix B.1 shows that the estimated Pr. babrbarrrru pass = 1/zgpa) satisties Assumption 2.1 brief description of each attribute is provided Appendix B.
In Appendix
C we displays the results for BRC.
8

---

Table 2: Results on Law School dataset applying our randomized classifier
Randomized Classifier
Method
Deterministic Classifier
Lp 0.8
Lp
Lp 0.3
Fl score
0.680 + 0.013
0.587 + 0.010
0.585 + 0.012
0.345 + 0.011
0.545 + 0.011
IF ratio
3.161 + 1.671
0.561 + 0.008
0.449 0.007
0.221 + 0.003
0.175 + 0.005
S-DP EO-DP
0.443 0.012
0.476 + 0.019
0.470
0.399 - 0.019
0.350 0.014
0.350 0.028
0.433 1 0.041
0.431 0.034
0.357 0.040
0.309 0.041
ED-DP disparity
0.362 0.021
0.433 + 0.041
0.431 0.034
0.357 1 0.040
0.309 0.041
While fixing Lp = 1, we validate the effectiveness of our statistical parity constraint in Section by setting 12 as different values. From TableBandd the randomized classifiers can have better statistical parity as we decrease f2. At the same time, we get lower IF ratio compared to the baseline, which means we improve the group fairness and individual fairness simultaneously. Again, the results show no clear correlation between individual fairness and statistical parity.
Table 3: Results FICO dataset applying randomized classifier with statistical parity constraint.
Randomized Classifier
Method
Deterministic Classifier
Ω 0.1
Ω 0.08
f 0.06
Ω 0.04
Fl score
0.837 + 0.006
0.818 + 0.006
0.800 = 0.008
0.779 + 0.008
0.756 = 0.009
IF ratio
21.58 + 25.87
1.000 + 0.000
1.000 0.000
1.000 + 0.000
1.000 = 0.000
S-DP
0.115 = 0.022
0.114 0.018
0.094 = 0.022
0.072 - 0.019
0.050 = 0.015
Table 4: Results Law School dataset applying randomized classifier with statistical parity constraint.
Randomized Classifier
Method
Deterministic Classifier
Ω 0.1
Ω = 0.08
O = 0.06
Ω 0.04
Fl score
0.642 + 0.016
0.554 0.016
0.562 + 0.020
0.567 + 0.017
0.575 + 0.013
IF ratio
12.15 + 18.11
0.655 + 0.065
0.673 = 0.056
0.681 + 0.055
0.689 = 0.062
S-DP
0.047 + 0.038
0.039 0.018
0.036 0.017
0.031 + 0.016
0.026 = 0.014
7 Conclusion
In this paper, we prove the existence of unfairness in strategic classification when using determin- istic threshold-based classifiers. To address this issue, propose a novel approach that employs randomized thresholds, ensuring fairness through an optimizable threshold distribution. We show that this distribution can be efficiently determined using linear programming. Furthermore, by appro- priately constraining the threshold distribution, we can achieve both individual and group fairness simultaneously maintaining computational efficiency through linear programming.
8 Limitations
While our randomized classifiers offer significant advantages, it is important note that the proposed method is applicable only when the classification problem can be effectively addressed using threshold- based classifier. A key assumption the existence of function 1(x:) such that the cost depends solely on the distance between I(x1) and ((z2). If this assumption is violated, the method may no longer be valid. Additionally, when the dataset too small, estimation errors can negatively affect performance. The time complexity of solving linear optimization problem with K variables using the simplex algorithm can be exponential, i.e. (22 34 which may limit the number of bins that can be used in practice.

---

Acknowledgment
This work is supported by the U.S. National Science Foundation under award IIS-2301599, CMMI- 2301601, and DMS-2529302 and by grants from the Ohio State University's 's Translational Data Analytics Institute and College of Engineering Strategic Research Initiative.
References
[1] Anna M Costello, Andrea K Down, and Mihir N Mehta. Machine+ man: A field experiment on the role of discretion in augmenting ai-based lending models. Journal of Accounting and Economics, (012-))1013360 2020.
[2] Yi-Chi Chou and Han-Yen Yu. Based on the application of ai technology in resume anal- ysis and job recommendation. In 2020 IEEE International Conference on Computational Electromagnetics (ICCEM), pages 291-296. IEEE, 2020.
[3] 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.
[4] Zeyu Tang, Yatong Chen, Yang Liu, and Kun Zhang. Tier balancing: Towards dynamic fairness over underlying causal factors. arXiv preprint arXiv:2301.08905 2023.
[5] Zhiqun Zuo, Tian Xie, Xuwei Tan, Xueru Zhang, and Mohammad Mahdi Khalili. Lookahead counterfactual fairness. arXiv preprint (ix::24/22000m66 2024.
[6] Yingqiang Ge, Shuchang Liu, Ruoyuan Gao, Yikun Xian, Yunqi Li, Xiangyu Zhao, Changhua Pei, Fei Sun, Junfeng Ge, Wenwu Ou, et al. Towards long-term faimeess in recommendation. In Proceedings of the 14th ACM international conference on web search and data mining, pages 445 453, 2021.
[7] Moritz Hardt, Nimrod Megiddo. Christos Papadimitriou,, and Mary Wootters. Strategic classi- fication. In Proceedings of the 2016 ACM conference on innovations in theoretical computer science, pages 11 111-122 2016.
[8] Tian Xie and Xueru Zhang, Non-linear welfare-awan strategic learning. In Proceedings of the AAAI/ACM Conference on Al, Ethics, and Society, volume pages 1660-1671, 2024.
[9] Tian Xie and Xueru Zhang, Automating data annotation under strategic human agents: Risks and potential solutions. Advances in Neural Information Processing Systems, 37:127436-127482 2024.
[10] Ravi Sundaram, Anil Vullikanti, Haifeng Xu, and Fan Yao. Pac-learning for strategic classifica- tion. Journal of Machine Learning Research, 24(192):1-38, 2023.
[11] Hanrui Zhang and Vincent Conitzer. Incentive-aware pac learning. In Proceedings of the AAAI Conference Artificial Intelligence, volume 35, pages 5797-5804, 2021.
[12] Juan Perdomo, Tijana Zmic,, Celestine Mendler-Düinner, and Moritz Hardt. Performative prediction. In International Conference on Machine Learning, pages 7599-7609. PMLR, 2020.
[13] Philippe Besse, Eustasio del Barrio, Paula Gordaliza, Jean-Michel Loubes, and Laurent Risser. A survey of bias in machine learning through the prism of statistical parity. The American Statistician, 76(2):188-198, 2022.
[14] Zhiqun Zuo, Ding Zhu, and Mohammad Mahdi Khalili. Post-procsssing for fair regression via explainable svd, 2025.
[15] Moritz Hardt, Eric Price, and Nati Srebro. Equality of opportunity in supervised learning. Advances in neural information processing systems, 29, 2016.
[16] Matt Kusner, Joshua Loftus, Chris Russell, and Ricardo Silva. Counterfactual fairness. Advances in neural information processing systems, 30, 2017.
10

---

[17] Zhiqun Zuo, Mahdi Khalili, and Xueru Zhang. Counterfactually fair representation. Advances in neural information processing systems, 36:12124-1214 12140, 2023.
[18] Felix Petersen, Debarghya Mukherjee, Yuekai Sun, and Mikhail Yurochkin. Post-processing for individual fairness. Advances in Neural Information Processing Systems, 34:25944-25955, 2021.
[19] Xueru Zhang, Mohammad Mahdi Khalili, Kun Jin, Parinaz Naghizadeh, and Mingyan Liu. Faimess interventions as (dis) incentives for strategic manipulation. In International Conference on Machine Learning, pages 26239-26264. PMLR, 2022.
[20] Emily Diana, Saced Sharifi Sharifi-Malvajeerdi, and Ali Vakilian. Minimax group fairness in strategic classification. arXiv preprint arXiv:2410.02513, 2024.
[21] Andrew Estorell, Sanmay Das, Yang Liu, and Yevgeniy Vorobeychik. Group-fair classification with strategic agents. In Proceedings of the 2023 ACM Conference on Fairness, Accountability, and Transparency, pages 389-399, 2023.
[22] Smitha Milli, John Miller, Anca D Dragan, and Moritz Hardt. The social cost of strategic classification. In Proceedings of the Conference Fairness, Accountability, and Transparency, pages 230-239, 2019.
[23] Vijay Keswani and L Elisa Celis. Addressing strategic manipulation disparities in fair clas- sification. In Proceedings of the 3rd ACM Conference on Equity and Access in Algorithms, Mechanisms, and Optimization, pages 1-11, 2023.
[24] Stephen Cole Kleene. Introduction to metamathematics, sixth reprint, 1971.
[25] GB Arfken and HJ Weber. Mathematical methods for physicists (chapter 1, section 1.15), 2000.
[26] Cynthia Dwork, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Richard Zemel. Fairness through awareness. In Proceedings of the 3rd innovations in theoretical computer science conference, pages 214-226, 2012.
[27] David Gale. Linear programming and the simplex method. Notices of the AMS, 54())3644-36, 2007.
[28] Simon Caton and Christian Haas. Fairness in machine learning: A survey. ACM Computing Surveys, 56(7):1-38, 2024.
[29] Eunice Chan, Zhining Liu, Ruizhong Qiu, Yuheng Zhang, Ross Maciejewski, and Hanghang Tong, Group fairness via group consensus. In The 2024 ACM Conference on Fairness, Account- ability, and Transparency, pages 1788-1808, 2024.
[30] Negin Golrezaci, Rad Niazadeh, Kumar Kshitij Patel, and Fransisca Susan. Online combinatorial optimization with group fairness constraints. Available at SSRN 4824251, 2024.
[31] Reuben Binns. On the apparent conflict between individual and group fairness. In Proceedings of the 2020 conference on fairness, accountability, and transparency, pages 514-524, 2020.
[32] Yaniy Romano, Stephen Bates, and Emmanuel Candes. Achieving equalized odds by resampling sensitive attributes. Advances neural information processing systems, 33:361-371. 2020.
[33] Linda F Wightman. Lsac national longitudinal bar passage study. Isac research report series. 1998.
[34] John Fearnley and Rahul Savani. The complexity of the simplex method. In Proceedings of the forty-seventh anmual ACM symposium on Theory of computing, pages 201-208, 2015.
[35] eds8531. Lsac dataset eda and predictions. https::/ //t::://wwww www. www.kaggl..oo com/ code/oodeeceeeoooo /53d/// 1sac- eda- oace-aaaaaa---dd------rreeeetttd andddaattddrreiiiiionnnn... 2022. Accessed: 2025-04-30.
11

---

NeurIPS Paper Checklist
The checklist is designed encourage best practices for responsible machine learning research, addressing issues of reproducibility, transparency, research ethics, and societal impact. Do not remove the checklist: The papers not including the checklist will be desk rejected. The checklist should follow the references and follow the (optional) supplemental material. The checklist does NOT count towards the page limit.
Please read the checklist guidelines carefully for information on how to answer these questions. For each question in the checklist:
You should answer [Yes], [No] or [NA]. .
[NA] means either that the question is Not Applicable for that particular paper or the relevant information is Not Available.
Please provide short (1-2 sentence) justificatin right after your answer (even for NA).
The checklist answers are an integral part of your paper submission. They are visible to the reviewers, area chairs, senior area chairs, and ethics reviewers. You will be asked to also include (after eventual revisions) with the final version of your paper, and its final version will be published with the paper.
The reviewers of your paper will be asked to use the checklist as one of the factors in their evaluation.
While "[Yes] " is generally preferable to "[No]" ", is perfectly acceptable to answer "[No] "provided proper justification is given (c.g., "error bars are not reported because it would be too computationally expensive" or "we were unable to find the license for the dataset we used"). "[No] or "[NA] is not grounds for rejection. While the questions are phrased in binary way, we acknowledge that the true answer often more nuanced, so please just use your best judgment and write justification to elaborate. All supporting evidence can appear either in the main paper or the supplemental material, provided in appendix. If you answer [Yes] to a question, in the justification please point to the section(s) where related material for the question can be found.
general, answering
IMPORTANT, please:
Delete this instruction block, but keep the section heading "NeurIPS Paper Checklist",
Keep the checklist subsection headings, questions/answers and guidelines below.
Do not modify the questions and only the provided macros for your answers.
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: We have two main claims the abstract and introduction: using randomized classifier to satisfy individual faireess and extending it group faimness notions. The former claim is addressed in Section 3 and Section 4 and the latter one is discussed in Section
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results
be expected to generalize other settings.
is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors? Answer: [Yes]
12

---

Justification:
We discuss the limitations of our method in Section g
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: General assumptions needed for the theorems are explicitly stated in Assump- tion 2. and 5.1 The additional assumptions used by each theorem included in the theorem itself. The proofs for the theorems are provided in Appendix A
Guidelines:
The answer NA means that the paper does not include theoretical results. All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: We presents the details of experiment implementation in Section 6 and Ap- pendix for reproducing our results. We would also release the code and data used in the experiments to enhance reproducibility.
13

---

Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm. (b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g.. a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open- open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: We submit the code and dataset we used to produce the experiment results with paper.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips. cc/
for more details.
While we encourage the release of code and data, we understand that this might be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
/ ptaips.cc//uulic//uuu
for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
14

---

At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible supplemental material (appended to the paper) recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: We present all the important setting in Section and Appendix In the supplemental material, we include the code.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Question:
Does the paper report error bars suitably and correctly defined or other appropriate
information about the statistical significance of the experiments?
Answer: [Yes]
Justification: For all the numbers in the results, report the variance when changing different random seeds for data split and sampling.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative enror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
We present the information about this in Appendix B.2
Guidelines:
15

---

The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics http://////arr....coooo///////ta
Answer: [Yes]
Justification: Our paper does not involve human participants. The datasets we used are all publicly available and do not include privacy information.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e-g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: discussed in Section X that when our method applied when the assump- tions not hold, it could have negative effect fairness.
Guidelines:
The answer NA means that there no socictal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g.. deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of MI.).
11. Safeguards
Question: Does the paper describe safeguards that have been put in place for responsible release of data models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
16

---

Answer: [NA]
Justification:
Our paper does not release any new model or dataset.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (c.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification:
The two dataset used in our experiments are well cited in Section 6
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
The paper does not release any assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/moodll as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
17

---

Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Question:
Answer: [NA]
Justification: No human subjects are involved in the research.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Justification:
LLM is only used for grammar and spelling checking while writing the paper.
Guidelines:
The answer NA means that the method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy / ce /c////oaaeeeeccce/222////111 for what should or should be described.
18

---

A Proofs
A.1 Proof for Theorem 3.1
Proof. When to E (C + CC D), we can find 21 such that ((11) = to C in X. From the definition
of BRC, we have (2(x)) = f. For any positive constant know that for ig satisfying (x22)
to - C - (z(( = O. Because (x) satisfies
((x1)) (2221 2 La | 22l12
(25)
have
(cg(x1) -c((x2) = X
(26)
|01 x2l12 Li
(27)
When <
Lt_ M. we have (cy(x1) - cy(22) > Mc ||2 x22l
A.2 Proof for Theorem 3.2
Proof. For any input æ, the individual cost is
((())C c5 = (((n)
g(t - (d==(()))(t)dt.
(28)
The gradient of c (z) is
- ('a)tt (((t)(()))((tdd
Vocs(z) vx((x) 9(C)p (1xx) + +C) -00(()((((())))
(29)
[(())
From the assumptions that g(0) = 0 and g(C) 1.4 we have
((0)+C Lee
[V = (=))l pp(((2) +C)
g'(t c(t-1(x)) (())(()))(tdtt)
(30)
Since g(-) is strictly increasing, have g.) > 0. Therefore,
x0((())+))- +0)- - g'(t ((t-1(z))p(tt))
[Lp((())) + +C) - [ite) dli))(
g'(t g((t-1(x)) (x)))(()((()) if ()(((x)+))2 S(a) d(0)+ g'(t - (())))
Unle dio)+e g((t - ((x))p(t)dt - tp(((x)) +C) otherwise.
(31)
If (p((x)) + C) 2 lite g'(l ((1--(2)))) (())((()))((ddL, then
plx)+e
CiLe
/Vcc((E)la S [ f(((()) +C) X
(32)
If T., AMs C then [V (2)ll2 s Mc.
(p((()))+0) + < [ite
Mxx+C
g'(t ((x))p(t)dt, then 1x)+C
|V < V.l(1)l1
(33)
((2)
Mr If L. C.C,C. then v (=cs(E)]1 Me
Therefore, L. min { AMM M )
C. -.C,J..
19

---

A.3 Proof for Theorem 4.1
Proof. When to E CC+C, we can find 21 E X such that ((x1) to C. From the definition of
Y=(),, we know that
(0)))) = f(21:t0) = 1. For any positive constant can find 22 X satisfying (x22) = to C and we have
(34)
(x2) s02 (0) 0.
(35)
Since (x)) satisfies
((x11) - (x22] 2 Li | 22112
(36)
we obtain
2 ø2112 S Li
(37)
When M. have
- {3((2) > Mp ||||1 - x2ll2-
(38)
L
A.4 Proof for Theorem 4.2
Proof. Consider an arbitrary 21 X, we know that f(x1; t) = if and only there exists æ1, such that
((x1)= 2 t and ((x)--(a)) sc.
(39)
Therefore,
((os)) p(t)dt.
(z(x1)= Jo+c
(40)
Again, we have
-
Junyte p(()dt
S Lp [xx1) [(x2)).
(41)
Because ||=[(x)]]z is upper bounded by Ct, and Lp = ot we have
Me
{ Ys (12) S Mp || - x2ll2
(42)
B Implementation Details
B.1
Dataset
The Law School dataset contains 12 attributes. The information about them are displayed in Table 5 Figure [ shows the estimation of Pr(bar_pass pass- 1 /2ggaa} from the whole dataset. Since the condi- tional probability is an increasing function w.r.t zgpa, Assumption 2. is satisfied. We can regard zgap as 1(x).
B.2
Computational Resources
All experiments are conducted on a server equipped with 64 AMD EPYC 16-Core CPUs. The server also includes 8 NVIDIA RTX A5000 GPUs (24GB each), although GPU resources not utilized for our experiments.
Each experiment runs efficiently, completing 5 random seeds in under hour. The optimization of the randomized classifier computationally inexpensive. However, evaluating the Individual Fairness (IF) ratio is more time-consuming, it requires comparing all pairs (x,, 22) in the dataset {Z,, y)) W)),N resulting in computational complexity of O
20

---

Table 5: The meaning of attributes in the Law School dataset [35
Attribute
Description
Data Information
decilelb
First-year law school GPA decile
integer, ranging from to 10
decile3
Third-year law school GPA decile
integer, ranging from to 10
Isat ugpa
LSAT score
integer, ranging from 0 to 60
Undergraduate GPA on a 4.0 scale Standardized ferst-year GPA (z-score) Standardized final GPA (z-score)
real values in [0, 4.0]
zfygpa
real values in [-4.0, 4.0]
zgap
real values [-4.0, 4.0] 1: full-times, O: part-time
fulltime
Enrollment status
fam_inc
Family income bracket
integer, ranging from 1.0 to 5.0
male
Gender indicator
1: male, 0: female
racetxt
Race category
binary, not clear the meaning of 0 and 1 integer, ranging from to
tier
Law school tier
pass_ban
Bar exam pass indicator
1: pass, O: not-pass
1.0
0.8
Pr (passpar 1/zpa]
0.4
0.2
0.0
-3
-2
Standardized Final GPA (zgpa)
Figure I: Estimated Pr(bar_pass 1/zgpa}
C Additional Results
In this section, we displays the additional experiment results about measuring individual fairness metric (IF ratio) w.r.t. BRC.
21

---

Table Results on FICO dataset applying our randomized classifier with IF ratio measured w.r.f. cost.
Randomized Classifier
Method
Deterministic Classifier
Lc
0.5
Le 0.25
Le
Fl score
0.986 1 0.001
0.986 0.001
0.986
0.001
0.984 1 0.002
0.975 1 0.003
ratio
3.412 1: 1.156
0.866 0.041
0.450
0.034
0.227 0.018
0.090 + 0.006
S-DP
0.355 + 0.020
0.356 -:00
0.356
- 0.018
0.352 1 0.017
0.355 : 0.015
EO-DP
0.016 = 0.011
0.010
0.019 0.010
0.016 + 0.006
0.026 = 0.011
ED-DP
0,016 = 0.011
0.016 =
0.019
0.010
0.016 0.006
0.026 = 0.011
Table 7: Results on Law School dataset applying randomized classifier with IF ratio measured w.r.t. BRC.
Randomized Classifier
Method
Deterministic Classifier
L
Lg 0.8
Le 0.4
Lg 0.3
F1 score
0.680 + 0.013
0.587 + 0.010
0.585 + 0.012
0.545 + 0.011
0.545 + 0.011
ratio
3.776 + 3.039
0,270 + 0.107
0.150 0.085
0.057 : 0.018
0.036 0.018
S-DP EO-DP
0.443 : 0.012
0.476 + 0.019
0.470 0.019
0.399 0.019
0.350 0.014
0.350 0.028
0.433 + 0.041
0.431
0.034
0.357 0.040
0.309 0.041
ED-DP disparity
0.362 0.021
0.433 1 0.041
0.431 0.034
0.357 0.040
0.309 0.041
Table 8: Results FICO dataset applying randomized classifier with statistical parity constraint and ratio measured w.r.t. BRC.
Randomized Classificr
Method
Deterministic Classifier
Ω = 0.1
? = 0.08
Ω = 0.06
? 0.04
Fl score
0.857 + 0.006
0.818 0.006
0.800 + 0.008
0.779 + 0.008
0.756 + 0.009
IF ratio
7.105 + 5.233
0.868 + 0.047
0.853 + 0.037
0.829 + 0.025
0.796 + 0.079
S-DP
0.115 + 0.022
0.114 + 0.018
0.094 0.022
0.072 + 0.019
0.050 + 0.015
Table 9; Results Law School dataset applying randomized classifier with statistical parity constraint and IF ratio measured w.r.t. BRC.
Randomized Classifier
Method
Deterministic Classifier
Ω 0.1
Q = 0.08
f 0.06
Q 0.04
Fl score
0.642 + 0.016
0.554 0.016
0.562 + 0.020
0.567 + 0.017
0.575 + 0.013
IF ratio
12.15 + 18.11
0.166 + 0.055
0.181 + 0.087
0.153 + 0.080
0.147 + 0.025
S-DP
0.047 + 0.038
0.039 0.018
0.036 0.017
0.031 0.016
0.026 + 0.014
22


Reviews:
[{"review_id": "4XV3zHTsDM", "reviewer": "Reviewer_YkdX", "summary": "This paper proposes a method for individual fairness in with respect to varying response costs: interventions on some feature(s), e.g. recourse. Specifically, the authors define their method wrt the Best Response Cost. The authors give significant analytical results over this problem, specifically focusing on randomized classifiers.\n\nThe proposed method is clearly outlined in Algorithms 1 and 2. The authors evaluate their method on two real-world datasets, FICO and Law School. Overall, the method evaluates very well, and flexibly trades off between F1 and individual fairness (alternatively: group fairness).", "questions": "Mostly from above:\n\n1. Could you please elaborate on feature-attribution and and interpretability aspects of randomized classifiers? Is there any way to use a randomized classifier class that is both interpretable and individually-fair wrt intervention costs?  \n\n2. Is there a non-diferentiable heuristic for Ack which handles other base model classes?", "limitations": "Overall, the authors address the model's computational limitations, and the broader potential impacts. The authors demonstrate group- and individual-fairness, which is a strength in the fairness literature; the authors might consider more elaboration of the conflict between groupwise and individual fairness to highlight that this method doesn't sacrifice one for the other.", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 4, "originality": 3, "strengths_and_weaknesses": "Strengths\n\n1. Overall, this is a significant result in individual fairness under recourse. In several domains (e.g. financial), recourse is a legal requirement, and there is much concern about fairness implications (both group and individual) for these recourse responses.\n\n2. The model seems to evaluate quite well, and the evaluation methodology is strong. \n\n3. The model is quite flexible to both individual fairness and statistical parity regularization, L_c, Ω, respectively. This shows significant contribution to group fairness under recourse as well.\n\nWeaknesses\n\n1. The primary weakness seems to be the requirement for a randomized classifier class. While fair recourse is crucial in some domains (Strength #1), so is model *interpretability*. A randomized class of model seems less amenable to feature-attribution scores (e.g. with SHAP), and other governance requirements for these same domains. So in a sense, it seems one step forward (recourse), and one step back (governance). \n\n2. The class of base classifier here seems very restrictive. Assumption 2.1 assumes continuous and differentiable. But tree-based models tend to be ubiquitous in the domains relevant to recourse (e.g. finance). So, overall, what is the problem domain where the base model is differentiable, *and* recourse is of value, *and* interpretability isn't? \n\nWhile I think the result is significant in the IF literature, my doubt is whether the model addresses the paired limitations in strategic classification. \n\n(Small) Clarity: In the limitations, the authors note that the linear optimization problem with K variables is 2^ K. But in the evaluation section, the binning factor is K=80, 100. This seems(?) intractable. Are these different uses of K? \n\nDisclaimer: Some of the details around group fairness Eqs 18-22 I only understood intuitively. I defer the correctness of these to another reviewer. For these analytical results I'm primarily dropping my confidence.", "was_revised": true, "final_justification": "This paper has strong analytical results on an interesting (and under-analyzed) class of model. The approach evaluates very well, showing controllable trade-offs through the hyperparameters.\n\nThe authors somewhat addressed my concern. But my first point is not a fatal flaw. Randomized model interpretability is out-of-scope of the paper (is the better answer), and future work gains in that model class are straightforwardly additive to this work.", "rebuttal": "**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. \n\nFrom 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. \n\n**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)$. \n\n**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. \n\n**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. \n\n**Limitations**: Thank you for your suggestion. We will elaborate more about the relationship between individual fairness and group fairness in the next version. \n\n[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. \n\n[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. \n\n[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)."}, {"review_id": "49AnVm8apP", "reviewer": "Reviewer_hq9t", "summary": "This paper considers individually fair decision-making settings in which individuals can adjust their features (by paying some cost). Assuming that each individual will behave optimally, constraints for individual fairness are derived and a randomized classifier with maximal accuracy is constructed using linear programming. Evaluations on Law School and FICO datasets show that individual fairness can be provided by this approach with reasonable decreases in predictive performance.", "questions": "Q1. Why are the costs of feature adjustments assumed to be related to the l function in Eq. (7)? Is the method strongly dependent on this assumption (i.e., necessary for individual fairness, or computationally needed)? It seems that in real applications, the cost would simply be domain specific (and given) and generally unrelated to the prediction function. If given an arbitrary cost function, what could be done using your approach?\n\nQ2. It seems individual fairness requires randomized classifiers in general (i.e., in non-strategic settings). Why is there such a strong emphasis on this randomization in the paper? \n\nQ3. In (8), what does the left-hand side notation mean? Should (3) also match this notation?\n\nQ4. Are there smoother probability baselines (e.g., based on logistic regression) to compare against?", "limitations": "yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths:\n+ This paper identifies an important gap in fair machine learning research: individual fairness in strategic classification settings.\n+ The approach is novel, leveraging a distribution over linear threshold functions obtained using a linear program to provide individual fairness.\n+ The approach is versatile and can be combined with group fairness criteria, as the authors demonstrate.\n+ The experimental results show a good trade-off between predictive performance and providing individual fairness. \n\nWeaknesses:\n- The assumptions about the cost function (relating specifically to the linear threshold function) appear unnatural to me (see Q1), decreasing the general applicability of the approach to only work in settings with very strict assumptions.\n-  The framing of the paper seems a little strange to me. I believe individual fairness generally requires randomized decisions, so the focus on this aspect in the strategic setting is unnecessary (see Q2).\n- Related to the last point, since (I believe) randomization is essential for individual fairness, this suggests that better randomized baselines should be employed (Q3) rather than the deterministic classifier.\n\n----\n\nThere is a small typo in the Section 3 header.", "was_revised": true, "final_justification": "The author response addressed my main concerns about the generality/assumptions of the approach.", "rebuttal": "**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]. \n\nFor a more general cost function, we can have the following theorem. \n\n**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. \n\n$$|c(x_{1}, x') - c(x_{2}, x')| \\leq C_{c} ||x_{1} - x_{2}||,  \\forall x_{1}, x_{2},$$\n\nand $\\mathcal{F} = \\\\{f(x; t)|t \\in [C, D]\\\\}$ for randomized classifier $\\mathscr{F}$. Denote the best response as $r(x, t)$ and\n\n$$ r(x;t) = \\begin{cases}\n            \\arg\\min_{x'}\\\\{c(x,x') | l(x') \\geq t\\; c(x,x') \\le \\tfrac{1}{\\lambda}\\\\},\n            & \\text{if a solution exists}, \\\\\\\\\n            x, & \\text{otherwise}.\n\\end{cases}.\n$$\n\nAssume $\\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,\n    $$\n        |c_{\\mathscr{F}}(x_{1}) - c_{\\mathscr{F}}(x_{2})| \\leq M_{c}||x_{1} - x_{2}||.\n    $$\n\n**Proof** : The individual cost is\n\n$$\nc_{\\mathscr{F}}(x_{1}) = \\int_{C}^{D} c(x_{1}, r(x_{1}; t))p(t)\\mathrm{d}t.\n$$\n\nTherefore,\n\n$$\n|c_{\\mathscr{F}}(x_{1}) - c_{\\mathscr{F}}(x_{2})| \\leq \\int_{C}^{D}|c(x_{1}, r(x_{1}; t)) - c(x_{2}, r(x_{2}; t))|p(t)\\mathrm{d}t.\n$$\n\nBecause\n\n$$\nc(x_{1}, r(x_{1}; t)) \\leq c(x_{1}, r(x_{2}; t)), ~~~ c(x_{2}, r(x_{2}; t)) \\leq c(x_{2}, r(x_{1}; t)),\n$$\n\nwe have\n\n$$\n |c(x_{1}, r(x_{1}; t)) - c(x_{2}, r(x_{2}; t))|  \n\\leq  \\max \\\\{|c(x_{1}, r(x_{2}; t)) - c(x_{2}, r(x_{2}; t))|, |c(x_{2}, r(x_{1}; t)) - c(x_{1}, r(x_{1}; t))|\\\\} \n\\leq  C_{c}||x_{1} - x_{2}||.\n$$\n\nWith $p(t) \\leq \\frac{M_{c}}{C_{c}(D - C)}$,\n\n$$\n|c_{\\mathscr{F}}(x_{1}) - c_{\\mathscr{F}}(x_{2})| \\leq M_{c}||x_{1} - x_{2}||.\n$$\n\n**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. \n\nIn 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$. \n\n**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)))$. \n\n**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. \n\nIn 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. \n\nIn 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. \n\n|Metric|F1 score|IF ratio|S-DP| EO-DP| ED-DP|\n|---|---|---|---|---|---|\n|Logistic regression |0.627 $\\pm$ 0.007| 0.232 $\\pm$ 0.037|0.304 $\\pm$ 0.016|0.211 $\\pm$ 0.031|0.301 $\\pm$ 0.031|\n|Our method $L_{p} = 0.2$|0.635 $\\pm$ 0.008| 0.212 $\\pm$ 0.030|0.293 $\\pm$ 0.046|0.219 $\\pm$ 0.065|0.270 $\\pm$ 0.033|\n|Our method $L_{p} = 0.15$|0.586 $\\pm$ 0.022|0.159 $\\pm$ 0.023|0.310 $\\pm$ 0.029|0.248 $\\pm$ 0.049|0.259 $\\pm$ 0.041|\n\nIf you have any other smoother baselines that can be used here, we would be very glad to provide a comparison during the discussion. \n\n \n\n[1] Milli, Smitha, et al. \"The social cost of strategic classification.\" Proceedings of the conference on fairness, accountability, and transparency. 2019. \n\n[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. \n\n[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. \n\n[4] Estornell, Andrew, et al. \"Unfairness despite awareness: group-fair classification with strategic agents.\" arXiv preprint arXiv:2112.02746 (2021)."}, {"review_id": "smiiiNZrao", "reviewer": "Reviewer_xwZK", "summary": "This paper studies individual fairness in strategic classification, where individuals may modify their features to influence machine learning decisions. The authors demonstrate that deterministic threshold-based classifiers inherently violate individual fairness in such settings, particularly concerning the cost individuals incur to adjust their features. To address this, they propose randomized threshold classifiers, proving under certain distribution conditions that these classifiers can guarantee individual fairness while maintaining high accuracy. They design these classifiers as an efficient linear programming problem and extend the method to incorporate group fairness notions. Experiments on the FICO and Law School datasets show that the proposed method significantly improves individual fairness and group fairness simultaneously.", "questions": "- Given the method relies on threshold-based classifiers and specific assumptions on l(x), could the authors give an example of scenarios where these assumptions might not hold and discuss whether the method could be adapted to such cases?\n\n- How sensitive is the method’s performance (fairness vs. accuracy) to hyperparameters like the number of bins k. This could help to tune the method effectively.\n\n- Could the authors elaborate on the practical structure or interpretability of the learned threshold distribution p(t)? For example, does p(t) typically concentrate around certain thresholds, and how should this be interpreted in terms of fairness-accuracy trade-offs?\n\nVery nice work !", "limitations": "Yes. The authors explicitly discuss limitations regarding reliance on threshold-based classifiers, assumptions on the existence of a score function l(x), small datasets, and simplex solver complexity.", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 3, "originality": 4, "strengths_and_weaknesses": "Strengths:\n- This study addresses the underexplored area of individual fairness.\n- It proves when individual fairness is impossible with deterministic thresholds and how to achieve it using randomized thresholds.\n- It presents a linear programming formulation for designing fair classifiers and extends the approach to incorporate group fairness simultaneously with individual fairness.\n- The approach is tested on two datasets with a detailed quantitative analysis.\n\nWeaknesses:\n- The approach relies on threshold-based classifiers and assumptions on l(x), which limits its applicability to broader ML settings.\n- The experiments are limited to 2 datasets and do not test sensitivity to hyperparameters such as the number of bins (k), which could generate computational challenges if larger values are required.", "was_revised": true, "final_justification": "The authors have addressed most of my concerns with detailed theoretical clarifications and additional empirical results.\nWhile the approach is still limited to threshold-based classifiers and evaluated on two datasets, I believe the paper makes a meaningful and novel contribution to the underexplored area of individual fairness under strategic behavior.", "rebuttal": "**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. \n\n\n**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. \n\n$$|c(x_{1}, x') - c(x_{2}, x')| \\leq C_{c} ||x_{1} - x_{2}||,  \\forall x_{1}, x_{2},$$\n\nand $\\mathcal{F} = \\\\{f(x; t)|t \\in [C, D]\\\\}$ for randomized classifier $\\mathscr{F}$. Denote the best response as $r(x, t)$ and\n\n$$ r(x;t) = \\begin{cases}\n            \\arg\\min_{x'}\\\\{c(x,x') | l(x') \\geq t\\; c(x,x') \\le \\tfrac{1}{\\lambda}\\\\},\n            & \\text{if a solution exists}, \\\\\\\\\n            x, & \\text{otherwise}.\n\\end{cases}.\n$$\n\nAssume $\\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,\n    $$\n        |c_{\\mathscr{F}}(x_{1}) - c_{\\mathscr{F}}(x_{2})| \\leq M_{c}||x_{1} - x_{2}||.\n    $$\n\nOur 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. \n\n**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. \n\n|Metric |#bins = 50| #bins = 100|#bins = 150|#bins = 200|#bins = 250|\n|---|---|---|---|---|---|\n|F1 score |0.978 $\\pm$ 0.002|0.984 $\\pm$ 0.003| 0.985 $\\pm$ 0.003|0.986 $\\pm$ 0.001| 0.985 $\\pm$ 0.002|\n|IF ratio |0.408 $\\pm$ 0.046 |0.432 $\\pm$ 0.040 |0.461 $\\pm$ 0.016 |0.450 $\\pm$ 0.034 |0.452 $\\pm$ 0.014 |\n|S-DP|0.357 $\\pm$ 0.016 |0.355 $\\pm$ 0.017 |0.355 $\\pm$ 0.017 |0.356 $\\pm$ 0.018 |0.355 $\\pm$ 0.015 |\n|EO-DP |0.032 $\\pm$ 0.011 |0.014 $\\pm$ 0.008 |0.014 $\\pm$ 0.011 |0.019 $\\pm$ 0.010 |0.018 $\\pm$ 0.011|\n|ED-DP |0.032 $\\pm$ 0.011 |0.014 $\\pm$ 0.008 |0.014 $\\pm$ 0.011 |0.019 $\\pm$ 0.010 |0.018 $\\pm$ 0.011| \n \n**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."}, {"review_id": "yOFdDk9qqt", "reviewer": "Reviewer_wL1p", "summary": "The authors consider the problem of enforcing individual fairness when deploying threshold classifiers in situations where individuals engage in strategic behavior. They find that deterministic classifiers will fail to enforce individual fairness with respect to both outcome and cost, the authors also show that deploying a randomized classifier can fix this problem and provide algorithms that find an optimal but fair distribution over the thresholds by breaking the distribution $p(t)$ into piecewise constant functions. Results are extended to group fairness and experiments are provided on FICO and law school data sets.", "questions": "* Is it unknown if the constraint (20) is feasible to enforce? Can the authors add more discussion on the use of their relatively strong assumptions?", "limitations": "yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 2, "originality": 3, "strengths_and_weaknesses": "**Strengths**\n* The authors analysis includes a novel cost-based definition of individual fairness for strategic classification which requires $|C(x_1, f)-C(x_2,f)|<|x_1-x_2|$. This contrasts with the usual outcome based definitions of individual fairness.\n* The theory and methodology are evaluated in two real world settings (admissions and credit scoring) where individuals are likely to engage in strategic behavior.\n\n**Weaknesses**\n\n* The theory requires the following assumptions: (i) The existence of a function $l$ s.t. $Pr(Y=1|x) \\geq Pr(Y=1|z)$ iff $l(x) \\geq l(z)$. (ii) c(x,x') = g(l(x)-l(x')) for some increasing function $g$. (iii) The learner deploys classifier $f(x;t) = 1 [l(\\Delta(x(f)) ≥ t]$. (i) is reasonable for many applications but (iii) implicitly requires that the learner know $l$ which is a very strong assumption and (ii) requires that the cost be directly related to l(), but often the features that individuals can game are not the direct cause of the outcome of interest. For example, someones credit often does not directly cause a default in debt down the line. \n* Unless I missed it, the group fairness results seem to miss a theorem on the feasibility of the constraint (20).\n* The paper is very dense with derivations, including many inline definitions of constants and algebra steps making readability limited.", "was_revised": true, "final_justification": "The authors addressed my points in rebuttal", "rebuttal": "**Weakness 1**: Assumption ii can be relaxed with the following theorem. \n\n**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. \n\n$$|c(x_{1}, x') - c(x_{2}, x')| \\leq C_{c} ||x_{1} - x_{2}||,  \\forall x_{1}, x_{2},$$\n\nand $\\mathcal{F} = \\\\{f(x; t)|t \\in [C, D]\\\\}$ for randomized classifier $\\mathscr{F}$. Denote the best response as $r(x, t)$ and\n\n$$ r(x;t) = \\begin{cases}\n            \\arg\\min_{x'}\\\\{c(x,x') | l(x') \\geq t\\; c(x,x') \\le \\tfrac{1}{\\lambda}\\\\},\n            & \\text{if a solution exists}, \\\\\\\\\n            x, & \\text{otherwise}.\n\\end{cases}.\n$$\n\nAssume $\\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,\n    $$\n        |c_{\\mathscr{F}}(x_{1}) - c_{\\mathscr{F}}(x_{2})| \\leq M_{c}||x_{1} - x_{2}||.\n    $$\n \n\nFor 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. \n\n \n\n**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. \n\n \n\n**Weakness 3** : We will reduce the inline definitions and algebra steps in the next version of the paper."}]

Author rebuttal:

Meta-review: The paper studies individual fairness in a strategic classification setting in which individuals may modify their features to influence machine learning decisions. All the reviewers are positive or mildly positive about the paper, and the rebuttal helped to clear out the reviewers' initial concerns.
Decision: Accept (poster)