Pushing the limits of fairness impossibility: Who's the fairest of them all?
Authors: Brian Hsu
Rahul Mazumder
Preetam Nandy
Kinjal Basu
Venue: NeurIPS 2022 Accept (2022)
Keywords: fairness in machine learning
fairness trade-off
impossibility theorem
non-convex optimization
mixed integer programming

Abstract: The impossibility theorem of fairness is a foundational result in the algorithmic fairness literature. It states that outside of special cases, one cannot exactly and simultaneously satisfy all three common and intuitive definitions of fairness - demographic parity, equalized odds, and predictive rate parity. This result has driven most works to focus on solutions for one or two of the metrics. Rather than follow suit, in this paper we present a framework that pushes the limits of the impossibility theorem in order to satisfy all three metrics to the best extent possible. We develop an integer-programming based approach that can yield a certifiably optimal post-processing method for simultaneously satisfying multiple fairness criteria under small violations. We show experiments demonstrating that our post-processor can improve fairness across the different definitions simultaneously with minimal model performance reduction. We also discuss applications of our framework for model selection and fairness explainability, thereby attempting to answer the question: Who's the fairest of them all?

Pushing the limits of fairness impossibility: Who's the fairest of them all?
Brian Hsu LinkedIn Corporation Sunnyvale, CA bhsu@l inkedin.iinii..m com
Rahul Mazumder"
LinkedIn Corporation, Sunnyvale, CA
(Massachusetts Institute of Technology, Cambridge, MA) rmazumder inkedin. com
Preetam Nandy LinkedIn Corporation Sunnyvale, CA pnandy0linkedin. com
Kinjal Basu Linkedln Corporation Sunnyvale, CA kbasu@linkedin. com
Abstract
The impossibility theorem of fairness is a foundational result the algorithmic fairness literature. It states that outside of special cases, cannot exactly and simultaneously satisfy all three common and intuitive definitions of fairness demographic parity, equalized odds, and predictive rate parity. This result has driven most works to focus on solutions for one or two the metrics. Rather than follow suit, in this paper we present framework that pushes the limits of the impossibility theorem in order to satisfy all three metrics to the best extent possible. We develop an
based approach that can yield a certifiably optimal post-processing method for simultancously satisfying multiple fairness criteria under small violations. We show experiments demonstrating that our prss-proessoor can improve fairesss across the different definitions simultaneously with minimal model performance reduction. We also discuss upplications of our framework for model selection and fairness explainability, thereby attempting answer the question: who's the fairest of them all?
Introduction
While fairness in machine learning has received significant attention in recent years, most existing works focus on one the many fairness criteria [3]. Consequently, practitioners are perhaps left with choice but to their best judgment apply single fairness criterion. We suspect that the conflicting nature of existing mathematical definitions of fairness might have led to this undesirable practice of narrowing down fairness-related measurement and mitigation to one chosen definition. This is somewhat analogous to the trade-off between precision and recall while evaluating model performance [5]. Instead of choosing one of precision or recall evaluate the performance of classification model, practitioners often evaluate the trade-off and choose models that can maintain certain level of precision while optimizing recall or vice-versa (14] In this paper, we provide framework for explicitly addressing such trade-offs among multiple fairness criteria and model performance toward optimal model selection.
One of the most prolific examples of fairness in machine learning arose from the ProPublica recidivism study ((2)), in which a risk assessment tool called COMPAS was found to be biased against black defendants. But beyond the immediate implications in criminal justice, the study also prompted
"This work was done when Rahul Mazumder was consultant for LinkedIn.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

more general studies in algorithmic faimess and, in particular, led to a key result highlighted in [T]. and [8] which some colloquially refer to as the "impossibility theorem" in faimess 22
10
This theorem essentially states that three common definitions of algorithmic fairness demographic
parity [I], equalized odds [66, and predictive parity [3), cannot simultaneously satisfied outside of pathological situations. Several works following these initial results have therefore focused on
satisfying one metric (166 (33 or proposing adaptable methods for different metrics (18) 277.. Yet, while we do not deny the conclusions of the impossibility theorem, we also believe there have not been sufficient efforts to reconcile the conflicting fairness definitions to the best extent possible. We fill this gap in the literature by translating the trade-offs among multiple faimess criteria and model performance into a constrained optimization problem and propose a post- postessoesssing methodology for simultaneously achieving approximate faimess in the conflicting definitions simultaneously.
We believe our framework would alleviate the practitioner from making the hard choice in choosing particular metric. Instead, if they have partial ordering of importance amongst the metrics (which many possess), our framework would explicitly allow them to evaluate such trade-offs. The application which we highlight in Section 4 discusses these in detail. Overall, we make three main contributions in this work:
1. We design a flexible optimization framework that returns a post-processing score transformation function that can make scores group c-fair along three definitions (demographic parity, equalized odds, and predictive rate parity) simultaneously. This framework can be applied to any binary classifier that produces a continuous score, can be configured for singular or multiple metrics of fairness, and also can account for fairness vs. performance trade-offs in terms of ROC-AUC.
2. We present a novel reformulation of this non-convex optimization problem as a Mixed Integer Linear Program (MILP) [3]] This reformulation allows us to find provably globally optimal solutions. We further show that in practice, we can consistently find better solutions through our global optimization method compared to local optimization methods in reasonable time.
We discuss and extend our framework from a post-processing mechanism to a tool that can aid practitioners in better understanding their data and models' empirical fairness characteristics and trade-offs and compare these traits across models.
The rest of the paper is organized as follows. In Section 2 we mathematically define fairness metrics and the multiple fairness optimization problem. We discuss the optimal solution via MILP in Section 3 We try to answer the question of ""who's the fairest of them all?" through our applications and experiments in Section 4 Finally, we conclude with a discussion in Section 5 section with a discussion of the related literature.
We wrap up this
Related Work: Early works 100 exploring the conflicts between fairness definitions show that for a binary predictor, predictive rate parity conflicts with equalized odds (16)) unless base rates are equal or the model is perfectly predictive. Chouldechova [10] also considers tradc-offs between the fairness definitions in the binary prediction case. Kleinberg et al. [18] generalizes this study by showing that statistical (i.c.. demographic) parity is also inconsistent with predictive rate parity and equalized odds. The same paper studies these inconsistencies in a more general bin-wise prediction setting and shows that approximate fairesss definitions (predictive rate parity, equalized odds) can simultaneously hold but only under c-approximate equal base rates or c-approximate perfect performance. This work further proves that there is an inherent trade-off between faireess and loss.
Beyond impossibility theorem results, several works have focused trade-off's between faimess and model performance [T6] 12 27 32)
They develop in-processing solutions aimed at reducing one metric while maintaining accuracy. A few authors have analyzed trade-offs or attempted achieve multiple fairness. One example is Pleiss et al. (26). which shows that predictive rate parity and a relaxed form of equalized odds are reconcilable under randomized prediction scheme. Another notable example is Celis et al. [8] which develops flexible in- proccesssing approach to achieve multiple types of fairness (potentially at the same time). Like Celis al. [. the framework we develop also aims for a flexible approach to focus on one or many faimesss metrics simultaneously. However, our method distinct in that it is a post-processing based solution and also more general as it works for continuous scores (rather than binary classification). Our work is most closely related to Nandy et al. 23 in terms of the underlying score transformation mechanism, and we leverage some of their methods. However, whereas 223 only targets equalized odds, we go further and include
2

---

demographic parity and predictive rate parity in our framework thins posits computational challenges, which we address by proposing novel methodology based on integer programming.
As noted at the end of [88, some open questions are how to optimally assign scores to satisfy multiple criteria when base rates are equal and additionally, how to satisfy predictive rate parity and either equal TPR or TNR when one cost outweighs the other. To our knowledge, no prior work has attempted to reconcile all three fairness conditions (demographic parity, equalized odds, and predictive rate parity) simultaneously with model performance through a post-processing framework. Although the post-processing methods tend to be less flexible for fairness-pent pernesssspe trade-offs than their in- processing counterparts, they can be much more easily added on top of any existing model training pipeline. This makes a post-processing approach modular, and in particular, more appealing in complex web-scale recommender systems that use (a combination of) certain prediction scores to rank a list of items.
2 Multiple Fairness Optimization
We consider binary classification problem where the i-th observation is characterized by their label y/ E (0. }, their group membership 9i 9, and model predicted probability (also known as risk score (18) E [0, 1] for i = 1, ,,...., N. The corresponding random variables are denoted as Y. G and S respectively. To set up the problem, we discretize the scores into nonempty bins b E B = {1, ..... [B]] by using, for example, quantile transformation (we will denote [B] as B). Additionally, let 2 denote the number of group g positive class (y: = 1)) instances in bin b, N:
denote the total number of instances of group g instances in bin N199 (NVll) be the total number of group positive (negative) instances, and N/ be the total number of group instances. Lastly, our approach seeks achieve fairness by moving instances from one bin to another bin: hence, we define variable [o] as the probability of moving an instance of group attribute g and score in bin
into a new bin b' In other words, for every group g. the collection [o] Jo.8' can be represented as a B x B transition matrix (with additional constraints, as discussed next).
For the optimization framework and the remainder of this paper, translate single fairness definition (e.g. equal true positive rate) as a constraint that controls for the worst-case violations across all bins. Below, discuss different fairness constraints that consider in our framework, and describe how they can be represented in terms the optimization variables {1881.
2.1 Fairness Constraints Under Binning Framework
Demographic Parity (DP): For simplicity, we assume that there are exactly two groups g E {1, as we formulate the fairness metrics, although everything discussed below can be applied for non-binary groups by using pairwise constraints, which we elaborate on in Section 2 Starting with demographic or statistical parity from [T], this condition states that the model's predicted score is independent of group membership. This is equivalent to
P(S = s 1) G= 2). 2).
Our version of this constraint uses bins B to empirically approximate the probability P(S G = .) and we also relax the equality to an e-approximate equality (for some pre-specified > 0). Therefore, after transforming the scores using (11g) Jo,y the app-approximaee DP can be expressed via linear constraints
[1] N
1
N N
< EDD
A b E B,
NE
BEB
DEB
where Ny(0l denote the number of observations from group g in bin b (before transformation). and visl = EbEs N/ol In practice, we choose cDp to be larger than the approximation error
In applications. can discretize the scores into B bins with quantile discretizer and consider how move them across bins. More bins allow for more granular interpretation of the transformed scores at the cost of us solving harder problem and vice versa. For every 6', the constraint I can be written collection of linear constraints
3

---

((1/VNl) as we replace P(S
G = g) with its empirical counterpart.
Equalized Odds (EOdds): The equalized odds condition for binary predictors, given Hardt et al. 16 is balance condition where the groups must have equal true positive and false positive rates. For continuous scores, it translates to having equal score distributions for each group conditional on their true labels
23
P(S=s y, -
y. G = 2)
for y {0, {0.
Like demographic parity, our empirical score bin version requires that the distribution of positive or negative instances be (gOdds- approximately equal between groups in the new bins b'. Both equal true positive rate and false positive rate can be expressed as linear constraints, respectively:
P] bb
2 D+
S EBOdAs A A
N
by
N
NEB
bEB
(2)
11
N 66
2
S cpodds A b' E B.
NO
N
BEB
bEB
Predictive Rate Parity (PRP): Lastly, examine the predictive rate parity condition popularized
in [O]. This condition states that the probability of being a positive instance is independent of group membership when condition on the score. Formally:
P(Y = 1 G, = 1 1 = = 2)
Using the empirical score bin framework, an approximate version of the above implies that the proportion of positive instances in each bin must be epRp-approximately equal among groups:
! EE The Gt
(2) 2222 ELEB Jee
S EPPP E
Σ BE 26
N
EbER Eb
N
Unlike constraints 4 and (2), which can be expressed as linear function of the optimization
variables {= }. condition yields bilinear terms and is in general a non-convex constraint. A main technical difficulty of framework arises from this non-convex fairness constraint-Seecai
3 presents an integer programming framework to handle this non-convexity, ensuring we can obtain a globally optimal solution to the resulting optimization problem.
Remark. Our definition fairness as the worst-case violation across all bins aims to resemble approximations of the respective probabilistic definitions but we have not found identical definitions other works. We comment on the differences and discuss why it does not contradict the traditional impossibility theorem of [18) in Appendix ??.
2.2 MFOpt: Multiple Fairness Optimization Framework
We use constraints discussed in Section 2.1 to state the multiple faimess optimization (MFOpt) problem:
No
minimize
ΣΣΣ
(5)
5v 3
(4a)
N
DEG BEB MEB
Σ 6
A V
(4b)
BEB
[n)
-
A be E B, g E G
(4c)
g)) i
A 6' s.t. 16' 6 2 Vgeg
(4d)
Fairness Constraints:
I
(4e)
ELER 2 b+
[a) N911
EBER 1(8'+1)
lol
lss bi
<
A ( B-
(4
EBES 200
[9] Nis]
ELEO 0(041)
viss

---

S 1, A b. 0 S 50
Tol
(4g)
Above, the optimization variables are the group-specific movement probability ber terms and all remaining terms are problem data and/or configurable hyperparameters. Starting with the objective (4a), we define 56 as the midpoint score in the bin and hence the objective is the product of the movement distance S6- S6 weighed by the fraction of total samples moved x/ol/v and the amount
[g] of movement 1'65- 4b) states that the total movement out of bin b, including the movement back to
|all] itself, must sum up to 1 and along with (4g) ensures that 4' represent probabilities in a transition matrix. (4c) states that the total movement from bin b back to itself must be lower bounded by hyperparameter &. This parameter controls how far we allow the new scores to stray from the original and is necessary to prevent zero denominators in and 4f Constraint (4d) represents window constraints to restrict extreme movements of scores beyond w bins. Constraint (4e) are the fairness constraints in Section 2.1 4f
ensures that we preserve the rank-ordering of the scores and expected values, which is desirable for comparing bins against each other. While constraints (4d). {4f) are not fairness-related,
add them to retain the utility of the solution. The predictive rate parity constraint (3) and (4r) both introduce non-convexities into Problem (4) These two constraints also require us to assume overlap, or that each bin contains at least one member from each group. Without overlap, predictive rate parity is undefined since it is not possible to compare expectations across groups for a given bin and demographic parity is likely violated as it means one group has zero probability of landing in a given bin.
Another option we considered for the objective following ((23) is the Riemann approximation of AUC from the bins. ROC AUC be approximated by the FPR at bin & and TPR of the cumulative bins b E (k..... B). Hence, it possible optimize for maximizing AUC as a quadratic objective rather than minimizing score movement as a linear objective. However, in our empirical experience, maximizing AUC as the objective led harder numerical optimization problem (e.g, in terms of finding good feasible solutions) compared to minimizing score movement.
We close this section with two major benefits of this framework compared to inprocessing solutions such as adding fairness regularization ([22 12 (27)) or using an entirely different fairness-based
model (18), (33) ). First, the number of optimization variables scales in the order of [ ())
while the number of constraints scale in the order of (( This is significant as it entails that framework can be applied in arbitrarily large data settings long score-based binning is possible. Applying the transformation is equally scalable, as it only requires binning observations and making independent draws from multinomial distribution with B possible outcomes. Extending the framework to non-binary groups requires creating pairwise constraints for all groups in each bin to achieve the same faimess effect. This means that the number of constraints scale in the order of (IBB) [ (in practice, we expect |G| to be in the range of 3-4). This pairwise procedure does not affect the scaling of the number of optimization variables, which remains (
The second benefit of our framework is that it returns a highly interpretable solution as it returns one optimized B B transition matrix per group. Hence given newly scored instance, several facts can be read from the corresponding row of the matrix such as the likelihood of moving to a specific bin b, moving into any higher or lower bin, etc. These probabilities can also be controlled via constraints as shown with the window constraints (4d) and max movement constraints (4c). This interpretability is an advantage over model regularization frameworks, where it is difficult to know how an individual's
score might change when switching from the base model to a fair model or evaluating how much regularization is required to achieve a certain fairness effect.
3 Finding Optimal Solutions via Mixed Integer Programming (MIP)
The primary difficulty of the above optimization problem are the predictive rate parity constraint 3 and rank-order constraint (4h) which turn the problem non-convex. Non-convex constrained optimization is generally NP-hard and traditional methods that seek locally optimal solutions include gradient-basse interior point optimization (30)). sequential quadratic programming ([3) ) or algo-
"Without the reformulation we present in 3 the pairwise constraints from pairwise groups would generate O(BB"(g g ?) bilinear terms from the cross- mostipuuliliiitiionn of the numerntor/deenmiiatoo sums and result in a much more computationally intensive problem.
5

---

rithms specific to eeterratiiaalycosssraaiitn -uaddratic------- guadratte-programs programs (QCQPs) such as operator splitting methods, semidefinite relaxations, among others (see [24] for an overview).
Rather than pursuing a locally optimal solution, we study a reformulation (7, 66 of the problem as -eaeddeitee---eeaa---ae
(MILP), which theoretically be solved global optimality in finite time via branch-and-boumd methods [3T] Our reformulation grants two benefits over traditional locally optimal solvers. First, global strategies theoretically enable us to find the best possible solution. Second, as our problem primarily scales with the number of bins, we find that in practice, our problem solvable to mear-optimality when utilizing the power of modern MIP solvers.
3.1 Reformulations for computational efficiency
We first observe that direct reformulation of the fractional terms into bilinear terms constraints (3) and (40) will lead bilinear terms in the order of O We show that
reduce this to (
bilinear terms through substitution that exploits the problem structure. Next, we take advantage of the vastly reduced number of bilinear terms apply the normalized multiparametric disaggregation technique (NMDT, (I) which we explain in Section 3.1.2 This allows us to approximate products of continuous variables as products of binary variables, which can be easily linearized and handled by MIP solvers. Importantly, this transformation of ry (i.e, product) terms requires upper and lower bounds for and y and we propose method in Section 3.1.2 for generating and tightening these bounds by solving fractional linear program subproblems (9) Taken together. the reduction of bilinear terms combined with the bound-tige tight-inggnning procedure enable us to effectively apply the NMDT methodology and transform the problem from a non-convex QCQP to an MILP that can be solved to global optimality.
3.1.1 Step 1: Reducing the number of bilinear terms
We reduce the number of bilinear terms in our problem by making a substitution for the fraction term
by introducing new optimization variables ip [gl > (to represent sum) and xlal > (to represent the fractional quantity) as additional variables (see Appendix ?? for more details). We can then use them write equivalent constraints with only ((B) bilinear terms.
Let,
[g] U/
Σ
lsl Na
and
Lol Lol N
Σ
Jol Tay
lsl
A E
beB
bEB
Then we have the following:
Constraint
3
//
1/
I EPRP V E,
Constraint
B.............
b++
3.1.2 Step 2: NMDT and bound tightening through fractional LP subproblems
Linearizing bilinear terms (NMDT): We show how we can model each bilinear term + e/!) by using a binary expansion for the continuous variables ([9l mg and by observing that the product of binary variables can be modeled via integer programming (see (20 29 for reference). To this end, we make use of the NMDT transformation [.. We review this method below following I Given any bounded optimization variable [LL, ZU). and precision factor p, negative integer, we can represent this variable exactly as x = (IU xL)A + IL where
Σ
2'21 + AA
1E(-P....))
where 0 AA < 2D is remainder term and 21 {0, 1} are binary optimization variables. Dropping the remainder term AÀ gives us the approximate form and product forms zy become dot products of several integer variables, which be effectively handled via modern MIP solvers, such (15). Although we are solving an approximation (e.g. precision of 1d) this is not a practical problem
'The open-source implementation can be found in Quadratic/oBinarry.um (MIT License) which utilize.

---

since it is precise enough for reasonable choices of e and we do not expect the constraints to hold exactly when we apply the post-processor on the testing data.
Bounds on of d. via Fractional LPs: A key requirement to apply NMDT is that all optimization
(1 in our case) must be bounded and need to be able variables in the bilinear terms (1/0) and 1/.
to accurately estimate these bounds (i.e., tighter bounds leads to faster runtimes [ We propose obtaining these lower and upper by minimizing and maximizing respectively, the sub-problems while keeping all faimess constraints except the quadratic constraints. Firstly, note that bounds on ((0] vig can be solved as a simple LP (details in Appendix ??). Meanwhile, obtaining bound on t())
requires solving a nonlinear problem due to fact that t/.1 represents a fractional objective (ratio of two affine terms of optimization variables). However, we observe that we can apply the Charnes- Cooper transformation 9 to reformulate the nonlinear problem into simple LP (details in Appendix ??).
3.2 Choice of algorithm: QCQP (heuristic) vs MIP (optimal solution)
In this section we show the results and benefits of our reformulation from a non-convex QCQP to an MILP. In T we take each dataset, create 60/40 train-test split, train grid-searched random forest model, and score the training data. Next, we discretize the scores into bins, parameterize the problem (# bins, e, max movement, window size, solve time) on the scored training data, and compare our MILP solution solved by Gurobi ((55) against the QCQP problem solved by IPOPT ((II), which is a generic interior-pon perriotr-pointttoe log-barrier penalty method for nonlinear constrained optimization. We discuss the datasets and problem parameters for all experiments in the Appendix ??. For each metric such as AUC, use AU CINT and AUCIP to denote the average result of applying the interior-poii (INT, for short) or integer programming (IP) method, respectively. The metrics used are the objective value, optimality gap (%A), [%A)),andd and AUC. We also report the statistical significance of the improvement based the p-value from the Wilcoxon signed-rank test to determine if / S %A INT is consistent result. Bold figures indicate statistical significance w.r.t. 1 standard deviation
Table 1: Interior Point Solution vs. MIP Solution
Dataset
Objint
Objip
%AiNT
%Air
p-value
AUCINT
AUCIP
ACS Income
2,0809
1,9682
15.076 # 6.461
10.621 + 3.402
0.0029
0.9041
0,9044
ACS Insurance
0,9769
0.9599
3,432 = 0.225
1.715 + 0.169
0.0010
0.7411
0.7413
ACS Mobility
2.4580
2.3781
5.37 # 0.803
2.193 = 0.138
0,0010
0.7971
0.7973
ACS Poverty
2.0693
2.0526
3.756 = 0.435
2.972 0.324
0,0010
0,8440
0,8440
ACS Coverage
8.9361
1.9665
7.878 + 2.207
0.0010
0.5420
0.8149
ACS Travel
2.3935
2.3859
2.554 = 0.254
2,242
0.0010
0.7725
0.7725
Heart Disease
1.8871
1,3035
26.385 + 17.401
3.81 = 0.864
0.0010
0.8302
0.8629
COMPAS 7.4551
3.1300
62.88 + 13.407
17.055 + 7.482
0.0010
0.5143
0.7378
As the results show, the MIP reformulation consistently beats the interior point solver applied on the raw optimization problem, even when solving for only 10 minutes. We also observe that in most cases, regardless of the method we choose, we can quickly find near optimal solutions that are high performing in the AUC sense. This is significant result it means that even locally optimal solution to our optimization problem can yield a practically useful post-proe pest-processing result. Additional experiments these datasets showing the effectiveness of MFOpt with respect to performance and fairness in a training/testing data scenario can be found in Appendix ??
We conclude this section by reiterating two benefits of the reformulation. yields lower bounds that can be used to prove optimality or otherwise gauge the quality of a feasible solution. Second, by framing the problem as MIP, we can always theoretically continue improving
First, solving a MIP method
'The optimality gap is defined %A Upper Bound Lownd where the upper bound is the best feasible Upper Bound
solution and the lower bound produced by the branch-and-boume annund method. The INT method does not have the benefit of providing lower bounds, hence we use the bound produced by the method to compute this.
We are limited in the number of trials we can run and actively chose to prioritize the variety of datasets we apply on rather than large number of trials for single dataset. As such, expect relatively large standard errors but we reflect the consistency of our method through the p-value.
"See Appendix ?? for an explanation of the stark underperformance of IPOPT on the ACS Coverage and COMPAS datasets.
7

---

the solution to optimality based on the acceptable time limits. There are other applicable global optimization methods, such as spatial branch and bound. We considered these solutions but ultimately opted for MIP approach due to the maturity and availability of solvers (see Appendix ?? for details).
Applications
In this section, we illustrate a few methods of applying our framework and how it can be used to help model developers select and understand models from a fairness perspective. To apply these procedures, we first require developing an efficient frontier of faimess solutions to understand which configurations are feasible for a given model type and dataset. To generate this frontier, we solve the problem over a grid of parameters EDP, EgOdds: CPRP. Each feasible solution will yield point {(AUC, EDp. EgOdds {PRP)} and the collection of non-dominated points from the solution set yields efficient frontier. We show the 2-d profile shots of our 4-d faireess surface in Figure [] as an example, where the axes represent one of three fairness metrics and the point color gradient represents AUC. In theory, we could obtain a true Pareto-optimal frontier since we have devised method of obtaining globally optimal solutions. However, we generate this frontier using IPOPT due to practical limitations we are solving a 7 x 7 x 7 grid of parameters.
Figure I: Efficient frontier of solutions for ACS West Insurance data
0.35
0.030
0 025
eodos
DID
0.72
0.15
0.71
0.010
0.005
0.70
0 0.00
0.69
0.02
0.03
0.02
0.03
0.03
dp
dp
eodds
Table 2: Performance Fairness Trade-off Analysis
Trade...
For...
AAC
SePA
Base
Base
0.7434
0.0123
0.018
0.0123
AUC
CDp
AUC
EEddds
AUC
EPRP
0.7422
0.0123
0.0180
0.0067
EDP
0,7436
0.0152
0.0123
0.0067
Fodds
EPRP
Fodds
EDP
0,7436
0.0152
0.0123
0.006
4.1 Understanding fairness tradeoff's
After the Pareto frontier generated, the modeler can pick an operating point s based on the desired AUC and tolerable fairness violations However, when communicating fairness properties to stakeholders and accounting for potential changes strategy, can helpful additionally understand the cost of further increasing fairness in terms of <pp, FEOds: PPRP
This tradeoff can be understood by looking at the characteristics of points on the frontier near the operating point. Suppose we are at an operating point If we want to trade AUC for eBOdds- then we would find point s' with at least as good éDP, EPRP but worse AUC and better epOdds- More generally, if we pick trade performance/faimees characteristic (cost) for characteristic (benefit), then we hold all other factors constant and find a point with better and worse e. We illustrate this in the Table [ The first row shows hypothetical operating point while the following rows show other points on the efficient frontier that we could move to when we make a certain trade. Blank rows indicate that no such point was found that permits the desired trade-off. This trade-off perspective can enable developers to better understand and communicate the costs to performance or other fairness metrics when trying to close the disparity in one fairness metric.
8

---

Table 3: Comparison with other fairness methods
Testing Data Method
Method
Metric
Base
MF-Opt
AUC
0.7471 = 0.003
0,6619 = 0.0022
0.747 = 0.003
Rezaci
CDP
0.0117 = 0.0014
0.0124 = 0.0013
0.0088 = 0.001
EpOdds
0.0266 + 0.007
0.0291 = 0.0059
0.0167 = 0.0029
<PяP
0.1091 = 0.0143
0.0986 + 0.0133
AUC
0.8319 = 0.0033
0.8149 = 0.0087
0.831 + 0.0032
Pleiss
EDP
0.0212 = 0.0016
0.0137 = 0.0016
0.0106 + 0.0011
éBddds
0,0329 = 0.0042
0.023 = 0.0038
0.0142 # 0.0028
CPRP
0.1465 = 0.0178
0.4147 = 0.1537
0.1547 = 0.0293
4.2 Performance Comparison
Lastly, we compare our framework against two methods and show that we can satisfy fairness constraint(s) just as well or better, while obtaining significantly stronger performance. Our comparison is done as follows (details in ??), in each iteration we randomly split and pre-process the data, tune and fit random forest model, and score the training and testing data to get the base scores ÿu- Next, we run the methodology that we are comparing against (i.e. build model or apply the postprocessor) to get method scores In- We then bin the outputs of the base model and compared method and compute the AUC along with the fairness metrics (Cp, Cn). Next, we solve our constrained optimization problem on the training data, where we set the parameters to min((o, <m After optimizing, we
apply the optimal solutions =1gg to assign bins in the testing data based on the original score
bins. One method of assigning group instance with score s E b (denote as !ol) would be to randomly draw from a multinomial distribution parameterized by probabilities (x [g] ..........).... )(8)) We propose alternative methods to this stochastic assignment method in the Appendix ? Lastly, we compute the resulting AUC and faimess metrics remapped bins for the testing data (and do the same for Jo and fm on the testing data). These figures are shown in Table 3 We only show the results on the test set due to space constraints and have placed the results for the training set Appendix ??. Bold figures indicate that metric is statistically significant to I standard deviation.
First, compare framework against the in in-processing framework in Rezaei et al. 127] which is robust optimization based logistic regression model for reducing equality of opportunity violation. We found that this method works well compared to standard logistic regression and managed decrease fairness violations while maintaining the similar performance. It improves in Fodds compared to a random forest well. However, its weakness is that the underlying model is still logistic regression and therefore has limited expressiveness. In comparison, MFOpt can be applied on top of any model class and thus the performance advantages of more fiexible models are better maintained.
Next, we compare our framework against the post-processing framework in Pleiss et al. (26]. this method, the authors use randomization maintain the model's calibration while simultaneously satisfying a relaxed equalized odds condition (whereby a linear combination of TPR and TNR are satisfied). Again, shrinks equalized odds violations, and even decreases demographic parity violations too. However, results in large violations of bin-wise predictive rate parity in contrast to method.
that this method maintains close performance the base model, successfully
4.3 Who's the fairest of them all?
In industry, machine learning model selection is guided by many factors including performance, speed, interpretability, among others. Yet, the fairness dimension is commonly overlooked unless the developers specifically induce it in their model. Even then, picking specific faimess metric to optimize for can be a nebulous task. Rather than focus on a single metric, we describe a simple and intuitive method of gauging model's efficiency in trading between different fairness definitions.
To do so, we first construct the frontier for the two models in question and then filter all points on the efficient frontier with tolerable performance AUC 2 AU Aminn Next, find the point on the

---

respective frontiers with minimum Euclidean distance to the origin. The model with the shorter distance their frontier can then be declared the model that has better tradeoff properties. This procedure combined with the trade-off analysis can be useful when developer is iterating between models that were not designed for fairness, but wants a model that can be flexibly made more fair through the MFOpt framework. As fairness requirements may change over time, the model that can yield the best tradeoff's between different definitions can offer the most overall utility.
Discussion
In our study, have devised flexible and interpretable post-processing method which apply to push the limits of the impossibilityy theorem. We show that while theoretical limitations remain undisputed, there is path forward to practically reconciling the conflicting faimess definitions. These results extend the findings of (28), which state that the trade-off of fairness and accuracy are negligible in practice. Our work reinforces this claim but also adds that trade-off's between fairness definitions can be negligible as well. For further research, one area is to improve the consistency of the PRP violation reduction, we observed the largest standard error in reducing this metric. This could be due to us using random forests for all experiments, which is known to be an uncalibrated model 4). One method to address this is therefore first calibrating the model through other methodologies such as Platt scaling ([25)) or binning- based calibration ([19)) before applying MFOpt. We could also consider incorporating uncertainty in the training data through principled approaches such as stochastic or robust optimization.
Acknowledgements
We would sincerely like to thank David Durfee and Osonde Osoba for their insightful feedback. We would also like to thank Ye Tu, Sakshi Jain, Shaunak Chatterjee, Ram Swaminathan, Romer Rosales, and Ya Xu for their support. Finally, we would also like to thank the anonymous reviewers for their helpful comments which improved the paper.
Rahul Mazumder contributed to this work while he was consultant for LinkedIn (in compliance with MIT's outside professional activities policies). This work is not a part of his MIT research.
10

---

References
[1] Andrade, Oliveira, S. Hamacher, and A. Hberhard. Enhancing the normalized multi- parametric disaggregation technique for mixed-integer quadratic programming. J. of Global
Optimization, 73(4)7701-222, apr 2019. ISSN 0925-5001, doi: 10.10077//0898--18--0222
URL/ttps: http:: org/10. wtw.g//...000//////1/
0728-9
[2] J. Angwin, J. Larson,
S.
Mattu, and L. Kirchner.
Machine
bias, May 2016.
URL https //www/wwwww... http:///wwwppooobo. propublica. org/article/
machine- bias roso-rik--- assesements- in criminal wwwmminnn--eteeninnn.n. sentencing
[3] S. Barocas, M. Hardt, and A. Narayanan. Fairness and Machine Learning. fairmlbook.org. 2019. http:://ww. http///owwwairilbooooooooooo org
[4] H. Boström. Calibrating random forests. In 2008 Seventh International Conference on Machine Learning and Applications, pages 121-126, 2008. doi: 10. 10.1109/CMLA.2208..
[5] M. Buckland and F. Gey. The relationship between recall and precision. Journal of the American society for information science, 45(1):12-19 1994.
[6] M. Castro. Tightening piecewise mccormick relaxations for bilinear problems. Computers & Chemical Engineering, 72:300-311, 311, 2015. ISSN 0098-1354, doi: http:://oi. 10110 2twp:cheemmmn.221400033 URL //www. sciencedirect. com wttss/ccececariccce/ article/ p11/500981134440000066 A Tribute to Ignacio E. Grossmann.
[7] P. M. Castro. Normalized multiparametric disaggregation: An efficient relaxation for
mixed-intes -ixtedr bilinear problems. of Global Optimization, 64(4).765-784, apr 2016. ISSN 0925-5001. doi: 10.1007/s10898 000007//10098--01--33-2222 URL https://doi. 0ttp://000...g//11100007/ 015-98-015-034400
[8] L. E. Celis, Huang, V. Keswani, and N. K. Vishnoi. Classification with fairness constraints: meta-algorithm with provable guarantees. FAT '19, page 319-328, New York, NY, USA, 2019. Association for Computing Machinery. ISBN 9781450361255,
doi: 10.1 10.11457285500.2285566
0041/111715600 URL /dttps:/://doi org/ 10. 1145 3287560 3287586
[9] A. Charnes and W. W. Cooper. Programming with linear fractional functionals. Naval Research Logistics Quarterly, 9(3-4):81-1866 1962. doi: http::/bbb.oogg.o...00//aaaa.a.
URL
https://onlineliin
welll..wlllge wiley. com/ /oi/ abs/ 1002/nav..vvvv htt.:////aa330090000000 3800090303
[10] A. Chouldechova. Fair prediction with disparate impact: A study of bias in recidivism prediction
instruments. Big Data, 5(2):153-163, 2017. doi: 00.10899big.2016.0444 URL https
//doi org/10 1089/bigg..e /bgg.iii.... 2016.00200
[11] C. Dwork, M. Hardt, T. Pitassi, O. Reingold, and R. Zemel. Fairness through awareness. In Proceedings of the 3rd innovations in theoretical computer science conference, pages 214-226. 2012.
[12] B. Fish, J. Kun, and Ádám D. Lelkes. A Confidennce-Baseed Congideccce-BaseedAppphchhh and Accurucy, pages 144-152. doi: 99717779997811111733333 URL https://epubs: siam. siam.org/ wwwp///////...//ooo 11w./1 httb://00.13333/977711111432333 9781871174111111117718
Approach for Balancing Fairness
[13] E. Gill and E. Wong. Sequential quadratic programming methods. 2012.
[14] M. Gordon and M. Kochen. Recall-precision trade-off: A derivation. Journal of the American Society for Information Science, 40(3):145-151, 1989.
[15] Gurobi Optimization, LLC. Gurobi Optimizer Reference Manual, 2022. URL https: h //www gurobi com
[16] M. Hardt, E. Price, E. Price, and N. Srebro. Equality of opportunity in supervised learning. In
D. D. Lee, M. Sugiyama. U. V. Luxburg, I. Guyon, and R. Garnett, editors, Advances in Neural Information Processing Systems 29, pages 3315-3323, Curran Associates, Inc., 2016.
[17] K. Karthik, The impossibility theorem of machine fairness A causal perspective. CoRR, 04422007.06024 2020. URL httphs://tratii //wrxiaa.vvvv////////a wwg.oos////////oooooo...oeee abs/2007 2200000020.0...
11

---

[18] J. Kleinberg, S. Mullainathan, and M. Raghavan. Inherent Trade- Trade-Offfs. in the Fair Determination of Risk Scores. In C. H. Papadimitriou, editor, 8th Innovations in Theoretical Computer Science Conference (ITCS 2017), volume 67 of Leibniz International Proceedings in Informatics (IIPlcss), pages 43:1-43:23, Dagstuhl, Germany, 2017. Schloss Dagstuhl-Leibbni-ZZennne fuer Informatik. ISBN 978-3 378-3-95977-002-33 doi: //drops httpp/uiiedee/pppppooootttttte/e
http
[19] A. Kumar, P. S. Liang, and T. Ma. Verified uncertainty calibration. In Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurlPS 2019, 2019.
[20] H.-L. Li and C.-T. Chang. An approximate approach of global optimization for polynomial programming problems, In European Journal of Operations Research, pages 625-632 European Journal of Operations Research Volume 107, 1996.
[21] R. Hougee-Heimerr. The common optimization interface for operations research: Promoting open-source software in the operations research community. IBM Journal of Research and Development, 47(1):57-66, 2003. doi: 10. 14.11d//rd.471 470507
[22] T. Miconi. The impossibility of "fairness": a generalized impossibility result for decisions, 2017. https://///ax wttpi//...ggb/b////////ee .01995
[23] Nandy, C. Diciccio, D. Venugopalan, H. Logan, K. Basu, and N. E. Karoui. Achieving fairness via post-pooessiing in web-scale recommender systems, 2020. URL https://arxii org/abs/2006. 11350
[24] J. Park and S. Boyd. General heuristics for nonconvex quadratically constrained quadratic programming, 2017. URL
http://rxxiv..rr/aa//////....
[25] J. C. Platt. Probabilistic outputs for support vector machines and comparisons to regularized likelihood methods. In ADVANCES IN LARGE MARGIN CLASSIFIERS, pages 61-74. MIT Press, 1999.
[26] G. Pleiss, M. Raghavan, F. Wu, J. Kleinberg, and K. Q. Weinberger. On fairness and calibration. In Advances in Neural Information Processing Systems, pages 5680-5689, 2017.
[27] A. Rezaci, R. Fathony, O. Memarrast, and B. Ziebart. Faimess for robust log loss classification. Proceedings of the AAAI Conference on Artificial Intelligence, 34(04):5511-5518 apr 2020. doi: 10.1609/aaai. wtt./////....3.0....... v34i04.6002 URL https: //do:.///oiioo org/ 10. 16t.9/9a99/aaaaa v34104. 6002
[28] K. T. Rodolfa, H. Lamba, and R. Ghani. Empirical observation of negligible faimess-accuuaay trade-offs in machine learning for public policy. Nature Machine Intelligence. 3(10):896- 904, oct 2021. doi: 00.1033//4255--02--00086 2Fs42256 021-00396-x
URL httph:://///t //doi. org/10. 11t./1..11300 1038%
[29] J. P. Teles, P. M. Castro, and H. A. Matos. Univariate parameterization for global optimization of mixed-integer polynomial problems. European Journal of Operational Research, 229(3):
615.625, 2013. ISSN 0377-2217. doi: http://ww......ccoocc/c//c/ce//a
URL
http::/ww..cioncedreeen http://ttc.cocccccce/////tti///e
[30] A. Wächter and L. Biegler. On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming. Mathematical Progrumming, 106:25-57, 2006.
[31] L. A. Wolsey and G. L. Nemhauser. Integer and combinatorial optimizution, volume 55. John Wiley & Sons, 1999.
[32] M. B. Zafar, I. Valera, M. G. Rogriguez, and K. P. Gummadi. Fairness Constraints: Mechanisms for Fair Classification. In A. Singh and J. Zhu, editors, Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, volume 54 of Proceedings of Machine Learning Research, pages 962-970. PMLR, 20-22 Apr 2017. StRL.tttps//pprceediin
mlr. www.pprssssseeee wwwppppws.//epppp http///4///a/// zaf ar 17a. html
12

---

[33] B. H. Zhang, B. Lemoine, and M. Mitchell. Mitigating unwanted biases with adversarial learning. AIES '18, page 335-340, New York, NY, USA, 2018. Association for Computing Machinery. ISBN 9781450360122 28.
doi: 10. (0.1145/5778721.2277779
htt.https://dol.
10. 10.1145/3278721.1 32777779
13


Reviews:
[{"review_id": "SBxJuEMqAJG", "reviewer": "Reviewer_qwXE", "summary": "This paper proposes an optimization-based method to simultaneously reduce the gap in demographic parity, equalized odds, and predictive rate parity. The fairness problem is first formulated as a non-convex optimization task and then solved using mixed integer programming. Experimental results that compares the proposed method against two existing baselines are provided.", "questions": "\n1. What change should be on the target and constrains if protected attributes are non-binary?\n\n2. In table 1, INT significantly under-performs IP for ACS coverage and COMPAS. What's the reason behind this gap for these two datasets?\n\n3. It would be great if the authors could provide additional ablation experiment on the size of bins and see how B impacts the performance.", "limitations": "Please see the weakness in the previous section for major concern. Minor concerns are:\n\n1. Figure 1 needs to be improved: clearer labels for x,y axis and legend.\n\n2. The experiment set up seems unclear. How was the training/validation/test set split? At which subset the X matrix is learned? \n\n", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. This paper provides a novel solution to the well-known impossibility theorem in algorithmic fairness. The motif of the paper is novel and very relevant to the fairness community.\n2. One major strength of this paper is that this methodology enables the user to select the model from the frontier that offers the best trade-off among all fairness metrics and performance. This feature is very appealing to models that are deployed under multiple applications.\n3. This paper is well-organized. All concepts are clearly explained. The authors provide sufficient intuition along with rigorous definitions. \n4. The formulation of the constrained optimization problem fits well with the fairness application. The constraints are well-explained and intuitively make perfect sense.\n5. The proposed MILP solution is novel and suitable to this application. MILP is computationally tractable and globally optimal (although the problem formulation accepts tolerance).\n\nWeakness:\nThe major concern for this approach is on its generalizability. Will the transformation matrix (X) learned on a tune/train set transfer (with great fairness & accuracy performance) to the test set? How is the binning method impact the generalizability? Technically, one can make B -> infinity and learn a X that achieves (almost) perfect performance on both fairness and accuracy perspective. But this performance will not generalize to the unseen test set. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "HiS_X4--oMx", "reviewer": "Reviewer_mnAD", "summary": "This paper studies how to deal with the trade-off among three common fairness notions: demographic parity, equalized odds, and predictive rate parity. The paper proposes a post-processing approach that aims to modify the decision made by any prediction model. The variable is the probability of flipping the decision from one to another for each group (in the case of continuous decision it is to move instances from one to another). Then, a combinatorial optimization problem is defined which contains the formulations of all fair constraints. The paper develops an efficient approach to solve the problem via mixed integer programming. Finally, experiments show that the proposed method can help the decision maker balance the trade-off between model utility and different fairness constraints.", "questions": "A critical question that may affect my final rating is that, in Eq. (1), when the number of instances in b’ after transformation is computed, why only considering the instances that are transformed into b’? What about the instances that are transformed out of b’?\n\nOther questions:\n\nMixed integer programming in general is still NP-hard. Why does the paper claim that the proposed MIP reformulation is tractable?\n\nThe paper states that the challenge for solving the optimization problem comes from Constraint (3) and (4f) which introduce non-convexities. What if we remove Constraint (3) and (4f)? For Constraint (3), since the most commonly used fairness notions are demographic parity and equalized odds, in some cases it is fine not to consider the third one. For Constraint (4f), it seems to me that its purpose is to further preserve the utility of the solution in addition to the objective function. Thus, it is not a necessary condition in the optimization.\n", "limitations": "Yes.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength\n\nThe proposed optimization framework is not limited to binary classification. The reformulation makes the optimization problem tractable. The optimization framework is also scalable since its complexity does not depend on the number of features and samples in the data. The experiment results are interesting which show that the proposed method is practically meaningful to practitioners and decision makers.\n\nWeakness\n\nAlthough the size the optimization problem only depends on the number of groups and the number of bins, in many cases the number of groups may be much larger than two. For example, when we consider intersectional fairness for multiple protected features, and when we consider conditional fairness notions (e.g., conditional demographic parity) which can produce a large number of subgroups by conditioning on certain features, the number of groups will increase significantly. The paper does not analyze the scalability of the proposed method under such situation.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "2gUsGDdYzpB", "reviewer": "Reviewer_nPyX", "summary": "This paper pushes the limit of fairness impossibility theorem where all three group fairness definitions cannot be satisfied simultaneously. Based on an integer-programming approach, the authors propose a framework to yield a certifiably optimal post-processing method for simultaneously satisfying multiple fairness criteria under small violations. In experiments, the framework with minimal model performance reduction achieves fairness improvement across different definitions simultaneously. As an application, the framework advises on model selection and fairness explainability. ", "questions": "- In Figure 1, what does different colours mean?\n- Why do authors compare with an in-processing algorithm while the proposed work is a post-processing algorithm?", "limitations": "There is no negative societal impact of this work.", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength: \n- The motivation of the paper is very interesting. \n\nWeakness:\n- There is no experimental comparison with existing fairness works.\n - While the proposed method belongs to post-processing fairness algorithms, experiments do not include any comparison with post-processing algorithms. \n- Tables and figures are uninformatively presented. \n- In Table 3, few cells are in bold fonts. No interpretation is given. \n- A motivating example is missing, where authors could compare theoretical fairness impossibility result vs. their proposed solution.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept