Individual Arbitrariness and Group Fairness
Authors: Carol Xuan Long
Hsiang Hsu
Wael Alghamdi
Flavio Calmon
Venue: NeurIPS 2023 spotlight (2023)
Keywords: predictive multiplicity
fairness in machine learning
Rashomon effect
TL;DR: We demonstrate that fairness interventions in machine learning optimized solely for group fairness and accuracy can exacerbate predictive multiplicity.

Abstract: Machine learning tasks may admit multiple competing models that achieve similar performance yet produce conflicting outputs for individual samples---a phenomenon known as predictive multiplicity. We demonstrate that fairness interventions in machine learning optimized solely for group fairness and accuracy can exacerbate predictive multiplicity. Consequently, state-of-the-art fairness interventions can mask high predictive multiplicity behind favorable group fairness and accuracy metrics. We argue that a third axis of ``arbitrariness'' should be considered  when deploying models to aid decision-making in applications of individual-level impact.
To address this challenge, we propose an ensemble  algorithm applicable to any fairness intervention that provably ensures  more consistent predictions.

Individual Arbitrariness and Group Fairness
Carol Xuan Long', Hsiang Hsu"t, Wael Alghamdi*,, Flavio P. Calmon
Abstract
Machine learning tasks may admit multiple competing models that achieve similar performance yet produce arbitrary outputs for individual samples phenomenon known as predictive multiplicity. We demonstrate that fairness interventions in machine learning optimized solely for group fairness and accuracy can exacerbate predictive multiplicity. Consequently, state-of-the fairness interventions can mask high predictive multiplicity behind favorable group fairness and accuracy metrics. We argue that a third axis of "arbitrariness" should considered when deploying models to aid decision-making in applications of individual- impact. To address this challenge, we propose an ensemble algorithm applicable to any faireess intervention that provably ensures more consistent predictions.
1 Introduction
Non-arbitrariness is an important facet of hon-discriminatory decision-making. Substantial arbi- trariness exists in the training and selection of machine learning (ML) models. By simply varying hyperparameters of the training process (e.g., random seeds in model training), we can produce models with arbitrary outputs on individual input samples [9, 13, 26, 35J. The phenomenon where distinct models exhibit similar accuracy but arbitrary individual predictions is called predictive multiplicity! [35]. The arbitrary variation outputs due to unjustified choices made during training disparately impact individual samples, i.e., predictive multiplicity is not equally distributed across inputs of a model. When deployed in high-stakes domains (c.g., medicine, education, resume screening), the arbitrariness in the ML pipeline may target and cause systemic harm to specific individuals by excluding them from favorable outcomes [7. 15, 40].
Popular fairness metrics in the ML literature do not explicitly capture non-arbitrariness. A widely recognized notion of disdimcriminntionn is group group fairness. Group fairness is quantified in terms of, for example, statistical parity [18], equal opportunity, equalized odds [23], and variations such as multi-accuracy [30] and multi-calibration [24]. Broadly speaking, methods that control for group fairnsss aim to guarantee comparable performance of a model across population groups in the data. The pursuit of group fairness has led to hundreds fairness interventions that seek to control for performance disparities while preserving accuracy [25].
The central question we tackle in this paper is: Do models corrected for group faimesss exhibit less arbitrariness in their outputs? We answer this question in the negative. We demonstrate that state- of-the-art fairness interventions may improve group fairness metrics the expense of exacerbating arbitrariness. The harm is silent: the increase in arbitrariness is masked by favorable group fairness and accuracy metrics. Our results show that arbitrariness lies beyond the fairness-accurace frontier:
"qqull contributions.
Prepared prior to employment at JPMorgan Chase & Co.. Email: hsiang. hww.jjschasseeee... com.
JJhhn Paulson School Engincering and Applicd Sciences, Harvard University, Boston, MA 02134. Emails: carol_ parol_longgg harvard. edu, alghamdi@g @g. harvard. edu, flaviodseas. harvard. edu. In the of the paper, informally use the terms "arbitrariness" and "predictive multiplicity" exchange- ably to refer the phenomenon inconsistent predictions caused by randomness model training.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

ENEM (Random Forest)
1.0
Post-iinerveen Score Stdl
0.6
Quandies of Store Stdl
0.8
Accuracy
0.6
0.8
0.64
Reckation
Reaction
0.4
(Aco EG, Kean EDS p01
0.2
0.62
LyvbyCyp For Prquection
0.
Raductoon Los Fay
0.1
Bose
0.0
(Aee Eo, Kean RC1 201
0.0
0.00
0.05
Mean Equalized Odds
0.10
0.15
0.20
0.25
0.0
0.1
0.2
0.3
0.4
0.5
0.1 0.2
0.3 0.4 0.5
Classifler Score
Threshalded Baseline Output Std. (Rounded)
Figure 1: Securacy-fairness frontier does not reveal arbitrariness in competing models. Left: Fairness- Accuracy frontier of baseline and fair models corrected by fairness interventions: point clouds generated by different random seed choices. Middle: The cumulative distribution functions (CDF) of per-sample score std. across classifiers at different intervention levels (sce Definition 3). For each sample, std. is measured across competing scores produced by classifiers initialized with different random sceds. A wider CDF indicates more disparity of the impact of arbitrariness on different individuals. Right: The distribution of score std. relative to the thresholded baseline model. Removing samples that receive very low score std. both from thresholded baseline and fair classifiers, the largest group (blue area) in this violin plot are those individuals for which std. increases from O to large positive value (median around 0.15). Hence, significant arbitrariness is introduced by the fairness intervention, in addition to and separate from the effects of thresholding the baseline.
predictive multiplicity should be accounted for in addition to usual group-fairness and accuracy metrics during model development.
Figure 1 illustrates how faimess interventions can increase predictive multiplicity. Here, state-of- the-art fairness interventions are applied* to a baseline random forest classifier to ensure group fairness (mean equalized odds [23], Definition 6) in student performance binary prediction task. We produce multiple baseline classifiers by varying the random seed used to initialize the training algorithm. Each baseline classifier achieves comparable accuracy and fairness violation. They also mostly agree in their predictions: for each input sample, the standard deviation of output scores across classifiers is small (see Definition 3). After applying a fairness intervention each randomly initialized baseline classifier, we consistently reduce group fairness violations at a small accuracy cost, as expected. However, predictive multiplicity changes significantly cost-intervention:: for roughly half of the students, predictions are consistent across seeds, whereas for 20% of the students, predictions are comparable coin flip. For the latter group. the classifier output depends on the choice of a random seed instead of any specific input feature. The increase in predictive multiplicity is masked by the dirness-accuracy curve, does not impact all samples equally, and is consistent across datasets and learning tasks.
At first, the increase in predictive multiplicity may seem counter-intuitive: adding fairness constraints to a learning task should reduce the solution space, leading to less disagreement across similarly- performing classifiers relative to an unconstrained baseline. We demonstrate that, in general, this is not the case. For given hypothesis class, the non non-convex nature of group fairness constraints can in fact increase the number of feasible classifiers at given fairness and accuracy level. We show that this phenomenon occurs even in the simple case where the hypothesis space is comprised of threshold classifiers over one-dimensional input features, and the optimal baseline classifier unique. To address this challenge, we demonstrate both theoretically and through experiments that ensembling classifiers is an effective strategy to counteract this multiplicity increase.
The main contributions of this work include
1. We demonstrate that the usual "fairness-accuracy" curves systematically mask increase of predictive multiplicity. Notably, applying state-of-the-art faimess interventions ineur higher arbitrariness in the MI. pipeline.
2. We show that multiplicity can be arbitrarily high even if group fairness and accuracy are controlled, when we do not have perfect classifiers. Hence, fairness interventions optimized solely for faimess and accuracy cannot, in general, control predictive multiplicity. We also provide examples of why fairness constraints may exacerbate arbitrariness.
4 'See Scction for a detailed description of the experiment and dataset. Proofss and additional experiments are included in the Appendices.

---

3. We propose an ensemble algorithm that reduces multiplicity while maintaining faimess and accuracy. We derive convergence rate results to show that the probability of models disagreeing drops exponentially as more models are added to the ensemble.
4. We demonstrate the multiplicity phenomena and benchmark our ensemble method through comprehensive experiments using state-of-the-an fairness interventions across real-world datasets.
1.1 Related Works
Multiplicity, its implications, and promises. Recent works have investigated various factors that give rise to multiplicity. D' Amour et al. [17] studied how under-specification presents challenges to the credibility of modern machine learning algorithms. More precisely, under-specified optimization problems in machine learning admit a plethora of models that all attain similar performance, and which model to deploy in practice may ultimately depend on arbitrary choices of the randomization made during training procedure [3]. The arbitrariness of the model could potentially harm the reproducibility of model predictions [5], and hence the credibility of the conclusion made thereof.
Creel and Hellman [15] thoroughly explored the notion of arbitrariness in machine learning and discuss how high-multiplicity predictions lead to systematized discrimination in society through "algorithmic leviathans." " Multiplicity in prediction and classification can also have beneficial effects. Black et al. [7]. Semenova et al. [39], and Fisher et al. [20] view multiplicity of souulll-performing models as an opportunity to optimize for additional criteria such as generalizability, interpretability. and fairness. Coston et al. [14] develop framework search over the models in the Rashomon set for a better operation point on the accuracy-fairness frontier. However, they do not discuss the potential predictive multiplicity cost of existing fairness interventions nor propose algorithms to reduce this cost.
The work most similar to ours is [13]. Cooper et al. [13] consider the problem of predictive multiplicity as a result of using different splits of the training data. Therein, they quantify predictive multiplicity by prediction variance, and they propose bagging strategy [8] to combine models. Our work considers a different problem where predictive multiplicity is exacerbated by group-fairness interventions. Our work is also different from Cooper et al. [13] we fix the dataset when training models and consider multiplicity due to randomness used during training. In this sense, our ensemble algorithm is actually voting ensemble [41] (see Section 4); see also ensembling and reconciliation strategies proposed by Black et al. [6] and Roth et al. [38] that aim to create more consistent predictions among competing models. To the best of the authors' knowledge, we are the first to measure and report the arbitrariness cost of fairness interventions.
Hidden costs of randomized algorithms. Recent works [21, 31, 32] examine the potential detri- mental consequences of randomization the ML pipeline. In their empirical study, Ganesh et al. [21] observe that group fairness metrics exhibit high variance across models at different training epochs of Stochastic Gradient Descent (SGD). The authors point out that random data reshuffling in SGD makes empirical evaluation of fairness (on test set) unreliable, and they attribute this phenomenon to the volatility of predictions in minority groups. Importantly, they do not incorporate fairness interventions in their experiments. In contrast, we apply fairness interventions to baseline models. Specifically, we examine the variance in predictions among models with similar fairness and accuracy performances. In addition to the observations made by Ganesh et al., our sreoretically-groundee study reveals the different paths that lead to group-fairness, i.e., that arbitrariness can be an unwanted byproduct of imposing fairness constraints. Krco et al. [31] empirically study if fairness interventions reduce bias equally across groups, and examine whether affected groups overlap across different fairness interventions. In contrast, work examines the multiplicity cost of group faimess and its tension with individual-leve prediction consistency, rather than the fairness cost of randomness in the ML pipeline. Another work on the hidden cost of randomized algorithms is given by Kulynych et al. [32], who report that well-known differentially-prig -private training mechanisms can exacerbate predictive multiplicity.
In an early work [34], Lipton et al. indirectly points to the potential arbitrary decision on individuals as result of imposing group fairness constraints. They give an illustrative example using synthetic hiring data to show that a fair model resorts to using irrelevant attribute (hair length) to make hiring decision in order to achieve near-equal hiring rate for men and women.
3

---

2 Problem Formulation and Related Works
We explain the setup and relevant definitions in this section.
Prediction tasks. We consider a binary classification setting with training examples being triplets (X with joint distribution Px .SY. Here, X is an -valuee feature vector, S is discrete random variable supported on [K] _ {1...., ; K} representing K (potentially overlapping) group memberships, and Y is a binary (i.e., {0, 1 }--alueed) random variable denoting class membership. We consider probabilistic classifiers in a hypothesis space H. where each h E H. is a mapping h: R + [0, 1/. Each value of a classifier h((r) aims to approximate Py "y|x==(U) (1). The predicted
labels y can be obtained by thresholding the scores, e.g., y = 1 [()(z) 2 0.5), where 1f } is the indicator function. Finally, we denote by A the probability simplex over e dimensions.
Randomized training procedures and the Rashomon set. We assume access to the following:
1. a training dataset of n i.i samples D _ {(z,, 8t yo) drawn from Px,s,y:
2. a randomized training procedure T: and
3. induced distribution T(D) the hypothesis class of predictors H.
We denote a sampled classifier by ~ T(D), which can be sampled, for example, using different random seeds at the beginning of the execution of procedure T on D. For concreteness, the above data may for example correspond to the following practical setting.
The dataset D can be comprised of resumes of individuals applying for a job, and the training procedure T is an algorithm to predict whether to extend an interview opportunity for an applicant. For example, T can be a neural network with unspecified hyperparameters (c.g., random seed that needs to be chosen at the outset); alternatively. T can be the same pre-trained neural network composed with fairness intervention method. The classifiers considered will be the last layer the neural network (or the classifier after fairness enhancement), which will belong to hypothesis class H determined by the chosen neural network architectre. By varying the random seed, say, m times, would obtain independent classifiers, denoted by h.m. s.i.d. T(D).
Example 1.
We are interested in detecting whether competing classifiers (i.e., deployed for, and performing similarly in the same prediction task) have confficting predictions non-uniformly across individuals. Next, we define the set of competing models obtained from the randomized training procedure T.
For a loss function é [0, 1] x 1) + RR+ finite dataset D C Rd [K] x 10, and clas- sifier h : _dd + [0. 1]. we let the empirical loss incurred by h on D be denoted by E(h; D) & [DI- "e("",,, ((((x), y). The (empirical) Rashomon set (e-level set) of competing models is defined as the set of models with loss lower than e [26], i.c., R(H e) é {h E H. l(h; D) S e). We extend the definition of the Rashomon set to take into consideration the effect of the randomized algorithm T, as follows.
Definition 1 (Empirical Rashomon Set of Randomized Training Procedure). Fix finite dataset D, a hypothesis class H. and a randomized training procedure 'I inducing the distribution T(D) on H. Given loss function f: [0, 1] {0, 1} - R+ and a parameter > O, we define the empirical Rashomon set with m models induced by T as the collection of m classifiers independently sampled from T (D) and having empirical loss less than
Rm, (T,
{ hi,,.., .. Am E H h1 Am i.dd T(D) and D(h;; S <eVj [m]]. (1)
Here, is approximation parameter that determines the size of the set. The set R., (T, D, c) can be viewed as an approximation of the Rashomon set of "good" models [9, 35, 40], and indeed we have where H = (upp(T(D)) Note that the set R,, (T, D, e)
the inclusion Rm D. e) C. R(H,D, itself random even for a fixed dataset D. where the source of randomness is coming from the distribution T(D). In the sequel, we omit the arguments of Rm D,E) when they are clearly implied from context.
We note that our setup be readily extended multi-class prediction.

---

There are various metrics to quantify predictive multiplicity across models in Rmm by either consider- ing their output scores [40] or thresholded predictions [35]. focus on two metries: 1) ambiguity for evaluating the predictive multiplicity of thresholded predictions, and 2) cumulative distribution function (CDF) of standard deviation (std.) of output scores when model outputs are in the interval [0, 1] (interpreted as the probability of the positive class). Those two metrics are defined as follows.
Definition 2 (Ambiguity [35]). Fix a dataset 'D = {(2s, 8;, Mi) NE)M) C CR x [K] x {0, 1) and a
finite set of models R H. Let f(r) è 1rr 2 0.5} be the thresholding function. The ambiguity of a dataset over the set of models R is the proportion of points in the dataset that can be assigned a conflicting prediction by competing classifier within R:
a (D, R.
Σ kE(M
max
1 +
D
K.EER
To define the CDF of std. of scores, we first delineate what we mean by empirical std. of scores. Definition 3 (Std. of Scores). Fix finite set of models R {by ha(mm] C H. The empirical standard deviation (std.) of scores for sample x E I2d relative to is defined by
s(x, R)
Σ JE(m)
(hy(2)
p=)
(3)
m
1
where jiz A 1. mn Eje(m) (x) denotes the empirical mean (over R. of the scores.
Further, to understand the std. of scores of the population, we consider the empirical cumulative distribution function of the std. of the scores, defined as follows.
Definition& 4 (Quantiles of std. of Scores). Fix a dataset D = {(x;, 5;, w:) hejn C R [K] x {0, I} and finite set of models R C H. We define the empirical cumulative distribution function of the std. of the scores by (where 8 (ze R) is the empirical std. as in Definition 3)
(1)
Σ iE(n]
1 {,(0,, St.
(4)
D
Example 2. Consider resume screening task where the algorithm decides whether to extend an interview opportunity. If (0.5) 90%, then for 10% of the individuals in the dataset, the predictions produced by the competing models are arbitrary and conflicting: regardless of the mean scores, with an std. of least 0.5, there would exist models with scores falling above and below the one-half threshold, so the thresholded output can be both 0 (no interview) and I (offer interview).
A note on related metrics. An alternative measurement of score variation is Viable Prediction Range as defined in [40], which measures the difference in max and min scores among competing models on each individual. For thresholded scores, the original definition of Ambiguity [35] considers the proportion of a flip in prediction with respect to a bascline model (from empirical risk minimization with fixed hyperparameters and randomness). Since we consider randomized training procedures with no clear baseline model, the definition for ambiguity above is a variation of the original.
Group fairness. We consider three group fairness definitions for classification tasks statistical parity (SP), equalized odds (EO), and overall accuracy equality (OAE) [11, 18, 23, 37J. OAE and Mean Equalized Odds (MEO) are defined below as they are used in the next sections, and we refer the reader to Appendix D for the remaining definitions.
Definition 5 (Overall Accuracy Equality, OAE). Let V be the predicted label obtained, e.g., from thresholding the scores of a classifier : Rd -> [o, 1]. The predictor ÿ satisfies overall accuracy equality (OAE) if its accuracy is independent of the group attribute: for all groups s, s' E [K],
Pr(p = Y S 8) = Pr(P = Y s= s/).
For binary classification, SP boils down to requiring the average predictions to be equal across groups, while EO requires true positive rates (TPR) and false positive rates (FPR) to be calibrated. this paper, we consider mean equalized odds (MEO): the average of absolute difference in FPR and TPR for binary groups E 10, We consider binary group since this is the setup for most fairness intervention methods.
5

---

Definition 6 (Mean Equalized Odds, MEO [4, 23]), Let Y be the predicted label. S E {0, 1 denotes binary group membership. Mean Equalized Odds is the average odds difference for binary groups:
MEO 1
([TPR 5= - 1 -PRs-11 11))
where TPRs= Pr(Y- = Y 1,8 S s) and FPRs= & Pr(Y 1 =
To examine whether current fairness intervention methods lead to an exacerbation multiplicity, we survey state-of-the-ard intervention methods, including Reductions [1]. Fair Projection [2], Reject Options [29], and EqOdds [23]. We offer a brief discussion of their mechanism in Appendix D.
Orthogonality of Fairness and Arbitrariness
We discuss next why arbitrariness is third axis not captured by fairness and accuracy. Models with similar fairness and accuracy metrics can differ significantly in predictions. Morcover, a set of fair and approximately accurate models can attain maximal predictive multipliciiyy We also explore through an example one fundamental reason why adding fairness constraints can lead to more arbitrariness.
Example (Ambiguity # OAE). Overall Accuracy Equality (OAE, Definition 5) does not capture the ambiguity of model outputs (Definition 2). Consider two hypothetical models that are fair/unfair and exhibit high/low predictive multiplicity in Figure 2. Here, in each panel, the rectangle represents the input feature space and the shaded regions represent the error region of each model.
In the top left panel, both Model and have equal accuracy for both groups, since the proportion of the error regions (red stripes and pink shade) for both groups are the same. Hence, both models are considered group-fair in terms of OAE. However, the error regions of the two models disjoint. Since ambiguity is measured by the percentage of the samples that receive conflicting predictions from either models, samples from the union of the two error regions contribute to ambiguity. Hence, Model and 2 bear high predictive multiplicity despite being group-fair.
In the lower right panel, Model 1 and 2 attain low fairness and low predictive multiplicity. Both models have higher accuracy for Group 2 than Group 1, so they are both unfair. The error regions completely overlap, which means that the two models making the same error ambiguity is 0.
The schematic diagram in Figure shows that predictive multiplicity is not captured by OAE, Indeed, ambiguity of a collection models is global property (i.e., verified at the collection level), whereas OAE is local property (i.e., ver- ified the classifier level). Hence, one should not a priori expect that set of competing mod- els each satisfying OAE would necessarily com- prise a Rashomon set with favorable ambiguity.
Eire Rapin
Fair
Unfair
Erzu
High Predictive Mullipliiiy
Label
Label
Negative
Negativo
Label
Labal
Group Group
Group Group
Postive
Poeiiu
We prove the orthogonality of OAE and Sta- tistical Parity (SP) from ambiguity formally in the proposition below, where show that it is possible to construct classifiers with very strin- gent accuracy and perfect fairness constraint, albeit with maximal ambiguity. We determine the Rashomon using the (-1 loss:
Predictive Mullipliity
Y=
Lobel
Label
Figure 2: Illustration on two models being fair/unfair and exhibit high/low predictive multiplicity through the models' error regions in each of the cases. The met- ries for fairness predictive multiplicity are Overall Accuracy Equality (Definition 5) and ambiguity (Defini- tion 2). respectively.
l0-1 (h; D)
Σ
1
10 + Ath.
(B (DD
where D. {0, 1} is the class membership of æ; predicted by h. We prove the following orthogonality in Appendix A.
Proposition 3.1 (Orthogonality of OAE/SP and Ambiguity). Fix any empirical loss value < S and any number of models m > Then, for some finite dataset D Rdd [K] x 10, there is realization of the empirical Rashomon set Rm (hem)) satisfying the following simultaneously:

---

Deiss Diat daatin
Prob Emor and ED
Threshud Cleas
06
Protebilty Endr
0.0
MX00-15-0
Swal
Mean EDH0.1
Swil
00-
02-
Figure 3: Data distribution of population with two groups used in Example (Left). In Right, without the Mean EO constraint (6) (green line), there is unique optimal classifier (with threshold 0) that attains the smallest probability of error (blue line). Adding the Mean EO constraint enlarges the set of optimal threshold classifiers to two classifiers (red and blue dots) with indistinguishable accuracy and faimess levels (Right) but different decision regions. We illustrate the decision regions of each classifier as red and bluc arrows the Left.
1. Each hy has 0-1 loss upper bounded by la. (a.(h;;:) S
2. Each hy satisfies OAE perfectly, or each h satisfies SP perfectly;
3. The collection R.n. has the worst ambiguity, i.e., (D, Rmn)= 100%.
Remark For OAE, such Rashomon set Rm exists for any dataset satisfying the two conditions:
1. with n, denoted the number of samples in D belonging to group k E [K], the greatest common divisor of the ngg is at least (mn- 1)/(me - 1).
2. if (æ, 8,y), (x, s', v') E DD share the same feature vector then y = y' too.
The requirement that the na share a large enough common divisor is used in the proof to guarantee perfect OAE, One could relax this requirement at the cost of nonzero OAE violation.
Proposition 3.1 implies that there exists a dataset and competing models for which all samples receive confficting predictions. Specifically,
can construct a large enough set of competing models (m > 1) such that 100% of the samples in the dataset can receive conflicting predictions from this set of perfectly fair models with respect to OAE.
In the next example, we demonstrate that, counter-intuitine counter-inuiitively, adding a fairness constraint can enlarge the set of optimal models, thereby increasing predictive multiplicity. This points to fundamental reason why adding fairness constraints can lead to more arbitrariness in model decisions.
Example 4 (Arbitrariness of Threshold Classifiers with Faimesss Constraint). Given data distribution of population with two groups (Figure Left), consider the task of selecting threshold classifier that predicts the true label. Without fairness considerations, the optimal threshold is 0 - i.c., assigning positive predictions to samples with æ > 0 and negative predictions to æ I minimizes the probability of error (Figure 3 Right). This optimal model is unique. Adding fairness constraint that requires Mean EO < 0.1, the previously optimal classifier at 0 (with Mean EO 0.15, Right) does not meet the fairness criteria. Searching over the threshold classifiers that minimize the probability of error while satisfying Mean EO constraint yields two equally optimal models (red and blue dots Right) with distinct decision regions (red and blue arrows Left). Even in this simple hypothesis class, the addition of fairness constraints yields multiple models with indistinguishable fairness and accuracy but with distinct decision regions. The arbitrary selection between these points can lead to arbitrary outputs to points near the boundary.
4 Ensemble Algorithm for Arbitrariness Reduction
To tackle the potential arbitrariness cost of faireess intervention algorithms, we present a disparity- reduction mechanism through ensembling. We provide theoretical guarantees and numerical bench- marks to demonstrate that this method significantly reduces the predictive multiplicity of fair and accurate models.
In a nutshell, given competing models h,...., Ny. we argue that the disparity in their score assign- ment can be reduced by considering convex combination of them, defined as follows.
7

---

Definition 7 (Ensemble Classifier). Given m classifiers (h1,- . hm R - [0. 1]} and vector À A m. we define the X-ensembling of the h to be the convex combination ons, Eje(m] Ayh3-
4.1 Concentration of Ensembled Scores
We prove in the following result that any two different ensembling methods agree for fixed individuals with high probability. Recall that fix dataset 'D and set of competing models T(D)) coming from a stochastic training algorithm T (see Section 2). All proofs are provided in Appendix B.
Theorem 4.1 (Concentration of Ensembles' Scores). Let Ba....,,mm!' h.. id T(D) be 2m models drawn from T(D), and h hoas, be the ensembled models (constructed with thi..... hm and {hi,..., him). respectively) for 7, E Am (see Definition 7) satisfying | 11 c/m for an absolute constant c. For every x E R and v 2 O, we have the aioonenniallydeccaiinn (in m) bound
P (1 (x) - 1t 10 2 w) S 4e (e-mmm/(2))
(7)
In particular, for any validation set Dvalid. c. Rdd size (Dvalid|== | n. we have the uniform bound
(noms (x)) (ho0s.(xr)) < v for all x E Dvalid.)
> 1 4ne / m2(22).
(8)
4.2 Concentration of Predictions Under Ensembling
The above theorem implies that we can have a dataset of size that is exponential in the number of accessible competing models and still obtain similar scoring for any two ensembled models (uniformly across the dataset).
In practice, cares more about the agreement of the final prediction of the classifiers. The following result extends Theorem 4. I to the concentration of thresholded classifiers. For this, we need to define the notion of confident classifiers.
Definition (Confident Classifier). Fix a probability measure Px over I&d and constants 8, 0 E [o, 1]. We say that a classifier h R2d [0, 1] is (Px, 6, -)-oofidentt if (lh(x) = 8) < 0.
In other words, h is a confident classifier if it is "more sure" of its predictions. We observe in experiments that models corrected by fairness interventions have scores concentrated around 0 and 1.
Using confident classifiers, we able extend Theorem 4.1 thresholded ensembles, follows.
Theorem 4.2. Let hns.. he be in Theorem 4.1, and assume that both ensembled classifiers are (Px, 8, 0) connfient in the sense of Definition 8. Let f(t & 11t > 0.5} be the thresholding function. For any set Vaataa. C. IR of size (Dvana. we may guarantee the probability of agreement in the predictions for all samples under the two ensembles be least
P (f
f(h (T." for every Dvalid)) ) 2 1-44 (4e-26pm/c + 20 n.
(9)
We note that in the curmess-interventionn setting, the set D in the above theorem would be chosen as the subset of samples having the same group attribute. Thus, the size no of D would be significantly smaller than the total size of the dataset, and the parameter then can be required to be moderately small.
Remark 2. In Appendix C, discuss how optimize the ensembling parameters A. In the next section, we will stick to the uniform ensembling: hens,
Eje(m] hy. i.e., À = 111 1. This simple uniform ensemble suffices to illustrate the main goal of this paper: that arbitrariness can be a by-product of fairness intervention methods, and ensembling can mitigate this unwanted effect.
5 Experimental Results
We present empirical results to show that arbitrariness is masked by favorable group-fairness and accuracy metrics for multiple fairness intervention methods, baseline models, and datasets 7, We also demonstrate the effectiveness of the ensemble reducing the predictive multiplicity of fair models.
"ode can be found at https::/ //te:///tttttt waom//Caolllaaa
wowm/Carool-oongPPPreeeeeee LoageLLooo/////ee//s/... and Arb Arbitrariness

---

ENEM (Random Forest)
1.0
EqOdds
0.86
Rejection
0.8
Accuracy
Reduction
Quantiles
0.8
LevEqOop
0.64
Fair Projection
0.4
Reduction (Acc:0.66 66, EO violation:0.04) ROC (Acc:0 66, EO violation: 04) Leveraging (Acc:0.86, EO violation:
Base
0.62
Baselne (Acc:0.67, ED violetion: 28)
0.0
0.2 Mean Equalized Odds
0.1
0.0
0.1
0.2
0
0.4
0.5
Standard Deviation of Scores
Figure 4: Quantile plot on high nigh-fairness bin for various fairness interventions v.s. baseline ENEM. Left: Fairess-Accuracy frontier. Right: Fair models produce larger score std. top percentiles compared to the baseline model (horizontal axis computed via (6)). (REJECTION and LEVERAGING output thresholded scores directly.)
Setup and Metries. We consider three baseline classifiers (BASE): random forest (RF), gradient boosting (GBM), and logistic regression (LR), implemented by Scikit-learn [36]. By varying the random seed, we obtain 10 baseline models with comparable performance. Then, we apply various state-of-the-art fairness methods (details in Appendix D) on the baseline models to get competing fair models.
On the test set, we compute mean accuracy, Mean EO (Definition 6), and predictive multiplicity levels on competing models before and after fairness interventions. We use ambiguity (Definition 2) and score standard deviations (Definition 3) as metrics for predictive multiplicity.
Datasets. We report predictive multiplicity and benchmark the ensemble method on three datasets two datasets in the education domain: the nigh-school longitudinal study (HSLS) dataset [27, 28] and the ENEM dataset [16] (see Alghamdi et al. [2] Appendix B.I), and the UCI Adult dataset[33] which is based on the US census income data. The ENEM dataset contains Brazilian college entrance exam scores along with student demographic information and rocio-economic questionnaire answers (e.g. if they
computer). After pre-prooe preepeccessing the dataset contains 1.4 million samples with 139 features. Race is used as the group attribute S, and Humanities exam score is used as the label Y. Scores are quantized into White and Asian (S = 1) and others (S = 0). The experiments are run with a smaller version of the dataset with 50k samples. Complete experimental results can be found in Appendix E.
classes for binary classification. The race feature S is binarized into
Results that Reveal Arbitrariness. We juxtapose the fairness accuraccy frontier and metrics for predictive ambiguity to reveal arbitrariness masked by favorable group-fairnen fairness and accuracy metries in Figure and 4. Starting with 10 baseline classifiers by varying the random seed used to initialize the training algorithm, we apply the fair interventions REDUCTION [1], REJECTION [29], LEVERAGING (12) to obtain point clouds of models with comparable faimess and accuracy metrics. In Figure 4, we take models that achieve very favorable accuracy and MEO metrics (in blue rectangle in Left) and plot the std. of scores to illustrate predictive multiplicity Right. Group fairness violations are greatly reduced (from 0.28 in baseline to 0.04 in fair models) at a small accuracy cost (from 67% in baseline to 66% in fair models). However, there is higher arbitrariness.
Compared to baseline (red curve), fair models corrected by REDUCTION and ROC produce lower score arbitrariness for the bottom 50% but much higher arbitrariness for the top 50% of samples; importantly, the induced arbitrariness becomes highly nonuniform across different individuals after applying the two fairness intervention. We observe that LEVERAGING produce models that agree on 90% of the samples, thereby not inducing concerns of arbitrariness.
Remarkably, arbitrariness does not vary significantly among models with different fairness levels. We consider two sets of models trained with high and low fairness constraints using REDUCTION in Figure I.
Results on the Effectiveness Ensembling. We pair our proofs in Section 4 with experiments that demonstrate the concentration of scores of ensembled models. In Figure 5 Left, taking the competing

---

ENEM
HSLS
Reduction (Acc:3 56, ED vislatio:(..4)
90th Quanttle Std Scores
0.4
Roductin (Acc:0.73, vidlationD.085
Baseline (Acc:0.87, EO vio allon:0.28)
Baseline (Aoc:0.74, EO violation..11 0.177
Guantie Sid
0.3
0.3
Avo ED vialation of Ereembi 0.06
0.2
Ave ED vidiatoon of Froverble: 0.08
01
0.1
15
Number Models in Ensemble
Number of Models in Ensemble
Figure 5: Standard deviation of ensembled models trained on ENEM and HSLS with baseline random forest classifiers. We fix the high-fairness bin and vary the number of models mn in each ensemble. As we increase the number of ensembles, score std. (on 10 ensembles) drops and meets the score std. of 10 baseline RFC when 30 on ENEM and 17 on HSLS. (Mean EO is computed using (6).
models in the high-fairness bins corrected with REDUCTION that achieve an Mean EO violation of 0.04 but very high score std. for half of the samples (blue rectangle in Figure 4), ensemble the models with increasing number of models per ensemble (m) ranging from I to 30. For each m, we measure std. of scores in 10 such ensembles. The top percentile std. of the ensembled fair models drops to baseline with 30 models. Similar convergence occur on the HSLS dataset. Importantly, the ensembled models are still fair, the Mean EO violations of the ensembled models remain low.
Final Remarks
We demonstrate in this paper that arbitrariness is facet of responsible machine learning that is orthogonal to existing fairness-accuracy analyses. Specifically, fairness-vs-accuraay frontiers are insufficient for detecting arbitrariness in the predictions of group-fair models: two models can have same fairness- aicness-accuracy curve while at the same time giving widely different predictions for subsets of individuals. We demonstrate this undesirable phenomenon both theoretically and experimentally on state-of-the of-thc-art fairness intervention methods. Furthermore, towards mitigating this arbitrariness issue, propose ensemble algorithm, where convex combination of several competing models used for decision-making instead of any of the constituent models. We prove that the scores of the ensemble classifier concentrate, and that the ensuing predictions can be made to concentrate under mild assumptions. Importantly, we exhibit via real-world experiments that our proposed ensemble algorithm can reduce arbitrariness while maintaining fairness and accuracy.
Limitations. The proposed framework for estimating the predictive multiplicity of fairness inter- ventions requires re-training multiple times, limiting its applicability to large models. We consider model variation due to randomness used during training. In practice, competing models may exist due to inherent uncertainty (i.e., non-zero confidence interval) when evaluating model performance on a finite test set. In this regard, models with comparable average performance can be produced by searching over this Rashomon set even if training is deterministic (e.g.. equivalent solving convex optimization problem).
Future directions. An interesting future direction is to explore the multiplicity cost of fairness interventions in such deterministic settings. Furthermore, our ensembling strategy may not guarantee that the ensemble classifier ensures fairness constraints due the non-convex nature of such con- straints. Though we empirically observe that faimess constraints are indeed satisfied by the ensemble model, proving such guarantees theoretically would be valuable.
Societal impacts. While fairness intervention algorithms can effectively reduce the disparate impact among population groups, they can induce predictive multiplicity in individual samples. The increase in predictive multiplicity does not impact all individuals equally. If predictive multiplicity caused by fairness interventions not accounted for, some individuals will bear the brunt of arbitrary Docision-making thhir predictions could be arbitrary upon re- re-training the classifier using different random initializations, leading to another level of disparate treatment to certain population groups
10

---

Acknowledgements. The authors would like to thank Jamelle Watson-Danin Daniela Arpita Biswas and Bogdan Kulynych for hepful discussions on initial ideas. This material is based upon work supported by the National Science Foundation under grants CAREER 1845852, CIF 1900750, CIF 231 2312667 and FAI 2040880, and by Meta Ph.D. fellowship.
Disclaimer. This paper was prepared by Hsiang Hsu prior to his employment at JPMorgan Chase & Co.. Therefore, this paper not product of the Research Department of JPMorgan Chase & Co. or its affiliates. Neither JPMorgan Chase & Co. nor any of its affiliates makes any explicit or implied representation or warranty and none of them accept any liability in connection with this paper, including, without limitation, with respect to the completeness, accuracy, reliability of the information contained herein and the potential legal, compliance, tax, or accounting effects thereof. This document is not intended as investment research investment advice, or a recommendation, offer, or solicitation for the purchase or sale of any security, financial instrument, financial product or service, to be used in any way for evaluating the merits of participating in any transaction.
References
[1] Agarwal, A., Beygelzimer, A., Dudík, M., Langford, J., and Wallach, H. (2018). A reductions approach to fair classification, In International Conference on Machine Learning, pages 60-69. PMLR.
[2] Alghamdi, W., Hsu, H., Jeong, H., Wang, H., Michalak, P., Asoodeh, S., and Calmon, F. (2022).
Beyond adult and compas: Fair multi-class prediction via information projection. Advances in Neural Information Processing Systems, 35:38747-3877
[3] Bahri, D. and Jiang, H. (2021). Locally adaptive label smoothing for predictive churn. arXiv preprint arXiv:2102.05
[4] Bellamy, R. K., Dey, K., Hind, M., Hoffman, S. C., Houde, S., Kannan, K., Lohia, P., Martino, J., Mehta, S., Mojsilović, A., et al. (2019). Ai faimess 360: An extensible toolkit for detecting and mitigating algorithmic bias. IBM Journal of Research and Development, 63
[5] Bhojanapalli, S., Wilber, K., Veit, A., Rawat, A. S., Kim, S., Menon, A., and Kumar, S. (2021). On the reproducibility of neural network predictions. arXiv preprint arXiv:2102.03349
[6] Black, E.,, Leino, K., and Fredrikson, M. (2021). Selective ensembles for consistent predictions. arXiv preprint
[7] Black, E., Raghavan, M., and Barocas, S. (2022). Model multiplicity: Opportunities, concerns, and solutions. In 2022 ACM Conference Fairness, Accountability, and Transparency, pages 850-863.
[8] Breiman, L. (1996). Bagging predictors. Machine learning, 24:123-140.
[9] Breiman, L. (2001). Statistical modeling: The two cultures (with comments and a rejoinder by the author). Statistical science, 1693):199-231.
[10] Caton, S. and Haas, C. (2020). Fairness in machine learning: A survey. arXiv preprint arXiv:2010.04053.
[11] Chouldechova, A. (2017). Fair prediction with disparate impact: A study of bias in recidivism prediction instruments. Big data, 5(2):153-163.
[12] Chzhen, E., Denis, C., Hebiri, M., Oneto, L., and Pontil, M. (2019). Leveraging labeled and unlabeled data for consistent fair binary classification. Advances in Neural Information Processing Systems, 32.
[13) Cooper, F., Barocas, S., De Sa, C., and Sen, (2023). Variance, self-consistency, and arbitrariness in fair classification. arXiv preprint arXiv:2301.
[14] Coston, A., Rambachan, A., and Chouldechova, A. (2021). Characterizing fairness over the set of good models under selective labels. In International Conference on Machine Learning, pages 2144-2155. PMLR.
11

---

[15] Creel, K. and Hellman, D. (2022). The algorithmic leviathan: arbitrariness, faimeess, and opportunity in algorithmic decision-makinn systems. Canadian Journal of Philosophy, 52(1):26- 43.
[16] Cury, C. R. J. (2022). Instituto nacional estudos pesquisas educacionais anísio teixeira: uma trajetória em busca de uma educação de qualidade.
[17] D' D'Amour, A., Heller, K., Moldovan, D., Adlam, B., Alipanahi, B., Beutel, A., Chen, C., Deaton, J., Fisenstein, J., Hoffman, M. D., et al. (2022). Underspecification presents challenges for credibility in modern machine learning. The Journal of Machine Learning Research, 23(1):00237- 10297.
[18] Dwork, C., Feldman, V., Hardt, M., Pitassi, T., Reingold, O., and Roth, A. (2015). Preserving statistical validity in adaptive data analysis. In Proceedings of the forty-seventh annual ACM symposium on Theory of computing, pages 117-126.
[19] Dwork, C., Hardt, M.. Pitassi, T., Reingold, O., and Zemel, R. (2012). Fairness through awareness. In Proceedings of the 3rd Innovations in Theoretical Computer Science Conference, ITCS 12, page 214 226, New York, NY, USA. Association for Computing Machinery.
[20] Fisher, A., Rudin, C., and Dominici, F. (2019). All models are wrong, but many are useful: Learning variable's s importance by studying entire class of prediction models simultaneously. J. Mach. Learn. Res., 20(177):1-81.
[21] Ganesh, P., Chang, H., Strobel, M., and Shokri, R. (2023). On the impact of machine learning randomness on group fairness. In Proceedings of the 2023 ACM Conference on Fairness, Account- ability, and Transparency, FAccT '23, pages 1789-1880 1800, New York, NY, USA. Association for Computing Machinery.
[22] Hajek, B. and Raginsky, M. (2019). Statistical learning theory. Lecture Notes, 387.
[23] Hardt, M., Price, E., and Srebro, N. (2016). Equality of opportunity in supervised learning. Advances in neural information processing systems, 29.
[24] Hébert-Johnson, U., Kim, M., Reingold, O., and Rothblum, G. (2018). Multicalibration: Calibration for the cimmuuationally-idennffaaiit masses. In International Conference on Machine Learning, pages 1939-1948. PMLR.
[25] Hort, M., Chen, Z., Zhang, J. M., Sarro, F,, and Harman, M. (2022). Bia mitigation for machine learning classifiers: A comprehensive survey, arXiv preprint arXiv:2207.07066
[26] Hsu, H. and Calmon, F. d. P. (2022). Rashomon capacity: A metric for predictive multiplicity in probabilistic classification. arXiv preprint arXiv:2206.0122 01295.
[27] Ingels, S. Pratt, D. J., Herget, D. R., Burns, L. J., Dever, J. A., Ottem, R., Rogers, J. E., Jin, Y., and Leinwand, S. (2011). High school longitudinal study of 2009 (hsls: 09): Base-year data file documentation. nees 2-31-328. National Center for Education Statistics.
[28] Jeong, H., Wang, H., and Calmon, F. P. (2022). Fairness without imputation: A decision tree approach for fair prediction with missing values. Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pages 9558 -5666.
[29] Kamiran, F., Karim, A.. and Zhang. X. (2012). Decision theory for discrimination aware classification. In 2012 IEEE 12th international conference on data mining, pages 924-929. IEEE.
[30] Kim, M. P., Ghorbani, A., and Zou, (2019). Multiaccuracy: Black-box post-processing for fairness in classification. In Proceedings of the 2019 AAAI/ACM Conference A1, Ethics, and Society, pages 247-254.
[31] Krco, N., Laugel. T., Loubes, J.-M., and Detyniecki, M. (2023). When mitigating bias is unfair: A comprehensive study on the impact of bias mitigation algorithms. arXiv preprint a7..02230..07185.
12

---

[32] Kulynych, B.. Hsu, H., Troncoso, C., and Calmon, F. P. (2023). Arbitrary decisions are hidden cost of settrentiall--privart training. In Conference on Fairness, Accountabilityy and Transparency (FAceT). ACM.
[33] Lichman, M. et al. (2013). Uci machine learning repository, 2013.
[34] Lipton, Z., McAuley, J., and Chouldechova, A. (2018). Does mitigating ml's impact disparity require treatment disparity? Advances neural information processing systems, 31.
[35] Marx, C.,, Calmon, F,, and Ustun, B. (2020). Predictive multiplicity in classification. In International Conference on Machine Learning, pages 6765-6774. PMLR.
[36] Pedregosa, F., Varoquaux, G., Gramfort, A., Michel, V., Thirion, B., Grisel, O., Blondel, M.. Prettenhofer, P., Weiss, R., Dubourg, V., et al. (2011). Scikit-leam: Machine learning in python. the Journal of machine Learning research, 12:2825-2885
[37] Pleiss, G., Raghavan, M., Wu, F., Kleinberg. J., and Weinberger, K. Q. (2017). On fairness and calibration. Advances in neural information processing systems, 30.
[38] Roth, A., Tolbert, A., and Weinstein, S. (2022). Reconciling individual probability forecasts. arXiv preprint arXiv:2209.01687.
[39] Semenova, L., Rudin, C., and Parr, R. (2019). A study in rashomon curves and volumes: A new perspective on generalization and model simplicity in machine learning. arXiv preprint UrXiv:1908.01755
[40] Watson-Daniels, J., Parkes, D. C., and Ustun, B. (2022). Predictive multiplicity in probabilistic classification. arXiv preprint arXiv:2206.01
[41] Witten, I. and Frank, E. (2002). Data mining: practical machine learning tools and techniques with java implementations. Acm Sigmod Record, 31(1)776-77.
13

---

Appendix
The appendix is divided into the following five parts. Appendix A: proof of the orthogonality of OAE and SP from ambiguity (Proposition 3, Appendix B: proofs from Section 4; Appendix C: discussion optimizing ensemble parameters; Appendix D: additional discussions on group faimess and fairness interventions; and Appendix E: additional experiments and details on the experimental setup.
A Proof of Proposition 3.1: Orthogonality of OAE and SP from Ambiguity
We divide the proof into two cases according to the group-faimesss metric considered (OAE or SP).
A.1 Proof for the OAE Metric
Let D C F x [K] x {0, be a dataset satisfying the two conditions listed in Remark 1, namely,
1. with denoting the number of samples in D belonging to group k E [K], the greatest common divisor of the ng least (m 1)/(mc - 1).
2. if (a, y), (ax, s', v/) E DD share the same feature vector then y = y too.
Consider the partition along group membership D UKE[K] DE. {(Kks, k. (eseee) for each k E [K], where ng
may write D3
- |Dal. By assumption on the nk,, we have
m 1
g a ged (RI, nx)
(10)
me - 1
Now, let A - lcgl/g. and note that obtain the integers M4 8 n& for le E [K], because g divides
each me by definition of the ged. Let X a 1 Using [t] > 1 1-1 1, note that
1 +1
+15m m,
(11)
where the last inequality follows by assumption on being large enough (10). Thus, taking the ceiling of both sides above, obtain À + 1 < m. Hence, it suffices to prove that there À + 1 classifiers R = {hy)æe(>+)) satisfying the claim in the proposition (i.e., with À + replacing m)).
It is straightforward to check that λuς= I ng for each k. We divide each D3 into À sets of size pk each, and collect the remainder into a separate subset. Thus, for each [K]. consider any partition
DE UJE(++1) Dj where !DA pu for each j E [A] and 1
Tip
Apk-
Next, we define the classifiers based on the partitions of the Dx. For each j E [A + 1], define the classifier h2 over DD as follows. Fix (x,, k, 3) D. We set the value hy(x) be
(x) A 1 1- y
if (x, y) E EDi
(12)
otherwise.
Note that this makes hy well-defined by the second property assumed on DD at the beginning of this proof. We show that the set R (hyBselAtH satisfies the desired properties in the proposition.
Accuracy. First, we show that each hy incurs 0-1 loss less than e. Indeed, we have that, for each j E [A].
(h;; D)
D
Σ = 0,
(13)
n2
[E[K]
kE[K]
whereas the error for the last classifier is
E(hx11; D)
1
ID de
Σ
n
Afls =1- 20.
(14)
7
n
k
kE(K]
Thus, it suffices to check that 0, 1 X0 S Recall that we set 0 Leg]/ [gg hence 0 05 is immediate.
Further, as we take À [_= 8. the inequality 1 - 20 follows immediately too. Hence, we have that E(hy; D) for all j E [1.
14

---

Fairness. Next, we check that each hy satisfies Overall Accuracy Equality (OAE) perfectly. Let Y; be the prediction of the classifier h so PÝ, x (1) hy (2z). Then, for j E [A] the predictions of the j-th classifier satisfy
[
Pr (
Mk T2k
= 0
for every group l E [K],
(15)
T
and similarly the last classifier satisfies
Pr (V++I + 5 (
[D
Tik
Apak
=
1
20
for every group & E [K]. (16)
71
Hence, the n, for j E [A + 1], all satisfy OAE perfectly.
Ambiguity. Finally, we show that the set R (hybEn++ exhibits full ambiguity. Note that we have a partition D = [((=))e[K](([=-] D.C Fix a sample (æt, s,y) E D and consider the index (k, E [K] x [A + 1] of the unique part including it in the partition, i.e., (x, s, E Dj-- By construction of R. have that (x)
y (so Y, 11- but hy y (so Y,. y) for any j' * j. In other words, for every fixed sample in D, there a pair of classifiers R. assigning conflicting predictions. Thus, the ambiguity is a(D, R) 100%.
A.2 Proof for the SP Metric
Consider now the SP group-fairness constraint instead. In this case, we define we construct
the following alternative dataset DD c I& x [K] {0,1), Let A [1/c] 2 For each
(k:, v) [K] x 10,1}, fix any dataset Day {( ki v)evet C Rd {k} {y}. let
D A ((x1)) DR.y C Rd x [K] x {0, 1}, and assume that Øky. = Tg then
y y'. Denote n & |D|= 2Kt.
i.e., (o = [t] Define the set of classifiers R = {hy [hy] on D as follows. For each j E [t] and each (ke, y, E [K]] x 10. x
For each v) E [K] x {0, 1). let dk.y be permutation on [t].
[4], we set
{1 f1- y ifi
hy(
(17)
otherwise.
We show that the set R {h1 helt satisfies the desired properties in the proposition.
Accuracy. Consider first the 0-1 loss incurred by the hj- We have that, for each j [t].
((h;; (k.g,))
Σ
1Wi = ok.,(()))))
Σ
2K
(18)
n (k.))E[K]
2Kl
7'
Therefore, [(hy: D) 1/t - 1/[1/c <. In other words, R. is realization of the c-level empirical
Rashomon set of size
Fairness. Next, we check that each h2 satisfies SP perfectly. In other words, we check that hy assigns to the class y = 1 the same percentage samples across the groups [K]. Indeed, this is true as we are switching the class memberships of exactly one sample from each of the Dr.g- In partieular, hy assigns the class membership to exactly 1 + (|Pa.1l11) the total [D U DD.1 21 samples belonging group k. As the ratio 1/(2t) = 1/2 is independent of the group k. we obtain the desired result that h, satisfies SP.
[Dr,1|= |= samples out of
Ambiguity. Finally, we check that the set R = {h, hee( suffers from 100% ambiguity. Fix sample (K kt y) E 'D and we will show that there are two classifiers in R assigning conflicting predictions to it. Indeed, let j = 1 (i) and let j' E [t] (r} be any other index. Then, h, (Z = 1 y, whereas hy (2 = y- Therefore, the sample (#t.g, y) contributes to the overall ambiguity a(D, R). As this is true for all samples in D, we conclude that (DD,, R) = 100%, as desired. This completes the proof of the proposition.
15

---

B Proofs of Section
B.1 Proof of Theorem 4.1
We assume that ||>| 1 1 e/m for an absolute constant c, e.g., we have == for the uniform ensembling x= (1/m, ..., 1/m) as then | 1/m. Fix at, and denote the mean of the classifiers Mi (D) [h(=)] The mapping (fu,,-.,, hm)) + , satisfies the bounded-difference condition in the McDiarmid inequality. Indeed, changing h2 can change n by at most X Furthermore, = (xx has the mean
E
[x)]
Σ xE[m)
= Mr Σ
A Mr.
(19)
tE(m]
Hence, by Mcdiarmid's inequality, we have the bound
-2v2
-2v²m
P ( Mx 2 v) S 2exp
2exp
(20)
Σ Eigim)
X2
The same inequality holds for in place of A:
-2v²m
P (x)
Ma 2 2) 2xxp
(21)
Therefore, we obtain the bound
((non))a))) onn (az)
2 =P 2ehhoo /hom. (xx) - Mx + Mi (a))) <V)
(22)
Al
h 1jons,2 (x)) - Maz
7 7e (xx Ho <v)
(23)
2
eens (xx)) - Ma < 2
h cms (xx) - 1.
<
V
2
(24)
1 - P (Ihams((r))
Man
2 2
v
U
h
7 (xx)
Max
2 5
(25)
-v²2
2 1 exp
(26)
2c
where the first inequality comes from triangle inequality, the following from probability of subset
of events (P(4) 2 P(B) if A 2 B), the equality from taking complement, and the last line from applying McDiarmid's inequality along with the union bound.
Finally, applying the union bound on Dealid with D |=
n, we obtain the bound
P
(2) - 7 7x)) < v
= =1 P
U
(x))
- h eas (2))))())))))))))))())))
22
(27)
.E Deaid
LonE Deldd
-1²m²
2 4nexp
(28)
2c
and the proof complete.
B.2 Proof of Theorem 4.2
The main idea is as follows: first observe that for the ensembled labels to disagree on sample (given that the scores are bounded away from with high probability), the two models need to produce scores in the range [o, 2 5) J + 5, 1]. This means that the scores need to deviate at least 28 which has an exponentially low probability given Theorem 4.1.
We will show that
P
U LeDDo
((h + f (()))
(12)) S (4e (26-m//0/ + 20) no-
(29)
16

---

Indeed, for each fixed æ E Do. we may reduce the failure probability to the case of separation of scores:
IP (f(h)m)))))) # f(hm))(x))) SP ((nmmi
0, 1 -
1
E
8
n n
8,
2
(30)
U h (ax)
0, - 8
n h
(x)) E
+ 6,
(31)
1 2
Uh ans (x)
8,
+ 8
(32)
2
1
1
Uh (x)) E
6,
+
0
(33)
2
2
< P / (ar) - h T. (xx) 26
+
20
(34)
(-20²m) + 20.
S 4 exp
(35)
Finally, applying the union bound, we obtain that
TP
n f(h ((h = (2x)) Do
= =1
s(h (x)) # ((r)))(()))
(36)
LoEDo
2 1 - (e 20-22pm/e + 20 no.
(37)
and the proof complete.
C Discussion on optimizing ensemble parameters
We have taken the weights À E Am which determines the ensembled model hems, to be fixed. We explain here how À can be optimized according to given cost. Specifically, given a loss function é: [0, 1] x {0, 1 + R4, we can search for the optimal À E Am that minimizes the total cost
L (A) - E
[&(h e (X), Y)]-
(38)
For the above optimization problem, we think of the constituent models h1,"", hm as being fixed and the randomness is from that of (X, Y).
However, in practice, we have access to only samples (x W1) ~ Px,.. Thus, we consider minimizing the regularized sample mean (for fixed B > 0)
Lens A)
Σ ( ( (1)). + sE[m]
B
| 2-
(39)
The 2-norm regularization is added facilitate proving convergence. This convergence result can be obtained via known results from statistical lcarning theory, c.g., using Theorem 13.2 in [22]. Specifically, consider the following two restrictions:
Consider only À E Am satisfying ||||ss a for preseribed a. Note that we may take a 1 to encapsulate the whole probability simplex. However, we may choose À to be slight modification of the uniform ensembling, in which case we would have a of order 1/vm.
Assume that the function À + E(hens.A()) y) is convex and A-Lipschitz for each fixed (x.
In this case, choosing 3 = A/o o: and denoting the optimizers
A (n) A argmin
L (A).
(40)
Allasa
17

---

we can bound the utility of these minimizers by
T + Sa² vn (1+ 5/n )n)) 2 21-6
P Trons (A()) S
inf IAllaSa
(41)
for any 8 E (0, 1).
D Additional discussion on group fairness and fairness interventions
In addition to OAE (Definition 5), two other important faimess criteria are Statistical Parity [18] and Equalized Odds [23].
Definition 9 (SP). Pr(Y 1|5 8) Pr(Y -1/5 s') for all groups s, [K]
Definition 10 (EO). Pr(Ý 1|5 s, 6) Pr(y 1 s',Y y) for all groups 8, E [K]. and binary labels y E {0,1).
Essentially, SP requires the predicted label 4 - arg max h XX) to be independent of the group membership S [19]. In comparison, EO conditions on both group and the true label [23]. EO improves upon SP in the sense that it does not rule out the perfect classifiers whenever the true label Y is correlated with the group membership S [1]. In practice, we quantify EO violation by measuring Mean EO as in Equation (for two groups) and, more generally, in Equation 42 below (beyond two groups). Similarly, we can measure SP violation as in Equation 43.
1 ([TPRs STPRS== TPR TPRs ||PR FPRs
MEAN EO
(42)
S 2
SP VIOLATION & ,
max
11/) Pr =1S== ='))
(43)
Next, we offer brief discussion of various intervention mechanisms used in this paper. The fairness interventions can be categorized into two categories: in-processing and post-processing In-processing mechanisms incorporate fairness constraints during training. It usually add the fairness constraint to the loss function and outputs fair classifier. Post-processing mechanisms treat the model as a black box and update predictions to achieve the desirable fairness constraints [10].
REDUCTION [1], short for exponentiated gradient reduction, is an in-processing technique that reduces fair classification to a sequence of cost-sensitive classification problems, and yields randomized classifier with the lowest empirical eтror subject to the desired constraints. This technique achieves fairness with a minimal decrease accuracy, but it computationally expensive since it requires re-training multiple models.
REJECT OPTION CLASSIFIER [29] is postprocessing technique that achieves fairness constraints by modifying outcomes of samples in a confidence band the decision boundary with the highest un- certainty. It gives favorable outcomes unprivileged groups and unfavorable outcomes privileged groups. It outputs a thresholded prediction rather than a probability over the binary labels.
EOODDS [23] is post-processing technique that formulates empirical risk minimization with faimess constraint as a linear program and modifies predictions according to the derived probabilities to achieve equalized odds.
FAIR PROJECTION [2] is post-processing technique that can accommodate fairness constraints in setting with multiple labels and multiple groups. The fair model is obtained from 'projecting' pre-trained (and potentially unfair) classifier onto the set of models that satisfy target group-fairnes requirements.
E Additional experiments and details on the experimental setup
Our proposed methodology can be summarized in the pipeline in Figure 6.
18

---

Accuracy, Fairness, Predictive Multiplicity
Accuracy,
Accuracy,
Faireess, Predictive Multiplicity
Fairness, Predictive Multiplicity
Test Data
vary random seeds
apply lairness interventione
apply optimal eneemble
Competing Baseline Models
Data
Compeling Fair Models
Ensembled Fair Models
Training Data
Figure 6: Flow chart of experimental procedure.
E.1
Data
The HSLS dataset [27, 28] an education dataset collected from 23,000+ students across high schools in the USA. Features of the dataset contain extensive information students' demographic information, their parents' income and education level, schools' information, and students' academic performances across years. We apply the pre-processing techniques adopted by Alghamdi al. [2). with the number samples reduced to 14,509. For the binary classification task with fairness constraints, the group attribute chosen is RACE {WIITE, NON-WIITE! and the prediction label is students 9th-Grade GRADEBIN E {0, 1}. binarized according to whether a student's 's grade is higher lower than the median.
The ENEM dataset [16] is a Brazilian high school national exam dataset introduced by Alghamdi et al. [2]. It has 138 features containing students' demographic information, socio-cconomic questionnaire answers (c.g., parents' education level and they own a computer), and students' exam scores. Adopting the preprocessing technique in Alghamdi et al. [2], sample 50K samples without replacement from the processed ENEM Year 2020 data. Identical to HSLS, the group attribute chosen is RACE E (WITTE, NON- WII--HHINN WHITE) and the prediction label is students Grade binarized into GRADEBIN E {0, 1 according to whether a student's grade is higher or lower than the median.
For the widely known Adult dataset [33], also known as "Census Income" dataset, choose the group attribute as SEX E (MALE, FEMALE] and predicted label to be INCOME E (0, 1]. where income bin denotes whether person's income higher or lower than 50K/yr.
E.2 Competing Baseline Models
We the Scikit-learn implementation of logistic regression, gradient boosting, and random forest as baseline models. For logistic regression and gradient boosting, the default hyperparameter is used; for random forest, we set the number of trees and minimum number of samples per leaf 10 to prevent wer--ftting. To get 10 competing models for each hypothesis class, we use 10 random seeds (specifically 33-42).
In practice, the competing models, i.e., Rm can be obtained using different methodologies, such as sampling and adversarial weight perturbation [26, 40]. We suggest one method for sampling. First, split the data into training, validation, and test dataset. We train a set models by changing the randomized procedures in the training process, e.g., using different initializations, different cuts for cross-validation, data shuffling, etc. this paper, we change the random seed feed into the baseline models to obtain competing models. We use the validation set to measure corresponding to this empirical Rashomon Set.
E.3 Competing Fair Models
For EQODDS, REJECTION, and REDUCTION, we use the functions BOODDSPOSTPROCESINNG REJECTOPTOOCLASSICC..
and EXPONENTAATEGGRADINTT EECTT from AIF360 toolkits [4]. For LEVERAGING and FAIR PROJECTION, we use the codes provided in the correspond- ing Github repositories of Chzhen al. [12] and Alghamdi al. [2].
Remark 3. We observe in practice that fairness classifiers are more confident and have scores that are thresholded- (Figure 7 Left). From the similarity the shape of the thresholded baseline curve and the fair models' curves (Figure 7 Right), thresholding-likk behavior of some interventions may explain some-but certainly not all (see Figure Right) -increae in score std dev and the ensuing arbitrariness. Recall from the violin plot in Figure I that the largest group (blue area)
19

---

1.0
Densty Samples in Bire
0.4
Pooi--inte Scones
Quandlee S.orr
Reduction High FarrAcc Meen E0
0.2
0.4
Falr(AccOO
ED:0:5)
Rejection High FaintAcc 682, Meen EC:0.60)
02
Rejection Fali(AcsO,Bik
60.0..55 25)).28)
Baseline (Aceil 063, Meen EC:0 20)
holldd Beselina (Aos:0 683, Mawi ED.0.85)
8.0
0.0
0.4
0.8
1.0
Caesifier Scores in Bine
Score Standand Deviation
Figure 7: Left: We plot the score distribution of the REDUCTION approach example. The scores concentrate around O and 1, while scores of the baseline classifier are normally distributed. Given this thresholded-lik scores of fair classifiers, include thresholed baseline in the quantile plot of score std.. The thresholded Baseline curve largely overlaps with Rejection curve with MEO 0.26 since they have the same MEO level.
Right:
ENEM (Random Forest)
0.88
Rejaction
Accuracy
LovEqOpp
Reduction
Quantiles
0.6
0.84
Fair Projection
0.4
Base
High Faimess (Acc:0.88) 656, EO violation 0 04)
0.82
0.2
Low Faireess (Acc:0 864, EO violation:0 (Acc:0 864, atien: 28)
0.0
0.2 Equalized Odds
0.0
0.1
0.2
0.3
0.4
0.5
Deviation of Scores
Figure 8: Left: Accuracy-fairness curves baseline random forest models v.s. fair models on the ENEM dataset. Right: Quantiles of per-sample score std. across high/low fairness models and baseline.
those individuals which std. increases from a large positive value (median around 0.15). Hence, the blue area shows that significant arbitrariness is introduced by the fairness intervention, in addition to and separate from the effects of thresholding the baseline.
E,4 Complete Experimental Plots
In order to evaluate the predictive multiplicity of models with similar accuracy and faimeess levels. we divide the accuracy-fainee fairness frontier plots into 8x8 grids and put models the corresponding bins. To compare the arbitrariness of models satisfying high/low faimess constraints, different MEO ranges and bins with baseline models. Then, we compute the standard deviation of scores of models corrected by REDUCTION in the three bins (high fairness/low faimess/baseline) and plot the quantile curves. We use PANDAS package's quantile function with default linear interpolation method.
select bins in two
Across three baseline model classes (random forest, gradient boosting, and logistic regression), fair models exhibit higher score arbitrariness. Especially at top quantiles, all fair models have standard deviations in scores going up to 0.5. This means that for the individuals the top percentile, the model prediction can flip if another random seed is used in model training.
Furthermore, evaluate the predictive multiplicity of models corrected by different faimess interven- tion methods. Across datasets, all fairness intervention methods exhibit maximal standard deviation of scores of 0.5 at top quantiles for random forest baseline methods. LEVERAGING [12] exhibit score arbitrariness comparable to that of baseline for GBM and Logistic Regression methods. REJECTION and LEVERAGING output thresholded scores directly, while REDUCTION outputs probabilities (with most scores close to 0 or l).
20

---

ENEM (GBM)
1.0
EqOdds
0.67
Rejection
0.8
Reduclion
Quantiles
0.66
0.8
LevEqOpp
Fair Projection
0.4
Buse
High Faimess (Acc:0 664, EO violation: 0 04) Low Fairness (Acc:0.873, EO violeliin:0.144
0.2
0.83
Basaline (Acc:0 673, EO via attondo 30)
0.0
0.1
0.2
0.3
0.0
0.2
0.3
Mean Equalized Odds
Standard Deviation of Scores
Figure 9: Left: aecuracy-faimess curves of baseline gradient boosting models (GBM) fair models the ENEM dataset. Right: Quantiles of per-sample score std. across high/low fairness models and baseline.
ENEM (Logistic Regression)
EqOdds
0.67
Rejaction
0.8
Reduction
Quanti 65
0.66
LevEqOpp
0.8
0.85
Fair Projection
0.4
Base
High Faimess (Acc:0 0.64, EO violation Low Faimess (Acc:0.673, ED violalion:0.11
0.64
0.2
Baseling (Acc:0 673, EO via ationd0 30)
0.0
0.1
0.2
0.3
0.0
0.1
0.2
0.3
0.4
0.5
Mean Equalized Odds
Standard Deviation of Scores
Accuracy-fairness curves of baseline logistic regression models v.s. fair models on the ENEM dataset. Right: Quantiles of per-sample score std. across high/low fairness models and baseline.
Figure 10: Left:
HSLS (Random Forest)
0.74
EqOdds
Rejaction
0.8
Reduction
Quantiles
Acouracy
0.72
LevEqOpp
0.6
Fair Projection
0.4
0.70
Base
High Fairness (Acc:0,73, EO violation 0. 0.06)
0.2
Low Faimess (Aco: 0.74, EO liolation:..0g)
Baseine (Acc:0. 74, EO via ation:0 17)
0.15 Mean Equalized Odds
0.05
0.10
0.0
0.1
0
0.4
0.5
Standard Deviation of Scores
Accuracy-fairae curves of baseline random forest models v.s. fair models the HSLS dataset. Right: Quantiles of per-sample std. across high/low fairness models and baseline.
Figure 11: Left:
HSLS (GBM)
EeOdds
0.75
Rejaction
0.8
Accuracy
Reduction
Quanties
0.6
LevEgOpp
0.73
Fair Projection
0.4
0.72
Bese
High Faimess (Acc:0.745, 745, EO violation 0.02
0.71
0.2
Low Fairness (Acc:0.745, ED violation:0.06)
Baseline (Acc:0 749, EO via ation:00 19)
0.05
0.10
0.15
0.0
0.1
0,2
0.3
0.4
0.5
0.6
Mean Equalized Odds
Standard Deviation of Scores
Accuracy- fairness curves of baseline gradient boosting models (GBM) v.s. fair models on the HSLS dataset. Right: Quantiles of per-sample score std. across high/low fairness models and baseline.
Figure 12: Left:
21

---

HSLS (Logistic Regression)
0.73
EqOdds
Rejection
0.8
0.72
Reduction
Quantiles
0.6
0.71
LevEqOop
Fair Projection
0.4
0.70
Base
High Falmess (Acc0..11 716, EO violation 02)
0.2
Low Fairesss (Acc:0.720, EO vislation:0.07
0.89
Baseline (Ace:0 733, EO violation:0 21)
0.0
0.2
0.0
0.
0.2
0.3
0.4
0.5
0.8
Mean Equalized Odds
Standard Deviation Scores
Accuracy-faime faimess curves of baseline logistic regression models v.s. fair models on the HSLS dataset. Right: Quantiles of per-sample score std. across high/low fairness models and baseline.
Figure 13: Left:
Adult (Random Forest)
1.0
EqOdds
Reduction
0.8
Accuracy
0.850
LevEqOpp
Quantiles
Fair Projection
0 845
Base
04
High (Aoc:0.852 violation
0.2
854, EO violation:0.0n
0.835
Baseline (Acc:0 856, EO ation:0 06)
0.830
0.0
0.0
0.1
0.2
0.3
0.5
Mean Equalized Odds
Standard Deviation of Scores
Accuracy-faiie facinesy-airnesss curves baseline random forest models v.s. fair models on the Adult dataset. Right: Quantiles of per-sample score std. across high/low fairness models and baseline.
Figure 14: Left:
Adult (GBM)
1.0
EqOdds
0.860
Reduction
0.8
0.855
LevEqOpp
Quantilos
0.6
Projection
0.4
0.845
High Faimess (Acc:0.855, EO violation: 0.02 Low Fairness (Acc:0.864 EO violation:0.04)
0.840
Baseline (Acc:0 860, ED ailon0 07)
0.0
0.02
0.04
0.06
0.0
0.1
Moan Equalized Odds
Standard Deviation of Scores
Figure 15: Left: fairres curves of baseline gradient boosting models (GBM) v.s. fair models the Adult datasct. Right: Quantiles of per-sample score std. across high/low faimess models and baselinc.
22

---

ENEM (Random Forest)
ENEM (GBM)
1.0
1.0
0.8
0.8
0.6
Quantiles
0.6
0.4
Reduction (Acc:0.658, EO violetion:0.00 ROC (Acc:0.855 856, EO vio latioo:..04
0.4
Reduction (Ac4:0,664, violalion:O 04)
ROC (Acc:0.66 864, EO violation: 0.04)
0.2
Leveraging (Acc:0 658, EO violation:O. 04)
0.2
Leveraging (Acc:0 660, EO via ation:0 02)
Baseline (Acc 664, violation: 28)
Baseline (Acc:0
violation: 30)
0.0
0.0
0.0
0.1
0.2
0
0.4
0.5
0.1
Standard Deviation Scores
Standard Deviation Scores
ENEM (Logistic Regression)
Quantlles
Reduction (Acc:0.864 EO violation:0.00 04)
ROC (Acc006644, violation 0.04)
Leveraging (Acc:0.686 684, EO ation:0.04)
Baseline (Acc:0 873, ED violation:0.30
0.0
0.1
0.2
0
0.8
Standard Deviation of Scores
Figure 16: Quantile plot models in high-fairness bin for various fairness interventions v.s. baseline models ENEM. Fair models produce larger score std. top percentiles compared to the baseline model.
HSLS (Random Forest)
HSLS (GBM)
1.0
1.0
0.8
0.8
Quantiles
0.6
0.6
0.4
Reduction (Acc:0 728, EO violation:0000 0.06)
0.4
Reduction (Acc:0 0455, EO violetion: 0404)
ROC (Acc0,77 728, EO violation:..0e 0.06)
ROC (Acc:0.745 745, EO via alion:0.02 0.00)
0.2
Leveraging (Acc:0. 728, EO violation:O.co 06)
0.2
Leveraging (Aca:0.745, EO violation 0.00 0.04)
Baseline (Acc:0
violation:
Baseline (Acc:0.749, EO violation:0. 19)
0.0
0.0
0.0
0.1
0,2
0.3
0.5
0.0
0.1
0.3 Standard Deviation Scores
0.2
Standard Deviation Scores
HSLS (Logistic Regression)
Quantles
Reduction (Ace: 716, EO violation: 06)
ROC (Acc:0.723 violation
Leveraging 0.720 EO vio ittion:.04))
Baseline (Acc: 733, ED violation:0.29
0.1
0.2
0
0.4
0.6
Standard Deviation of Scores
Figure 17: Quantile plot models in high-fairness bin for various faimesss interventions v.s. baseline models on HSLS. Fair models produce larger score std. top percentiles compared to the bascline model.
23


Reviews:
[{"review_id": "ZpLafQLHNL", "reviewer": "Reviewer_47CU", "summary": "This paper studies the effect of group fairness regularization constraints on a notion termed arbitrariness. Here, arbitrariness is defined to be the variability of the predictions, for a set of similarly accurate models, on individual samples. In this paper, they show that when a model is regularized to satisfy group fairness constraints, it is still possible that the predictions of similarly accurate models show variability in the individual predictions. The set of similarly accurate models on a given subpopulation of data is termed the rashomon set. Here, the authors measure arbitrariness with the quantile of the standard deviation of the output of the models in a rashomon set. They also measure ambiguity by computing the proportion of points in the dataset that can be assigned multiple conflicting predictions. They prove that it is possible for a model to satisfy accuracy equality (i.e. all protected subgroups have similar accuracy), but for the arbitrariness of the rashomon set to be as high as up to 100 percent. To counter this challenge, they propose a simple scheme that ensembles the models in the rashomon set (convex combination), and show theoretically and empirically (on three datasets for random forest models) that this ensembling scheme reduces arbitrariness.", "questions": "- Is equality of accuracy interchangeable with any other group fairness constraint in proposition 3.1? I know Example 2 discusses equality of opportunity, but the main argument for why group fairness constraints and predictive multiplicity are perhaps orthogonal is this proposition, but in reading the proof, it is not clear to me that you can extend this to other fairness metrics. Accuracy parity makes sense here, but I don't think something like group calibration fits the theme. Can the authors comment on this? \n\n\n- How does one pick the number of models in a rashomon set? In practice, in the experiments, it seems like you need to set a number for the size of the rashomon set, and this parameter might have an oversized influence on the arbitrariness and other properties of the set. How was this number determined?", "limitations": "Discussed in the final section of the paper.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "**Originality**\\\nThis paper follows in the line of work on predictive multiplicity and underspecification. Overall, this paper explores the interplay between the predictive multiplicity of a rashomon set and and group fairness properties of that set. A key insight in this work that I hadn't seen before is that it is possible for group fairness constraints to increase the predictive multiplicity of the rashomon set. This finding seems counter-intuitive. The ensembling approach discussed in this work has been mentioned in past work, like the underspecification paper by D'amour et. al., however, it was not explicitly used to address predictive multiplicity as it is used here. Overall, this paper furthers the discussion in a particularly interesting way.\n\n**Quality/Clarity**\\\nThe paper is well-written and clear. Figure 2 was quite helpful for trying to understand the main message of the paper. Overall, this is a high quality paper.\n\n**Significance**\\\nIf it remains the case that arbitrariness is orthogonal to group fairness constraints, then that is an important finding and has far reaching impact on how to obtain models with reliable predictions. The paper has opened up a line of work that can be explored in several ways.", "weaknesses": "None of the weaknesses I discuss here are disqualifying, but I note below places where the paper can be improved.\n\n**Unify the terms Predictive multiplicity, Arbitrariness, and Ambiguity**: Right now, I think these three terms are all referring to the same general phenomenon, but it is unclear whether there is an instantiation of each that is different. Perhaps the authors could unify this.\n\n**Proposition 3.1 is only for accuracy parity/equality**: Unclear if this proposition generalizes to other metrics (see questions section).\n\n**Restricted model class and dataset**: This paper only explores random forest models on tabular datasets.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank Reviewer 47CU for the thoughtful comments and for appreciating the novelty and value of the work. We hope that the answers below address the points raised in the review.\n\n---\n\n**Q1: Proposition 3.1 shows orthogonality of group fairness and predictive multiplicity. Can you extend equality of accuracy to other group fairness constraint (e.g. group calibration) in this proposition?**  \n\n--- Thanks for the question! We confirm that the orthogonality result in Proposition 3.1 extends to group-fairness constraints beyond Overall Accuracy Equality (OAE), which we will add to the Appendix in the final version. What changes now is that there will always be a floor for the probability of error (denoted $\\\\epsilon_{\\\\min}$), and then the condition for attaining maximal ambiguity would be to have at least $m > 1/(\\\\epsilon - \\\\epsilon_{\\\\min})$ competing models. (Note that $\\\\epsilon_{\\min}=0$ for OAE!) \n\nWe illustrate the case of Statistical Parity (SP) below. We note that group calibration can also be done in the more general setup of probabilistic prediction, so the probability of error is taken with respect to the population distribution. We will add further details on this generalized setup for group calibration in the final version of the paper.\n\nConsider SP for binary classes and groups: $\\\\mathrm{Pr}(\\\\hat{Y} = 1 \\\\mid S=0) = \\\\mathrm{Pr}(\\\\hat{Y} = 1 \\\\mid S=1)$. If $Y$ does not satisfy SP, then any predictor $\\\\hat{Y}$ satisfying SP must make an error of at least \n\n$$ \\\\epsilon_{\\\\min} := P_Y(1) - \\\\min(P_{Y|S=0}(1) , P_{Y|S=1}(1)).$$\n\nWe have the following analogue of Proposition 3.1.\n\n**Proposition 3.1 (For Statistical Parity).** For small $\\\\epsilon > \\\\epsilon_{\\\\min}$, and $m$ large enough, there is an empirical Rashomon set $\\\\hat{\\\\mathcal{R}}_m=\\\\{ h_1, \\\\cdots , h_m\\\\}$ such that: 1) each classifier $h_i$ has probability of error $\\\\epsilon$; 2) each classifier $h_i$ satisfies Statistical Parity (SP) exactly; and 3) the set $\\\\hat{\\\\mathcal{R}}_m$ has $100\\\\%$ ambiguity.\n\n In particular, under mild assumptions on $P_{Y,S}$, it suffices to have  $m> 1/(\\\\epsilon-\\\\epsilon_{\\\\min})$ models.\n\n**Proof.** Denote $p=P_{Y|S=0}(1), q=P_{Y|S=1}(1)$. Assume $p \\\\le q$. \n\nLet $\\\\alpha_{0,0}=\\\\epsilon-\\\\epsilon_{\\\\min}$, $\\\\alpha_{1,0}=1-\\\\alpha_{0,0}$, $\\\\alpha_{0,1} = \\\\frac{1-p}{1-q}\\\\alpha_{0,0}$, and $\\\\alpha_{1,1}=\\\\frac{p}{q} \\\\alpha_{1,0}$. For each $(y,s)\\\\in \\\\{0,1\\\\}^2$, let $h$ be a classifier that assigns the class $1$ to a fraction $\\\\alpha_{y,s}$ of the individuals $x$ that have true class $y$ and group $s$. (We have $0<\\\\alpha_{y,s}<1$ if, e.g.,  $\\\\epsilon < \\\\epsilon_{\\\\min} + (1-q)/(1-p)$.) The classifier $h$:\n\n1. has probability of error $\\\\epsilon$;\n2. and satisfies SP exactly.\n\nBy partitioning the sets of individuals into subsets of relative sizes $r_{y,s}:=\\\\min(\\\\alpha_{y,s},1-\\\\alpha_{y,s})$, we may construct $m>1/\\\\min_{y,s}(r_{y,s})$ classifiers as above that make conflicting predictions on each individual (similar to the proof of Proposition 3.1), i.e., the constructed set has ambiguity $100\\\\%$. Finally, if, e.g., $q \\\\le 1-p(1-p)$ (and $\\\\epsilon$ is correspondingly small enough), then the condition simplifies into $m> 1/(\\\\epsilon-\\\\epsilon_{\\\\min})$.\n\n---\n\n**Q2: “How does one pick the number of models in a rashomon set? How was this number determined in the experiments?”**\n\n--- We thank the Reviewer for the question. The number of models sampled from the Rashomon Set indeed may have an important influence on the arbitrariness metric being measured, but the importance varies with the chosen metric. For example, ambiguity (percentage of samples receiving a conflicting label) is non-decreasing with the number of models. On the other hand, standard deviation of scores—our metric of choice—is less influenced by the choice of the hyper-parameters. In practice, the number of models one can sample depends heavily on available computation resources. Through literature research and some initial experimentation, we find 10 models being a reasonable number to estimate the standard deviation of scores, given the size of the datasets, computation required to train the 3 baseline model classes with the various fairness interventions. Repeating the result using 10 random splits of the data also produce small error bars (in shaded region), which acts as a sanity check that the estimation is fairly consistent. There is a separate question of how many models one should sample in order to accurately estimate a metric of arbitrariness within a Rashomon set. This pertains to a line of work that investigates the size of a Rashomon set, which also depends on the volume of the hypothesis space. We refer the Reviewer to Hsu and Calmon [20] for a related discussion.\n\n---\n\n**Q3: “Unify the terms Predictive multiplicity, Arbitrariness, and Ambiguity.”**\n\n--- Thanks for the suggestion! The three terms are connected in the following way. Arbitrariness refers to the general phenomena where a choice — a model or a decision — cannot be justified. Arbitrariness can result from predictive multiplicity, which pertains to prediction tasks and refers to the phenomena where multiple competing models yield conflicting predictions. Ambiguity, proposed by Marx et al. [28], is also a metric of predictive multiplicity of a dataset.\n\nWe understand the confusion since we sometimes use these terms informally. We will add the above discussion to clarify the terminology in the revised version. \n\n---\n\n**Q4: “Restricted model class and dataset: This paper only explores random forest models on tabular datasets.”**\n\n--- Thanks for the comment! We would like to point out that we have provided results for two other model classes—gradient boosting and logistic regression—in **Section D** of the Appendix, as discussed in **Section 5** of main body."}, {"review_id": "Gu8FUDksES", "reviewer": "Reviewer_MNFT", "summary": "The authors theoretically and empirically study predictive multiplicity as it relates to fairness and accuracy. They show in both ways that multiplicity increases as a result of bias mitigation. ", "questions": "The paper is pretty clear.", "limitations": "Nothing specific noted.", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "This is a problem that has not been studied and was worth studying because practitioners don't think about it, and should start doing so.\n\nBoth the theory and the experiments are compelling.\n\nThe paper is well written.\n\nThe math looks correct.\n\nBravo.", "weaknesses": "The authors should justify why arbitrariness is so bad under limited resources that can be allocated. If two people are exactly the same and right at the decision boundary, what other than an arbitrary decision is just if there is only one spot? Similarly, the authors should mention that several bias mitigation post-processing algorithms including [23] have an arbitrariness nature to them as part of the way they work. \n\nIt would be nice if the authors could connect their concentration results more to the original work in (non-fairness) ensemble classifiers, including Breiman's original paper on Random Forests (https://link.springer.com/article/10.1023/a:1010933404324) and the parameters used therein: strength and correlation. There may be simple ways of doing so by extending the operating points of  https://doi.org/10.1109/TKDE.2012.219 to also consider fairness metrics. \n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank Reviewer MNFT for the thoughtful review and for appreciating the novelty, complexity, significance, and positive prospects of the work!\n\n---\n\n**Q1: “Justify why arbitrariness is so bad under limited resources. If two people are exactly the same and right at the decision boundary, what other than an arbitrary decision is just if there is only one spot?”**\n\n--- This is a great point. We agree that, within the context of a single model, making an arbitrary decision between two individuals who are indistinguishable in scores (i.e., equally-distant to the boundary) seems fair. However, when viewed from the perspective of a collection of equally effective models, one person may end up being more likely to experience a change in prediction than the other ************across************ models, resulting in a disparate incidence of arbitrariness. \n\nIn your example, equal distance to a boundary for a single fixed model does not necessarily imply equal likelihood of score change across a collection of competing models. While conventional fairness measures address the average performance of a single classifier across groups, arbitrariness (as considered in our paper) and predictive multiplicity is a global concept that requires a suite of equally accurate and fair models in order to be measured.\n\nThe potentially detrimental impact of disparate arbitrariness has been increasingly recognized in recent literature [12,14,28]. Although arbitrariness might be unavoidable—especially when dealing with over-parametrized models such as neural networks—serious harm can occur when (i) the selection of a model from a set of \"equally good and fair\" options disproportionately impacts certain individuals, (ii) the model is employed in high-stakes applications with significant individual consequences, and/or (iii) a single model is used across multiple institutions, possibly leading to systemic exclusion for certain individuals (the “Algorithmic Leviathan” in [12]). We delve deeper into this topic in our global response — please take a look.\n\nA key point of concern arises when the arbitrariness in model selection remains unknown or unacknowledged. In many fairness interventions, like existing implementations of the “Reductions Approach,” the output for a sample is a thresholded score, in which case a decision (0-1 output) is always given for an individual output. In your example, an apparently inconsequential choice, such as the random seed used to initialize model parameters or a fairness intervention, can dictate the selected individual, transforming a seemingly innocuous decision into a potentially harmful one. Of greater concern is when this harm is silent, and model selection is oblivious to such disparate arbitrariness and masked by the assurance of group fairness. We hope our work sheds light on this issue.\n\n---\n\n**Q2: “Mention that several bias mitigation post-processing algorithms including [23] have an arbitrariness nature to them as part of the way they work.”**\n\n--- Thanks for the Reviewer’s suggestion. Indeed, several bias-mitigation algorithms used to ensure group fairness have inherent randomness that may exacerbate arbitrariness, and we will highlight this issue. In fact, even outside of fairness, Kulynych et al. [26] show that Differential Privacy mechanisms could also unintentionally increase arbitrariness by adding randomness to ensure privacy.\n\nThis phenomenon also seems intertwined with the behavior of fairness interventions outputting overly confident classifiers; please see **Fig. R4** and the accompanying discussion in our common reply in this rebuttal.\n\n---\n\n**Q3: “Connect their concentration results more to the original work in (non-fairness) ensemble classifiers”**\n\n--- Thanks for the Reviewer’s suggestion! It would be an interesting future direction to extend the existing work on ensemble classifiers and specifically Random Forests to consider fairness metrics. (We note that the referenced concentration results pertain to the probability of error, whereas our concentration results have to do with score agreement between ensembled classifiers.)"}, {"review_id": "7ogFSdwXA6", "reviewer": "Reviewer_APJf", "summary": "The authors discuss arbitrariness in automated decision-making, i.e. the fact that similarly trained classifiers may end up disagreeing on the most suitable label for a data point. In particular, the authors observe that arbitrariness can be worsened by fairness interventions, suggesting that increased group fairness may mean that some individuals arbitrarily receive worse decisions. A solution is proposed in the form of an ensemble algorithm that takes many (arbitrarily) fair classifiers and takes a majority vote. ", "questions": "Please find my questions and suggestions in the Weaknesses box.\n\nIf the authors have limited time during the rebuttal, then please consider only answering my questions related to the first weakness.", "limitations": "The (negative) societal impact of the work was not discussed. The authors may want to consider whether ensemble classifiers are a reasonable solution to arbitrariness in practice. Fairness in general has many societal risks if implemented incorrectly.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 4, "strengths": "The authors visit the active yet understudied topic of arbitrariness in a seemingly novel way. Not only may fairness metrics be oblivious to arbitrariness, their optimization may even worsen it. This nuance meaningfully adds to the debate.\n\nThe arguments are presented in a simple manner, and the theoretical results are only as complicated as they need to be.\n\nThe paper is clearly thought-provoking and it invites discussion at a level fit for NeurIPS.", "weaknesses": "1. My biggest concern for the paper is a philosophical one: why is arbitrariness (under your definition) harmful? \n    * In Example 1, this is not very clear: in the 'fair' column, each group receives mistakes at the same rates. Why is arbitrariness problematic here? \n    * I have a similar concern with Example 2: it is elegantly shown that two classifiers are each equally EO-fair yet use a different threshold (leading to arbitrariness). Why should individuals care which classifier is chosen?\n    * Perhaps the argument could be made that arbitrariness is a form of unfairness, and that certain fairness notions are oblivious to it. Yet also in this case I wonder whether there is not always a fairness notion that *does* appropriately consider arbitrariness. For example in Figure 2, the arbitrariness could be detected through the Equalised Opportunity fairness notion (i.e. equal false negative rates). In that case, model 2 would be considered fair and model 1 would not be.\n    * Please note I have not read up on the socio-technical arguments for studying arbitrariness. Nevertheless, I believe the examples in this paper should clarify why arbitrariness is important.\n\n2. Figure 4 presents a worrying result. Should we not be able to see the orange curve (low fairness) trend towards the green curve (baseline)? To their credit, the authors remark this as a remarkable result, but I wonder whether the authors can discuss why we don't see a more gradual shape evolution from green to orange as the fairness intervention is done more and more intensively. If not, then it raises the question if the baseline curve is comparable to the others.\n\n3. Many parts of the presentation are unpolished. Here are some examples.\n    * Equations 1, 2 and 3 all use different symbols for the score / classifier function. Equation 2 in particular is inconsistent, as it indexes the data samples with $i$, and it selects models as elements from a set whereas other equations use the symbol $i$.\n    * It seems $\\mu$ in Eq. 3 should also have a subscript $x$.\n    * Definition 3 presents the random variable $\\hat{Y}$ whereas $h(x)$ was used before.\n    * Section 4 rather suddenly makes the jump from binary classification to multiclass classification.\n    * Figure 3 unnecessarily has a different font and layout. Its x-axis is unlabeled on the right, even though it seems different from the x-axis on the left. The colors in Figure 5 should also be more consistent (as the same methods are used on both sides).\n\n4. Something appears to be wrong with the LaTeX settings. There are no line numbers, and the \"Anonymous Authors\" block is hidden. If this was done to save space, then this gives an unfair advantage compared to other authors that do follow the template correctly.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank Reviewer APJf for the thoughtful comments and for appreciating the novelty and value of the work. We hope that the answers below address the points raised in the review.\n\n---\n\n- **Q1: ‘’My biggest concern for the paper is a philosophical one: why is arbitrariness (under your definition) harmful?’’**\n\n--- We thank the Reviewer for raising this important question! Please refer to the **global response** in this rebuttal for an in-depth discussion of arguments and examples presented in the literature as to why arbitrariness is harmful. In particular, we include under the paragraph **\"Why is arbitrariness (i.e., predictive multiplicity) harmful?\"** in our response a discussion that will be reflected in the final version of the paper. We hope this response clarifies your concerns.\n\nThe Reviewer also raised an important point on whether some fairness notions capture arbitrariness while others are oblivious to it. We would like to first note that Figure 2 is a simplified example. In general, harmful arbitrariness is a **global** notion, one that can only be measured with a pool of equally good models, not with a single classifier. In contrast, group-fairness notions are **local**: they pertain to a *single* classifier and its average performance across groups. Hence, harmful arbitrariness cannot *a priori* be captured by *local* notions such as group fairness. Our work shows that this disentanglement between fairness and arbitrariness is extreme: one can be orthogonal to the other (as can be inferred by, e.g., our Proposition 3.1; see also our generalization result included in the response to **Reviewer 47CU**'s **Q1**).\n\n---\n\n- **Q2: “Figure 4 presents a worrying result. Should we not be able to see the orange curve (low fairness) trend towards the green curve (baseline) (…) as the fairness intervention is done more and more intensively?”**\n\n--- Thanks for the great question! It is indeed natural to expect that as a fairness intervention is applied with a less-stringent group fairness constraint, the scores’ standard deviation tend towards the baseline. However, this is not what we observe, and this phenomena actually reveals the inherent overconfidence, almost thresholded-like, scores from the fairness intervention. Increased arbitrariness still exist even comparing the fair classifiers with the thresholded baseline models. Please refer to our detailed discussion under the paragraph **\"Explanation of Attached Figures to the Rebuttal\"** in the global response.\n\nTo be clear, the classifiers chosen in Figure 1 and 4—obtained from the reductions approach using the implementation from the IBM AIF360 package—outputs scores. However, the majority of the samples receive 0 or 1 post-intervention (see Figure R4). Once we threshold the baseline scores and compute the relevant statistics, the thresholded baseline curve and those with fairness intervention have a closer resemblance (see Figure R3)—thresholding produces the initial phase transition at 0 and high standard deviation at top quantiles. \n\nBeyond the samples that have 0 standard deviation in scores (i.e., consistent prediction) in the thresholded baseline model to begin with, the result remains worrying. As shown in Figure R2, removing the samples that receive consistent predictions both pre and post intervention (about 40% of them), there is a notable group (blue region), the biggest group by count, where the standard deviation increased significantly post-intervention. \n\n---\n\n- **Q3: ‘’Many parts of the presentation are unpolished. Here are some examples. (...)’’**\n\n--- We appreciate the Reviewer for pointing out details and parts of the paper where the notation and layout can be clarified and improved. We will make all the suggested changes in the revised version of the paper.\n\n1. Use $h$ to denote classifiers in equations (2) and (3);\n2. Use appropriate indices in equation (2);\n3. Clarify that $\\bar{\\mu}$ denotes the empirical mean for a fixed $x$;\n4. Change the random variable $\\hat{Y}$ to $h(X)$ in equation (5);\n5. Use the notation of binary classification in Section 4 and explain in Appendix the generalization to multi-class classification;\n6. Clean up Figure 3 and 5 for consistency in font, layout, and color.\n\nThanks a lot for providing the detailed feedback that further strengthens the paper!\n\n---\n\n- **Q4: ‘’Something appears to be wrong with the LaTeX settings.’’**\n\n--- This is an unfortunate and accidental mistake because of an oversight on our side: we used the “preprint” instead of the “review” option in the NeurIPS style file. We recompiled the document under the “preprint” option and observed no meaningful change in length. We regret the error.\n\n---\n\n- **Q5: ‘’The (negative) societal impact of the work was not discussed. The authors may want to consider whether ensemble classifiers are a reasonable solution to arbitrariness in practice. Fairness in general has many societal risks if implemented incorrectly.’’**\n\n--- We thank the Reviewer for the valuable remark. Fairness interventions are at risk of creating the illusion of fairness if not implemented correctly—we will add this note to the limitation section. Ensembling acts as a stabilizing step in mitigating arbitrariness—rather than stopping at a single fair and accurate model, we retrain the model several times with different hyperparameters (e.g. random initialization) to get many models that satisfy both fairness and accuracy constraints. As shown in Fig. 6, this strategy reduces score variation while maintaining baseline fairness and accuracy values. For large models, where training is costly, such an ensembling procedure may be computationally expensive. It is definitely valuable to explore a more computationally efficient strategy in such cases. We will add a discussion in the limitation section as well."}, {"review_id": "LOqTL3sdHJ", "reviewer": "Reviewer_gGVC", "summary": "This paper explores the interaction of predictive multiplicity with fairness interventions, making the observation that models which receive common fairness interventions often result in increased predictive multiplicity within the Rashomon set. They back this up with some theoretical exploration and experiments, proposing ensembling as an approach for reducing multiplicity.", "questions": "- is reducing predictive multiplicity ultimately a good thing? the upside is that the output is more consistent, but the downside is that the more consistent output is not necessarily chosen in a principled manner. I'd be interested to hear more discussion of this tradeoff\n- I'm curious about why the Leveraging approach improves multiplicity so much - this would be good to explore a bit if you have space or at least discuss\n- do we know that ensembles will satisfy fairness metrics if their component models do?", "limitations": "n/a", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "- the observation that models under fairness interventions have higher predictive multiplicity is a novel and interesting one\n- the paper is well-presented and well-scoped, making a clear and useful contribution\n- Figure 3 is a nice intuitive explanation for why the observed phenomenon occurs\n- ensembles are a reasonable mitigation for this problem", "weaknesses": "- I'm a little confused by the discussion around \"confidence\" in 4.2. It would be useful to give more explanation of how confident (or unconfident) classifiers improve the multiplicity problem, and if this matters before or after ensembling. I also cannot seem to find the referred discussion around fairness and confidence in the Appendix - it sounds like an interesting observation and would be interesting to highlight it a bit more.\n- some questions around the formalisms in Sec 2: 1. I think T(D) should be a distribution rather than a set, 2. the writing of equation 1 is a little confusing - it's not quite clear how both m and epsilon can be parameters (what if there aren't m models of loss less than epsilon? is it the m lowest loss or any m?) 3. is the domain of \\ell above Eq 1 [0, 1] x {0, 1}?\n- in Prop 3.1, is there some assumption made around what loss function is used?\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank Reviewer gGVC for the thoughtful comments and for appreciating the novelty and value of the work. We hope that the answers below address the points raised in the review.\n\n---\n\n- **Q1: “Is reducing predictive multiplicity ultimately a good thing?”**\n    \n    --- We thank the Reviewer for this important question! There are mainly two lines of thought on this topic. One line is motivated by the growing recognition that at least some forms of arbitrariness are harmful (common response). For a discussion on positive views of predictive multiplicity, see Kulynych et al. [30], Section 7.1.\n    \n    When predictive multiplicity poses harm to individual users, we believe having a mechanism that stabilizes training is important. One danger of multiplicity is when the model developer is unaware that trivial and innocuous choices during training (even the choice of random seed for parameter initialization!) may lead to arbitrary predictions during model deployment. Our research aims to spotlight this issue, revealing that the addition of group fairness constraints does not necessarily preclude arbitrariness (see **Fig. R1** and our **global response** in this rebuttal). Our proposed solution—an ensembling method—retrains the model with different hyperparameters to produce multiple models that satisfy both fairness and accuracy constraints. As shown in Fig. 6, this approach not only leads to more consistent predictions but also maintains baseline fairness values. \n    We will incorporate this discussion, including the trade-off you've highlighted, into the concluding section of our paper.\n    \n\n---\n\n- **Q2:** **“why the Leveraging approach improves multiplicity so much”**\n    \n    ---  The primary goal of the leveraging approach is to identify an optimal threshold that reduces the disparity of opportunities based on distinct groups while ensuring optimal accuracy. This threshold is applied to generate the final decision output, i.e., binary outcomes in a classification task, as opposed to outputting the likelihood of class memberships.\n    \n    In cases where the variance of scores is low, implementing thresholding on the scores can yield a more stable and consistent output, except for those points near the decision boundary. The leveraging approach, much like other group-fairness-oriented interventions such as the rejection approach, focuses primarily on decision (i.e., binary) outputs rather than raw scores (i.e., values in $[0,1]$). These fairness interventions essentially result in a compression of score variance, contributing to the straight line at 0 in **Fig. R3**.\n    \n    We must note, however, that not all fairness interventions exhibit this pattern. For instance, calibration-based interventions, which are predicated on score outputs, may yield results quite distinct from the leveraging approach, which outputs either 0 or 1. This is because, while group-fairness notions focus on predictions, calibration is based on scores.\n    \n    To further clarify this point, we have supplemented the rebuttal with Figure R3, which demonstrates the effect of thresholding the scores of the baseline model. The behavior exhibited by this curve exhibit resemblance with that of the leveraging approach, but, as shown in the violin plot and discussed in the global response, the increase in score std dev and the ensuing arbitrariness persists after thresholding.\n    \n\n---\n\n- **Q3:** **“do we know that ensembles will satisfy fairness metrics if their component models do?”**\n    \n    --- Great question! The answer depends on the nature of the fairness metrics in question.\n    \n    If the group fairness metrics amount to convex constraints on model performance, ensembling — which is a linear combination of models — will still satisfy the fairness constraints. For example, score-based formulations of Statistical Parity, Equalized Odds, and Overall Accuracy Equality are examples of fairness metrics that can be expressed as convex (in fact, linear) constraints on probabilistic classifiers that output scores instead of thresholded predictions; see Alghamdi et al. [2, Appendix A.7] for a thorough discussion. \n    \n    However, when fairness metrics are cast in terms of thresholded classifier outputs (e.g., differences in FPR and FNR across groups), we cannot provide a theoretical guarantee that fairness constraints will continue to hold post-ensembling due to the metrics’ non-convex nature. Nevertheless, we observe empirically that these fairness constraints are typically met by the ensemble model, as demonstrated in **Figure 6**. We will stress this limitation in the revised version of the paper.\n    \n\n---\n\n- **Q4: “It would be useful to give more explanation of how confident (or unconfident) classifiers improve the multiplicity problem, and if this matters before or after ensembling.”**\n    \n    --- We thank the Reviewer for raising this question! In general, a classifier giving very confident scores, say 0.95 for class 1 or 0.05 for class 0, does not improve the multiplicity problem. While the score is often interpreted as “confidence”, the score is sometimes a proxy for the label, and has no implication of the classifier’s confidence. For example, in Fig.1 of [20], when given a picture of a dog, all scores assigned by competing models are high, but on different classes. \n    \n    We add the confidence assumption, before ensembling, to prove the concentration of predictions in ensembled models. We say a classifier is confident when, roughly, its scores are bounded away from 0.5 with high probability. This assumption enables us to translate consistent scores among ensembled models to consistent predictions in Theorem 4.2. \n    \n\n---\n\n- **Q5: “some questions around the formalisms in Sec 2”**\n    \n    --- We appreciate the Reviewer for pointing out details where the notation can be improved! We will make the relevant changes to the notation of the empirical Rashomon set in Section 2."}]

Author rebuttal:
We thank all reviewers for their time and effort! We are glad our paper was positively received. In particular, we were encouraged that all reviewers recognized the novelty and impact of our work: “If it remains the case that arbitrariness is orthogonal to group fairness constraints, then that is an important finding and has far-reaching impact on how to obtain models with reliable predictions. The paper has opened up a line of work that can be explored in several ways.” (**Reviewer 47CU)**; “This is a problem that has not been studied and was worth studying because practitioners don't think about it, and should start doing so.” (**Reviewer MNFT**); “The authors visit the active yet understudied topic of arbitrariness in a seemingly novel way” (**Reviewer APJf**); and “the observation that models under fairness interventions have higher predictive multiplicity is a novel and interesting one” (**Reviewer gGVC**).

We appreciate the reviewers’ thoughtful input. We believe we have addressed all critical points in the rebuttal below and have outlined how we plan to update the paper accordingly.

---

### **Why is arbitrariness (i.e., predictive multiplicity) harmful?**

In response to **Reviewer MNFT Q1, Reviewer APJf Q1, Reviewer gGVC Q1**, we provide a further discussion (will be added to the revision) to contextualize this work. Our work is motivated by recent literature that delineates the harmful impact of arbitrariness. See Creel and Hellman [12] for a philosophical overview of the hazards of arbitrariness in algorithmic decision-making, the introduction of Marx et. al [28] for potential harms of predictive multiplicity in ML, and D’Amour et. al [14] for extensive examples on how underspecification and the ensuing arbitrary choices among competing models can challenge the credibility of ML models. 

There is a growing recognition that at least some types of arbitrariness in ML can be viewed as harmful; and in particular *disparate* arbitrariness. Arbitrariness itself may be inevitable— when models are overparametrized. Harm arises when (i) an arbitrary choice of model across the set of “equally good and fair” models impacts different individuals differently, (ii) the model is deployed in a high-stakes application with individual-level consequences, and/or (iii) the same model is used across institutions, where an arbitrary choice of model may lead to systemic exclusion for certain individuals. One example from [12, 28] is: 

- **Recidivism prediction:** consider a recidivism risk prediction task that admits competing models with similar accuracy and group fairness levels. In this case, a person who is predicted to recidivate by one model may achieve a lower recidivism risk score by a competing model. An arbitrary choice between these models may lead to unjustified harm, e.g., some defendants may receive consistent predictions across competing models whereas others may not. The harm is particularly concerning when the existence of competing models is unknown or not communicated to the model user. In such cases, arbitrariness can strengthen the growing calls to forgo the use of ML in criminal justice.

As thoroughly discussed by Creel and Hellman [12] (“Algorithmic Leviathans”), arbitrariness may lead to systemic exclusion of opportunities for certain individuals when a single decision-making system, out of the many equally good ones, is chosen without deliberation. 

---

### **Explanation of Attached Figures to the Rebuttal**

We would like to direct your attention to the attached page, with further analysis the fairness-intervention-induced arbitrariness. These figures aim to address points raised by **Reviewer APJf (Q2) and Reviewer gGVC (Q2 and Q4)**. In short, these figures illustrate three points: **1)** Fairness intervention makes classifiers overly confident (attached **Fig. R4**); **2)** This overconfidence partially explains the increase in arbitrariness after intervention; and **3)** Additional significant arbitrariness is induced post-intervention that affects a sizable portion of the population that had no arbitrariness pre-intervention (attached **Fig. R2**).  

- In response to **Reviewer APJf**’s question on the missing trend in **Fig. 4** in the manuscript, in **Fig. R3**, we added 3 curves to the original **Fig. 1** in the main paper, including different levels of intervention using the Rejection approach [23] as well as the thresholded baseline. From the similarity in the shape of the thresholded baseline curve and the fair models’ curves, thresholding-like behavior of some interventions may explain some—but certainly not all (see **Fig. R2**)—increase in score std dev and the ensuing arbitrariness. We plot in **Fig. R2** the distribution of score std. relative to the *thresholded* baseline model. Removing samples that receive very low score std. both from thresholded baseline and fair classifiers, the largest group (blue area) in this violin plot are those individuals for which std. increases from 0 to a large positive value (median around > 0.15). Hence, the blue area shows that significant arbitrariness is introduced by the fairness intervention, in addition to and separate from the effects of thresholding the baseline. Combining the findings from **Figs. R2** and **R3** reveals that overconfidence of scores post-intervention partially explains the shape of the cumulative plots in the original **Fig. 1** of the manuscript.
- Lastly, the aforementioned overconfidence of the post-intervention classifiers is illustrated in **Fig. R4** (addressing **Reviewer gGVC**’s **Q4**). **Fig. R4** provides a histogram of the scores of fair classifiers (from the Reductions [1] approach), which displays the inherent overconfidence, almost thresholded-like, scores from post-intervention.

---

Please do follow up with us if you have additional suggestions and feedback that can further strengthen the paper. Thank you very much!

Meta-review: The paper explores the phenomenon of predictive multiplicity where similar performing models can produce very different predictions on individual samples. The paper demonstrates that procedures for statistical based fairness metrics often exacerbate the predictive multiplicity. The paper argues that so-called arbitrariness should be considered in addition to usual accuracy and fairness and proposes an ensemble algorithm agnostic to the fairness intervention that can ensure more stable predictions with theoretical guarantees.

The reviewers all enjoyed reading the paper and enthusiastically recommended acceptance.

In addition, there are a couple of related works that may be relevant about “churn” which appears to have a very similar definition to predictive multiplicity:

[1] D. Bahri, and H. Jiang. "Locally adaptive label smoothing for predictive churn." ICML 2021

[2] Bhojanapalli, S., Wilber, K., Veit, A., Rawat, A. S., Kim, S., Menon, A., & Kumar, S. (2021). On the reproducibility of neural network predictions. arXiv preprint arXiv:2102.03349
Decision: Accept (spotlight)