Fairness Through Matching
Authors: Kunwoong Kim
Insung Kong
Jongjin Lee
Minwoo Chae
Sangchul Park
Yongdai Kim
Venue: Accepted by TMLR ()

Abstract: Group fairness requires that different protected groups, characterized by a given sensitive attribute, receive equal outcomes overall.
Typically, the level of group fairness is measured by the statistical gap between predictions from different protected groups.
In this study, we reveal an implicit property of existing group fairness measures, which provides an insight into how the group-fair models behave.
Then, we develop a new group-fair constraint based on this implicit property to learn group-fair models.
To do so, we first introduce a notable theoretical observation: every group-fair model has an implicitly corresponding transport map between the input spaces of each protected group.
Based on this observation, we introduce a new group fairness measure termed Matched Demographic Parity (MDP), which quantifies the averaged gap between predictions of two individuals (from different protected groups) matched by a given transport map.
Then, we prove that any transport map can be used in MDP to learn group-fair models, and develop a novel algorithm called Fairness Through Matching (FTM), which learns a group-fair model using MDP constraint with an user-specified transport map.
We specifically propose two favorable types of transport maps for MDP, based on the optimal transport theory, and discuss their advantages.
Experiments reveal that FTM successfully trains group-fair models with certain desirable properties by choosing the transport map accordingly.

Published in Transactions on Machine Learning Research (12/2024)
Fairness Through Matching
Kunwoong Kim
kukim www.oooonnnnnnnmiicccmmmm
Deportment of Statistics Seoud National University
Insung Kong"
Kessungkong@uuueeteee
Department of Applied Mathematics University of Twente
Jongjin Lee
filee www.eeeemmngg.comm. com
Samsung Research
Minwoo Chac
mchae(@pottech.ac.
Department of Industrial and Management Engineering Pohang University of Science and Technology (POSTECH)
Sangchul Park
parks oc.kr
School of Law
Scoul National University
Yongdai Kim!
ydkim@0903@gmail.comm com
Deportment of Statistics
Interdisciplinary Program Artificial Intelligence Seoul National Universily
Reviewed on OpenReview: https: // openreview. net/ forum? id= dHljjaNHh
Abstract
Group fairness requires that different protected groups, characterized by a given sensitive attribute, receive equal outcomes overall. Typically, the level of group fairness is mcasured by the stalistical gap between predictions from different protected groups. In this study, we reveal an implicit property of existing group fairness measures, which provides an insight into how the group-fair models behave. Then, we develop new group-fair constraint based on this implicit property to learn group-fair fair models. To do so, we first introduce a notable thcoretical observation: every group-fair model has an implicitly corresponding transport map between the input spaces of each protected group. Based on this observation, we introduce new group fairness mcasure termed Matched Demographic Parity (MDP), which quantifies the averaged gap between predictions of two individuals (from different protected groups) matched by given transport map. Then, we prove that any transport map can be used in MDP to learn group-fair models, and develop a novel algorithm called Fairness Through Matching (FTM which learns a group-fair model using MDP constraint with an user-specified transport map. We specifically propose two favorable types of transport maps for MDP, based on the optimal transport theory, and discuss their advantages. Experiments reveal that FTM successfully trains group-fair models with certain desirable properties by choosing the transport map accordingly.
The source code of FTM is publicly available at https: // thub. com/ kwkimon www.iiooonnnnnee.moooooo FTM "This research was conducted while the author affiliated with Secul National University.
i &Correspondngg author.

---

Published in Transactions on Machine Learning Research (12/2024)
1 Introduction
Artificial Intelligence (AT) technologies based machine learning algorithms have become increasingly prevalent crucial decision-making tools across diverse areas, including credit scoring, criminal risk assessment, and college admissions. However, when observed data contains unfair biases, the resulting trained models may
produce discriminatory decisions (Calders et al. 2009 Feldman et al., 2015 Angwin et al., 2016 Barocas
& Sclbst, 2016 Chouldechova 2016 Kleinberg ct al.
2018 Mchrabi et al. 2019; Zhou et al., 2021 For
instance, several cases of unfair preferences lavoring specific groups, such as white individuals or males, have
been reported (Angwin et al. 2016 Ingold & Soper 2016 Dua & Graff 2017). In response, there is growing
trend in non-discriminatio laws that calls for the consideration of fair models (Hellman 2019).
Under this social circumstance, ensuring algorithmic fairness in Al-based decision- has become crucial mission. Among several notions of algorithmic fairness, the notion of group fairness is the most explored one, which requires that certain statistics of each protected group should be similar. For example, the ratio of positive predictions should be similar across each protected group (Calders et al. 2009 Barocas
& Selbst. 2016 Zafar et al. 2017 Donini et al. 2018 Agarwal et al. 2018).
Various algorithms have been proposed to learn models achieving group fairness. Existing methods for group fairness are roughly categorized into three: are-processing, in- in-processing and post-processing. Pre-processing
approaches (Zemel et al., 2013 Feldman et al.) 2015 Webster et al. 2018 Xu et al. 2018 Madras et al. 2018
Creager et alla|12011111 2019 Kim et al. 2022a) aim to debias a given dataset, typically by learning fair reprosentations whose distribution is independent of a given sensitive attribute. The debiased data (or fair representation) is
then used to learn models. In-processing approaches (Kamishima et al. 2012: Goh et al.] 2016
Zafar et al.
2017
Agarwal ct al.) 20188 Wu et al., 2019: Cotter et al.) [019 Celis et al., 2019; Zafar ct al.
2019 Jiang
ct al. 2020a Kim et al.]
2022b) train models by minimizing a given objective function under a specified
group fairness constraint. Post-processing approaches (Kamiran al. 2012 Hardt al.
2016b Fish et. al.
2016
Corbett-Davies et al.
2017 Pleiss et al. 2017 Chzhen et al. 2019 Wei et al.) 2020
Jiang al. 2020a
transform given prediction scores, typically provided by an unfair model, to satisfy certain fairness level.
Most group-fair algorithms correspond to specific group fairness measures, typically defined by explicit quantities such as prediction scores and sensitive attributes. For example, demographic parity (Calders et al. 2009; Feldman et al., 2015 Angwin et al. 2016) considers the gap between two protected groups in terms of the positive prediction ratio.
However, a shortcoming of such group fairness measures is that they only concern statistical disparities without accounting for implicit mechanisms about how given model achieves group fairness. Consequently, models can achieve high levels of group fairness in very undesirable ways (see Section B of Appendix for an example). Dwork et al. (2012) also noted that focusing solely on group fairness can lead to issucs such as subset largeting and the sell-fuliiling prophecy. These observations serve as the motivation of this study. Moreover, our empirical investigations on real-world datasets reveal that unfairness on subsets can be observed in group-fair models learned by existing algorithms, which are designed to achieve group fairness merely (see Scction 5.
In this paper, we first propose new group fairness measure that reveals implicit behaviors of group-fair models. Based on the proposed measure, we develop an in-processing algorithm to learn group-fair models with less undesirable properties (c.g., unfairness on subsets), that cannot be explored or controlled by existing fairness measures.
To do so, we begin by introducing notable mathematical finding; every group-fair model implicitly corresponds to transport map, which moves the measure of one protected group to another. Building on this observation, propose new measure for group fairness called Matched Demographic Parity (MDP), which quantifies the average prediction gap between two individuals from different protected groups matched by given transport map. We further prove that the reverse of this finding also holds: any transport map can be used in MDP to learn a group-fair model. Consequently, we develop an algorithm called Fairness Through Matching (FTM), designed to learn a group-fair model under a fairness constraint based on MDP with a given transport map. FTM can provide group-fair models having specific desirable properties (c.g., higher fairness on subsets) by selecting transport map accordingly. Note that FTM is not designed to achieve the
2

---

Published in Transactions on Machine Learning Research (12/2024)
optimal ddirness-prediction trade-off, rather, the focus is on mitigating undesirable properties when achieving group fairness (e.g., unfairness on subsets).
In contrast, existing algorithms that focus solely on group fairness may lack such flexibility, In fact, FTM with a transport map that is not carefully selected could result in unreasonable group-fair models, even though group fairness achieved.
Therefore, the key to effectively using FTM lies in selecting good transport map. To this end, we propose two specific options for the transport map: one is the optimal transport (QT) map in the imput space, and the other is the OT map in the product space of input and output. Each is designed to achieve specific goals. For example, the former achieves higher fairness levels on subsets, while the latter yields better prediction performance and attains higher levels of equalized odds compared to the former. Experiments on real benchmark datasets support our theoretical findings, showing that FTM successfully learns group-fair models with more desirable propertics, than those learned by existing algorithms for group fairness.
Main contributions
We introduce a notable mathematical observation: every group-fair model has a corresponding implicit transport map. Building on this finding, we present novel mcasure of group fairness called Matched Demographic Parity (MDP).
2. We prove that any transport map can be used in MDP to learn group-fair models. Subscquently, we devise novel algorithm called Fairness Through Matching (FTM), designed to find group-fair model using a constraint based on MDP with a given transport map. We propose two favorable transport maps tailored for specific purposes.
Experiments on benchmark datasets illustrate that FTM successfully learns group-fair models. Furthermore, we examine the benefits of the two proposed transport maps learning more desirable group-fair models, compared to those learned by existing algorithms that focus solely on achieving group fairness.
2 Preliminaries
2.1 Notations & Problem setting
In this section, we outline the mathemattcal notations used throughout this paper. We focus on binary classification task in this study. We denote X e X' c Rd and Y y' 1] as the d-dimensional input vector and the binary label, respectively. Whenever necessary, we split X, i.e., the domain of X, with respect to S and write X, as the domain of X sensitive attribute is binary, we denote S E {0, 1) as the binary sensitive attribute. For given s (0, 1), the realization of S, we write s' = - s. For the probability distributions of these variables, let P and Px represent the joint distribution of (X, Y, and the marginal distribution of X, respectively. Furthermore, let P. Px s e 1) be the conditional distributions of X given = s. We write E and E, as the corresponding expectations of and P., respectively. For observed data, denote D = [(x,, Bi, s;) }i as the training dataset, consisting of independent copies of the random tuple (X,Y, P. Let || denote the -|- ||a for simplicity.
For given S {0,1), we let s' ===1 =1-s s. Assuming the pre-defined
Lp norm. We also write the L2 norm by || |l, i.e., I- || ==|
We denote the prediction model as f f(. s {0. 1), which is an estimator of P. = 1|x belonging to a given hesos class F c cf= (0,1) [0, Note that the output of ʃ is restricted to the interval [0. I], making If bounded. For simplicity, we sometimes write f(;5) = f+)) whenever necessary. For given f and s e 1), we denote P,, as the conditional distribution of f(X,8) given S s. Furthermore, let C₁ I[f(-,s) 2 7) be the classification rule based on f, where 5 is a specific threshold (typically, 7 7= 0.5).
2.2 Measures for group fairness & Definition of fair model
In the context of group fairness, various measures have been introduccd quantify the gap between predictions of each protected group. The original measure for Demographic Parity (DP), ADP(S)
3

---

Published in Transactions on Machine Learning Research (12/2024)
JP(C (x 1|S = 0)- - PC (X) = = =|S = 1))
has been initially considered in various studies (Calders et al.
2009
Feldman et al.
2015
Donini et. al.
2018 Agarwal et al. 2019 Zafar et 2019). Its relaxed version.
ADP (f) = E fo X
S = 0) - | f1 (X)) -
1)),
has also been explored widely (Madras et al.
2018 Chuang
& Mrouch 2021 Kim et al. 2022al..
However, (f) has a limitation as it relies on a specific threshold r (Silvia et al. 2020 j. To overcome this issue, the concept of strong DP (which requires similarity in the distributions of prediction values of each protected group) along with several measures for quantifying the discrepancy between Pr, and Py, has been considered (Jiang et al. 2020b, Chzhen et al. 2020 Silvia et al. 2020 Barata et al. 2021 A AWDP(f) := W(P Py)). ATVDP()) == TV(P)t Py),, and AKSDP(f) := KS( for Py,) are the examples of the measure for strong DP. Here, W, and KS represent the Wasserstein distance, the Total Variation, and the Saatnooorro--mminnoo distance, respectively. For given two probability distributions Q1 and Q2, the three distributional distances are defined as follows. The (I-)Wasserstein distance is defined as W(21, 22) = inf E ((..)))> y where I 7(21, Q2) is the set of joint probability distributions of marginals Q and 22- The Total Variation is defined as TV(2), 22) sup AeAl 12 (A) 22(A)), where A is the collection of measurable sets. The Kolmogorov- -oirnovv distance is defined as KS (2,, Q2) == suP Fee (2) (z)
where Fe(x)= == Q(X s x) is the cumulative distribution function of Q
Let A = A-) be a given fairness measure. A given model I is said to be group-fair (with level <) if it satisfies (s) S e. Furthermore, if A(f)= = O, we say f is perfectly group-fair (with respect to A).
2.3 Optimal transport
The concept of the Optimal Transport (OT) provides an approach for geometric comparison between two probability measures. For given two probability measures Q1 and 22, a map T from Supp( (2)) to Supp (2) is called a transport map from Q to 22 if the push-forward measure Tw Q1 is equal to Q2 (Villani 2008). Here, the fush-forward measure is defined by Ty (A) = Q (A) for any measurable set A. In other
words, T Q1 is the measure of T(X),X- ~ Q1. For given source and target distributions Q1 and 22, the OT map from Q1 to Q2 is the optimal one among all transport maps from Q1 to O2. In this context, 'optimal' means minimizing transport cost, such as Lp distance in Euclidean space.
Monge 1781 originally formulates this OT problem: for given source and target distributions 21. 22 in Rd and a cost function с (c.g., L2 distance), the OT map from Q1 to 22 is defined by the solution of minT.T a 21 Ex-2, (c(X, T(X))) If both Q1 and 22 are discrete with the same number support points, the OT map exists as one-to-one mapping. For the case when Q1 and Q2 are discrete but have different numbers of supports, Kantorovich relaxed the Monge problem by secking the optimal coupling between two distributions ions (Kantorovich) 2006). The Kantorovich problem is formulated as inf (nf.ee(())).9))) Ex Y-r (c(X, Y)), where IT(1,, 22) is the set of all joint measures of Q and Qz. Note that this formulation can be also applied to the case of Q1 and 22 with an identical number of support. See Section C of Appendix for more details about the Kantorovich problem.
Various feasible estimators for the OT map have been developed (Cuturi 2013 Genevay et al. 2016), and applied to diverse tasks such as domain adaptation (Damodaran al. 2018 Forrow al. 2019) and computer vision (Su et al. 2015 Li et al. 2015 Salimans et al. 2018), to name few.
2.4 Related works
Algorithmic fairness Group fairness is a fairness notion aimed at preventing discriminatory predictions over protected (demographic) groups divided by pre-defined sensitive attributes. Among various notions of
group fairness, Demographic Parity (DP) (Calders et al.) 2009 Feldman et al.) 2015 Agarwal et al. 2019 Jiang et al. 2020b Chzhen et al.] 2020) quantifies the statistical gap in predictions between two different protected groups. Other measures, including Equal opportunity (Eqopp) and Equalized Odds (EO), consider
groups conditioned on both the label and the sensitive attribute (Hardt et al. 2016a)). Various algorithms
have boen proposed to learn group-fair model satisfying these group fairness notions (Zafar et al.) 2017
Donini et al. 2018 Agarwal et al. 2018 Madras et al. 2018 Zafar et al.
2019
Chuang & MMouch 2021
Kim et al. 2022a).
4

---

Published in Transactions on Machine Learning Research (12/2024)
Individual fairness, initially introduced by Dwork et al. (2012): is another fairness notion based on the philosophy of treating similar individuals similarly. It. is noteworthy that Dwork et al. (2012) highlighted that focusing solely on group fairness is not always a complete answer, pointing out issues such as subset targeting and the fulf-fulii prophecy. Subsoquent researches (Yona & Rothblum 2018 Yurochkin et al.) 2020;
Yurochkin & Sun 2021: Petersen el al.) 2021; have been studied in both theories and methodologies. However, individual fairness has two bottlenecks: (i) it strongly depends on the choice of the similarity metric, which hinders its practical applicability, and (ii) by itself, it does not ensure group fairness when the distributions of protected groups differ significantly. See Section 3.3 for detailed comparison between individual fairness and our proposed framework.
Counterfactual foirness, which requires treating a counterfactual individual similarly to the original individual, has been studied by Kusner et al. (2017); Chiappa & Gillam ; yoo Kügelgen et al. (2022): Nilforoshan
ct al.] (2022). Its application, however, is limited since it requires causal models, which are difficult to obtain
only with observed data. Instead of using graphical models to define counterfactuals, this paper suggests
using& a transport map from X, to Xy having certain desirable properties. See Proposition 4.3 in Section 4.1
for the relationship between counterfactual fairness and our proposed algorithm.
On the other hand, in presence of multiple sensitive attributes, the concept of subgroup fairness can be considered (Kearns et al. 2018a b Shui et al. 2022 Mehrotra et al.] 2022 Molina & Toiseau 2022 Carvalho
et al. 2022). emphasizing the need for models that satisfy fairness for all subgroups defined over the multiple sensitive attributes. In addition, Wachter et al.] (2020); Simons et al. (2021); Mougan et al. (0024) have suggested that not only statistically equal outcome but also the notion of equal treatment, i.e., treating individuals with equal reasons, should be considered in algorithmic fairness.
Fair representation learning (FRL) FRL algorithm aims al searching a fair representation space, in the sense that the conditional distributions of the encoded representation with respect to the sensitive attribute are similar (Zemel et al.) 2013). After learning the fair reprosentation, FRL constructs a fair model by applying a supervised learning algorithm to the fair representation space. Initiated by [Ewwrds & Storkey (2016), various FRL algorithms have been developed (Madras et al., the adversarial-learning technique used in GAN [Goodfellow et al., 2014
2018 Zhang et al. 2018) motivated by
See Section 3.3 for the detailed
comparison between FRL and our proposed framework.
Applications of the OT map to algorithmic fairness Several studies, including Gordaliza et al. 2019
Jiang et al.] (2020b); ; Chzhen et al. (2020); Silvia et al. (2020) Buyl & Bie (2022) have employed the OT map for algorithmic fairness. Gordaliza et al. (019)) introduced a fair representation learning method that
aligns inputs from different protected groups using the OT map. [Tiang et al. (2020b): : Chzhen et al. (2020); Silvia et al. (2200) proposed aligning prediction scores from different protected groups using the OT map or OT-based barycenter. Buyl & Bie (2022) developed method that projects prediction scores onto fair space by optimizing the projection through minimizing the transport cost calculated on all pairs of inputs.
Most of these algorithms (e.g., Jiang et al. (0200b: Chzhen et al. 2020); Silvia et al. (2020)) ) focus on applying the OT map in the prediction space, i.e., aligning two conditional distributions Pi and Pn,- These methods fundamentally differ from our proposed approach, which focuses on applying the OT map in the input space. On the other hand, Gordaliza et al.] (2019) and our approach are particularly similar in the sense that both apply the OT map on the input. space. See the detailed comparison between Gordaliza et al. 2019 and our approach in Section 3.3
It is worth noting that our proposed algorithm becomes the first to define a group faimess measure based on the transport map in the input space and to propose reasonable choices for the transport map.
3 Learning fair model through matching
The goal of this section is to explore and specify the correspondence between group-fair models and transport maps. In Section 3.1, we show that every group-fair model has a corresponding implicit transport map in the input space that matches two individuals from different protected groups. We then introduce new fairness measure based the correspondence. In Section 3.2 we show the reverse, i.e. any given
5

---

Published in Transactions on Machine Learning Research (12/2024)
transport map be used to learn group-fair model, then present proposed algorithm for learning group-fair models under a fairness constraint based on given transport map.
3.1 Matched Demographic Parity (MDP)
Proposition 3.1 below shows that for a given perfectly group-fair model f (i.c., Ps = = or equivalently A = =0), there exists an corresponding transport map the input space that matches two individuals from different protected groups. Its proof is in Section A of Appendix. Throughout this section, we assume a condition (C): 8 0, 1, absolutely continuous with respect to the Lebesgue mcasure. This regularity condition is assumed to simplify the discussion, since it guarantecs the existence of transport maps between two distributions. See Proposition A.1 in Section A of Appendix, which presents similar result for the case where P,, = 0, are discrete. Let T be the set of all transport maps from P, to Par.
Proposition 3.1 (Fair model = Transport map: perfect fairness casc). For any perfectly group-fair model i.e., P/o p1, there erists transporl map T, T..raans salisfying I (X,s)= (T.((),)),c)
The key implication of this mathematical proposition is that all perfectly group-fair models are not the same and the differences can be identified by their corresponding transport maps. We similarly define a transport map corresponding to a given not-perfectly group-fair model (i.e., A >> 0), by using novel fairness measure termed Matched Demographic Parity (MDP) defined as below.
Definition 3.2 (Matched Demographic Parity). For given model f f and transport map T, trams the measure for MDP is defined as
AMDP(S,T)) == -
The idea behind MDP is that two individuals from different protected groups are matched by T., and AMDP(f. T.) quantifies the similarity between the predictions of these two matched individuals. Subsequently, Theorem 3.3 below presents relaxed version of Proposition 3.T showing that any group-fair model f has a transport map T, such that AMDP(f, T,) small. Refer Scction A of Appendix for the proof of Theorem 3.3 and see Figure 1 for the illustration of MDP.
Theorem 3.3 (Fair model = Transport map: relaxed fairness case). Fix a fairness level 2 O. For any given group-faär model f such that ATVDP(f) S 6, there crists transport map T, T T-tras satisfying AMDP(J, T.) 25.
Matched Demographic Parity
Female
Male
Treat female male similarly!
Transport map
Figure 1: Simplified illustration of MDP. Once two individuals A and B are matched (+),, a model treats the pair of matched individuals A and B similarly (as well as all the other pairs). This implicit mechanism contributes to making the model fair.
We define the fair matching function for a given f as the transport map that altains the infimum of equation [ as formulated in Definition 3.4 below. The term 'farr' is used because MDP minimized by this transport map. Through investigating the fair matching function, we can understand the mechanism behind how griup-fair model behaves. That is, the fair matching function specifically reveals which pairs of individuals from two protected groups are treated similarly by the given group-fair model.

---

Published in Transactions on Machine Learning Research (12/2024)
Definition 3.4 (Fair matching function of f). For given f, denote Tς := arg w ET AMDP(f, T&), SE 10, For == arg min, (0.1) AMDP(f. T(), the fair matching function of f is defined as T := T
Note that the existence of this fair matching function is guaranteed by Brenier's theorem (Villani 2008
Hütter & Rigollet 2021). To be specific, since Ps. {0,1] are absolutely contimuous by (C), and the cost function in MDP, i.e, c(x,y) = (f(x,)) s) - f(y, 8'),, is lower semi-continuous and bounded from below, the minimizer of AM uniquely exists.
Practical computation of the fair matching function In practice, estimate the fair matching lunction using the observed data = ((x, (e,,,,,)))) 8t) Let =o= (x; 8, = 0} (x, (
Tim1 and Dj (xy= 8y f-1 be the set of inputs given the sensitive attribute, where My + We here introduce practical methods for computing the fair matching function in Definition 3.4 by considering two cases:
1) = (xx(())) (x()) ya
1. Case of no n2: When the sizes of two protected groups equal (ng- n1), we easily find the fair matching function by quantile matching. We first sort the scores in [fx(x))xED, for each group s {0, 1}. Then, we match the individuals having the same rank (i.e., quantile) in each set, thereby obtaining the fair matching function of f. This straightforward procedure is theoretically guaranteed by the definition of 1-Wasserstein distance, which calculated by quantile matching (Rachev & Rüschendorff] 1998 Chzhen et al., 2020; Jiang et al. 2020b). We formally present this procedure in Proposition 3.5 below. Its proof is provided in Section A of Appendix. Let F, represents the cumulative distribution function of fx(x). E D.. For technical simplicity, we assume that there is no tie in
Proposition 3.5. Let T be the fair malching funclion of J on Do and Dj (where the empirical distributions with respect to Do and Dj are used in Definition 3.4). Then, the matched individual (x) of any x E DD is obtained by T (x) fz o F o F3 o fa()..
fz
2. Case of no 4 n1: When the sizes differ, we can consider a stochastic fair matching function (a stochastic transport map that minimizes AMDP), which matches individuals with probability, not deterministically. In fact, a stochastic transport map corresponds to a joint distribution between two protected groups, i.c., a stochastic transport map can be defined by a joint distribution, as follows:
Denote Q as a joint distribution between Do and D1, and let Xg and X₃ be the random variables following the empirical distributions on Do and D1, respectively. For given joint distribution Q, the stochastic transport map T, (corresponding to the Q) is defined by Tx())") =x with probability
(o')
Q(X,= = x x(,= X. x(6")) Once we find the stochastic fair matching function, i.e., the stochastic transport map (joint distribution Q) minimizing AMDP(J, Q) = E(x,.x., Bxxx.x))-o (X), 0) f(X,, 1)), we can compute its transport cost as Xxx,,X,)--|IXx, xX Note that the minimization of AMDP with respect to the stochastic transport map is technically equivalent to solving the Kantorovich problem, which can be easily solved by the use of linear programming. See Section A and Section C for more details about the stochastic transport map and the Kantorovich problem, respectively.
Alternatively, in practice, we can apply a mini-batch sampling tcchnique. We first sample two random mini-batches D. Do and D, c D2 with identical size m. Then, we follow the process in '(1) Case of no n1² above. The transport cost of the fair matching function can be then estimated by the average transport costs computed on many random mini-batchos. See Remark A.2 in Section A for the statistical validity of this mini-batch technique.
Furthermore, Remark 3.6 below explains how the transport cost can serve as metric for assessing the desirability of given group-fair models.
Remark 3.6 (Usage of the transport cost of the fair matching function). Purthermore, the transport cost of the fair matching function can serve as a measure to assess whether a given group-fair model is desirable. For ezample, when choosing a model between two group-fair models with similar levels of group fairness or or/and prediction accuracies, the model with the lower transport cost would be preferred. In Section 5.3.2 we compare transport costs of fair matching functions for two different group-fair models, using the méni-batch technique.
7

---

Published in Transactions on Machine Learning Research (12/2024)
3.2
Fairness Through Matching (FTM): learning group- fair model with transport map
The goal of this section is to formulate our proposed algorithm. Before introducing it, we provide theoretical support, which shows that a group-fair model can be constructed by MDP using any transport map. Theorem 3.7 below, which is the reverse of Thcorem 3.3 shows that any transport map in the input space can construct a group-fair model. Precisely, for a given transport map, if a model provides similar predictions for two individuals who are matched by the transport map, then it is group-fair. The proof is given in Section of Appendix.
Theorem 3.7 (Transport map = Group-fair model). For a given T, E T if A/ ó then we have AWDP(f) s and ADP(f) S.
Again, it is remarkable that griup-fair model and its corresponding transport map are closely related, Le., every group-fair model has its corresponding implicit transport map, and vice versa. This finding can be mathematically expressed as follows. Let A be a given (existing) fairness measure, and define Fa == { E F A(f) & 8) as the set of group-fair models of level (with respect to A). == (f F AMDP(S, T.) s 6). Then, following from Theorem 3.3 and 3.7 we conclude that the three measures (i.e., TVDP, WDP, and MDP) are closely related: FATVDP ()) S UT, (f: AMDP(F, T.) S 28) & F26D
Similarly, for MDP, define F FAMDP(T,
As discussed in Section as well as several previous works (e.g., Dwork et al. 2012 ), there exist group-fair models having undesirable properties such as subset. largeting or self-fulflling prophecy. The advantage of MDP is that we can screen out such undesirable group-fair models during the learning phase, to consider desirable group fair models only. And, using MDP achieves this goal by considering group-fair models whose transport maps have low Transport costs. That is, can search for group-fair model only on UT,eTpood trans (f AMDP(J,T.) T.) 25); where Tgood trans _ T.tras is set of specified 'good' transport maps. See Section 4 for such good transport maps that specifically propose. It is worth noting that such screening would be challenging with existing group-fair measures.
FTM algorithm Based Theorem 3.7 we develop learning algorithm named Fairness Through Matching (FTM), which learns group-fair model subject to MDP being small with given transport map. FTTM consists of two steps. First, we select a (good) transport map. Then, we learn a model under the MDP constraint with the selected transport map. The precise objective of FTM is formulated below.
Suppose transport map T, selected (see Section for the proposed transport maps). FTM solves the following objective for given loss function (e.g., cross-entropy) and a pre-defined fairness level ó 820 0:
FFM((T.) = arg min BI(Y, (() subject to min A se(0,1)
(2)
fef
Unless there is any confusion, write FFTM instead of (TTM(T,) for simplicity. By Theorem 3.7 it is clear that FFTM is fair (i.c., A estimate FFTM with observed data D using mini-batch technique along with a stochastic gradient descent based algorithm (see Section for details).
s 8) for any transport map T,- In practice, we
3.3 Conceptual comparison of existing approaches and FTM
Individual fairness FTM and individual fairness are similar in the sense that they try to treat similar individuals similarly. A difference is that FTM aims to treat. two individuals from different protected groups similarly, while the individual fairness tries to treat similar individuals similarly regardless of sensitive attribute (even when it is unknown). That is, similar individuals in FTM could be dissimilar in view of individual fairness, especially when the two protected groups are significantly different.
On the other hand, a limitation of individual fairness is that group fairness is not guaranteed. FTM can be also understood as a tool to address this limitation by finding models with higher individual fairness among frirp-fair models. Empirical results support this conjecture that FTM improves individual fairness compared to baseline methods for group fairness (see Table in Section 5.4.2
8

---

Published in Transactions on Machine Learning Research (12/2024)
Fair representation learning FTM and FRL (Fair Representation Learning) are similar in the sense that they align two conditional distributions. However, the role of the alignment in FTM and FRI are different: FTM builds a prediction model in the original input space, using transport map in the MDP constraint only. In contrast, FRL methods first learn fair representation by aligning the conditional distributions of representation, and then use the learned fair representation as input.
Furthermore, FTM and FRL methods are motivated by fundamentally different objectives. FTMM is designed to learn group-fair models with desirable properties (c.g., higher fairness subsets), whereas FRL methods aim to obtain fair representations which can be used for downstream tasks requiring fairness. The FRL approach proposed by Gordaliza et al. (2019) is particularly similar to FTM, as both apply the OT map on the input space. However, unlike FTM, it trains a prediction model on the (pre-trained) fair representation space derived from the OT map. On the contrary, FTM builds the prediction model on the original imput space and utilizes the OT map solely within the fairness constraint. As a result, the prediction model of FTM is not tied to the OT map, making it more flexible and leading to improved prodiction accuracy. Empirical evidence supporting this claim is provided in Table 5 in Section 5.4.3 which demonstrates the superior performance of FTM compared to several FRL methods, including Gordaliza et al. 2019
4 Empirical algorithm with transport map selection
The implication of Theorems 3.3 and 3.7 is that any transport map corresponds to a group-fair model.
However, an improperly chosen transport map can result in undesirable outcomes, even if group fairness is satisfied, as shown in Theorem 3.7
(see Section B of Appendix for an example of a problematic group-fair model due to an unreasonable transport map). Thus, selecting an appropriate transport map crucial when using FTMM, which is the primary focus of this section.
Specifically, we propose two favorable choices of the transport map T, used in FTM. In Section we suggest using the OT map in the input space X, resulting in a group-fair model with a higher fairness level on subsets. In Section 4.2 we propose using the OT map in the product space X x V, to improve prediction performance and the level of equalized odds, when compared to the OT map in the input space.
4.1 OT map on X
For given T2 T.traus the transport cost (on X) of T, is defined by - First, we propose using the OT map between the two input spaces, which is the minimizer of the transport cost on X among all transport maps. From now on, we call this OT map on X' as the marginal OT map.
In this section, we explore a benefit of using the marginal OT map (i.e., low transport cost) by showing a theoretical relationship between the transport cost and fairness on subsets. Many undesirable behaviors of group- fair models have been recognized and discussed (Doork et al. 2012: Kearns et al. 2018a Wachter
et al. 2020 Mougan et al., 2024). Subsel fairness, which a similar concept to subset largeting in Dwork et al. 2012), , is one of such undesirable behaviors. We say that a group-fair model is subset-unfair if it is not group-fair against a certain subset (e.g., aged over 60s) even if it is group-fair overall. The definition of subset fairness can be formulated as follows.
Definition 4.1 (Subset fairness). Let A be a subset of X. The level of subset fairness over A is defined as ADP == [B(S(X 0, x A) BB(( X A)].
Intuitively, we expect that a group-fair model with a low transport cost would exhibit a high level of subset fairness. This is because the chance of two matched individuals (from different protected groups) belonging to the same subset A tends to be higher when the transport cost is smaller. Theorem 4.2 theoretically supports this conjecture, whose proof is provided in Section of Appendix.
Theorem 4.2 (Low transport cost benefits subset fairness). Suppose F is the collection of L-Lipschit functions. Let A be a given subset in X. Then, for all satisfying AMDP(F. T!) s 8, we have
ADP & L (E. Te (x)) + TV(Po.A, + Us,
2A function g X + R is L-Lipschitz if lg(x1) g(xx)) s L|xi - x2I| for all X1, X2,2 x.
9

---

Published in Transactions on Machine Learning Research (12/2024)
where Pa,A is the distribution of X|S s, x,X E A, and U > 0 is a constant only depending A and Ps, 0,
The first term of RHS, L (E. cost helps improve the level of subset fairness. The uncontrollable term AV certain subsets. For example, for disjoint sets A Ax of A, suppose that P. is a mixture of uniform distribution given as P.(+)= = 1 P.ul(. E A&) with Psk 2 0 and Ek=1 = 1 (e.g,, the histogram). Then, TV(Po.A,PL, becomes zero for all Ak, k E [K]. The last term U6 becomes small when ō is small.
implies that using a transport map with small transport
can be small for
Connection to counterfactual fairness The concept of FTM is also related to counterfactual fairness Kusner et al.) 2017). In specific, under a simple Structural Causal Model (SCM), the imput transported by the marginal OT map is equivalent to the counterfactual input. Particularly, let X, X = for s (0,1) and consider an SCM
X, = [4x AXa Eg
(4)
for given A e Rdxdd Me e Rd with Gaussian random noise 6, ~ NO, D) of a diagonal matrix D idddd and variance scaler o2. An example DAG (Directod Acyclic Graph) for equation is Figure 2
Let. X2 be a realization of X, and assume (La-A) A) has its inverse B (Ia-A)-1, where Ia Raddd is the identity matrix. Then, its counterfactual becomes XCP =Bu o. La(x, Bu,) (proved with Proposition 4.3
6 ~ (N(N0,,
together in Section [A] of Appendix). On the other hand, by Lemma A.3 in
Section A of Appendix, the image of x, by the marginal OT map is given as x -Bp + W (x, (x,) for some W, E Radd, Proposition below 4.3
S
X
shows xCF =x;-, OT whose proof is deferred to Section A of Appendix.
Figure An example DAG of the SCM in equation (4
Proposition 4.3 (Counterfactual fairness and the marginal OT map). For all A having (Ia- A)-1, W. becomes L That is, xCF =x00"
We further present an example in Section of of Appendix showing that a transport map with high transport cost can lead to problematic griur-fair model. Moreover, Scction 5.2.2 empirically shows that group-fair models learned by FTM with the marginal OT map altain higher fairness levels on various subsets that are not explicitly considered in the training phase, compared to group-fair models learned by existing algorithms.
Estimation of the marginal OT map To estimate the marginal OT map in practice we sample two random mini-batches Do {x, == c Do and D, (x, y
( Di with an identical size S n. For given two empirical distributions on Do and D1, the cost matrix between the two is defined by C== [c[[c]] e R where C.j | -x,") 1 The optimal coupling is then defined by the matrix I = [x]]] R which solves
(0)
the following objective:
m Σ
min Coll
min oo s.t. HH
Yh Σ
The = Vi.t 2 O. 1-1 J-1
(5)
Due to the oqual sample sizes of De, 8 (0, the optimal coupling has only one non-zero (positive) entry for each row and column (i.c., I is a doubly stochastic matrix scaled by a constant factor of 1/m). Then, the marginal OT map for each ( Do is defined by To,6(x()) =x(") 11 > 0) and T Fi is defined similarly.
4.2 OT map on x
One might argue that using the marginal OT map could degrade the prediction performance much, since the matchings done by the marginal OT map do not consider the similarity in Y. As remedy for this issue, we consider incorporating the label Y into the cost matrix calculation to avoid substantia ial degradation in prediction performance.
For this purpose, we define new cost function on Xxx V. Let a be a given positive constant. The new cost function ca d Idd+1 R. is defined by: e c((()) (x2,)))()2)2)))))) v2)) == ||x x2| 2 alyi y2l, for given
10

---

Published in Transactions on Machine Learning Research (12/2024)
X1, X2 Rd and y1. E R. Among all transport maps from the distribution of X, Y|S to the distribution of X.Y|S s', we find the OT map that minimizes this modified transport cost on X' x ) (i.e., the expected value of c², where the expectation is taken over the distribution of X, = s). We call this OT map on X'x y as the joint OT map.
Using this joint OT map with a positive a can contribute to the improvement in prediction accuracy compared to the marginal OT map. This is because, while the marginal OT map does not care labels when matching individuals, the joint OT map tends to match individuals with the same label much as possible when is sufficienlly large.
Not only the prediction accuracy, but also the level of equalized odds (i.e., demographic parities on the subsets consisting of those with Y= 0 and == 1, respectively) can be improved. This is because, FTM with the joint OT map tends to predict similarly for individuals with the same labels but from different protected groups, which directly aligns with the concept of equalizod odds. We can thcoretically prove this claim wol., (l((X,,) 8) (X),
as follows. First, we decompose AMDP(S, T.) as AMDP(J,
WI,,, (If(X, s) - (XT,,(X,,s) +') 1), where wy := P(Y = y/S s).y e {0, 13. Note that by the definition of the joint OT map, we have for almost all x with respect to the distribution of X|S = 8, P(Y y/X = x, S = 8) P(Y= = x|x= T, (x), S s¹) for all y {0, 1} when + oo. Then, we have that C max (APR(()) AFPR(/)) we (TP(())) + wi AFPR(() 5 AMDP( T.), where C min Wo; w1 is constant. Here, ATPR()) 1,5
0) =) 1)I are the smooth versions of ATPR(J) and AFPR(J), respectively. Hence, we can conclude that using the joint OT map with large can improve EO, compared to the marginal OT map.
B(f((X)) -) 1, 1)] and AFPR(f)
(X)()X((( = 0, B(fi (X))Y= 0,
We empirically confirm this claim in Section 5.3 by showing that group-fair models learned by FTM with the joint OT map offer improved prediction accuracies as well as improved levels of equalized odds, when compared to FTM with the marginal OT map.
Estimation of the joint OT map We apply a similar technique to the marginal OT map case, starting (1) by sampling two random mini-batches Do and D1 with an identical size m S n. Let y (0) and f) be the corresponding labels x (0) E DD and x5" E D1, respectively. For a given a 2 0, we modify the cost matrix as
follows: C : [c],g] ε R. where & = |lx!") x 11 alu;") (0) -,,", Note that when a = O, this problem becomes equivalent to the case of the marginal Of map in equation 5 We similarly calculate the optimal
coupling the matrix by solving the following objective:
1 N.. 2 0. m
min | o F T
min Ny 75.
N. s.t. Σ
M.j
Σ j-1
(6)
Then, the joint OT map for each x; (0) e Do is defined by To (x,( =x, -x())(( 1(n,5 > 0) and T1 defined similarly.
4.3 Empirical algorithm for FTM
In practice, we learn f with a stochastic gradient descent algorithm. For each update, calculate the expectod loss, we sample a random mini-batch D' c D of size n' n. Then, we update the solution using the gradient of the following objective function
1 C(f)
Σ 1(y,, (x,, s:)) + Σ [(((") 100-f(T,ppp (x()) m (..
(7)
n' (x..Wiss))DD
for any S {0, 1), where A >>0 O is the Lagrange multiplier and T + is a pre-specified transport map from D. to Dyr (e.g., the marginal OT map from Section 4.1 or the joint OT map from Section 4.2
11

---

Published in Transactions on Machine Learning Research (12/2024)
5 Experiments
This section presents our experimental results, showing that FTM with the proposed transport maps in empirically works well to learn group-fair models. The key findings throughout this section are summarized as follows.
Section f
FTM with the marginal OT map successfully learns group-fair models that exhibit (i) competitive prediction performance (Section 5.2.1) and (ii) higher levels of subset fairness (Section 5.2.2 when compared to other group-fair models learned by existing baseline algorithms. Beyond subset fairness, we further evaluate the self-fulflling prophecy (Dwork et al. 2012) as an additional benefit of low transport cost (see Table 10 and I1 in Section of Appendix).
FTM with the joint OT map has the ability learn group-fair models with improved prediction performance as well as improved levels of equalized odds, when compared to FTM with the marginal OT map (Section 5.3
5.1 Settings
Datasets We use four real-world benchmark tabular datasets in our experiments: ADULT (Dua & Graff 2017), GERMAN (Dua & Graffi 2017), DUTCH (Van der Laan 2001h, and BANK (Moro al. 2014). The basic information about these datasets is provided in Table 6 in Section D.I of Appendix. We randomly partition each dataset into training and test datasets with the 8:2 ratio. For each split, we learn models using the training dataset and evaluate the models on the test dataset. This process is repeated 5 times, and the average performance on the test datasets is reported.
Baseline algorithms and implementation details For the baseline algorithms, we consider three most popular state-of-the-art methods: Reduction AAgaraal et al. 2018 Reg (minimizing cross-entropy + AADP" which is considered in Donini et al.] (2018); Chuang & Mroueh (2021)), and Adv (adversarial learning for ensuring that the model's predictions are independent of sensitive attributes, which is proposed by [Zhan et al. (2018)). Additionally, we consider the unfair baseline (abbr. Unfair), the ERM model trained without. any fairness regularization or constraint. For the measure of prediction performance, we use the classification accuracy (abbr. Acc). For fairness measures, consider ADP, ADP and AWDP, which are defined in Section 2.2
For all algorithms, we employ MLP networks with ReLU activation and two hidden layers, where the hidden size is equal to the input dimension. We run all algorithms for 200 epochs and report their final performances on the test dataset. The Adam optimizer (Kingma & Ba 2014] with the initial learning rate of 0.001 used. To obtain the OT map for cach mini-batch, we solve the lincar program by using the POT library (Flamary le al. 2021). We utilize several Intel Xeon Silver 4410Y CPU cores and RTX 3090 GPU processors. More implementation details with Pytorch-style esuedo-code are provided in Section D.2 and D.3 of Appendix.
Adult
German
Dutch
Bank
Unfair
Unfair
Unfair
Unfair
Reduction
Reduction
Reduction Reg
Reduction
Reg
Reg
Reg
Adv
Adv
Adl
Adv
FTM/
500
65%
AWDP
xitk
041
AWDP
AWOP
SWDP
Figure 3: Cairness-predictts trade-offs: AWDP vs. Acc on (Left to right) ADULT, GERMAN, DUTCH, BANK datasets. Similar results are observed for ADP and ADP in Figure & in Section E of Appendix.
5.2 FTM with the marginal OT map
This section presents the performance of FTM with the marginal OT map, in terms of (i) fairness-predictins trade-off and (ii) improvement in subset fairness.
12

---

Published in Transactions on Machine Learning Research (12/2024)
5.2.1 Fairmess- prreessspreiitionn trade-off
In this section, we empirically verify that learned models by FTM successfully achieves group fairness (demographic parity). Figure 3 below shows that FTM successfully learns group-fair models for various fairness levels.
Another main implication is that using the marginal OT map does not hamper prediction performance much. Figure 3 supports this assertion in terms of fairness-prediction trade-off, that is, FTM is competitive with the three baselines. In most datasets, the performance of FTM is not significantly worse than that of the top-performing algorithm (i.e., Reduction). Notably, on GERMAN dataset, FTM performs the best, whereas Reduction fails to learn group-fair models with fairness level under 0.06. Additionally, FTM mostly outperforms the other two baseline algorithms, Reg and Adv. Hence, we can conclude that FTM also a promising algorithm for achieving group fairness.
5.2.2 Improvement in subset fairness
This section highlights the key advantages of using the marginal OT map in termss of subset fairness, which is thcoretically supported by Theorem 4.2 We examine two scenarios for the subset in Definition 4.1 (1) random subsets and (2) subsets defined by specific input variables.
Random subsets First, we generate a random subset Daub from the test data defined as Duub (i: x; 0}, using random vector v drawn from the uniform distribution on [-1,1] Then, we calculate ADP on Duub Figure 4 presents boxplots of the ADP values calculated 1,000 randomly generated Duub Outliers in the boxplots (points in red boxcs) represent the example instances of subset unfairness. For fair comparison, evaluate under given ADP for each dataset: 0.06 for ADULT, 0.01 for GERMAN, 0.07 for DUTCH, and 0.04 for BANK. Notably, FTM consistently has the fewest outliers than all the baselines, indicating that FTM achicves higher fairness on random subsets.
Adult
German
Dutch
Bank
0J35 on Dan
ADPs on Duo
ADPs on Das
AJPS
8651 (TOO
Reg
Filer
Reauctinn
Rég
FTM
Redurton
Ad
(8,0200
Redurtin
Rng
(2.111)
Figure 4: Fairness on random subsets: Boxplots of the levels of ADP on 1,000 randomly generated subsets Daub of test datasets. (Left to right) ADULT, GERMAN, DUTCH and BANK. The values presented under the algorithm name (e.g., 0.0151 for FTM in GeRMAN) are the standard deviations.
Subsets defined by specific input variables Second, we focus on subsets defined by a specific input variable. For this scenario, we construct two subsets by binarizing a specific input variable using median value. Note that learn models considering only gender the sensitive attribute. Tableepreeeett the fairness levels (with respect to gender) in the two subsets of the learned models. We consider GERMAN and DUTCH datasets for this analysis. For GERMAN dataset, the two subsets are defined by {x of high age) and (x of low age). For DUTCH dataset, the two subsets are defined by {x who is married) and (x who is not married]. The results highlight the superiority of FTM in achieving higher fairness in these specific subsets.
5.3
FTM with the joint OT map
This section shows the effect of using the joint OT map, in terms of improvement in (i) prediction accuracy, level of equalized odds (Section 5.3.1) and (ii) the transport cost (Section 5.3.2 We use ADULT dataset for this analysis. For FTM with the joint OT map, we fix = 100, because the results with a > 100 are almost. (0) (1) fully
identical to those with 100. In other words, 100 is the minimum value for where alv; ツ dominates the transport cost. |x (1)
13

---

Published in Transactions on Machine Learning Research (12/2024)
Table 1: Fairness levels on the subsets defined by specific input variables: Bold faced ones highlight the best results, and underlined ones are the second best ones. Standard errors are provided in Table X and g in Section of Appendix. (Left) The subsets are defined by the input variable 'age' on GERMAN dataset under given ADP- 0.045. (Right) The subscts are defined by the input variable 'marital status' on DUTCH dataset under a given ADP- 0.120.
GERMAN
DUTCH
Measure
Subset
Reduction
Reg
Adv
FTM
Subset
Reduction
Reg
Adv
FTM
ADP
0.073
0,077
0.048
0.045
0.258
0.372
0.237
0.204
ADP
High age
0.049
0.029
0.028
0.026
Married
0.182
0.164
0.187
0.152
AWDP
0.053
0.039
0.042
0.038
0.183
0.172
0.193
0.152
ADP
0,118
0,116
0.122
0.077
0.061
0.131
0.095
0.068
ADP AWDP
Low age
0.047
0.050
0.053
0.047
Not married
0.045
0.062
0.098
0.036
0.058
0.059
0.061
0.054
0.045
0.072
0.098
0.045
5.3.1 Improvement in prediction accuracy and equalized odds
Table 2 shows that FTM with the joint OT map can provide higher prodiction performance than FTM with the marginal OT map in certain scenarios, where more accurate group-fair models than FTM with the marginal OT map ist (e.g., ADP 0.06 in Figure B.. Fur- thermore, we observe that the level of equalized odds can also be improved in these scenarios. To assess the level of equalized odds, we basically use the dif- ferences in TPR and FPR, defined as ATPR JP(Cj, (X)
Table 2: Comparison between (i) the marginal OT map and (ii)
the joint OT map in terms of prediction accuracy and level of equalized odds, with the two fixed fairness level ADPs at 0.033
and 0.054.
ADP 0.033
Acc (t)
ATPR (1)
AFPR (L)
ΔЕO (4)
Marginal OT map Joint OT map
0.806
0.052
0.012
0.032
0.810
0.043
0.013
0.028
ADP 0.054
Acc (t)
ATPR (1)
AFPR (1)
ΔEO (1)
Marginal OT map Joint OT map
0.826 0.830
0.031
0.023
0.027
0.021
0.019
0.020
1|S O,Y
1) P(C,, (X) 118 = 1,Y 1)] and
AFPR == IP(C,, (X) - 1|5 = 0,Y 0) - (X) 1|S = 1,Y 0)), respectively. Note that ATPR
is also a measure for equal opportunity. We additionally use an overall measure defined as AEO :=
1 1E iP (X)= = 1|5 = 0, Y y) ) (CC 1|$ = 1, Y =y],, which is also considered in previous works
Donini et al. 2018
Chuang & Mroueh 2021
Adult
German
Dutch
Bank
ACC
Unfer Recuction
ACC
Unfur
Jriei
Uniar
Reduction
Sedluttcce
Recluttion
Rog
Rog
Tog.
Reg
ASV
(jinn)
(4kec)
g
700 261% vel cen
+0
720
720
ADP
ADP
ADP
ADP
Figure 5: Pairness-predietiis trade-offs: ADP vs. Acc on (Left to right) ADULT, GERMAN, DUTCH, BANk datasets. FTM (joint) FTM with the joint OT map. FTM (marginal) = FTM with the marginal OT map.
In addition, we compare FTM using the marginal OT map, FTM using the joint OT map, and other baseline methods, in terms of the overall fairness- prediction trade-off. As shown in Figure 5 FTM with the joint OT map achieves performance comparable to the best-performing bascline. This result suggests that using FTM with an appropriate transport map can empirically achieve the optimal trade-off, highlighting the flexibility of FTM in controlling the fairness- pirness-prediction trade-off, by selecting an appropriate transport map.
fairness-prediction
14

---

Published in Transactions on Machine Learning Research (12/2024)
5.3.2 Increase in transport cost
On the other hand, using the joint OT map can result in a higher transport cost (of the fair matching function) compared to the marginal OT map. To compute the transport cost the fair matching function, we follow the mini-batch technique introduced in Section 3.1 We use 100 random mini-batches with batch size of m 1024. The left panel of Figure G illustrates that increasing a can improve prodiction accuracy, though this improvement comes with a higher transport cost, especially when group-fair models more accurate than FTM with the marginal OT map exist. That is, at ADP 0.025, point where group-fair model more accurate than FTM with the marginal OT map exists (e.g., Reduction in Figure 3), both accuracy and transport cost. increase, as a increases.
In contrast, the right panel of Figure @ shows that increasing a does not significantly improve prediction accuracy while still incurring a higher transport cost, when FTM with the marginal OT map is competitive with other group-fair models in terms of accuracy. That is, at ADP 0.073, point where the accuracy of FTM with the marginal OT map is similar to that of other group-fair models, increasing or does not. yield notably beneficial results.
Overall, FTM with the joint OT map using an ap- propriately tuned could be a desirable solution, especially when seeking for a group-fair model that is more accurate than a group-fair model learned by FTM with the marginal OT map. However, tun- ing a can be challenging, and compromising subset fairness would be generally not advisable. Addition- ally, as discussed in Section 5.2.1, using the marginal OT map is also competitive with other baselines in torms of prediction accuracy. Therefore, we basically recommend using the marginal OT map for FTM, while considering the joint OT map particularly useful when the prediction accuracy of group-fair model learned by FTM with the marginal OT map is suboptimal.
ADP 0.025
ADP 0.073
6411
640
ACC
067-
001
007-
Transport Cost
Figure 6: Transport cost-prediction tradc-offs: Trans- port cost of the fair matching function vs. Acc of FTM with the joint OT map of a E {0, 1,5, 10, 50, 100} on ADULT dataset.
5.4 Further comparisons
To further assess the validity of FTM from various perspectives, we consider three scenarios for empirical comparison with baseline algorithms: (i) FTM is robust under a group imbalance setting (i.e., P(S= << improve the level of individual fairness, compared to existing group fairness algorithms. (iii) FTM outperforms several existing FRL methods, by achieving higher prediction accuracy for given level of fairness. For simplicity, we employ the marginal OT map in this section for these analyses.
P(S 1))- (ii) FTM
5.4.1 Comparison of stability under imbalance setting
We evaluate the stability of FTM and existing algorithms under an imbalanced scenario for the sensitive attribute. For this purpose, after training/tess data split, we construct an imbalanced training datasct with a 5:95 ratio (5% for 0 and 95% for 1) by randomly sampling data from Do and fully using Di. Then, measure the performances dataset. We use ADULT dataset for this analysis. For fixed fairness level of ADP 0.064, we calculate the corresponding prediction accuracy. This procedure is repeated five times, and we calculate the average as well as the standard deviation.
test dataset, where the models are learned on this imbalanced training
In Table 3 we present the average, standard deviation, and coefficient of variation (standard deviation * average) for each algorithm. The results indicate that FTM offers comparable stability the baselines, showing that FTM is not particularly unstable under this group imbalance setting.
15

---

Published in Transactions on Machine Learning Research (12/2024)
Table 3: Stability under imbalance setting: For a fixed fairness level ADP a 0.064, average (Avg), standard deviation (Std), and coefficient variation (CV) of the prediction accuracy (Acc) over five random training imbalanced datasets are provided.
Measure
Reduction
Reg
Adv
FTM
Avg
0.835
0.836
0.819
0.827
Std
0.003
0.003
0.021
0.002
CV
0.004
0.004
0.026
0.002
Table 4: Comparison in view of individual fairness: Given a fixed ADP, the level of individual fairness (i.e., Con) and corresponding Acc are provided. The bold faced values are the best values Con.
(Acc)
Dataset (ADP)
Reduction
Reg
Adv
FTM
Anurr (* 0.08)
0.915 (0.839)
0.902 (0.802)
0.899 (0.829)
0.935 (0.838)
GERMAN (s 0.06)
0.950 (0.743)
0.932 (0.745)
0.944 (0.672)
0.965 (0.744)
Durca (w 0.17)
0.952 (0.824)
0.914 (0.816)
0.921 (0.778)
0.980 (0.824)
BaNk (= 0.04) 0.927 (0.885) 0.978 (0.885) 0.911 (0.884)
0.972 (0.885)
5.4.2 Comparison in view of individual fairness
As discussed in Section 3.3 FTM is conceptually similar to the individual fairness, here compare FTM to baseline algorithms for group fairness, in view of individual fairness. For the measure of individual fairness, we use the consistency (Con) from Yurochkin et al. (2020p: Yurochkin & Sun (2021). which is the ratio of consistently predicted labels when we only flip the sensitive variable among the input variables. Table 4
presents the results, showing that FTM consistently achieves higher individual fairness than baselines.
5.4.3 Comparison with FRL methods
Table 5: Comparison between FTM and FRL methods: Given fixed ADP, the prediction accuracy (Acc) is provided. The bold faced values are the best values of Acc.
Acc Gordaliza et al.
Dataset (ADP)
LAFTR
sIPM-LFR
2019
FTM v
ADULT (* 0.06)
0.815
0.835
GERMAN (* 0.04)
0.721
0.741
0.728
0.743
DurcH (s 0.15)
0.810
0.813
0.811
0.820
BANK (+ 0.02)
0.877
0.878
0.876
0.878
In this section, we experimentally compare FTM with several existing FRI methods. The baseline FRL methods include three approaches: two adversarial tearning-based FRL mothods, LAFTR (Madras al. 2018 and sIPM-LFR (Kim al., 2022a), well as the FRL method proposed by Gordaliza al. (2019), which is particularly similar to FTM in that both utilize the OT map for aligning distributions. Note that in FRL, fair representations are first obtained (via barycentric mapping for Gordaliza et al. (2019) and adversarial learning for LAFTR and sIPM-LFR), and then we learn a prediction model on the fair representation space.
The results are presented Table 5 showing the superior prediction performance FTM compared to the bascline FRL methods. This outperformance of FTM due to the fact that FRL methods are pro-processing approaches (i.e., using fair representation as new input feature for the prediction model), whereas FTM is in-processing approach.
16

---

Published in Transactions on Machine Learning Research (12/2024)
6 Conclusion and discussion
In this paper, we have discussed the existence of implicit transport maps corresponding to each group-fair model. Specifically, we have introduced a novel group fairness measure named MDP. Building upon MDP, we propose a novel algorithm, FTM, designed for learning group-fair models with high levels of subset, fairness. Experimental results demonstrate that FTM with the marginal OT map effectively produces group-fair models with improved levels of subset fairness on various subsets compared to bascline models, while maintaining reasonable prediction performance. Moreover, we have proposed use the joint OT map to improve the prediction accuracy and equalized odds, compared to the marginal OT map.
We suggest several promising topics for future research: (1) Expanding FTM to incorporate other fairness notions would be valuable avenue for future work. For example, while this paper has focused DP (demographic parity) for simplicity and clarity, but applying FTM to Eqopp (oqual opportunity) would be straightforward by restricting the calculation of MDP instances where Y 1. (2) Exploring scenarios with multiple sensitive attributes, a topic frequently studied in group fairness research, is another valuable direction. Such cases require matching individuals from more than two protected groups, which would be challenging and is therefore left for future work. (3) There may be other transport maps that yield different types of group-fair models, while this paper has only considered two transport maps. Exploring other useful transport maps would yield interesting insights and applications.
Broader Impact Statement
The broad goal of this study is to caution users of fair AI models such social planners and courts against focusing solely group fairness without accounting for the risks of potential discrimination, such subsct fairness. Additionally, our study aims to equip them with tools to address these aspocts. Even though our study is rather technical, we believe that it can provide a new perspective on algorithmic fairness and could potentially impact policy- makiin and regulation in related fields.
A key social benefit of the proposed mothods is that we can train group-fair models with higher levels of subsot fairness without needing to collect and process additional sensitive data. By doing so, the proposed algorithm is expected to transcend the fairness-privacy trade-off, making it practical for without conflicting with data protection laws.
Another social impact of our study is that the relationship between transport maps and group-fair models may help us form a new concept of fairness that can be readily accepted by society. Our approach explores the micro-level behavior of a given group-fair model (i.e., how the model matches individuals rather than simply looking at the statistics), which could facilitate finding reasonable compromises for existing fairness concepts that may appear paradoxical.
Acknowledgments
YK was partly supported by the National Research Foundation of Korca(NRF) grant funded by the Korea government(MSTT) 2022R1 A5A7063908), Institute of Information & communications Technology Planning & Evaluation (ITTP) grant funded by the Korea government(MSIy) (No.RS- 11221114,,,, Development and Study of AI Technologies to Inexpensively Conform to Evolving Policy Ethics), and Institute of Information & communications Technology Planning & Evaluation (IITP) grant funded by the Korea government (MSIT) [NO.RS W--R--22--111 253-2021-IT211333 133443,, Artificial Intelligence Graduate School Program (Scoul National University)]. MC was supported by a Korea Institute for Advancement of Technology (KIAT) grant funded by the Korea Government (MOTIE) ERS-2024-00 00409092, 2024 HRD Program for Industrial Innovation).
17

---

Published in Transactions on Machine Learning Research (12/2024)
References
Alekh Agarwal, Alina Beygelzimer, Miroslav Dudik, John Langford, and Hanna Wallach. A reductions approach to fair classification. In Jennifer Dy and Andreas Krause (eds.), , Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pp. 60-69.
PMLR, 10-15 Jul 2018. URL httpt::t/p htttps::/prroceednng.. .ma.eeddiingm.........mmmm.. mlr. wwtpssa.w.......ee0//..e /0tp://vaaaaaa...aaaoamaa
Alekh Agarwal, Miroslav Dudik, and Zhiwei Steven Wu. Fair regression: Quantitative definitions and reduction-based algorithms. In Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA, 2019. URL http:://proceedingg. mlr. press/ v97 v97/agarwal 11teaa11ddd.. 19d. htmll
Julia Angwin, Jeff Larson, Surya Mattu, and Lauren Kirchner. Machine bias. ProPublica, May, 23:2016,
2016.
António Percira Barata, Frank W. Takes, H. Jaap van den Herik, and Cor J. Veenman. Fair tree classifier using strong demographie parity, 2021.
Solon Barocas and Andrew D Solbst. Big data's disparate impact. Calif. L. Rev., 104:671, 2016.
Rachel K. F. Bellamy, Kuntal Dey, Michael Hind, Samuel C. Hoffman, Stephanie Houde, Kalapriya Kannan, Pranay Lohia, Jacquelyn Martino, Sameep Mchta, Aleksandra Mojsilovic, Scema Nagar, Karthikeyan Nato- san Ramamurthy, John Richards, Diptikalyan Saha, Prasanna Sattigeri, Moninder Singh, Kush R. Varshney, and Yunfeng Zhang. AI Fairness 360: An extensible toolkit for detecting, understanding, and mitigating unwanted algorithmic bias, October 2018. URL htttp:://aret
org/abs/////oooooooo.o....... abs/ 1810.01943
Sarah Bird, Miro Dudík, Richard Edgar, Brandon Horn, Roman Lutz, Vanessa Milan, Mehrnoosh Sameki, Hanna Wallach, and Kathleen Walker. Fairlearn: A toolkit for assossing and improving fairness in ai. Technical Report TER--R-2000-32 Microsoft, May 2020.
Maarten Buyl and Tijl De Bie. Optimal transport of classifiers to fairness. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho (eds.), Advances in Neural Information Processing Systems, 2022.
URL https://openreviee httppparrrrreeeetttefforrrii--/s http://orrummddd=eeeiiirr
Toon Calders, Faisal Kamiran, and Mykola Pechenizkiy. Building classificrs with independency constraints. In 2009 IEEE International Conference on Dala Mining Workshops, pp. 13-18. IEEE, 2009.
Paul Carvalho, Bary Pradelski, and Cole Williams. Affirmative action with multidimensional identities. Available al SSRN 4070930, 2022.
L Elisa Colis, Lingxiao Huang, Vijay Keswani, and Nishoeth K Vishnoi. Classification with fairness constraints: A mela-algorithm with provable guarantees. In Proceedings of the Conference on Fairness, Accounlability, and Transporency, pp.
2019.
Silvia Chiappa and Thomas P. S. Gillam. Path-specific counterfactual fairness, 2018. URL https://arxix:
Lénaïc Chizat, Pierre Roussillon, Flavien Léger, François-Xave Vialard, and Gabriel Peyré. Faster wasserstein distance estimation with the sinkhorn divergence. In Proceedings of the 34th International Conference on Neural Information Processing Systems, NIPS 220, Red Hook, NY, USA, 2020. Curran Associates Inc ISBN 9781713829546.
Alexandra Chouldechova. Fair prediction with disparate impact: A study of bias recidivism prediction instruments, 2016. URL
Ching-Yao Chuang and Youssef Mrouch. Fair mixup: Fairness via interpolation. In International Conference on Learning Representations, 2021. URL http:///pp.pppooeere.ooo////o/oa
Evgenii Chzhen, Christophe Denis, Mohamed Hebiri, Luca Oneto, and Massimiliano Pontil. Leveraging labeled and unlabeled data for consistent fair binary classification. In Advances in Neural Information Processing Systems, pp- 12760-127700 2019.
18

---

Published in Transactions on Machine Learning Research (12/2024)
Evgenii Chzhen, Christophe Denis, Mohamed Hebiri, Luca Oneto, and Massimiliano Pontil. Fair regression with wasserstein barycenters. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Bal-
can, and H. Lin (eds.), Advances in Neural Information Processing Systems, volume 33, pp. 7321 7331. Curran Associates, Inc., 2020. URL httpss:/pproceedingg hew.oeeeeinnnn...iiippps....peee www.nneurriccocoooo /teerrppp.cc/pappr////////1/ pdf
Sam Corbett- Daveis, Emma Pierson, Avi Feller, Sharad Goel, and Aziz Huq. Algorithmic decision making and the cost of fairness. In Proceedings of the 29rd acm sigkdd international conference on knowledge discovery and data mining, pp. 797 806, 2017.
Andrew Cotter, Heinrich Jiang, and Karthik Sridharan. Two-player games for efficient non-convex constrained optimization. In ALT, 2019.
Elliot Creager, David Madras, Jörn-Henrik Jacobsen, Marissa Weis, Kevin Swersky, Toniann Pitassi, and Richard Zemel. Flexibly fair representation learning by disentanglement. In International Conference Machine Learning, pp. 1436-1445. PMLR, 2019.
Marco Cuturi. Sinkhorn distances: Lightspeed computation of optimal transport. In C.J. Burges, L. Bottou, M. Welling, Z. Ghahramani, and K.Q. Weinberger (eds.), Advances in Neurol Information Processing Systems, volume 26. Curran Associates, Inc., 2013. URL
peweeeddiiiinnnnnii..ere.. www.ips..cepaappeeppppe cc/1pper/2113
.df
Bharath Bhushan Damodaran, Benjamin Kellenberger, Rémi Flamary, Devis Tuia, and Nicolas Courty. Deep joint distribution optimal transport for unsupervised domain adaptation. In Computer Vision - ECCV 2018: 15th European Conference, Munich, Germany, September 8-14, 2018, Proceedings, Part IV, pp. 467 483, Berlin, Heidelberg, 2018. Springer- ISBN 978-3-030-01224-3 doi: 10.1007/ 078-3-030-01222-- 28. URL https:://oi..rg/// -- 000-0088--0000020-----1-0---01
Deepjdot:
Nabarun Deb, Promit Ghosal, and Bodhisattva Sen. Rates of estimation of optimal transport maps using plug-in estimators via barycentric projections. In NeurIPS, 2021.
Michele Donini, Luca Oncto, Shai Ben-David, John S Shawe- Taylor, and Massimiliano Pontil. Empirical risk minimization under fairness constraints. In Advances in Newral Information Processing Systems, pp- 2791-2801, 2018.
Shawe-Taylor,
Dheeru Dua and Casey Graff. UCI machine learning repository, 2017. URL http:://arrcivv..ic........ m1
Cynthia Dwork, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Richard Zemel. Fairness through awareness. In Proceedings of the 3rd Innovations in Theoretical Computer Science Conference, ITCS '12 pp. 214-226, New York, NY, USA, 2012. Association for Computing Machinery. ISBN 9781450311151 doi: 00.1145/2090236 20902255. URL httpp:://ooi.rrg/1000 11wp://000..112/09003333 2090255
Harrison Edwards and Amos Storkey, Censoring representations with an adversary. In International Conference in Learning Representations (TCIRR206), pp. 1-14, May 2016. URL
doku. wttppppp...cccr011:::..... 2016: Conference date: 02-05-2016 Through 04-05-2016.
html 4th International Conference Learning Representations, ICLR
Michael Feldman, Sorelle A Friedler, John Moeller, Carlos Scheidegger, and Suresh Venkatasubramanian. Certifying and removing disparate impact. In proceedings of the 21th ACM SIGKDD international conference on knowledge discovery and data mining, pp. 259 208,2268-44100 2015.
Benjamin Fish, Jeremy Kun, and Ádám D Lelkes. A confidence based approach for balancing fairness and accuracy. In Proceedings of the 2016 SIAM International Conference on Data Mining, pp. 144 152. SIAM, 2016.
Rémi Flamary, Nicolas Courty, Alexandre Gramfort, Mokhtar Z. Alaya, Aurélic Boisbunon, Stanislas Chambon, Lactitia Chapel, Adrien Corenflos, Kilian Fatras, Nemo Fournier, Léo Gautheron, Nathalic T.H. Gayrand, Hicham Janati, Alain Rakotomamonjy, levgen Redko, Antoine Rolet, Antony Schutz, Vivien Seguy, Danica J.
19

---

Published in Transactions on Machine Learning Research (12/2024)
Sutherland, Romain Tavenard, Alexander Tong, and Titouan Vayer. Pot: Python optimal transport. transppor Journal of Machine Learning Research, 22(78))1-8, 8, 2021. URL http://hah..orrr//apeeee//////20 .ttml
Aden Forrow, Jan- Christiin Hütter, Mor Nitzan, Philiippe Rigollet, Geoffrey Schiebinger, and Jonathan Weed. Statistical optimal transport via factored couplings. In Kamalika Chaudhuri and Masashi Sugiyama (cds.), Proceedings of the Twenty-Second International Conference Artificial Intelligence and Statistics, volume 89 of Proceedings of Machine Learning Research, pp. 2454-2222 2465. PMLR, 16 18 Apr 2019. URL https://proceedings mlr. (aaas//89/foore/
Aude Genevay, Marco Cuturi, Gabriel Peyré, and Francis Bach. Stochastic optimization for large-scale optimal transport. In Proceedings of the 30th International Conference Neural Information Processing Systems, NIPS'16, pp. 3440 3448, Red Hook, NY, USA, 2016. Curran Associates Inc. ISBN 9781510838819.
Gabriel Goh, Andrew Cotter, Maya Gupta, and Michael P Friodlander. Satisfying real-world goals with dataset constraints. In Advances in Neural Information Processing Systems, pp. 2415-2423, 2016.
Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial nets. In Z. Ghahramani, M. Welling, C. Cortes, N. Lawrence, and K.Q. Weinberger (eds.), Advances Neural Information Processing Systems, vol- ume 27. Curran Associates, Inc., 2014. URL https://prooeddngg..ner/// www.riiss.c.pppee////..... pdf
Paula Gordaliza, Eustasio Del Barrio, Gamboa Fabrice, and Jean-Michel Loubes. Obtaining fairness using optimal transport theory. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp. 2357 2365. PMLR, 09 15 Jun 2019. CRL https://proceedinga mml.. wtt.e//////oordaaizaaaaaaaa html
Moritz Hardt, Eric Price, Eric Price, and Nati Srebro. Equality of opportunity in supervised learning. In D. Lee, M. Sugiyama, U. Luxburg, I. Guyon, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 29. Curran Associates, Inc., 2016a. URI, /ttp:t//////reeedinggs wtw.:ooeeeddiigg....i....... wwwrine.r...om cc/
pdf
Moritz Hardt, Eric Price, and Nati Srebro. Equality of opportumity in supervised learning. In Advances in neural information processing systems, pp. 3315-3323, 2016b.
Deborah Hellman. Measuring algorithmic fairness. Criminal Procedure eJournal, 2019. URL https: :
//api. swwanticschollarr wwwpaaatttcccolaa.oooo/////////p 199002104
Aan-Christian Hütter and Philippe Rigollet. Minimax estimation of smooth optimal transport maps. The Annols of Statistics, 49(2):1166 1194, 2021. doi: 10. 10.1214/0-AOS1990 URL httptttss///ioorrggggeo 1214/
20 20-A091997
David Ingold and Spencer Soper. Amazon doesn't consider the race of its customers. should it. Bloomberg, April, 1, 2016.
Ray Jiang, Aldo Pacchiano, Tom Stepleton, Heinrich Jiang, and Silvia Chiappa. Wasserstein fair classification. In Uncertainty in Artificial Intelligence, pp. 862-872. PMLR, 2020a.
Ray Jiang, Aldo Pacchiano, Tom Stepleton, Heinrich Jiang, and Silvia Chiappa. Wasserstein fair classification. In Ryan P. Adams and Vibhav Gogate (eds.), Proceedings of The 35th Uncertainly in Artificial Intellgencce Conference, volume 115 of Proceedings of Machine Learning Research, pp. 862-872, PMLR, 22 Jul 2020b. URL
mlr. wttp:ismmmrrr.ees/eieeee http//1111///1ag0o html
Faisal Kamiran, Asim Karim, and Xiangliang Zhang. Decision theory for discrimination-wware classification. In 2012 IEEE 12th International Conference on Data Mining, pp. 924 929, IEEE, 2012.
Toshihiro Kamishima, Shotaro Akaho, Hidcki Asoh, and Jun Sakuma. Fairness-aware classifier with prejudice remover regularizer. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pp. 35 50. Springer, 2012.
20

---

Published in Transactions on Machine Learning Research (12/2024)
Lev Kantorovich. On the translocation of masses. Journal of Mathematical Sciences, 133:1381-1333 2006.
Michael Kearns, Seth Neel, Aaron Roth, and Zhiwei Steven Wu. An empirical study of rich subgroup fairness for machine learning, 2018a.
Michael Kearns, Seth Neel, Aaron Roth, and Zhiwei Steven Wu. Preventing fairness gerrymandering: Auditing and learning for subgroup fairness. In Jennifer Dy and Andreas Krause (eds.), Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pp.
PMLR, 10-15 Jul 2018b. URL htttps://proceeddngg mlr ppwss/v80 gress/v80/kearns kearns 18a. html
Dongha Kim, Kunwoong Kim, Insung Kong, Ilsang Ohn, and Yongdai Kim. Learning fair representation with a parametric integral probability metric. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato (eds.), Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pp. 11074 11101. PMLR, 17 23 Jul
2022a. CRL sppppee://rooceediggs. mlr wwt.:ppressse//eeeee http////22//mm22bbm..//m kim2bb.................mmm.bbk html
Kunwoong Kim, Ilsang Ohn, Sara Kim, and Yongdai Kim. Slide: A surrogate fairness constraint to ensure fairness consistency. Neural Networks, 154:441-454, 2022b. ISSN 0893-6080. doi: https: www.o../......eee....... S08926080220028811
URL httpps:/wwweeeeeeeeeirreee.eeeee http://wwwccccccccoo///////eataa
Diederik P. Kingina and Jimmy Ba. Adam: A method for stochastic optimization, 2014. URL https:
waaxiv.org/abs/1144 1980
Jon Kleinberg, Jens Ludwig, Sendhil Mullainathan, and Ashesh Rambachan. Algorithmic fairness. In Aea popers and proceedings, volume 108, pp. 22 27, 2018.
Martin Knott and C. S. Smith. On the optimal mapping of distributions. Journal of Oplimization Theory and Applications, 43:39-49, 1984.
Matt J. Kusner, Joshua R. Loftus, Chris Russell, and Ricardo Silva. Counterfactual fairness, 2017. URL
Yujia Li, Kevin Swersky, and Rich Zemel. Generative moment matching networks. In Francis Bach and David Blei (eds.), Proceedings of the 32nd International Conference on Machine Learning, volume 37 of Proceedings of Machine Learning Research, pp. 1718 1727, Lille, France, 07-09 Jul 2015. PMLR. URL https://procceddngg. wwr.iinnn.mm.....mm.....e...e S..L.ppress/v331115...
David Madras, Elliot Creager, Toniann Pitassi, and Richard S. Zemel. Learning adversarially fair and transferable representations. In JCML, 2018
Ninareh Mehrabi, Fred Morstatter, Nripsuta Saxena, Kristina Lerman, and Aram Galstyan. A survey on bias and fairness in machine learning. arXiv preprinl Xiv: 1908 09635, 2019.
Anay Mehrotra, Bary S. R. Pradelski, and Nisheeth K. Vishnoi. Selection in the presence of implicit bias: The advantage of intersectional constraints. In Proceedings of the 2022 ACM Conference on Fairness, Accountability, and Transparency, FAceT '22, pp. 599-609, New York, NY, USA, 2022. Association for Computing Machinery. ISBN 9781450393522. doi: 10. 111144/5531146653311111 URL https: http:://doi..rg///
1145/3531146. 3533124
Mathieu Molina and Patrick Loiseau. Bounding and approximating intersectional fairness through marginal fairness. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho (eds.), Advances in Neural Information Processing Systems, 2022. URL /ttps:///ppereeven http:s///ogpeerrreeeeeeeerrrrere net//formnieeeeffuucccee
Gaspard Monge. Mémoire sur la théorie des déblais et des remblais. De I'Imprimeric Royale, 1781.
Sérgio Moro, Paulo Cortez, and Paulo Rita. A data-driven approach prodict the success of bank telemar- keting. Decision Support Systems, 02:22-31, 2014. ISSN 0167-9236. doi: httpss://doi http:///////oooo////000000/ 2014. 03.001. URL http://wwwwwtteeeeeee...oteootta
21

---

Published in Transactions on Machine Learning Research (12/2024)
Carlos Mougan, Antonio Ferrara, Laura State, Salvatore Ruggieri, and Steffen Staab. Beyond demographic parity: Redefining equal treatment, 2024. URL
Hamed Nilforoshan, Johann D Gaebler, Ravi Shroff, and Sharad Goel. Causal conceptions of fairness and their consequences. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato (eds.), Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pp. 16848 16887. PMLR, 17 23 Jul 2022. URL
attps::/prroeeeding mlr. 2ress/vi22/nllfooosaaaa222 html
I. Olkin and F. Pukelsheim. The distance between two random vectors with given dispersion matrices. Linear Algebra and its Applications, 48:257-266 263, 1982. ISSN 0024-3795. doi: http::///ob.oog//0000000022222/0 URL http://p/www..oooeoee.c....oo/.p
Felix Petersen, Debarghya Mukherroe, Yuckai Sun, and Mikhail Yurochkin. Post-proccssing for individual fairness, 2021. URL
13796
Geoff Pleiss, Manish Raghavan, Felix Wu, Jon Kleinberg, and Kilian Q Weinberger. On fairness and calibration. In Advances in Newral Information Processing Systems, pp. 5680-5689, 2017.
Tai Le Quy, Arjun Roy, Vasileios Iosifidis, Wenbin Zhang, and Eirini Ntoutsi. A survey on datasets for fairness-aware machine learning. WIREs Data Mining and Knowledge Discovery, 12(3), mar 2022. doi:
1..1002/widm.. 1452. URL attps://doi.org// 100.00002222wiwc 1452
Svetlozar T Rachev and Ludger Rüicchendof.. Mass Transportation Problems: Volume I: Theory, volume 1. Springer Science & Business Media, 1998.
Tim Salimans, Han Zhang, Alec Radford, and Dimitris Metaxas. Improving gans using optimal transport, 2018.
Changjian Shui, Gezheng Xu, Qi CHEN, Jiaqi Li, Charles Ling, Tal Arbel, Boyu Wang, and Christian Gagné. On learning fairness and accuracy on multiple subgroups. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho (eds.), Advances in Neural Information Processing Systems, 2022. URL https://openreview
Chiappa Silvia, Jiang Ray, Stepleton Tom, Pacchiano Aldo, Jiang Heinrich, and Aslanides John. A general approach to fairness with optimal transport. Proceedings of the AAAI Conference on Artificial Intelligence, 34(04):3633 3640, Apr. 2020. doi: 10.1609/ 10.1609/aaai.vve AAAI LAAT/artiicle/vee/55771
URL https://ojs aaai oooooogg//ooo /iddxxxexx.. php/
Joshua Simons, Sophia Adams Bhatti, and Adrian Weller. Machine learning and the meaning of equal treatment. In Proceedings of the 2021 AAAI/ACM Conference on AI, Ethics, and Society, AIES '21, pp. 956-966, New York, NY, USA, 2021. Association for Computing Machinery. ISBN 9781450384735. doi: 10.1145/3461702.344222
URL https::////// http:////oooor///...// 1145/3461702 3462556
Zhengyu Su, Yalin Wang, Rui Shi, Wei Zeng, Jian Sun, Feng Luo, and Xianfeng Gu. Optimal mass transport for shape matching and comparison. IEEE Transactions on Pattern Analysis and Machine Intelligence, 37 doi:
224222299,2, 2015.
Paul Van der Laan. The 2001 Census in the Netherlands: Integration of Registers and Surveys, pp. 39-52. 12 2001.
C. Villani. Optimal Thansport: Old and New. Grundlehren der mathematischen Wissenschaften. Springer Berlin Heidelberg, 2008. ISBN 9783540710509, URL httpps:/bookss. wt..gle......///aoee htt.g//......//oooo/s////oooo...
J. von Kügelgen, A.-H. Karimi, U. Bhatt, I. Valera, A. Weller, and B. Schölkopf. On the fairness of causal algorithmic recourse. In Proceedings of the 36th AAAI Conference on Artificial Intelligence (AAA!), pp. 9584-9594 AAAI Press, February 2022. URL htttps://site: *also at ICML 2021 Workshop Algorithmic Recourse and NeurIPS 2020 Workshop Algorithmic Fairness through the Lens of Causality and Interpretability (AFCT).
com httm://eeeeeerorse///eeeeee
22

---

Published in Transactions on Machine Learning Research (12/2024)
Sandra Wachter, Brent Mittelstadt, and Chris Russell. Bias preservation in machine learning: the legality of fairness metrics under non-diserimination law. W. Vo. L. Rev., 123:735, 2020.
Kellie Webster, Marta Recasens, Vera Axelrod, and Jason Baldridge. Mind the gap: A balanced corpus of gendered ambiguous pronouns. Transactions of the Association for Computational Linguistics, 6:605-617, 2018.
Dennis Wei, Karthikeyan Natesan Ramamurthy, and Flavio Calmon. Optimized score transformation for fair classification. volume 108 of Proceedings of Machine Learning Research, pp. 1673-1683, Online, 26-28 Aug 2020. PMLR. URL http::/prroceedingg... .mlr, ppwss//100/veei000000 htmmllla..mmml
Yongkai Wu, Lu Zhang, and Xintao Wu. On convexity and bounds of kaire classification. In The World Wide Web Conference, WWW '19, pp. Computing Machinery. ISBN 9781450366748. doi: 10.1145/3300558.83111 3311377
New York, NY, USA, 2019. Association for URL https://doi.org:
1145/3308588.33199
Depeng Xu, Shuhan Yuan, Lu Zhang, and Xintao Wu. Fairgan: Fairness-aware generative adversarial networks. In 2018 IEEE International Conference on Big Data (Big Data), pp. 570-575. IEEE, 2018.
Gal Yona and Guy Rothblum. Probably approximately metric-fair learning. In Jennifer Dy and Andreas Krause (eds.), Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pp. 5680 5688, PMLR, 10 15 Jul 2018. URL https::/pprcceedingg .ml press/v80/yonalBa. html
Mikhail Yurochkin and Yuekai Sun. Sensei: Sensitive set invariance for enforcing individual fairness. In International Conference on Learning Representations, 2021. URL https://openreviior wtt.roooiioooeettt/oouuouii
DktZb97 Fx
Mikhail Yurochkin, Amanda Bower, and Yuekai Sun. Training individually fair ml models with sensitive subspace robustness. In International Conference Learning Representations, 2020. URL https: //openreview http://orumnid-Bggakaaao
Muhammad Bilal Zafar, Isabel Valcra, Manuel Gomez Rogriguez, and Krishna P Gummadi. Fairness constraints: Mechanisms for fair classification. In Arlificial Intelligence and Statistics, pp. 962 970, 2017.
Muhammad Bilal Zafar, Isabel Valera, Manuel fomee-Rodrigucc,, and Krishna P Gummadi. Fairness Constraints: Flexible Approach for Fair Classification. J. Mach. Learn. Res., 20(75): 42, 2019.
Rich Zemel, Yu Wu, Kevin Swersky, Toni Pitassi, and Cynthia Dwork. Learning fair representations. In
Sanjoy Dasgupta and David McAllester (eds.), Proceedings of the 30th International Conference on Machine Learning, volume 28 of Proceedings of Machine Learning Reseorch, pp. 225-333, Atlanta, Georgia, USA, 19 Jun 2013. PMLR. URL https: pecttss://rroeeeee http://poceeennn..//// mlr http:///ngg..m...preee////////// 11.1111...0 html
Brian Hu Zhang, Blake Lemoine, and Margaret Mitchell. Mitigating unwanted biases with adversarial learning. In Proceedings of the 2018 AAAI/ACM Conference on AI, Ethics, and Society, AIES '18, pp. 335-340, New York, NY, USA, 2018. Association for Computing Machinery. ISBN 9781450360128. doi:
10.1145/3278721.3225
URL https:: wrw.ii..rrr1...110 1145/3278721 3278779
Yuyin Zhou, Shih-Cheng Huang, Jason Alan Fries, Alaa Youssef, Timothy J. Amrhein, Marcello Chang, Imon Banerjee, Daniel Rubin, Lei Xing, Nigam Shah, and Matthew P. Lungren. Radfusion: Benchmarking performance and fairness for multimodal pulmonary embolism detection from et and ehr, 2021. URL
atttps:/aaxxe http://aaxxvv..ggbbb///aae www.//gg//////eeeeooo/ htgg/ab//2111..110 11665
23

---

Published in Transactions on Machine Learning Research (12/2024)
A Proofs of theorems
Let N be the set of natural numbers. For 8 0, and any measurable set A [0, we denote (A == fxE X /(x,s) s) E A}. Recall that Xg is the domain =|S=s.
Proposition 3.1 For any perfectly group-fair model f, ie., Pso = Pri, there exists a transport map T Tf(() satisfying f (X,s) 8) = (TT((X), s') a.ee
below implies - implies that If (X, (T, s s') ] 0 almost everywhere, which concludes the proof.
Proof of Proposition 3. By letting 8= = 0, Theorem 3.3
0. This
Theorem 3.3 Fix a fairness level 8 O. For any given group-fair model f such that ATVDP()) s 8, there exists transport map T. T satisfying AMDP(J,T, T.) 26.
Proof of Theorem 3.3 Without loss of generality, let 0 and s'= Let Fo: [0. 1] [0.1] and Fi [0,1] [0. denote the cumulative distribution functions (CDFs) of f(X,0)S= = and f(X, = 1, respectively. Note that Fo and Fi have at most countably many discontinuity points.
Define Dy as the set of all discontinuity points of Fs, which is countable. For each t D,, define the jump at as AF,(() = F.(())F.(t-),, where (t-t)) denotes the left limit of F, at
Define the sub-CDF (i.e., the continuous part of F2) as: Foom(() == ( (F.(t) for v é [0. 1]. Note that this function 1oonnt is continuous and non-decreasing on [0, 1]. Moreover, for any interval (a, b] s [00, [0, define Front (a.,b) F.on((b) Feont (a).
We here prove for the case when Front (1) s Foont()) (1). The other case (lont(1) Foont(1) can be treated similarly.
1. (Constructing subsets based Foont) Since Front( (1)
Foon((1); there exists 1 such that Front (1) F We partition the interval [0, 2] into subintervals of length at most 6. Let uo = 0 and define U2 := min UK-1 + 2 for k = I,..., m. Here, m E N is the number that satisfies Um Note that Front (1) = Ek Front Fron(((Xx-1, ((vk-1,u4]).
For each ke E (1,..., m), we compare the measures of the intervals as follows. If Front (11-1, U/]) S Foon"(((k- us]), then there exists 25 [1k-1, Uy] such that pronl((1)-11 = FOon ((*k-1, =)). Define No, == Jo ((v=-1 Do) and X1 == fi ((*=-1, "k] D1).
If F (bk-1, > Foont ((tg-1, m)),, we can define 2k, No, and X1, similarly.
2. (Defining probability measures and transport maps on subsets) For each k (I,...,m), define probability measures Pa,s, e {0, 1) such that (A) Pa(AnX..)) for measurable subsets A g X. P.(E..))
By Brenier's Theorem VVillan 2008; Hütter Rigollet 2021), there exists a transport map T(l) from (.) to ()) under (C). Since Up 1 $ 0, Vk, we have that
((T (x), 1) Vx Xo,
3. (Handling discontinuity points) Let Do,1 Do Dj be the intersection of Do and D1, which is the set of common discontinuity points.
Fix de Do.1- Suppose that Pi ((d)) < ((( Then, there exists for for (1d)) fo ((d)) such that Po(Jo ((d)))) PI(Fi (o(()
Define Xo,a := ((d)) and Xi. == fi ((d)). We can
define Lo,s and Li similarly when P2(fit((d))) > Po(So ((d)))
For each E Da,1, we define probability measures Po.d, (0, 1] such that (A) := P.(An P. (á for measurable subsets As X. Then, there exists transport map T(2) from Po,)() to Pi.a()) By the definition of Lo.d, we have that.
f(x,0) ( ((T(() d, Vx Lo.d-
24

---

Published in Transactions on Machine Learning Research (12/2024)
4. (Constructing the complement parts) We collect the complements
K/== = Xo
Xox
U k-1 d=Do.1
Ru,d and K1== == X1
X U Rnd
k-1
DeDu.
Because Po
1= No,x) - Pi Pi x1,x) and Po(UdeDo, Ro.a) = P, PUUdeDo,, R),d), we have Po(2))
1 1- Po(UUk((I.....) Xo,k) Po(UueDo. Ro PI (21) 5
Define probability measures P','& {0, 1] on X sE [0,1} such that P'(A) == (.(An)) P.(2)) for measurable
subsets A X. Then, there exists transport map TO²) from P²(() to Pí(.).
For é Ky have Pg())) 1- (E%L Po((o,,) EdeDo. Po(A), s since ATVDP())
TV (X P P((X.))s-1) & 6. Furthermore, since f(-) [0. 1], we have that
Eo (Is(x,0) - S(T)) (x),
e xx))= 11(x.0)- (X).1) (xxX)))))(X $ f X)dPo() Po(x))= $8.
1)1 (2),
(10)
5. (Overall transport map) Finally, combining 2 to 4 above, we define the (overall) transport map To
m (.
To(-) = Σ T 0.k
Σ ((d())(( Ro.d) T ())
(11)
de
We note that (( (Ro.d) d: K3} and (( (e X3} are partitions of X, and
= X1, respectively. Morcover, Po( ( yk, Po(Au,a) = Pi (A( Ad, and = (X?)) Hence, To is a transport map from Po to Pt.
6. (Calculation of the bound for AMDP To)) Using the constructed transport map To. we have that
AMDP(J, To) (x) 0) ((T,(X),, ((T
Σ Sr [f(x,0) (x)
No.k
Σ Se
- (x)
(12)
15(x,) 0) ((xx0)-f(T)))
X
Σ Po((o,,)+ f (f 0) f(T) (3) (x) 1x)PP)))
8
(*)
6-+6=20 28,
where (*) holds by the inequalities in and
25

---

Published in Transactions on Machine Learning Research (12/2024)
Theorem 3.3 without the condition (C): the case when Po and P1 are discrete The condition (C) is assumed for easier discussion involving continuous distributions. This is because the existence of (deterministic) transport maps is not guaranteed when the distributions Po and P1 are discrete and their supports are different. However, by using the notion of stochastic transport map (defined below), we can derive a tcal result similar to Theorem 3.3 when Po and P1 are discrete.
Let Xo (x1 :...; (x.,"....,xx Xno } and Xi = (x (x("......
(x
..... Xay ()) J. For this time only, define Po and Pi as the empirical
distributions on Do and D1 respectively. Let Xo and X, be the random variables following Po and Pi. respectively. Furthermore, let f(X)) = {f(x,0) 0)
No} and f(Xi) (f(x.1) K1). Denote Pso
and Pa be the empirical distributions on f(x)) and f(X),, i.c., the distributions of ((Xo), Xo ~ Po and f(X1), ~ PI, respectively.
For a given joint distribution Q between X. and X1, we can define AMDP(F. f(X,, which general version of AMDP(),T.). That is, instead of the deterministic (ono-to-onc) transport map, we define the stochastic transport map T, defined by Tx(x(") x xf() with probability
= (= =x
Q(X, X )
In Proposition A.1 below, we show that stochastic transport map a joint distribution Q (rather than the deterministic transport map) exists and satisfies AMDP Q) s 8. This is analogous to the result AMDP(f, T,) s 6 presented in Theorem 3.3 Note that if no n1. there cxist transport maps (i.c., onc-to-one mappings or permutations) between No and Xi.
Proposition A.1. Assume the supports of fo and Ps, share m(s no, m1) number of common points. Then, for arey given group-fair model f such that ATVDP(F) 6, there exists joint distribution Q between Xo and X, satisfying AMDP(f.Q) 88
Proof. If sulfices to show that there exists Q such that AMDP(S,Q) Q) ATVDP()). Without loss of generality, assume no S n, and let f(x (0) ,0) f(x(") 1) for i (1....,m) (i.c., the common points).
First, we calculate ATVDP(/) as follows. Recall the definition of TV for discrete measures: JV(P)o: pA) I/ (2)
For the m number of common points, the sum of differences is m 1 1T Ri
mg
noma
For the points only in f(K)) but not in fX)), the sum of differences is (nu - (ou-mm)nm mm/ng. Similarly, for the points only in s(X) but not in ((%), the sum of differences is (n1 m)/n/ As result, we have
ATVDP()) TV(P, fo P₁))
1(1 (mm n1 no
no
n1 m
(13)
2
non
74p
m1
m
Then, we construct Q as follows. Let Yis = Q(x, (0) X1 = x()) and r [ matrix based on n,,5, which we construct as below:
R Poxn1 be a
Build a diagonal matrix Fu
1 Im e RTxm where Im the identity matrix of size m x m. mys
Build a zero matrix P21 0 m)o RR (mo-m))m where O denoles the zero matrix.
3. Build matrices T12 (m)-())))) and matrix D22 TR. (m)mmmm))- satisfying I mnlnn-m = = 11
1
ni
(112
Tie Tzzlai-m ag no- and
I
L
1m-m-
T22
4. Complete : Th T12
Im
T12
R1 (m)-m))m
P21
T22)
0
1'22
Last, note that the I is a coupling matrix (i.e., satisfying the constraints EM Yi 1/no. Vj [nq] and Eng Ti.j 1/m1, Vi e [no]). Hence, we can define the joint distribution Q by the constructed I (i.e., T is
26

---

Published in Transactions on Machine Learning Research (12/2024)
matrix representation of Q equation 5 for the formulation). Finally, we have
AMDP(f. Q) (x ((1,
OXx 0 X1 = -x, (X 0) - f(X1, 1)1 h 0) 0) ((x,))
E
Holf(Xo, 0) 1)( Σ
mulf(Xo. 0) -f((1,1)
je[m]
Σ
mxoo(XX, - 1)
ve[nol jelrol-e(mm-......
Σ
Holf(Xo.0) f(X1,
Σ
Yij 1- m
S ATVDP(().
(e[mo] je[no].e[[m+ Je(m=I.....ss)
71
(14)
Therefore, any constructed by the steps 1-4 above satisfies AMDP(f.Q) S..
Proposition 3.5 Let T be the fair matching function of f on Do and D1 (where the empirical distributions with respect to Do and Dj are used in Definition 3.4 Then, the matched individual T' (xx) of any x DD is obtained by T (x) f7 F7 Fg fx(x).
Proof of Theorem 3.5 First, we aim to find a permutation map M = arg min ar Σ
(x(;) (xfx(x))))
subject to (M (x.) x, E D2} = (x;) x, E Dr). By Rachev & Rüschendorl (1998) Chzhen et al. (2020); Jiang et al. (2020b), we have the fact that 1- 1-Wasserstein distance equivalent to the average of difference between two prediction scores that have same quantiles in each group. That is, My Fz F.(1) for any y xxx
x Second, we have M is one-to-one and (f,( :x E D.) (f.( x E D.) (M
(M' (f.(x:)) xx; E D.).
since T is also an exact on--to-one map.
Therefore, we conclude that T (x) = f M [x(x) = 1 F Fg Sx(x) for all x e D,.
Remark A.2. Using Proposition 3.5 to estimate the fair matching function is equivalent to estimating the OT map belween two score distribulions. The statistical convergence rale for estimaling the OT map belween
one-dimensional distributions fast; it is of the order (2) (n -1/2 1/2 1/2) CCiiat et al. 2020 Deb et al. 2021 Hütter & Rigollet, 2021)). When we two mini-batched Do Do and D, cD with identical size m, the order becomes O (m- 12). This indicates that sufficiently large mini batch size con guarantee accurate estimation.
27

---

Published in Transactions on Machine Learning Research (12/2024)
Theorem 3.7 For given T3 T if AMMP(f..T.) 56, then have AWDP(f) 5 and ADP(f) 8.
Proof of Theorem 3.7 Fix f {f E F //T s 6}. Let L1 the set of all 1-Lipschitz functions. Using he fact that Wasserstein-1 distance is equivalent to IPM induced by set of 1-Lipschitz function Villani 2008). we have that
AWDP() - W ( S=0, P((X)))S=1)
sup
(uo ((x 5)) (u s1)l
neCi
< sup ueli
(u f(X. 5)) - (uo (TT, 5))l + sup (uo ((T(()) Ey f(X,
sup
ueLi
s sup Eg wn f(X, 8) u F(T, neli
sup ucL:
(X, ))) (uo f(X,
"cC:
S E,If(X, 8) (TT,((X),))) sup E. (u (X)(())ss)) - (uo f(X,s'))
weLi
<ō+ + sup (u (TT - s'))
neLi
E. $ + sup sup [E,(u -) |eF ueL1
< + TV # P..Pa)
(15)
The last equality holds since TV(T s Pa, Ps)) 0 for any transport map T.. For (fP(f) because the identity map is 1-Lipschitz, we have that ADP(f) s AWDP(f), which completes the proof.
28

---

Published in Transactions on Machine Learning Research (12/2024)
Theorem 4.2 Suppose F is the collection of L-Lipschitz functions. Let A be given subset in N. Then, for all satisfying A & 6, we have
ADP A - - PLA)
T(()))))
(16)
where PA,A is the distribution of X 5, X A, and 0 a constant only depending on and Ps; 8 = 0, 1.
Proof. We write T. = Tí for notational simplicity.
[E((X, 0, A) 11(
x -00 A))
(17)
+BC/CCC.....00--111322--4/7/111- A))
By (C1), the first term is bounded by -- (x),,, which is also bounded by L [E1IX- Ti(X) 13)
The second term is bounded by 5 up to a constant for all ʃ satisfying AMDP(S,T.) s 6. That is, we have
( (X) A)dP: ( A)dP
1, (E))))E(XXXX)))
A)I
JI(XE A)dP (X)
/I(X A)dPI(X)
S
$
XEA (((T((X).)) (()))
/ A)dP))
(18)
TI(XE ())PI(X) SSEN (((T( J(X, (((P)))))
1
U' P1) ())
(A, x
(X) 1/P((X A/S 1) is constant only depending P1 and A. The third term ()(X x ())))(((XX.) 0)|5 - 1,, é AA) is not controllable by cither the transport map or 8 but depends on the given distributions and A. That is,
where U'(A)PI) 1/ 1(X (X)
[(f((X 0 A) -O..(. 0)| 1,X A)I [(X,0))0)P)) S ((X,0)
(19)
sup JeF (P.(P..,PPI.A)
Hence, we have
[[(((,0)|== A) -(J(X 1, A)I T (A),)))
(20)
s X- X
We can similarly derive
R4//XX_0SS-00XXXX3---/////11)11) + (AA,
(21)
$
Letting U == max (U"(A..)) completes the proof. 0
29

---

Published in Transactions on Machine Learning Research (12/2024)
Lemma A.3 (Optimal transport map between two Gaussians). For mean vectors px, Rd and covariance matrices Σx, Ex с TRddd the OT map from N (uxx, Ex) to (ux, Ex) is given as T W x b
where WOT Ex X E
Ex and b =p W μI.
Proof. Consider the centered Gaussians, i.c,, Px = by at first. Based on Theorem 4 of Olkin & Pukelsheim 11982, we have that W2 (O, (O,, Tr(Ex+ + Ey 2 Xx>>">>>>>>>>>>>>>>>>>>>>>>>>>>> |ΣX E 1 where 1.ll is the Frobenius norm. Correspondingly, Knott & Smith (1984) derived the optimal transport map as 1/2 1/2 [x Ex
Σx Exxxx x.
Combining these results, we can extend the OT map formula of Gaussians with nonzero mcans follows. Since E E| (X
x - -xy) 2 E|| (X - -x) HY) 1 | 12,, the Wasserstein
distance is given as W2 (xN((u,,XxxxM
Ex)) || -X
|
1/2
2
Y 1 and so the corresponding opti-
1/2
mal transport map is also given as x Dx3/2 [x ا 2
1/2
x jx E
[>=1/2 Ey
1/22 1/2
>-1/2 Px:
which completes the proof.
Proposition 4.3 o Id. That is, XCF x01
(Counterfactual fairness and the OT map) For all having (Ia A)-1, W. becomes
Xn- Mo. By replacing the sensitive altribute on the randomness c0, we obtain of (B"'x) p1) o ( Xn po). Then, its
Proof of Proposition 4.3 Once we observe Xg, the randomness co is observed cu B-
counterfactual becomes x Bpr 01% I La(xo Bpo). Then, prove Proposition 4.3 by showing the if
and only if condition as follows.
W. (oB (CGBBDB)
= ( ((EBDD)))) (dRBDB')-1P
(BDD)) (BDB")-1?
(22)
=010 (BDE")"" ((BDT))) (BDBT)-112
= Ia.
The same result can be done for XI. Hence, we conclude W, = -0
30

---

Published in Transactions on Machine Learning Research (12/2024)
B Disadvantage of high transport cost
This section presents example of two completely different group-fair models where one is unrcasonable and the other is reasonable, particularly in terms of subset fairness. This example suggests that not all group-fair models are acceplable, thereby emphasizing the necessity of finding group-fair models corresponding to favorable implicit transport maps.
Suppose that the distribution of the imput variable is given as X|S= Unif(0, 1), for s {0,1]. Consider the following two classification models: f(x,s) s) -ign(2x-1)(122)))) 1)(1-2)++1 and f(x, 8) sign(2x 1)+1
2
2
It is clear that both f and f are perfectly fair, i.., Pj =P,, and Pjo -Pn- However, f has notable unfairness issue in its treatments of individuals within the subset {x 2 1/2} (as well
fx,,
Unreasonable matching
S= x 1/2 x2 1/2
5 1
as (x 1/2}); for when > 1/2, f assigns label for all individuals of s while it assigns label for all individuals of 8 = This indicates that f discriminates against individuals in the subset (x 2 1/2} (and also (x < 1/2)). In contrast, f does not exhibit such undesirable discrimination against the subsets. Hence,
==1 x < 1/2 x 1/2
5 0
==1
fxx,
Reasonable matching
=
1/2 2 1/2 1
== 5=1
say that f has less discrimination on the subsets than f. Figure provides a comparative illustration of f and f.
= X < 1/2 x2 1/2
S
The observed discrimination of f on subsets can be attributed to the unreasonable fair matching function of f. It turns out that the fair matching function of f is (x))= sign((2x-1)1-22))
Figure 7: (Top) A group-fair model with the risk of discrim- ination on subsets. (Bottom) A group-fair model without the risk of discrimination on subsets.
This function matches an individual in {x < 5 = 8) with one in {x S s'}, who are far apart from each other. In contrast, the fair matching function of f is (x())= x. This example emphasizos the need of group-fair models whose fair matching function have low transport costs.
C The Kantorovich problem
As shortly introduced in Section 2.4 the Kantorovich problem is to find the optimal coupling (i.e., joint distribution) between two given distributions. It can be mathematically expressed as the following. For two given distributions Q and Q2, inf Ex (c(X, Y)) where II(@,, Q2) is the set of all joint measures with marginals 21 and Q2. Let be the L2 cost function.
For given two empirical distributions on Du = fx (0) Fe and D1 = (x,, 1m f==1 we first define the cost matrix as C:= [c:_]] e R" where ejj ||x - x () Then, the solution of the Kantorovich problem, i.e. optimal joint distribution between the two distributions, is defined by the coupling matrix I' [[v,]] e BRnux which is the minimizer of the following objective:
1 T5
1
min Cooll min GUTR S.L. n.j 2 0, 7h
Σ 11
Σ Ti.j
(23)
71
n10
In fact, the Kantorovich problem can be solved by linear programming (Kantorovich 2006 Villani solve the linear program, we use practical implementation such as POT library in Python.
2008
To
31

---

Published in Transactions on Machine Learning Research (12/2024)
D Implementation details
In this section, we provide detailed descriptions for the implementation of the experiments.
D.1 Datasets
First, the URLs of these datasets are provided.
ADULT: the Adult income dataset Dua & Graff
2017 can be downloaded from the UCT repository
g
GERMAN: the German credit dataset Dua & Grafl
2017 can be downloaded from the UCI repository
DUTCH: the Dutch census datasct can be downloaded from the public Github of Quy et al. 2022
BANK: the Bank marketing dataset can be downloaded from the UCI repository
The following Table describes the basic information of the four datasets.
Table 6: The description of the real benchmark tabular datasets: ADULT, GERMAN, BANK, and DUTCH. X, Y and denote the input features, the sensitive attribute, the target label information, and the dimension of X, respectively. Train/Tees /Test sizes are the number of samples in the training and test datasets, respectively.
Dataset
Variable
Description
Dataset
Variable
Description
X
Personal attributes
X
Personal attributes Gender High crodit score 60
S
Gender Outcome $50k
S
Y
Y
ADULT
GERMAN
d
101 30,136/15,,08
d
Train / Test size
Train Test data size
800/200
X
Personal attributes Binarized age
X
Personal attributes
S
S
Gender
Y
Subscribing term deposit
Y d
High-level occupation
BANK
DUTCH
d
57
58 48, 18,336/12,00
Train "oss size
24,390/6,098
Train/ Test data size
Second, describe pre-processing method of the datasets used. For ADULT, GERMAN, and BaNK datasets,
follow the pre-processing of the implementation of IBM's ATF360 (Bellamy et al.
2018 T For DUTCH
dataset, follow the pre-processing of Quy et al. (2022)'s 's Githut Basically, continuous input variables are normalized by min-max scaling and categorical input variables are one-hot encoded. We set batch size as 1024, 200, 1024, and 512 for ADULT, GERMAN, DUTCH, and BANK datasets, respectively.
D.2 Algorithms
This section provides more detailed descriptions of the baseline algorithms used in our experiments.
2018 This algorithm is an in in-processing method that learns a fair classifier with the lowest empirical fairness level ADP. To implement this method for MLP model architecture, we employ FairTorch minimizes cross-entropy A- Reduction regularizer for a given >>
Reduction Agarwal et al.
Reg (Donini et al. 2018 Chuang & Mronch 2021 This method is a regularizing approach that
minimizes cross-entropy + X- ADD" for a given > 0. Tn Chuang & Mroueh (2021). they call this algorithm GapReg. This also similar to the approach of Donini al. (2018) the sense that the model is learned with constraint having given level of ADP.
"https://archivee ics www.uucuuuuuuu wei..eu//m//daaaseee.... /aduu adult
"https://un http://///ccivviis.ooo www.sssscccuuuuueeee.. mal/ddaassts//taae sttsssstttotttteoooo (eranoo---grrmmn--rrit-------
"https://githuu ttilequuy/ /fairuess dataset/tree htt/t//teeeeeeeeeeeeeeeeeeeeeeee moaiin/eppermmntts///oo wwtttt////d///aa/aaaaaaaa dutch.esv
"https://archive.iie ics. /ed.eedddd/aas//////e./ 2astasst/222/bank=matttt baank-mn
htttp:://ai0600.redtttcc co/cn//abllc/
"https://github.cm
ttalequyyyy ffirness dataset/ tttttttteee/eeeeeeee
http//////mmi/cppeeeeeeeeoeeeeee /ataa
htttps///gtthub... http://waaaat//aaatttrrrtt
32

---

Published in Transactions on Machine Learning Research (12/2024)
Adv (Zhang et al. 2018 This algorithm is in-processing method that regularizes the model outputs with adversarial network that the adversarial network is learned to predict the sensitive attribute using the model outputs as the inputs. It minimizes cross-entropy + A Adversarial loss for a given A> 0.
Note that Reduction and Adv are ones of the most popular in-processing algorithms, as widely-used libraries ATF360 (Bellamy et al. 2018) and Fairlearn (Bird et al. 2020) provide the usage and implementation of the two algorithms. Reg is vanilla approach of adding the regularization term in the loss function to learn the most accurate model among models satisfying given level of group fairness.
We basically train models with various fairness levels by controlling the Lagrangian multiplier X. The values are presented in the following table.
Table 7: Hyper-parameters used for controlling fairness levels for each algorithm.
Algorithm
Reduction Reg
6.0. 60
20.0, 30.0, 40.0, 50.0, 60.0, 80.0, 100.0, 150.0, 200.0, 300.0, (0.1, 0.3, 0.5, 0.6, 0.8, 0.9, 1,5, 2.0, 3.0. 5.0, 10.0, 50.0, 100.0) (0.1,0.2,033,0,,00,5.0000 0.7,
Adv FTM
1.0. 1.3, 2.0, 3.0.
15.0, 20.0, 30.0, 50.0, 100.0) 1.0, 13,, 300 10.0)
(0.1, 0.3. 0.4, 0.5, 0.6.
The Adam optimizer (Kingma & Ba 2014 with an initial learning rate of 0.001 is used, and the learning rate is scheduled by multiplying 0.95 at each epoch.
D.3 Pseudo-code
Here, provide Pytorch-style psuedo code of calculating the MDP constraint in FTM.
Algorithm 1: PyTorch-style pscudo-code of calculating the MDP constraint in FTM.
xs, xt: input vectors from the source, target distribution, respectively. model: a classifier to be trained
import ot
The matching constraint: matching with the 0T
weight_s torch.oness (xstze=(xxssizee(( }) xs.size(0)
weight_t forch.ones((e (sizeeexxxxtts }) xt.aizze() # identical to weight_s ot.dist(xs, (xs, xt:)
(weighhtt,,, weight_t,
matched xe xt [t(tocc (rg dim-1)]
output, matched matched_output model model (matched_xx))
FTH_REG (output (aachee_output)) (apputtaabbs abs() ()
33

---

Published in Transactions on Machine Learning Research (12/2024)
E Auxillary experimental results
In this section, we provide auxillary experimental results that are not displayed in the main body.
E.1
pairness-prediction trade-off (Section 5.2.1)
Figure
shows the trade-offs between the fairness levels with respect to ADP, ADP and classification accuracy.
Adult
German
Dutch
Bank
Unfair
Unfair
Unfair
Unfair
Reduction
Reduction
Reduction
Reduction
Reg
Reg
Reg
Reg
Adl
Adv
Apt
Adl
ACP
ADP
ADP
ACP
Adult
German
Dutch
Bank
Unteir
Untair
Untair
120
Reduction
Reduction
Reduction
Reduction
Rog
Reg
Reg
Rog
FTM,
FTW
FTN
FTM
4G% RSO
40%
Figure 8: Pairness-prediction trade-offs: (Left to right) ADULT, GERMAN, DUTCH, BANK. (Top to bottom)
ADP vs. Acc, ADP vs. Acc.
E.2 Improvement in subset fairness (Section 5.2.2)
Here, we provide experimental results showing fairness levels on subsets defined by input variables. Table S and are copics of Table D with standard errors.
Table 8: Fairness on subsets defined by the input variable age: Fairness levels on subsets defined by the input variable age on GERMAN dataset under a given ADP 0.045 with standard errors (s.e.).
Algorithm
Reduction
Reg
Adv
FTM
ADP (s.e.)
0.073 (0.015)
0.077 (0.013)
0.048 (0.020)
0.045 (0.021)
High age
ADP (a.e.)
0.049 (0.006)
0.029 (0.008)
0.028 (0.012)
0.026 (0.006)
AWDP (s.e.)
0.053 (0.005)
0.039 (0.003)
0.042 (0.008)
0.038 (0.003)
ADP (a.e.)
0.118 (0.035)
0.116 (0.037)
0.122 (0.047)
0.077 (0.032)
Low age
ADP (s.c.)
0.047 (0.015)
0.050 (0.009)
0.053 (0.017)
0.047 (0.007)
AWDP (s.e.)
0.058 (0.011)
0.059 (0.007)
0.061 (0.015)
0.054 (0.006)
Table 9: Fairness on subsets defined by the input variable marital status: Fairness levels on subsets defined by the input variable marital status on DUTCH dataset under given ADP 0.12 with standard errors (s.e.).
Algorithm
||
Reduction
Rog
Adv
ITM V
ADP (s.o.)
0.258 (0.005)
0.372 (0.003)
0.237 (0.083)
0.204 (0.003)
Married
ADP (s.o.)
0.1 (0.002)
0.164 (0.001)
0.187
(0.073)
0.152 (0.002)
AWDP (s.e.)
0.183 (0.002)
0.172 (0.001)
0.193 (0.071)
0.152 (0.002)
ADP (s.o.)
0.061 (0.007)
0.131 (0.006)
0.095 (0.038)
0.068 (0.005)
Not married
ADP (s.o.)
0.045 (0.002)
0.062 (0.003)
0.098 (0.035)
0.036 (0.003)
AWDP (s.e.)
0.045 (0.003)
0.072 (0.002)
0.098 (0.034)
0.045 (0.005)
34

---

Published in Transactions on Machine Learning Research (12/2024)
E.3 An additional advantage of using the marginal OT map: reducing the risk of self-fulfilling prophecy
We compare the risks of discrimination in the context of self-fulilling prophecy in Dwork et al. (2012),
critical limitation that can arise when focusing solely on group fairness: unqualified individuals with relatively low scores can be chosen to be qualified, while other individuals with relatively high scores are chosen to be unqualified. To quantify the risk of self- fulfiligi prophecy, we assume that the unfair model is optimal for predicting the true score of each individual. We consider the following two evaluation approaches under this assumption. For the transport map used in MDP constraint, we choose the marginal OT map.
(Evaluation 1)
The first measure for the risk of self-fulfilling prophecy is the Spearman's rank corvelation between unfair and fair prediction scores at each protected group: a higher rank correlation implies lower risk of self-fulilling prophecy. Table 10 shows that FTM has lower risks of suffering from self-fulfilling prophecy, in most cases.
Table 10: Spearman's correlation coelficients between the scores of the unfair model and group-fair models under fixed levels of ADP with standard errors (s.e.). Bold faces are the best ones, and underlined ones are the second bests.
Dataset
ADULT
GERMAN
ADP
0.10
Sensitive attribute
D
Reduction (s.e.)
0.935 (0.006)
0.987 (0.001)
0.996 (0.001)
0.997 (0.001)
Reg (s.o.)
0.762 (0.087)
0.806 (0.084)
0.997 (0.000)
0.998 (0.000)
Ady (s.e.)
0.876 (0.003)
0.979 (0.001)
0.986 (0.009)
0.986 (0.010)
FTM (s.e.)
(0.003)
(0.001)
(0.002)
(0.001)
Dataset
DurcH
BaNK
ADP
0.01
0.02
Sensitive attribute
0
Reduction (s.o.)
0.940 (0.001)
0.922 (0.001)
0.958 (0.010)
0.978 (0.005)
Reg (a.6.)
0.872 (0.003)
0.972 (0.003)
0.784 (0.031)
0.974 (0.003)
Ady (s.e.)
0.639 (0.171)
0.693 (0.185)
0.603 (0.207)
0.505 (0.238)
FTM (s.e.)
0.973 (0.002)
0.991 (0.000)
0.964 (0.007)
0.979 (0.004)
35

---

Published in Transactions on Machine Learning Research (12/2024)
(Evaluation 2) For the second approach, employ 2 X 2 confusion matrices to compare the predicted labels of the unfair and the group-fair models. In specific, in the privileged group S = 1, individuals predicted as Y = 0 (i.e., unqualified) by the unfair model but Y = = (i.e., chosen to be qualified) by the group-fair model are considered as undesirable instances in the context of self-fulilling prophecy. Likewise, in the unprivileged group O, individuals predicted as y by the unfair model but Y by the group-fair model are similarly considered undesirable.
That is, for the risk of self-fulfilling prophecy, count the number of individuals whose prediction is undesirably flipped (i.e., # of y = 0 (Unfair) - y (Fair) for = 1, and # of y (Unfair) - y = (Fair) for S = 0). Table 11 shows that the undesirable treatments of FTM are less observed than those of basoline methods, in most cases.
Table 11: 2 2 confusion matrices comparing the predicted labels of the unfair model and the group-fair models. The encircled numbers are the counts of undesirable instances. Bold faces are the best ones and underlined oncs are the sccond bests.
Dataset (ADP)
ADuLT (0.05)
GERMMN (0.05)
DUTCH (0.15)
BANK (0.04)
Unfair
S=1
==
F=1
Y
9=1
==0
y=1
Y=
Y
Reduction
= 0
6124
629
98
1
2170
662
5220
Y
22
1701
32
3158
62
579
Reg
Y 0
6144
2198
99
8
2164
311
5265
229
2
132
25
14
3509
412
Adv
y
6121
977
95
0
2152
1127
52555
516
25
1853
33
26
2693
27
125
1364
21774
802
5279
FTM V
==1
0
966
32
2958
244
Unfaic
S 0
Y 0
Y
Y
Y
0
Reduction
3/86
13
54
4137
129
1723
Reg
0
3748
104
54
4
4300
13
128
45
0
250
0
10
63
1710
2
Adv
Y 0
3655
53
3917
125
34
1638
PTM v
3719
11
54
4217
120
10
8
29
343
0
11
146
1717
10
35
36


Reviews:
[{"review_id": "ghe1eDT0rd", "reviewer": "Reviewer_i5aw", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n1. The paper is well organized and easy to follow. \n\n2. The new point of view to formulate fairness model using transportation problem is novel to the best of my knowledge.\n\n3. Experimental results show it promising to improve fairness through solving the re-formulation into transportation problem. \n\nWeakness:\n\n1. The experiment results seem not consistently outperforming baseline methods, as shown in Figure 2.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The authors proposed that all fairness models can be reformulated as transportation problems, and vice versa. This offers a new perspective on addressing group fairness. They further suggested achieving group fairness by solving the reformulated transportation problem. Experimental results on several widely used fairness research datasets demonstrate comparable performance to mainstream baseline methods.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. Is it reasonable to add accuracy numbers in Table 2?\n\n2. Is it reasonable to show the improvement on Equalized Opportunity [1]?\n\n\n[1] Equality of Opportunity in Supervised Learning", "broader_impact_concerns": "The authors addressed broader impact very well at the end of the paper. I don't have further concerns regarding this topic.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "O3OLsquSew", "reviewer": "Reviewer_H7Dq", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n1. This work introduces a novel transport-based fairness measure, called Matched Demographic Parity, and proves theoretical support that establishes connections with existing group fairness measures, such as strong demographic parity. \n2. The manuscript is well-structured and well-written.\n\nWeaknesses:\n\nThe main limitations found in the manuscript are the following:\n1. The motivation for the work is not sufficiently clear. In the Introduction, authors say that the existing group fairness measures, such as demographic parity, only take into account statistical disparities, with no concern for how models achieve group fairness, leading to high fair models obtained in unreasonable ways. However, this is a statement that requires more justification than the one referred to in Section C of the Appendix. In fact, the example they provide has to do with possible undesirable matchings, instead of with other concrete group fairness measures.\n2. Transportation plans have been widely used to improve fairness while ensuring the accuracy of the algorithms in different settings. Authors mention in Section 2 a very brief review of some related work, but do not make it clear how they improve on it. In this sense, the experimental part of the paper lacks a more detailed comparative study with other transportation-based approaches.\n3. Also related to review issues, I am missing counterfactual fairness approaches since in fact I appreciate certain similarities with the proposed definition of Matched Demographic Parity (MDP).\n4. The proposed fairness measure of a model depends on a given transport map. Thus, I have concerns about the robustness and stability of such a measure in a practical setting, as well as the scalability when very different models have to be trained. On the other hand, with regard to implementation in real problems where there is usually a large disproportion between the protected groups in the data, I wonder about the limitations of this approach.\n5. A confusing nomenclature for fairness notions is used throughout the paper. First of all, it is not clear what fair means for the authors. In Section 3 they mention “perfectly fair group-model” and “fair group-model” without a proper explanation. It can be deduced from the context that they refer to the strong demographic parity definition, that requires that the predictions in each protected group are equally distributed, which is equivalent to some distance between the probability distributions of $f(X)|S=0$ and $f(X)|S=1$ (e.g. Wasserstein distances, TV distance or KS distance) being zero. However, they do not state this at any point in the paper. On the other hand, another issue that leads to confusion in this regard, is that later in Section 4 they consider two other very different fairness measures: subset fairness (section 4.1.) and equalized odds (section 4.2.). This makes the objective of the work very ambiguous. \n6. Results in section 3, as well as their proofs in the appendix, are interesting but it is not clear what is the benefit of using MDP instead of other strong demographic measures, such as the Total Variation or Wasserstein distances.\n7. Regarding section 4:\n    - Subset fairness seems to be closely related to individual fairness measures, therefore a brief comparison with the existing literature of this type would be useful.\n    - Theorem 4.2. establishing an upper bound for the level of subset fairness in terms of different transport costs is promising. However, the first term of RHS is the transport cost of the minimizer of the MDP, which is a different problem. Hence, I would suggest authors to elaborate more, if possible, on the computation of the \"matching function of $f$\", and also to add a discussion of the transport cost of such a map. Furthermore, I would suggest to use a more concrete name for Definition 3.4., since \"matching function\" is quite general and is used in many different contexts.\n    - In practice, the proposed algorithm for FTM is actually based on Fair Representation Learning, since they compute the OT map between the probability distributions of $X|S=0$ and $X|S=1$. Therefore, I do not see the relationship of the definition of group fairness and the subsequent result (Theorem 4.2) to the regularization approach of FTM, since the penalization is done in terms of the OT map instead of the MDP of the \"matching function of $f$\" as stated in the theorem. Moreover, the convenience for this choice of the OT map carrying the distribution towards their weighted Wasserstein barycenter, which is the minimizer of the Wasserstein variation, has been previously proven in Gordaliza et al. (2019). In this sense, I would ask the authors to include some references about FRL, in particular, to the results on the application of Wasserstein barycenters to fair classification. \n    - The procedure for the “joint OT map” in section 4.2. is not sufficiently justified theoretically and the way to measure EO in section 5.3.1. is rather debatable. EO is a two-dimensional measure and calculating the mean of the differences $|\\mathbb{E}(f_0(\\mathbf{X}))|S=0, Y=y) - \\mathbb{E}(f_1(\\mathbf{X}))|S=1, Y=y)|  $, for $y=0,1$, may not be a very robust and informative indicator. Without sufficient support for the use of this definition, the results of experiments may not be entirely reliable.\n\nSome additional minor comments:\n\n8. Final paragraph in sections 4.1. and 4.2. is exactly the same, so it could be expressed in a more concise way to ease the reading.\n\n9. Authors should clarify the order of the Wasserstein distance, since both 1 and 2 have been widely used in fair learning.\n\n10. In Section 5: work -> works\n11. Notation: I do not find it appropriate to use the symbol Delta for the fairness measure.\n12. Proposition 3.1. is in fact a Corollary of Theorem 3.3. As the authors say in the proof, it is a particular case of the Theorem, for which Assumptions (C1) and (C2) are also needed. \n13. Title of 3.2. would be more informative with the full name of the algorithm.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The authors introduce a regularization approach for group fairness in the binary classification setting based on a new group fairness measure called Matched Demographic Parity, which quantifies the averaged difference between predictions of two individuals coming from different protected groups who are matched by a given transport map. They provide an algorithm, called Fairness Through Matching (FTM), that learns group fair classifiers and is dependent on the choice of the transport map. Two different choices of the transport map are proposed. The first one aims at minimizing the transport cost while obtaining both group and subset fairness. The second one also considers the similarity in the target variable, in order to improve the prediction accuracy. The authors justify their approach theoretically and present empirical results from experiments on several benchmark datasets.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Please, see the detailed weaknesses above.", "broader_impact_concerns": "None", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "byltVYDer5", "reviewer": "Reviewer_MW9E", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "# Strength\n\n- The authors observe an interesting connection between the DP and optimal transportation. That is, a group-fair model corresponds to an implicit transport map between the input spaces conditional on the sensitive group. \n- The main idea is clearly delivered.\n- The theoretical results seems to be sound, though the presentation and proof is quite sloppy. \n\n# Weakness\n\n(i) The biggest concern is that, Thm 3.3 and 3.5 actually reflect that the fairness of a model is equivalent to the performance of the optimal transport map. As a result, optimizing fairness is transformed to finding this optimal transport map, which does not essentially make the problem easier. To apply FTM, the practitioner has to pre-specify a mapping, which can be sub-optimal choice, e.g., an identity mapping, which leads to an undesirable accuracy-fairness trade-off. In a word, FTM seems not improving the efficiency to find a fair model. This is confirmed by the experiment results, where FTM typically is not the method with the best accuracy-fairness trade-off curve.\n\n(ii) The writing should be improved to enhance readability, especially on the theoretical statements and proofs. I name a few below:\n  1. Key definitions or quantities should be clearly defined to keep the paper self-contained, instead of referring to other works. Examples include transport map and push-forward measure in Section 2.3, and exact definition of Wasserstein distance, total variation, and K-S distance in Section 2.2.\n  2. The proof of Prop 3.1 depends on Theorem 3.3, which has two assumptions. However, those assumptions are not mentioned in Prop 3.1 and its implications.\n  3. Following point 2. The first condition (C1) that $F$ is bounded is automatically satisfied under this paper's setting, as $f$ predict a probability that belongs to $[0, 1]$. So (C1) is unnecessary. The second condition (C2), however, might be too strong to be practical. It requires that input $X$ has a absolutely continuous distribution, which is not satisfied for any categorical variables. For example, all datasets used in the experiments contains personal attributes such as gender, which is non-continuous. \n  4. In Prop 3.1, the writing of $T_s = T_s(f)$ is confusing. I think the authors meant that for each $f$ there exist a correspond transport map. Using $T_s^f$ instead of $T_s(f)$, and define symbol instead of equal symbol, will eliminate this misunderstanding.\n  5. The implication of Prop 3.1 also required more thinking. In particular, is this $T_s^f$ unique? \n  6. In Def 3.4, does there exist a $T_s^f$ that achieves the minimum? \n  7. The proof is too sloopy, with a bunch of undefined or not well-defined notations, such as $\\Delta F_s(t)$, $\\lfloor \\delta \\rfloor$, $F^{const}((v_{k-1}, v_k])$, etc. Without explanation, A CDF does not take an interval as the variable; $\\lfloor \\delta \\rfloor$ is understood as the floor of $\\delta$, which equals zero for $\\delta<1$ and makes proof invalid.\n\n(iii) The authors consider the setting with a single binary group and using DP as the fairness metric. Does the main observation and proposed method apply to more general scenarios? For example, multiple sensitive groups, multi-category group, and other fairness metrics such as equal opportunity, equalized odds, and calibration? The authors should discuss those limitations.\n\n(iv) There are several papers mentioned by the authors that also apply optimal transportation to address model fairness issue. As those are highly related, the authors should clearly state the contributions of existing work and the difference from them with more details.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This work showed that the model fairness regarding two sensitive groups, in terms of demographic parity (DP), is connected with the degree of match between the model outputs conditional on these two groups, up to a transport map on the input space. Specifically, the authors proposed Matched Demographic Parity (MDP) as a surrogate of strong DP. A small MDP guarantees a small DP and vice versa. The proposed algorithm Fairness Through Matching (FTM), which optimizes the empirical loss with a MDP penalty, can improve the subset-level fairness by properly specifying the transport map.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Please see the weakness part above. The most critical issues are:\n1. Point (i), what is the particular advantage of FTM compared to other methods? As there is no particular guide to select the optimal transport map, and ad hoc choices such as marginal or joint distribution do not offer better accuracy-fairness trade-off.\n2. The assumptions and proofs of all theoretical results should be reviewed throughly.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: Three reviewers recommended acceptance.

The reviewers raised several concerns, including the need for more details about existing works that use the optimal transport map for algorithmic fairness, particularly the work of Gordaliza et al. (2019), which is notably similar in applying the optimal transport map to the input space. Additionally, they requested further experimental results comparing the proposed method with fair representation learning approaches, including Gordaliza et al. (2019). Improvements to the writing were also suggested to enhance readability, especially regarding the theoretical statements and proofs.

These concerns were sufficiently addressed during the rebuttal period and are reflected in the revised manuscript.
Decision: Accept (poster)