# Post-Fair Federated Learning: Achieving Group and Community Fairness
in Federated Learning via Post-processing

Yuying Duan  Yijun Tian  Nitesh Chawla  Michael Lemmon

###### Abstract

Federated Learning (FL) is a distributed machine learning framework in which a
set of local communities collaboratively learn a shared global model while
retaining all training data locally within each community. Two notions of
fairness have recently emerged as important issues for federated learning:
group fairness and community fairness. Group fairness requires that a model’s
decisions do not favor any particular group based on a set of legally
protected attributes such as race or gender. Community fairness requires that
global models exhibit similar levels of performance (accuracy) across all
collaborating communities. Both fairness concepts can coexist within an FL
framework, but the existing literature has focused on either one concept or
the other. This paper proposes and analyzes a post-processing _fair federated
learning_ (FFL) framework called _post-FFL_. Post-FFL uses a linear program to
simultaneously enforce group and community fairness while maximizing the
utility of the global model. Because Post-FFL is a post-processing approach,
it can be used with existing FL training pipelines whose convergence
properties are well understood. This paper uses post-FFL on real-world
datasets to mimic how hospital networks, for example, use federated learning
to deliver community health care. Theoretical results bound the accuracy lost
when post-FFL enforces both notion of fairness. Experimental results
illustrate that post-FFL simultaneously improves both group and community
fairness in FL. Moreover, post-FFL outperforms the existing in-processing fair
federated learning in terms of improving both notions of fairness,
communication efficiency and computation cost.

Machine Learning, ICML

††footnotetext: 1 University of Notre Dame, {yduan2, ytian5, nchawla,
<EMAIL_ADDRESS>

##  1 Introduction

Federated Learning (FL) (McMahan et al., 2017) is a distributed machine
learning framework that uses data collected from a group of community
_clients_ to learn a global model that can be used by all clients in the
group. The communities served by these clients are formed from sets of remote
users (e.g. mobile phones) or organizations (e.g. medical clinics and
hospitals) that all share some defining attribute such as a similar
geographical location. FL algorithms such as FedAvg (McMahan et al., 2017)
train the global model in a distributed manner by first having each community
client use its local data to train a local model. This local model is then
sent to the cloud server who averages these models and sends the averaged
model back to the community clients who then retrain that model with their
local data. This interaction between the clients and server continues for a
several update cycles until it converges on a global model that is agreeable
to all clients. While there were no theoretical convergence guarantees with
the original FL algorithm (McMahan et al., 2017), subsequent analysis (Smith
et al., 2018; Li et al., 2020) did provide theoretical convergence analysis
for this FL training pipeline. Since then FL has come to be a dominant
framework for distributed machine learning (Kairouz et al., 2021),
particularly in smart city (Jiang et al., 2020; Zheng et al., 2022; Qolomany
et al., 2020; Pandya et al., 2023) and smart healthcare applications (Rieke et
al., 2020; Nguyen et al., 2022; Antunes et al., 2022; Brisimi et al., 2018) .

This paper considers two related notions of fairness relevant to federated
learning: Group Fairness and Community Fairness. Group fairness (Dwork et al.,
2012; Hardt et al., 2016; Zafar et al., 2017) is concerned with achieving
similar outcomes for groups defined by legally protected (a.k.a. sensitive)
attributes such as race or gender. For community fairness (Li et al., 2019;
Gross, 2007, 2008), a community may consist of individuals living in the same
geographic location. Community fairness, therefore, is more concerned with
ensuring that these geographically distinct communities have equal access to
resources. Group fairness, on the other hand, requires that all individuals
with the same legally protected attribute receive the same benefits as those
outside of the protected group regardless of their membership in these
geographically distinct communities or neighborhoods. Both fairness concepts
(group vs. community) are relevant to federated learning. This is particularly
true in smart healthcare applications where a physician’s decisions should not
be influenced by factors such as age, race, or gender (Parsa-Parsi, 2017) and
yet city leaders want to ensure that all geographically distinct neighborhoods
perceive they have the same accessibility to adequate health care. Whether one
can balance these two fairness concepts in an FL platform and what might be
the cost of attaining such balance is the main topic of this paper.

This paper defines group fairness with respect to Equal Opportunity (EO)
(Hardt et al., 2016) and community fairness with respect to Fair Resource
Allocation (Li et al., 2019). EO ensures that those who deserve services
receive them in a manner that is independent of any sensitive attributes. Fair
Resource Allocation requires the likelihood of accurate outcomes to be uniform
across all participating communities. We apply EO to group fairness because
most legal standards, such as those from the Equal Employment Opportunity
Commission (Peck, 1975), mandate that the true positive rate be consistent
across sensitive attributes. However, EO may not be appropriate for
communities that receive resources (services or infrastructure) from the city.
EO focuses exclusively on individuals who deserve to benefit from resources
(true positives), without preventing unqualified individuals from receiving
resources. It could lead to surplus resource allocation in some communities.
One example of this scenario might be seen in health care delivery, where a
hospital network sees that the number of clinics per capita is equal between
rural and urban residents. However, rural residents may still perceive
inequality because the effort required to access these clinics (distance
traveled) is much greater than that of the urban dwellers. Fair Resource
Allocation considers both true positives and true negatives across all
communities. This paper examines whether it is possible to achieve Equal
Opportunity and Fair Resources Allocation in federated learning and seeks to
estimate the cost we incur in achieving both fairness objectives.

Several recent papers have proposed methods for achieving either group or
community fairness in federated learning. The methods fall into three
categories: pre-processing, in-processing, and post-processing. Pre-processing
techniques achieve model fairness by modifying the data set used to train the
model. This may be done by weighting the training samples as described in
(Abay et al., 2020). Pre-processing techniques, however, cannot simultaneously
address group and community fairness. In-processing techniques typically
modify the federated learning framework’s optimization algorithms. Current
approaches either employ dynamic aggregation weights (Yue et al., 2023;
Ezzeldin et al., 2023; Chu et al., 2021; Rodríguez-Gálvez et al., 2021; Lyu et
al., 2020; Li et al., 2019) or use adversarial training (Du et al., 2021;
Mohri et al., 2019). These approaches, however, complicate the existing FL
training pipeline and lack formal convergence guarantees. Our paper is the
first to apply post-processing in FL. Post-processing uses models selected by
an existing training pipeline to generate a randomized model that achieves
fairness. Prior post-processing work (Hardt et al., 2016; Fish et al., 2016;
Menon & Williamson, 2017; Pleiss et al., 2017; Chzhen et al., 2019; Denis et
al., 2021; Zhao & Gordon, 2022; Zeng et al., 2022; Xian et al., 2023) does not
consider federated learning (FL), nor does it simultaneously address community
and group fairness, which is the subject of this paper.

This paper’s novel contributions are:

  * •

The first application of the post-processing technique in federated learning
to improve fairness.

  * •

Development of a post-processing fair FL framework (post-FFL) that
simultaneously enforces group fairness, i.e, Equal Opportunity and community
fairness, i.e., Fair Reources Allocation in both binary and multi-class
classification.

  * •

Results that characterize when post-processing can simultaneously achieve
group and community fairness for a given group of communities.

  * •

Results that enable the evaluation of the model’s accuracy loss when achieving
group and community fairness.

  * •

Finally, experimental results on a real-world dataset that show our framework
outperforms existing baselines in improving both notions of fairness,
communication efficiency and computational cost.

##  2 Preliminary Definitions

This section provides a statistical interpretation of group and community
fairness that allows us to address fairness issues in the federated learning
of models that predict outcomes for individuals in a group of communities. The
community group is a collection of geographically distinct human communities.
Each community is a _client_ that uses the local data it has on its
inhabitants to select a local model that predicts health outcomes for a given
inhabitant. All community clients send their local models to a global _server_
who then aggregates the models into a global model. The resulting global
model, however, may not be fair either with respect to group or community
notions defined below. The main problem is to find a way to _transform_ the
global model into a _fair global model_. Since this transformation is done
after the FL pipeline has selected the global model, this is a post-processing
approach to achieving fairness.

_Notational Conventions:_ This paper will denote random variables using upper
case letters, $X$, and lower case letters, $x$ will denote instances of those
random variables. A random variable’s distribution will be denoted as $F_{X}$
and an instance, $x$, drawn from that distribution will be denoted as $x\sim
F_{X}$. Bold face lower case symbols will be reserved for vectors and bold
face upper case symbols will be reserved for matrices.

To formalize our statistical setup, we first need to define the notion of a
community group.

######  Definition 2.1.

A community group consists of $K$ geographically distinct communities that we
formally represent as a tuple of jointly random variables, $D=(X,A,C,Y)$ with
probability distribution
$F_{D}:\mathcal{X}\times\mathcal{A}\times\mathcal{C}\times\mathcal{Y}\rightarrow[0,1]$.
An instance of the community group, $(x,a,c,y)$, is called an individual where
$x\in\mathcal{X}$ is the individual’s private data vector,
$a\in\mathcal{A}=\\{0,1\\}$ denotes the individual’s protected sensitive
attribute, and $c\in\mathcal{C}=\\{1,2,\ldots,K\\}$ denotes which community
the individual belongs to. The other value, $y\in\mathcal{Y}=\\{0,1\\}$
denotes the individual’s _qualified outcome_.

The variables in definition 2.1 have concrete interpretations in a community
health application. Each community is a geographically distinct neighborhood
served by a single health clinic. For an individual $(x,a,c,y)\sim F_{D}$, the
variable $x$ represents that individual’s private health data, $a$ may
represent a protected attribute such as race or gender, $c$ is the
individual’s local health clinic. Finally $y$ represents whether or not the
individual is ill and is therefore ”qualified” to access medical resources to
treat that illness.

We are interested in selecting an outcome predictor,
$\widehat{Y}:\mathcal{X}\times\mathcal{A}\times\mathcal{C}\rightarrow\mathcal{Y}$
for community group $D$ such that for any individual $(x,a,c,y)\sim F_{D}$ we
have $\widehat{Y}(x,a,c)=y$ with a high probability. In particular, let
$(1-\Delta)\in(0,1)$ denote a specified accuracy level, then the outcome
predictor is $\Delta$-accurate if ${\rm
Pr}_{D}\left\\{\widehat{Y}(X,A,C)=Y\right\\}\geq 1-\Delta$. With these
definitions and notational conventions we can now formalize the specific
notions of group fairness and community fairness.

######  Definition 2.2.

The outcome predictor
$\widehat{Y}:\mathcal{X}\times\mathcal{A}\times\mathcal{C}\rightarrow\mathcal{Y}$
for community group $D$ satisfies equal opportunity if and only if

$\begin{split}{\rm
Pr}_{D}\left\\{\widehat{Y}(X,A,C)=1\,|\,Y=1,A=1\right\\}={\rm
Pr}_{D}\left\\{\widehat{Y}(X,A,C)=1\,|\,Y=1,A=0\right\\}\end{split}$ (1)

Definition 2.2 asserts that the probability of the outcome predictor correctly
predicting a positive outcome for an individual $(x,a,c,y)$ from $D$ who
qualifies for the positive outcome (i.e. $y=1$) is independent of the
individual’s protected attribute $a$.

######  Remark 2.3.

This paper defines group fairness in terms of Equal Opportunity over the
global distribution. It solves a different problem than (Chu et al., 2021),
which focuses fairness over each local distribution. Global fairness and local
fairness are not equivalent. See the Appendix A for more details.

######  Definition 2.4.

The outcome predictor
$\widehat{Y}:\mathcal{X}\times\mathcal{A}\times\mathcal{C}\rightarrow\mathcal{Y}$
for community group $D$ satisfies community fairness if and only if for any
$j,k\in\mathcal{C}$, we have

$\begin{split}{\rm Pr}_{D}\left\\{\widehat{Y}(X,A,C)=Y\,|\,C=j\right\\}={\rm
Pr}_{D}\left\\{\widehat{Y}(X,A,C)=Y\,|\,C=k\right\\}\end{split}$ (2)

Definition 2.4 asserts that the probability of the outcome predictor correctly
predicting an individual’s qualified outcome is independent of which community
the individual belongs to.

This paper develops a post-processing FL algorithm that selects an outcome
predictor
$\widetilde{Y}:\mathcal{X}\times\mathcal{A}\times\mathcal{C}\rightarrow\mathcal{Y}$
that satisfies both _community fairness_ and _group fairness_. If a
$\Delta$-accurate predictor exists that achieves community and group fairness
on community group $D$, then we say the community group is
$\Delta$-equalizable. This paper will also establish necessary conditions for
a community group to be $\Delta$-equalizable.

##  3 Achieving Group and Community Fairness

Let $D=(X,A,C,Y)$ be a community group and consider the loss function
$\ell:\mathcal{Y}\times\mathcal{Y}\rightarrow\\{0,1\\}$ that takes values

$\displaystyle\ell(\widetilde{y},y)=\mathbbm{1}(\widetilde{y}\neq y)$ (3)

for any $\widetilde{y},y\in\mathcal{Y}$, where $\mathbbm{1}(\cdot)$ is the
indicator function. A fair outcome predictor is any map
$\widetilde{Y}:\mathcal{X}\times\mathcal{A}\times\mathcal{C}\rightarrow\mathcal{Y}$
that satisfies the equal opportunity equation (1) and community fairness
equation (2) with respect to community group $D$. The following proposition
asserts that if an outcome predictor $\widetilde{Y}$ satisfies the following
optimization problem in equation (8), then $\widetilde{Y}$ must be a fair
outcome predictor with respect to community group $D$.

######  Proposition 3.1.

Consider the community group, $D=(X,A,C,Y)$, and the binary loss function,
$\ell$, in equation (3). If the outcome predictor
$\widetilde{Y}:\mathcal{X}\times\mathcal{A}\times\mathcal{C}\rightarrow\mathcal{Y}$
satisfies the following optimization problem

$\displaystyle\begin{array}[]{ll}\text{minimize}&\mathbb{E}_{D}\left[\ell(\widetilde{Y}(X,A,C),Y)\right]\\\
\text{with respect
to}&\widetilde{Y}:\mathcal{X}\times\mathcal{A}\times\mathcal{C}\rightarrow\mathcal{Y}\\\
\text{subject to}&{\rm Pr}_{D}(\widetilde{Y}(X,A,C)=1\,|\,Y=1,A=0)={\rm
Pr}_{D}(\widetilde{Y}(X,A,C)=1\,|\,Y=1,A=1),\\\ &\text{${\rm
Pr}_{D}(\widetilde{Y}(X,A,C)=Y\,|\,C=j)$}=\text{${\rm
Pr}_{D}(\widetilde{Y}(X,A,C)=Y\,|\,C=k)$,}\quad\forall
j,k\in\mathcal{C}\end{array}$ (8)

then $\widetilde{Y}$ is a fair outcome predictor.

Proof: Any $\widetilde{Y}$ that solves optimization problem must satisfy the
given constraints. Since these constraints are equation (1) and (2) for equal
opportunity and community fairness, respectively, the outcome predictor must
also be fair with respect to community group $D$. $\diamondsuit$

It is not yet clear if the optimization problem in equation (8) actually has a
solution. To obtain conditions for the existence of a fair outcome predictor,
we will first show that equation (8) can be recast as a linear program. The
existence of a fair outcome predictor is then equivalent to that linear
program having non-negative solutions.

Let
$\widehat{Y}:\mathcal{X}\times\mathcal{A}\times\mathcal{C}\rightarrow\mathcal{Y}$
be an _optimal_ outcome predictor that minimizes the expected value of the
indicator loss function in equation (3) with respect to community group $D$.
For notational convenience we will drop the arguments on the outcome
predictors so we write $\widehat{Y}(X,A,C)$ (or $\widetilde{Y}(X,A,C))$ as
$\widehat{Y}$ (or $\widetilde{Y}$). For convenience we introduce the following
notational conventions for the optimal outcome predictor’s joint probability
of false or true positives and negatives:

$\begin{split}{\rm FN}^{ac}&={\rm
Pr}_{D}\left\\{\widehat{Y}=0,Y=1,A=a,C=c\right\\}\\\ {{\rm TN}}^{ac}&={\rm
Pr}_{D}\left\\{\widehat{Y}=0,Y=0,A=a,C=c\right\\}\\\ {\rm FP}^{ac}&={\rm
Pr}_{D}\left\\{\widehat{Y}=1,Y=0,A=a,C=c\right\\}\\\ {\rm TP}^{ac}&={\rm
Pr}_{D}\left\\{\widehat{Y}=1,Y=1,A=a,C=c\right\\}\\\ \end{split}$ (9)

We will also find it convenient to define the following statistics for the
group community, $D$.

$\begin{split}p_{c}&={\rm Pr}_{D}(C=c)\\\ \alpha&={\rm Pr}_{D}(Y=1\,,\,A=0)\\\
\beta&={\rm Pr}_{D}(Y=1\,,\,A=1)\end{split}$ (10)

$p_{c}$ is the probability of a random individual being in community $c$,
$\alpha$ is the probability of a random individual being qualified and non-
sensitive and $\beta$ is the probability of a random individual being
qualified and sensitive.

Finally, the variables we will use to characterize our fair outcome predictor,
$\widetilde{Y}$, will be

$\displaystyle z^{ac}_{j}$ $\displaystyle=$ $\displaystyle{\rm
Pr}_{D}\left\\{\widetilde{Y}=\widehat{Y}\,|\,\widehat{Y}=j,A=a,C=c\right\\}$
(11)

So $z^{ac}_{j}$ is the probability that the fair predictor’s outcome,
$\widetilde{Y}$, equals that of the optimal predictor’s outcome,
$\widehat{Y}$, for an individual, $(x,a,c,y)$, for which the optimal
predictor’s output is $j\in\mathcal{Y}$, the sensitive attribute is
$a\in\mathcal{A}$ and the community label is $c\in\mathcal{C}$.

######  Proposition 3.2.

(Appendix C.1) Let $\mathbf{z}\in\mathbb{R}^{4K}$ satisfy the following linear
program (LP)

$\displaystyle\begin{array}[]{ll}\mbox{minimize:}&\mathbf{c}^{T}\mathbf{z}\\\
\mbox{with respect to:}&\mathbf{z}\in\mathbb{R}^{4K}\\\ \mbox{subject
to:}&\mathbf{Az}=\mathbf{b}\\\ &0\leq\mathbf{z}\leq 1\end{array}$ (16)

where

$\displaystyle\mathbf{c}^{T}$ $\displaystyle=$
$\displaystyle\left[\begin{array}[]{cccc}\mathbf{c}_{1}^{T}&\mathbf{c}_{2}^{T}&\cdots&\mathbf{c}^{T}_{K}\end{array}\right]$
$\displaystyle\mathbf{z}^{T}$ $\displaystyle=$
$\displaystyle\left[\begin{array}[]{cccc}\mathbf{z}_{1}^{T}&\mathbf{z}_{2}^{T}&\cdots&\mathbf{z}^{T}_{K}\end{array}\right]$
$\mathbf{A}={\displaystyle\left[\begin{array}[]{cccccc}\mathbf{m}_{1}^{T}&\mathbf{m}_{2}^{T}&\mathbf{m}_{3}^{T}&\cdots&\mathbf{m}^{T}_{K-1}&\mathbf{m}^{T}_{K}\\\
-\frac{K-1}{K}\mathbf{n}_{1}^{T}&\frac{1}{K}\mathbf{n}_{2}^{T}&\frac{1}{K}\mathbf{n}_{3}^{T}&\cdots&\frac{1}{K}\mathbf{n}_{K-1}^{T}&\frac{1}{K}\mathbf{n}_{K}^{T}\\\
\frac{1}{K}\mathbf{n}_{1}^{T}&-\frac{K-1}{K}\mathbf{n}_{2}^{T}&\mathbf{n}_{3}^{T}&\cdots&\frac{1}{K}\mathbf{n}_{K-1}^{T}&\frac{1}{K}\mathbf{n}_{K}^{T}\\\
\frac{1}{K}\mathbf{n}_{1}^{T}&\frac{1}{K}\mathbf{n}_{2}^{T}&-\frac{K-1}{K}\mathbf{n}_{3}^{T}&\cdots&\frac{1}{K}\mathbf{n}_{K-1}^{T}&\frac{1}{K}\mathbf{n}_{K}^{T}\\\
\vdots&\vdots&\vdots&\ddots&\vdots&\vdots\\\
\frac{1}{K}\mathbf{n}_{1}^{T}&\frac{1}{K}\mathbf{n}_{2}^{T}&\frac{1}{K}\mathbf{n}_{3}^{T}&\cdots&-\frac{K-1}{K}\mathbf{n}^{T}_{K-1}&\frac{1}{K}\mathbf{n}^{T}_{K}\\\
\frac{1}{K}\mathbf{n}_{1}^{T}&\frac{1}{K}\mathbf{n}_{2}^{T}&\frac{1}{K}\mathbf{n}_{3}^{T}&\cdots&\frac{1}{K}\mathbf{n}^{T}_{K-1}&-\frac{K-1}{K}\mathbf{n}^{T}_{K}\end{array}\right]}$
$\displaystyle\mathbf{b}^{T}$ $\displaystyle=$
$\displaystyle\left[\begin{array}[]{ccccc}{\displaystyle\sum_{c=1}^{K}\left(\frac{{\rm
FN}^{1c}}{\beta}-\frac{{\rm
FN}^{0c}}{\alpha}\right)}&{\displaystyle\frac{1}{K}\sum_{c=1}^{K}(b_{1}-b_{c})}&{\displaystyle\frac{1}{K}\sum_{c=1}^{K}(b_{2}-b_{c})}&\cdots&{\displaystyle\frac{1}{K}\sum_{c=1}^{K}(b_{K}-b_{c})}\end{array}\right]$

with

$\displaystyle\mathbf{c}_{i}^{T}$ $\displaystyle=$
$\displaystyle\left[\begin{array}[]{cccc}({\rm FN}^{0i}-{\rm TN}^{0i})&({\rm
FP}^{0i}-{\rm TP}^{0i})&({\rm FN}^{1i}-{\rm TN}^{1i})&({\rm FP}^{1i}-{\rm
TP}^{1i})\end{array}\right]$ $\displaystyle\mathbf{n}_{i}^{T}$
$\displaystyle=$ $\displaystyle\frac{1}{p_{i}}\left[\begin{array}[]{cccc}({\rm
FN}^{0i}-{\rm TN}^{0i})&({\rm FP}^{0i}-{\rm TP}^{0i})&({\rm FN}^{1i}-{\rm
TN}^{1i})&({\rm FP}^{1i}-{\rm TP}^{1i})\end{array}\right]$
$\displaystyle\mathbf{z}_{i}^{T}$ $\displaystyle=$
$\displaystyle\left[\begin{array}[]{cccc}z_{0}^{0i}&z_{1}^{0i}&z_{0}^{1i}&z_{1}^{1i}\end{array}\right]$
$\displaystyle\mathbf{m}_{i}^{T}$ $\displaystyle=$
$\displaystyle\left[\begin{array}[]{cccc}\frac{-{\rm
FN}^{0i}}{\alpha}&\frac{{\rm TP}^{0i}}{\alpha}&\frac{{\rm
FN}^{1i}}{\beta}&\frac{-{\rm TP}^{1i}}{\beta}\end{array}\right]$
$\displaystyle b_{i}$ $\displaystyle=$ $\displaystyle\frac{1}{p_{i}}({\rm
TN}^{0i}+{\rm TP}^{0i}+{\rm TN}^{1i}+{\rm TP}^{1i})$

for $i=1,2,\cdots K$.

Let the solution of the linear program $\mathbf{z}$ be:

$\displaystyle\mathbf{z}^{T}$ $\displaystyle=$
$\displaystyle\left[\begin{array}[]{cccc}\mathbf{z}_{1}^{T}&\mathbf{z}_{2}^{T}&\cdots&\mathbf{z}^{T}_{K}\end{array}\right]$

with

$\displaystyle\mathbf{z}_{i}^{T}$ $\displaystyle=$
$\displaystyle\left[\begin{array}[]{cccc}z_{0}^{0i}&z_{1}^{0i}&z_{0}^{1i}&z_{1}^{1i}\end{array}\right]$

Then the outcome predictor
$\widetilde{Y}_{\widehat{Y},\mathbf{z}}:\mathcal{X}\times\mathcal{A}\times\mathcal{C}\rightarrow\mathcal{Y}$
taking values

$\begin{split}\quad\quad&\widetilde{Y}_{\widehat{Y},\mathbf{z}}(x,a,c)=\begin{cases}0&\text{with
probability }z_{0}^{ac}\\\ 1&\text{with probability
}1-z_{0}^{ac}\end{cases}\quad\text{if }\widehat{Y}(x,a,c)=1\\\ \text{or}\\\
\quad\quad&\widetilde{Y}_{\widehat{Y},\mathbf{z}}(x,a,c)=\begin{cases}1&\text{with
probability }z_{1}^{ac}\\\ 0&\text{with probability
}1-z_{1}^{ac}\end{cases}\quad\text{if }\widehat{Y}(x,a,c)=0\\\ \end{split}$

is a fair outcome predictor.

######  Remark 3.3.

Our post-FFL algorithm can be extended to multi-class classification tasks,
i.e., $\mathcal{Y}=\\{1,2,\cdots,N\\}$. The linear program for multi-class
classification is detailed in Appendix B.

######  Remark 3.4.

In general, we may not necessarily need to achieve strictly identical
performance across all communities. It is worth noting that the optimization
shown in (16) can incorporate a more relaxed version of equal opportunity and
community fairness constraints.

$\begin{split}|{\rm Pr_{D}}(\tilde{Y}=1|Y=1,A=0)-{\rm
Pr_{D}}(\tilde{Y}=1|Y=1,A=1)|&\leq\epsilon\\\ \forall k\in\mathcal{C},|{\rm
Pr}(\widetilde{Y}\neq Y|C=k)-\frac{1}{K}\sum_{c=1}^{K}{\rm
Pr}(\widetilde{Y}\neq Y|C=c)|&\leq\delta\end{split}$ (26)

In such cases, the linear program with the relaxed fairness constraints is:

$\displaystyle\begin{array}[]{ll}\mbox{minimize:}&\mathbf{c}^{T}\mathbf{z}\\\
\mbox{with respect to:}&\mathbf{z}\in\mathbb{R}^{4K}\\\ \mbox{subject
to:}&\mathbf{b}-\boldsymbol{\epsilon}\leq\mathbf{Az}\leq\mathbf{b}+\boldsymbol{\epsilon}\\\
&0\leq\mathbf{z}\leq 1\end{array}$ (31)

where,

$\displaystyle\boldsymbol{\epsilon}^{T}$ $\displaystyle=$
$\displaystyle\left[\begin{array}[]{cccc}\epsilon&\delta&\cdots&\delta\end{array}\right]$

By solving the linear program with different
$\boldsymbol{\epsilon}\in\mathbbm{R}^{(K+1)}$, we can precisely control the
degree of community fairness and group fairness, setting
$\boldsymbol{\epsilon}=\mathbf{0}$ gives us the outcome predictor that
strictly satisfies equal opportunity and community fairness.$\diamondsuit$

We can write the linear program (16) in the standard form by introducing a set
of slack variables $\mathbf{s}\in\mathbb{R}^{4K}$:

$\displaystyle\mathbf{s}^{T}$ $\displaystyle=$
$\displaystyle\left[\begin{array}[]{cccc}\mathbf{s}_{1}^{T}&\mathbf{s}_{2}^{T}&\cdots&\mathbf{s}^{T}_{K}\end{array}\right]$

with

$\displaystyle\mathbf{s}_{i}^{T}$ $\displaystyle=$
$\displaystyle\left[\begin{array}[]{cccc}s_{0}^{0i}&s_{1}^{0i}&s_{0}^{1i}&s_{1}^{1i}\end{array}\right]$

The variables we need to solve for in linear program (16) represent
probabilities, thus, $0\leq z_{j}^{ac}\leq 1$. It is equivalent to:

$\begin{split}z_{j}^{ac}+s_{j}^{ac}&=1\\\ z_{j}^{ac},s_{j}^{ac}&\geq
0\end{split}$ (35)

Combine the linear program (16) with (35), the standard form of the linear
program (16) is:

$\displaystyle\begin{array}[]{ll}\mbox{minimize:}&\mathbf{\bar{c}}^{T}\mathbf{\bar{z}}\\\
\mbox{with respect to:}&\mathbf{\bar{z}}\in\mathbb{R}^{8K}\\\ \mbox{subject
to:}&\mathbf{\bar{A}\bar{z}}=\mathbf{\bar{b}}\\\ &\mathbf{\bar{z}}\geq
0\end{array}$ (40)

with

$\displaystyle\mathbf{\bar{c}}^{T}$ $\displaystyle=$
$\displaystyle\left[\begin{array}[]{cccc}\mathbf{c}^{T}&\mathbf{0}\end{array}\right]\in\mathbb{R}^{8K}$
$\displaystyle\mathbf{\bar{z}}^{T}$ $\displaystyle=$
$\displaystyle\left[\begin{array}[]{cccc}\mathbf{z}^{T}&\mathbf{s}^{T}\end{array}\right]\in\mathbb{R}^{8K}$
$\displaystyle\mathbf{\bar{A}}$ $\displaystyle=$
$\displaystyle\left[\begin{array}[]{cc}\mathbf{A}&\mathbf{0}\\\
\mathbf{I}&\mathbf{I}\end{array}\right]\in\mathbb{R}^{(5K+1)\times 8K}$
$\displaystyle\mathbf{\bar{b}}^{T}$ $\displaystyle=$
$\displaystyle\left[\begin{array}[]{cccc}\mathbf{b}^{T}&\mathbf{1}_{4K}^{T}\end{array}\right]\in\mathbb{R}^{5K+1}$

where $\mathbf{1}_{4K}\in\mathbb{R}^{4K}$ is all $1$ vector.

######  Theorem 3.5.

(Appendix C.2) The linear program (40) always has non-negative solutions.

Theorem 3.5 indicates that the linear program (16), which is equivalent to
(40), always has a solution. Thus, there always exists fair outcome predictors
satisfying both equal opportunity and community fairness. We next demonstrate
the necessary conditions for the existence of a $\Delta$-accurate fair outcome
predictor. An outcome predictor:
$\widetilde{Y}:\mathcal{X}\times\mathcal{A}\times\mathcal{C}\rightarrow\mathcal{Y}$
is a $\Delta$-accurate fair outcome predictor if:

$\begin{split}{\rm Pr}_{D}(\widetilde{Y}\neq Y)&\leq\Delta\\\ {\rm
Pr}_{D}(\widetilde{Y}=1|Y=1,A=0)&={\rm Pr}_{D}(\widetilde{Y}=1|Y=1,A=1)\\\
\forall k\in\mathcal{C},{\rm Pr}_{D}(\widetilde{Y}\neq
Y|C=k)&=\frac{1}{K}\sum_{c=1}^{K}{\rm Pr}_{D}(\widetilde{Y}\neq
Y|C=c)\end{split}$ (45)

######  Theorem 3.6.

(Appendix C.3) The three conditions in (45) cannot hold simultaneously if
$\Delta<-\|\mathbf{\bar{c}}\|_{\infty}\frac{\|\mathbf{\bar{A}}^{T}\mathbf{\bar{b}}\|_{2}}{\underline{\sigma}^{2}}+\sum_{c=1}^{K}({\rm
TN}^{0c}+{\rm TP}^{0c}+{\rm TN}^{1c}+{\rm TP}^{1c})$ , where,
$\underline{\sigma}$ is the smallest singular value of the matrix
$\mathbf{\bar{A}}$.

Theorem 3.6 establishes a necessary condition for the existence of an
$\Delta$-accurate fair outcome predictor, based on the statistics of the data
represented by $\mathbf{\bar{A}},\mathbf{\bar{b}},\mathbf{\bar{c}}$. The
following theorem estimates the accuracy lost in a
$\boldsymbol{\epsilon}$-relaxed fair predictor.

######  Theorem 3.7.

(Appendix C.4) Let $\mathbf{z}\in\mathbbm{R}^{4K}$ be the solution of the
linear program (31) with a predefined $\boldsymbol{\epsilon}$, then the
minimum accuracy we lose for improving both community fairness and group
fairness under post-FFL is $\mathbf{c}^{T}(\mathbf{z}-\mathbf{1}_{4k})$,
where, $\mathbf{1}_{4K}$ is all $1$ vector.

Theorem 3.7 above can serve as a tool for evaluating the accuracy we lose for
improving group fairness and community fairness

##  4 Post-FFL: Fair Outcome Predictor in FL

This section shows how the linear program (16) can be used within a federated
learning framework to construct a fair outcome predictor. An overview of post-
FFL is shown in Fig. 1. The black arrows illustrate the exchange of local
model’s parameters and the global model’s parameters during FedAvg training.
The blue arrows depict the post-processing workflow following FedAvg, where
local communities send their local statistics to the global server. The global
server constructs a linear program and sends the solution back to the local
communities. Each local community uses the decision tree, as shown on the
right of Fig.1, to make fair outcome predictions. Below, we provide a list
itemizing the concrete training steps of post-FFL:

Figure 1: Overview of the proposed post-FFL framework. Algorithm 1 Fair
Outcome Predictor

Input: The optimal outcome predictor:
$\widehat{Y}:\mathcal{X}\times\mathcal{A}\times\mathcal{C}\rightarrow\mathcal{Y}$,
the community $k$’s corresponding minimizer:

$\mathbf{z}_{k}^{T}=\left[\begin{array}[]{cccc}z_{0}^{0k}&z_{1}^{0k}&z_{0}^{1k}&z_{1}^{1k}\end{array}\right]$

Output: Fair outcome predictor
$\widetilde{Y}_{\widehat{Y},\mathbf{z}_{k}}:\mathcal{X}\times\mathcal{A}\times\mathcal{C}\rightarrow\mathcal{Y}$

1\. randomly sample $s\sim U(0,1)$, the uniform distribution between (0,1)

2\. Construct $\widetilde{Y}_{\widehat{Y},\mathbf{z}_{k}}(x,a,k)$ as

$\widetilde{Y}_{\widehat{Y},\mathbf{z}_{k}}(x,a,k)=\left\\{\begin{array}[]{l}0,\text{
if }(a=0)\text{ and }((\widehat{Y}=0\text{ and }s\leq z_{0}^{0k})\text{ or
}(\widehat{Y}=1\text{ and }s>z_{1}^{0k}))\\\ 1,\text{ if }(a=0)\text{ and
}((\widehat{Y}=0\text{ and }s>z_{0}^{0k})\text{ or }((\widehat{Y}=1\text{ and
}s\leq z_{1}^{0k}))\\\ 0,\text{ if }(a=1)\text{ and }((\widehat{Y}=0\text{ and
}s\leq z_{0}^{1k})\text{ or }(\widehat{Y}=1\text{ and }s>z_{1}^{1k}))\\\
1,\text{ if }(a=1)\text{ and }((\widehat{Y}=0\text{ and }s>z_{0}^{1k})\text{
or }(\widehat{Y}=1\text{ and }s\leq z_{1}^{1k}))\end{array}\right.$

return $\widetilde{Y}_{\widehat{Y},\mathbf{z}_{k}}$

  1. 1.

Training an Optimal Outcome Predictor using FedAvg: The server and communities
collaboratively train an optimal predictor
$\widehat{Y}:\mathcal{X}\times\mathcal{A}\times\mathcal{C}\rightarrow\mathcal{Y}$
using the FedAvg algorithm (McMahan et al., 2017). The participating community
trains a local model at time $t$ and sends the local model’s parameters,
$\boldsymbol{\theta}_{c}^{t}\in\mathbb{R}^{n}$, to the global server. The
global server then aggregates the local models into a global model parameter,
$\boldsymbol{\theta}^{t}=\sum_{c=1}^{K}p_{c}\boldsymbol{\theta}_{c}^{t}$, and
sends it back to the local communities. This iterative process continues until
the parameters, $\boldsymbol{\theta}$, of the optimal predictor $\widehat{Y}$
are determined. The aggregation weight, $p_{c}=\Pr_{D}(C=c)$, is estimated
from the dataset as shown in (46).

$\begin{split}p_{c}=\frac{\text{number of samples in community
$c$}}{\text{number of total samples}}\end{split}$ (46)

  2. 2.

Local Prediction and Probability Calculation: Each local community generates
predictions $\widehat{Y}(X,A,C)\in\mathcal{Y}$, computes local statistics
${\rm Pr}_{D}({\widehat{Y}=y,Y=y^{\prime},A=a\mid C=c})$ for all
$(y,y^{\prime},a)\in\\{0,1\\}^{3}$ as specified in (47), and then transmits
these probabilities to the global server.

$\begin{split}&{\rm Pr}_{D}(\hat{Y}=y,Y=y^{\prime},A=a\mid
C=c)=\frac{\text{number of samples with ($\hat{Y}=y,Y=y^{\prime},A=a$) in
community $c$}}{\text{number of samples in community c}}\end{split}$ (47)

  3. 3.

Constructing and Solving the Linear Program: The global server computes the
parameters defined in Equations (9) and (10) using the probabilities sent by
the communities. The parameters ${\rm FN^{ac}},{\rm TN^{ac}},{\rm
FP^{ac}},{\rm TP^{ac}}$ in (9) are computed based on:

$\begin{split}&{\rm
Pr}_{D}\left\\{\widehat{Y}=y,Y=y^{\prime},A=a,C=c\right\\}=p_{c}{\rm
Pr}_{D}\left\\{\widehat{Y}=y,Y=y^{\prime},A=a\mid C=c\right\\}\end{split}$

The parameters $\alpha$ and $\beta$ in (10) are computed as:

$\displaystyle\alpha$ $\displaystyle=$ $\displaystyle{\rm
Pr}_{D}(Y=1,A=0)=\sum_{c=1}^{K}({\rm FN}^{0c}+{\rm TP}^{0c})$
$\displaystyle\beta$ $\displaystyle=$ $\displaystyle{\rm
Pr}_{D}(Y=1,A=1)=\sum_{c=1}^{K}({\rm FN}^{1c}+{\rm TP}^{1c})$

Using the above parameters, the global server constructs the linear program
(16), finds the minimizer $\mathbf{z}$:

$\mathbf{z}^{T}=\left[\begin{array}[]{cccc}\mathbf{z}_{1}^{T}&\mathbf{z}_{2}^{T}&\cdots&\mathbf{z}_{K}^{T}\end{array}\right]\\\
$

and then sends the corresponding minimizer $\mathbf{z}_{k}^{T}$ to community
$k$, where $k=1,2,\cdots,K$.

  4. 4.

Fair Outcome Predictor: The local community $k$, $(k=1,2,\cdots K)$ employs
Algorithm 1 to make fair predictions. The received minimizer
$\mathbf{z}_{k}^{T}$ indicates the probability that the fair predictor’s
outcome equals the optimal predictor’s outcome for community $k$.

Algorithm 1 provides a community dependent randomized function that is used to
decide whether to accept or deny the prediction from the optimal model. The
output of the optimal model, combined with the randomized function, will yield
a fair outcome predictor.

##  5 Experiments

We conduct experiments on the real-world dataset to demonstrate the
effectiveness of the post-FFL. Section 5.1 verifies that the proposed post-FFL
can simultaneously enforce both notions of fairness for binary and multi-class
classification tasks. It also shows that our framework can flexibly adjust the
degree of fairness. Section 5.2 compares our framework with other existing
fair federated algorithms. Our framework outperforms current in-processing
techniques in terms of achieving both notions of fairness, communication
efficiency, and computational cost. Section 5.3 presents results under
different data heterogeneity settings. Section 5.4 explores the effects of the
local epoch and batch size in FedAvg algorithm.

#### Dataset.

We use three real-world datasets: the Adult, the Diabetes, and the HM10000 to
demonstrate the effectiveness of post-FFL.

The Adult dataset (Asuncion & Newman, 2007) consists of 6 numerical features
(age, final weight, education number, etc.) and 8 categorical features (work
class, education, gender, race, etc.) and is used to predict a binary label.
The label indicates whether an individual earns more than 50K/year. We set
gender as the sensitive attribute. Following the federated setting in (Li et
al., 2020; Mohri et al., 2019), we split the dataset into two communities: one
is the PhD community, in which all individuals are PhDs, and the other is the
non-PhD community.

The Diabetes dataset (Strack et al., 2014) contains 10 numerical features
(time in hospital, number of procedures, etc.), 40 binary features (race,
gender, age range, admission source, diabetMed, etc.), and is used to predict
a binary label. The label indicates whether a patient will be readmitted
within 30 days. We set the group “older (aged over 60) African-American
females” as the sensitive group. We split the data into seven communities
based on their admission source. Communities 1, 2, 3, 4, 5, 6, and 7 represent
samples admitted from the Emergency Room, Physician Referral, NULL, Transfer
from a hospital, Transfer from another healthcare facility, Clinic Referral,
Transfer from a Skilled Nursing Facility, and Others, respectively.

The HM10000 dataset (Tschandl et al., 2018) comprises dermatoscopic images
from different populations and is used to predict seven classes. The seven
skin diagnostic classes are: akiec (Actinic Keratoses and Intraepithelial
Carcinoma), bcc (Basal Cell Carcinoma), bkl (Benign Keratosis), df
(Dermatofibroma), nv (Melanocytic Nevi), mel (Melanoma), and vasc (Vascular
Skin Lesions). We set individuals aged over 60 as the protected group. Equal
Opportunity in this multi-class problem is defined as the true positive rate
of Basal Cell Carcinoma being equal across the protected and unprotected
groups. We divide the dataset into five communities. These communities are
defined as follows: Community 1 represents individuals aged under 40;
Community 2, those aged 40 to 50; Community 3, individuals aged 50 to 60;
Community 4, those aged 60 to 70; and Community 5 includes those older than 70
and individuals of unknown ages.

#### Evaluation Metrics.

We evaluate the model’s performance from the following perspectives:

  * •

Model utility: We use the model’s Avg-Acc to measure its utility. The Avg-Acc
is the weighted average accuracy across all communities.

  * •

Group fairness: Group fairness, as defined in Definition 2.2, requires that
the true positive rates are the same for sensitive and non-sensitive groups.
We measure group fairness using the Equal Opportunity Difference (EOD), which
is defined as the difference in true positive rates between sensitive and non-
sensitive groups.

  * •

Community fairness: Community fairness, as defined in Definition 2.4, requires
that the model has similar accuracy across all communities. We measure
community fairness using Accuracy Disparity (AD) which is the difference
between the highest and lowest accuracy across all communities.

The full experiments details (including model and hyperparameters) are in
Appendix D.1

###  5.1 Fairness of post-FFL

In this section, we verify that the proposed framework can simultaneously
enforce group fairness and community fairness within a FL platform. We
demonstrate our framework can control the degree of group fairness and
community fairness by adjusting the $\epsilon$ and $\delta$ in the linear
program (31) respectively. Smaller $\epsilon$ and $\delta$ values will lead to
a fairer outcome predictor. Setting $(\epsilon=0,\delta=0)$ results in a
predictor that strictly achieves both group fairness and community fairness.
We further show that Theorem (3.7) within our framework allows one to evaluate
the accuracy loss incurred while improving group fairness and community
fairness.

#### Achieving group fairness and community fairness.

Table 1 reports Avg-Acc, EOD, and AD of FedAvg (McMahan et al., 2017) and
post-FFL $(\epsilon=0,\delta=0)$ for all three datasets. These results show
post-FFL reduced EOD and AD by 66.0%-87.5 % over FedAvg, thereby
simultaneously achieving high levels of group and community fairness.

Table 1: The EOD, AD and Avg-Acc of FedAvg and our post-FFL. The 95% confidence interval (mean$\pm$ margin of error) of all measurements is computed over 5 runs.  Dataset | Frameworks | EOD | AD | Avg-Acc
---|---|---|---|---
Adult | Fedavg | 0.10 $\pm$ 0.02 | 0.14 $\pm$ 0.11 | 0.85 $\pm$ 0.00
Post-FFL | 0.02 $\pm$ 0.00($\downarrow$80.00%) | 0.03 $\pm$ 0.01($\downarrow$78.57%) | 0.75 $\pm$ 0.03
Diabetes | Fedavg | 0.07$\pm$ 0.03 | 0.09 $\pm$ 0.02 | 0.83 $\pm$ 0.01
Post-FFL | 0.02$\pm$0.02($\downarrow$74.43%) | 0.03 $\pm$ 0.01($\downarrow$66.67%) | 0.82$\pm$ 0.01
HM1000 | Fedavg | 0.08 $\pm$ 0.02 | 0.33 $\pm$ 0.03 | 0.74 $\pm$ 0.02
Post-FFL | 0.01$\pm$0.02($\downarrow$87.50%) | 0.08 $\pm$ 0.01($\downarrow$75.75%) | 0.58$\pm$ 0.04

#### Flexibility of Adjusting the Trade-off Between Fairness and Accuracy.

Table 2 reports the Avg-Acc, EOD, and AD for different settings of
$(\epsilon,\delta)$ on all three datasets. These results show that with fixed
$\epsilon$, decreasing $\delta$ reduces AD and Avg-Acc, indicating the model
is fairer with respect to community fairness but has poorer performance.
Similarly, with a fixed $\delta$, the degree of equal opportunity was
effectively controlled by adjusting $\epsilon$. These results support our
assertion that post-FFL is effective tool for trading off fairness and model
accuracy.

Table 2: post-FFL performance for a range of $(\epsilon,\delta)$ relaxed fair predictors. Dataset | $(\epsilon,\delta)$ | EOD | AD | Avg-Acc | empirical accuracy loss | estimated accuracy loss | estimated error
---|---|---|---|---|---|---|---
Adult | (0.00, 0.00) | 0.016 | 0.012 | 0.780 | 0.074 | 0.074 | 0.000
(0.00, 0.02) | 0.008 | 0.053 | 0.804 | 0.050 | 0.056 | 0.006
(0.00, 0.04) | 0.001 | 0.091 | 0.841 | 0.013 | 0.012 | 0.001
(0.02, 0.00) | 0.033 | 0.014 | 0.766 | 0.088 | 0.095 | 0.007
(0.02, 0.02) | 0.030 | 0.051 | 0.802 | 0.051 | 0.056 | 0.004
(0.02, 0.04) | 0.017 | 0.090 | 0.837 | 0.017 | 0.018 | 0.001
(0.04, 0.00) | 0.049 | 0.016 | 0.758 | 0.095 | 0.096 | 0.001
(0.04, 0.02) | 0.029 | 0.056 | 0.797 | 0.057 | 0.057 | 0.000
| (0.04, 0.04) | 0.044 | 0.094 | 0.839 | 0.014 | 0.018 | 0.004
Diabetes | (0.00, 0.00) | 0.008 | 0.021 | 0.812 | 0.022 | 0.022 | 0.000
(0.00, 0.02) | 0.034 | 0.067 | 0.830 | 0.002 | 0.001 | 0.001
(0.00, 0.04) | 0.047 | 0.080 | 0.831 | 0.003 | 0.003 | 0.000
(0.02, 0.00) | 0.040 | 0.013 | 0.815 | 0.018 | 0.022 | 0.004
(0.02, 0.02) | 0.025 | 0.048 | 0.830 | 0.004 | 0.001 | 0.003
(0.02, 0.04) | 0.027 | 0.077 | 0.832 | 0.002 | 0.000 | 0.002
(0.04, 0.00) | 0.057 | 0.025 | 0.815 | 0.018 | 0.022 | 0.004
(0.04, 0.02) | 0.006 | 0.070 | 0.831 | 0.002 | 0.001 | 0.001
| (0.04, 0.04) | 0.032 | 0.076 | 0.831 | 0.002 | 0.00 | 0.002
HM10000 | (0.00, 0.00) | 0.012 | 0.089 | 0.623 | 0.146 | 0.131 | 0.015
(0.00, 0.05) | 0.010 | 0.176 | 0.687 | 0.083 | 0.077 | 0.006
(0.00, 0.10) | 0.034 | 0.242 | 0.736 | 0.032 | 0.023 | 0.009
(0.02, 0.00) | 0.060 | 0.060 | 0.617 | 0.152 | 0.131 | 0.021
(0.02, 0.05) | 0.043 | 0.160 | 0.682 | 0.087 | 0.077 | 0.010
(0.02, 0.10) | 0.044 | 0.249 | 0.723 | 0.045 | 0.023 | 0.022
(0.04, 0.00) | 0.060 | 0.045 | 0.616 | 0.152 | 0.131 | 0.021
(0.04, 0.05) | 0.050 | 0.154 | 0.669 | 0.100 | 0.077 | 0.023
| (0.04, 0.10) | 0.057 | 0.242 | 0.728 | 0.041 | 0.023 | 0.017

#### Estimating the accuracy trade-off for fairness.

The last three columns of Table 2 compare a relaxed post-FFL model’s accuracy
against the theoretical estimate of accuracy loss in Theorem (3.7). The
columns show a theoretical estimate that was within (74.65$\pm$11.34)% of the
empirical accuracy for the particular $(\epsilon,\delta)$ relaxations over all
three datasets. This suggests Theorem (3.7) can estimate the accuracy lost
when enforcing group and community fairness.

###  5.2 Comparison with other algorithms

This subsection compares post-FFL with other existing fair federated learning
algorithms. We did not find prior work that tries to simultaneously achieve
group fairness and community fairness in a federated setting. The most
relevant prior work employs in-processing (rather than post-processing)
techniques to achieve either equal opportunity or fair resource allocation
(community fairness) in a federated setting. We used q-FedAvg (Li et al.,
2019) and FairFed (Ezzeldin et al., 2023) as baselines for community fairness
and group fairness, respectively.

A full description of all baselines is provided in Appendix D.2

#### Achieving Both Notions of Fairness.

Table 3 examines the performance of post-FFL on the Adult and HM10000 datasets
using three evaluation metrics (EOD, AD, Avg-Acc). These results show that
FairFed improves group fairness (EOD) by $83.96$-$98.91$% over FedAvg on the
two datasets while making community fairness (AD) worse. The table results
show that q-FedAvg improves community fairness (AD) by $14.15$-$98.39$% over
FedAvg on two datasets with little change in group fairness (EOD). The table
shows that post-FFL was able to significantly improve group (EOD) and
community (AD) fairness over both datasets to levels consistent with FairFed
(EOD) and q-FedAvg (AD).

Table 3:  EOD, AD and Avg-Acc of all algorithms.  | Adult | HM1000
---|---|---
Algorithms | EOD | AD | Avg-Acc | EOD | AD | Avg-Acc
Initial FedAvg | 0.106 | 0.124 | 0.854 | 0.092 | 0.311 | 0.769
Our post-FFL $(\epsilon=0,\delta=0)$ |  0.016 ($\downarrow$84.91%) |  0.012($\downarrow$90.32%) | 0.780 |  0.012($\downarrow$86.96%) |  0.089($\downarrow$71.38%) | 0.623
q-FedAvg |  0.337($\uparrow$217.92%) |  0.002($\downarrow$98.39%) | 0.811 |  0.071($\downarrow$22.82%) |  0.267($\downarrow$14.15%) | 0.730
FairFed |  0.017($\downarrow$83.96%) |  0.362($\uparrow$191.94%) | 0.846 |  0.001($\downarrow$98.91%) |  0.420($\uparrow$35.05%) | 0.673

#### Communication Efficiency and Computational Cost

Table 4 reports the number of communication rounds, computation time for one
round, and total computation time for FedAvg, FairFed and q-FedAvg for the
Adult and HM10000 datasets. Note that because post-FFL simply post-processes
the models obtained by FedAvg, the communication and computation cost of post-
FFL is accurately represented by FedAvg’s cost. So the results in Table 4 are
actually comparing post-FFL’s computational cost to the inprocessing fair FL
algorithms FairFed and q-FedAvg. The computation time results were obtained on
a 16-Core 4.00 GHz AMD RYZEN Threadripper Pro 5955WX Processor. The average
time is calculated over 30 communication rounds for each method.

The results in Table 4 show that the number of communication rounds required
by post-FFL is 2-3 orders of magnitude lower than that required by q-FedAvg
and one order of magnitude lower than what FairFed required. The post-FFL’s
computation time for a single round was comparable to that used by q-FedAvg.
When compared to FairFed, post-FFL single round time was comparable on the
more complex HM10000 dataset and an order of magnitude faster on the Adult
dataset. The table shows for the total amount of time needed for algorithm
convergence, post-FFL was 2 order of magnitude faster on the Adult data set
and about one order faster on the HM10000 dataset for both in-processing fair
FL algorithms. Training curves for a specific run in Fig.4 of Appendix D.2
provide a more ”graphic” illustration of post-FFL’s convergence speed. These
results, therefore, support our assertion that post-FFL (FedAvg) has
significantly lower computational and communication cost than prior in-
processing approaches to fair FL.

Table 4: Number of communication rounds for convergence, average time taken for completing one round of update and total time for convergence of FedAvg, q-FedAvg andFairFed. | Adult | HM10000
---|---|---
Objectives | FedAvg | q-Fedavg | FairFed | FedAvg | q-Fedavg | FairFed
# of convergence rounds |  $\approx$ 5 | $>1000$ |  $\approx$20 |  $\approx$ 10 | $>200$ | $\approx 15$
Avg-time for 1 round | 0.631s | 0.639s | 16.428s | 10.619s | 10.863s | 14.016s
Total time for convergence |  $\approx$3.155s |  $>$639s |  $\approx$328.56s |  $\approx$106.19s |  $>$2172.6s |  $\approx$210.24s

###  5.3 Experimental Result With Different Data Heterogeneity Level

We present results with various degrees of data heterogeneity across all
communities. We introduce community heterogeneity by adjusting the mixture of
individuals with specific target and sensitive attributes. The results for
Adult dataset with two communities are presented, and the results for HM10000
are in Appendix D.3.

We define class 1 as positive male $(y=1,s=1)$, class 2 as positive female
$(y=1,s=0)$, class 3 as negative male $(y=0,s=1)$, and class 4 as negative
female $(y=0,s=0)$. We sample the local communities’ datasets so that the
class proportion of each community is as shown in Fig. 2. For scenario 1, data
is i.i.d. distributed across all communities. The sensitive attribute is
totally skewed across two communities in scenario 2. Both the target and
sensitive attributes are imbalanced across communities in scenario 3.

Table 5 presents the measurements for all scenarios. We observe resents these
results which show that post-FFL reduced EOD and AD by 50%-100 % over FedAvg
across all scenarios, thereby simultaneously achieving high levels of group
and community fairness across different heterogeneity scenarios. Compared to
Scenario 1, Scenario 2 has a higher degree of data heterogeneity, resulting in
a greater initial AD for FedAvg. Consequently, the accuracy traded for
fairness in Scenario 2 (0.110) is greater than in Scenario 1 (0.108). This
demonstrates that as the level of data heterogeneity increases, the accuracy
traded to ensure fairness also increases.

Figure 2: The class proportion of the three scenarios.

(a) Scenario 1

(b) Scenario 2

(c) Scenario 3

Table 5: Experimental results with different degrees of heterogeneity (Adult)

Level of heterogeneity | FedAvg | Post-FFL |  Accuracy trade for fairness
---|---|---|---
Avg-Acc | EOD | Acc @1 | Acc@2 | AD | Avg-Acc | EOD | Acc @1 | Accc @2 | AD
Scenario 1 | 0.817 | 0.080 | 0.826 | 0.808 | 0.017 | 0.799 | 0.013 | 0.809 | 0.788 | 0.021 | 0.018
Scenario 2 | 0.855 | 0.320 | 0.784 | 0.929 | 0.145 | 0.745 | 0.046 | 0.745 | 0.751 | 0.006 | 0.110
Scenario 3 | 0.875 | 0.242 | 0.840 | 0.910 | 0.070 | 0.837 | 0.036 | 0.846 | 0.828 | 0.018 | 0.038

###  5.4 Experimental results with various local Batch Sizes and Epochs.

Since post-FFL post-processes models obtained using FedAvg, it is important to
assess the sensitivity of post-FFL’s fairness with respect to FedAvg’s
hyperparameters, in particular the batch size $B$ and number of local epochs
$E$ used to obtain the local models. $B$ represents the fraction of data
samples used for each local model update. $B=1$ indicates that the full local
dataset is treated as a single minibatch. $E$ is the number of training epochs
in each communication round. ($B=1,E=1$) corresponds exactly to FedSGD
(McMahan et al., 2017). We present the results for the  Adult dataset. The
class proportion of communities used corresponds to Scenario 2 of Table 5.

The results with different $B,E$ are in Table 6. We observe that EOD is
reduced to $(0.01\pm 0.01)$ and AD are reduced to $(0.01\pm 0.01)$ after
applying post-FFL for all different settings. Post-FFL can simultaneously
ensure group fairness and community fairness, regardless of the local epochs
$E$ and local batch size $B$. Post-FFL’s has low sensitivity to batch size and
number of local epochs

Table 6: Experimental results with different $\mathrm{B}$ and $\mathrm{E}$ in
FedAvg algorithm (Adult)

Settings | FedAvg | Post-FFL | Accuracy trade for fairness
---|---|---|---
Avg-Acc | EOD | Acc @1 | Acc@2 | AD | Avg-Acc | EOD | Acc @1 | Accc @2 | AD
$\mathrm{B}=1,\mathrm{E}=1$ (FedSGD) | 0.841 | 0.350 | 0.719 | 0.924 | 0.205 | 0.67 | 0.019 | 0.679 | 0.661 | 0.018 | 0.171
$\mathrm{B}=1,\mathrm{E}=5$ | 0.860 | 0.241 | 0.768 | 0.921 | 0.153 | 0.722 | 0.012 | 0.714 | 0.729 | 0.015 | 0.138
$\mathrm{B}=1/3,\mathrm{E}=1$ | 0.863 | 0.440 | 0.799 | 0.923 | 0.124 | 0.668 | 0.003 | 0.669 | 0.668 | 0.001 | 0.195
$\mathrm{B}=1/3,\mathrm{E}=5$ | 0.855 | 0.300 | 0.801 | 0.912 | 0.11 | 0.759 | 0.008 | 0.759 | 0.745 | 0.014 | 0.096
$\mathrm{B}=1/6,\mathrm{E}=1$ | 0.862 | 0.493 | 0.799 | 0.924 | 0.125 | 0.679 | 0.001 | 0.670 | 0.687 | 0.017 | 0.183
$\mathrm{B}=1/6,\mathrm{E}=5$ | 0.868 | 0.229 | 0.796 | 0.895 | 0.098 | 0.724 | 0.015 | 0.724 | 0.724 | 0.000 | 0.144

##  6 Conclusions and Limitations

In this work, we propose the post-FFL framework, which simultaneously achieves
group and community fairness in FL. Experiments on real-world datasets
demonstrate that post-FFL allows users to adjust the degree of fairness, and
the theoretical results associated with it can predict the accuracy cost for
fairness. Post-FFL outperforms existing baselines in fair federated learning
in terms of fairness improvement, communication efficiency, and computational
cost.

Post-FFL selects a random outcome predictor from a fixed set of classifiers.
The fixed nature of this set may limit the achievable accuracy. Existing
literature (Hardt et al., 2016; Xian et al., 2023) derives fair predictor from
a pre-trained score function may lead to a more optimal model. We will explore
the score-based approach in FL in future work.

## Acknowledgments

The authors acknowledge the partial financial support of the Lucy Family
Institute for Data and Science and the National Science Foundation - grant
CNS-2228092.

## References

  * Abadi et al. (2015) Abadi, M., Agarwal, A., Barham, P., Brevdo, E., Chen, Z., Citro, C., Corrado, G. S., Davis, A., Dean, J., Devin, M., Ghemawat, S., Goodfellow, I., Harp, A., Irving, G., Isard, M., Jia, Y., Jozefowicz, R., Kaiser, L., Kudlur, M., Levenberg, J., Mané, D., Monga, R., Moore, S., Murray, D., Olah, C., Schuster, M., Shlens, J., Steiner, B., Sutskever, I., Talwar, K., Tucker, P., Vanhoucke, V., Vasudevan, V., Viégas, F., Vinyals, O., Warden, P., Wattenberg, M., Wicke, M., Yu, Y., and Zheng, X.  TensorFlow: Large-scale machine learning on heterogeneous systems, 2015.  URL http://tensorflow.org/.  Software available from tensorflow.org.
  * Abay et al. (2020) Abay, A., Zhou, Y., Baracaldo, N., Rajamoni, S., Chuba, E., and Ludwig, H.  Mitigating bias in federated learning.  _arXiv preprint arXiv:2012.02447_ , 2020.
  * Antunes et al. (2022) Antunes, R. S., André da Costa, C., Küderle, A., Yari, I. A., and Eskofier, B.  Federated learning for healthcare: Systematic review and architecture proposal.  _ACM Transactions on Intelligent Systems and Technology (TIST)_ , 13(4):1–23, 2022.
  * Asuncion & Newman (2007) Asuncion, A. and Newman, D.  Uci machine learning repository, 2007.
  * Brisimi et al. (2018) Brisimi, T. S., Chen, R., Mela, T., Olshevsky, A., Paschalidis, I. C., and Shi, W.  Federated learning of predictive models from federated electronic health records.  _International journal of medical informatics_ , 112:59–67, 2018.
  * Chu et al. (2021) Chu, L., Wang, L., Dong, Y., Pei, J., Zhou, Z., and Zhang, Y.  Fedfair: Training fair models in cross-silo federated learning.  _arXiv preprint arXiv:2109.05662_ , 2021.
  * Chzhen et al. (2019) Chzhen, E., Denis, C., Hebiri, M., Oneto, L., and Pontil, M.  Leveraging labeled and unlabeled data for consistent fair binary classification.  _Advances in Neural Information Processing Systems_ , 32, 2019.
  * Denis et al. (2021) Denis, C., Elie, R., Hebiri, M., and Hu, F.  Fairness guarantee in multi-class classification.  _arXiv preprint arXiv:2109.13642_ , 2021.
  * Du et al. (2021) Du, W., Xu, D., Wu, X., and Tong, H.  Fairness-aware agnostic federated learning.  In _Proceedings of the 2021 SIAM International Conference on Data Mining (SDM)_ , pp. 181–189. SIAM, 2021.
  * Dwork et al. (2012) Dwork, C., Hardt, M., Pitassi, T., Reingold, O., and Zemel, R.  Fairness through awareness.  In _Proceedings of the 3rd innovations in theoretical computer science conference_ , pp. 214–226, 2012.
  * Ezzeldin et al. (2023) Ezzeldin, Y. H., Yan, S., He, C., Ferrara, E., and Avestimehr, A. S.  Fairfed: Enabling group fairness in federated learning.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 37, pp. 7494–7502, 2023.
  * Fish et al. (2016) Fish, B., Kun, J., and Lelkes, Á. D.  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.
  * Goldman & Tucker (1957) Goldman, A. J. and Tucker, A. W.  _2\. Polyhedral Convex Cones_ , pp. 19–40.  Princeton University Press, Princeton, 1957.  ISBN 9781400881987.  doi: doi:10.1515/9781400881987-003.  URL https://doi.org/10.1515/9781400881987-003.
  * Gross (2007) Gross, C.  Community perspectives of wind energy in australia: The application of a justice and community fairness framework to increase social acceptance.  _Energy policy_ , 35(5):2727–2736, 2007.
  * Gross (2008) Gross, C.  A measure of fairness: An investigative framework to explore perceptions of fairness and justice in a real-life social conflict.  _Human Ecology Review_ , 15(2):130–140, 2008.  ISSN 10744827, 22040919.  URL http://www.jstor.org/stable/24707597.
  * Hardt et al. (2016) Hardt, M., Price, E., and Srebro, N.  Equality of opportunity in supervised learning.  _Advances in neural information processing systems_ , 29, 2016.
  * Jiang et al. (2020) Jiang, J. C., Kantarci, B., Oktug, S., and Soyata, T.  Federated learning in smart city sensing: Challenges and opportunities.  _Sensors_ , 20(21):6230, 2020.
  * Kairouz et al. (2021) Kairouz, P., McMahan, H. B., Avent, B., Bellet, A., Bennis, M., Bhagoji, A. N., Bonawitz, K., Charles, Z., Cormode, G., Cummings, R., et al.  Advances and open problems in federated learning.  _Foundations and Trends® in Machine Learning_ , 14(1–2):1–210, 2021.
  * Li et al. (2019) Li, T., Sanjabi, M., Beirami, A., and Smith, V.  Fair resource allocation in federated learning.  _arXiv preprint arXiv:1905.10497_ , 2019.
  * Li et al. (2020) Li, T., Sahu, A. K., Zaheer, M., Sanjabi, M., Talwalkar, A., and Smith, V.  Federated optimization in heterogeneous networks.  _Proceedings of Machine learning and systems_ , 2:429–450, 2020.
  * Lyu et al. (2020) Lyu, L., Xu, X., Wang, Q., and Yu, H.  Collaborative fairness in federated learning.  _Federated Learning: Privacy and Incentive_ , pp. 189–204, 2020.
  * McMahan et al. (2017) McMahan, B., Moore, E., Ramage, D., Hampson, S., and y Arcas, B. A.  Communication-efficient learning of deep networks from decentralized data.  In _Artificial intelligence and statistics_ , pp. 1273–1282. PMLR, 2017.
  * Menon & Williamson (2017) Menon, A. K. and Williamson, R. C.  The cost of fairness in classification.  _arXiv preprint arXiv:1705.09055_ , 2017.
  * Mohri et al. (2019) Mohri, M., Sivek, G., and Suresh, A. T.  Agnostic federated learning.  In _International Conference on Machine Learning_ , pp. 4615–4625. PMLR, 2019.
  * Nguyen et al. (2022) Nguyen, D. C., Pham, Q.-V., Pathirana, P. N., Ding, M., Seneviratne, A., Lin, Z., Dobre, O., and Hwang, W.-J.  Federated learning for smart healthcare: A survey.  _ACM Computing Surveys (CSUR)_ , 55(3):1–37, 2022.
  * Pandya et al. (2023) Pandya, S., Srivastava, G., Jhaveri, R., Babu, M. R., Bhattacharya, S., Maddikunta, P. K. R., Mastorakis, S., Piran, M. J., and Gadekallu, T. R.  Federated learning for smart cities: A comprehensive survey.  _Sustainable Energy Technologies and Assessments_ , 55:102987, 2023.
  * Parsa-Parsi (2017) Parsa-Parsi, R. W.  The Revised Declaration of Geneva: A Modern-Day Physician’s Pledge.  _JAMA_ , 318(20):1971–1972, 11 2017.  ISSN 0098-7484.  doi: 10.1001/jama.2017.16230.  URL https://doi.org/10.1001/jama.2017.16230.
  * Peck (1975) Peck, C. J.  Equal employment opportunity commission: Developments in the administrative process 1965-1975.  _Wash. L. Rev._ , 51:831, 1975.
  * Pleiss et al. (2017) Pleiss, G., Raghavan, M., Wu, F., Kleinberg, J., and Weinberger, K. Q.  On fairness and calibration.  _Advances in neural information processing systems_ , 30, 2017.
  * Qolomany et al. (2020) Qolomany, B., Ahmad, K., Al-Fuqaha, A., and Qadir, J.  Particle swarm optimized federated learning for industrial iot and smart city services.  In _GLOBECOM 2020-2020 IEEE Global Communications Conference_ , pp. 1–6. IEEE, 2020.
  * Rieke et al. (2020) Rieke, N., Hancox, J., Li, W., Milletari, F., Roth, H. R., Albarqouni, S., Bakas, S., Galtier, M. N., Landman, B. A., Maier-Hein, K., et al.  The future of digital health with federated learning.  _NPJ digital medicine_ , 3(1):119, 2020.
  * Rodríguez-Gálvez et al. (2021) Rodríguez-Gálvez, B., Granqvist, F., van Dalen, R., and Seigel, M.  Enforcing fairness in private federated learning via the modified method of differential multipliers.  _arXiv preprint arXiv:2109.08604_ , 2021.
  * Smith et al. (2018) Smith, V., Forte, S., Ma, C., Takáč, M., Jordan, M. I., and Jaggi, M.  Cocoa: A general framework for communication-efficient distributed optimization.  _Journal of Machine Learning Research_ , 18(230):1–49, 2018.
  * Strack et al. (2014) Strack, B., DeShazo, J. P., Gennings, C., Olmo, J. L., Ventura, S., Cios, K. J., Clore, J. N., et al.  Impact of hba1c measurement on hospital readmission rates: analysis of 70,000 clinical database patient records.  _BioMed research international_ , 2014, 2014.
  * Tschandl et al. (2018) Tschandl, P., Rosendahl, C., and Kittler, H.  The ham10000 dataset, a large collection of multi-source dermatoscopic images of common pigmented skin lesions.  _Scientific Data_ , 5(1):180161, 2018.  ISSN 2052-4463.  doi: 10.1038/sdata.2018.161.  URL https://doi.org/10.1038/sdata.2018.161.
  * Xian et al. (2023) Xian, R., Yin, L., and Zhao, H.  Fair and optimal classification via post-processing.  In _International Conference on Machine Learning_ , pp. 37977–38012. PMLR, 2023.
  * Yue et al. (2023) Yue, X., Nouiehed, M., and Al Kontar, R.  Gifair-fl: A framework for group and individual fairness in federated learning.  _INFORMS Journal on Data Science_ , 2(1):10–23, 2023.
  * Zafar et al. (2017) Zafar, M. B., Valera, I., Rogriguez, M. G., and Gummadi, K. P.  Fairness constraints: Mechanisms for fair classification.  In _Artificial intelligence and statistics_ , pp. 962–970. PMLR, 2017.
  * Zeng et al. (2022) Zeng, X., Dobriban, E., and Cheng, G.  Bayes-optimal classifiers under group fairness.  _arXiv preprint arXiv:2202.09724_ , 2022.
  * Zhao & Gordon (2022) Zhao, H. and Gordon, G. J.  Inherent tradeoffs in learning fair representations.  _The Journal of Machine Learning Research_ , 23(1):2527–2552, 2022.
  * Zheng et al. (2022) Zheng, Z., Zhou, Y., Sun, Y., Wang, Z., Liu, B., and Li, K.  Applications of federated learning in smart cities: recent advances, taxonomy, and open challenges.  _Connection Science_ , 34(1):1–28, 2022.

##  Appendix A Global Fairness and Local Fairness are not Equivalent.

As stated in Remark 2.3, ensuring fairness in each local distribution does not
guarantee global fairness, as local fairness and global fairness are not
equivalent.

The local fairness with respect to Equal Opportunity (EO) over each local
distribution in FL is defined as:

$\displaystyle\forall c\in\mathcal{C},{\rm Pr}(\widehat{Y}=1|Y=1,A=0,C=c)={\rm
Pr}(\widehat{Y}=1|Y=1,A=1,C=c)$ (48)

Our paper studies group fairness over the global distribution, i.e.,

$\displaystyle{\rm Pr}(\widehat{Y}=1|Y=1,A=0)={\rm Pr}(\widehat{Y}=1|Y=1,A=1)$
(49)

It is obvious that if the model is fair over the global distribution, it is
not necessarily fair over the local distributions, i.e., equation (49) does
not imply equation (48). Conversely, we cannot ensure global fairness by
simply training locally fair models, i.e., equation (48) does not imply
equation (49). The reason is as follows:

Assume we have a model,
$\widehat{Y}:\mathcal{X}\times\mathcal{A}\times\mathcal{C}\rightarrow\mathcal{Y}$,
that is fair within each community, i.e., satisfying equation (48). The global
Equal Opportunity Difference (EOD) for the model $\widehat{Y}$ is:

$\displaystyle{\rm EOD}:$ $\displaystyle=$ $\displaystyle{\rm
Pr}(\widehat{Y}=1|Y=1,A=0)-{\rm Pr}(\widehat{Y}=1|Y=1,A=1)$ $\displaystyle=$
$\displaystyle\sum_{c\in\mathcal{C}}\left[{\rm
Pr}(\widehat{Y}=1,C=c|Y=1,A=0)-{\rm Pr}(\widehat{Y}=1,C=c|Y=1,A=1)\right]$
$\displaystyle=$ $\displaystyle\sum_{c\in\mathcal{C}}\left[{\rm
Pr}(\widehat{Y}=1|Y=1,A=0,C=c)\cdot{\rm Pr}(C=c|Y=1,A=0)\right.$
$\displaystyle\quad\quad\left.-{\rm Pr}(\widehat{Y}=1|Y=1,A=1,C=c)\cdot{\rm
Pr}(C=c|Y=1,A=1)\right]$

Given that the model, $\widehat{Y}$ satisfies EO in (48), we can substitute
${\rm Pr}(\widehat{Y}=1|Y=1,A=1,C=c)$ with ${\rm
Pr}(\widehat{Y}=1|Y=1,A=0,C=c)$:

$\displaystyle{\rm EOD}$ $\displaystyle=$
$\displaystyle\sum_{c\in\mathcal{C}}\left[\left({\rm Pr}(C=c|Y=1,A=0)-{\rm
Pr}(C=c|Y=1,A=1)\right)\cdot{\rm Pr}(\widehat{Y}=1|Y=1,A=0,C=c)\right]$

The global EOD is not necessarily zero, i.e., the model is not fair over the
global distribution. The global EOD is zero when the community label $C$ and
the sensitive attribute $A$ are conditionally independent, given $Y=1$.
However, in most real-world scenarios of interest to us, the sensitive
attribute, for example, ”race” and the community label indicates which
geographic ”neighborhood” the household is located in are highly correlated
due to a history of racial segregation. So we cannot, in general, achieve
global fairness simply by enforcing local fairness at the client level.

##  Appendix B The LP for Multi-Class Classification.

As mentioned in Remark 3.3, our approach can be extended to multi-class
problems, where $x\in\mathcal{X}$, $a\in\mathcal{A}=\\{0,1\\}$,
$c\in\mathcal{C}=\\{1,2,\ldots,K\\}$, and
$y\in\mathcal{Y}=\\{0,1,\ldots,N\\}$.

In multi-class problems, the variables we use to characterize the fair outcome
predictor $\tilde{Y}$ are,

$\displaystyle z^{ac}_{kj}$ $\displaystyle=$ $\displaystyle{\rm
Pr}\left\\{\widetilde{Y}=k,|\,\widehat{Y}=j,A=a,C=c\right\\},\forall
k\in\mathcal{Y},j\in\mathcal{Y},a\in\mathcal{A},c\in\mathcal{C}$

We set $\alpha={\rm Pr}(Y=1,A=0)$, $\beta={\rm
Pr}(Y=1,A=1),p_{c}=\rm{Pr}(C=c)$ and use the the joint statistics over
$\hat{Y},Y,A,C$: $p_{kj}^{ac}={\rm Pr}(Y=k,\hat{Y}=j,A=a,C=c)$ to construct
the linear program.

The LP of multi-class problem is:

$\displaystyle\begin{array}[]{ll}\mbox{maximize:}&\sum\limits_{c\in\mathcal{C}}\sum\limits_{a\in\mathcal{A}}\sum\limits_{j\in\mathcal{Y}}\sum\limits_{k\in\mathcal{Y}}p_{kj}^{ac}z^{ac}_{kj}\\\\[14.22636pt]
\mbox{with respect to:}&z_{kj}^{ac}\in\mathbb{R},\forall
k\in\mathcal{Y},j\in\mathcal{Y},a\in\mathcal{A},c\in\mathcal{C},\\\\[8.5359pt]
\mbox{subject
to:}&\sum\limits_{c\in\mathcal{C}}\sum\limits_{j\in\mathcal{Y}}\frac{p_{1j}^{0c}}{\alpha}\cdot
z_{1j}^{0c}-\sum\limits_{c\in\mathcal{C}}\sum\limits_{j\in\mathcal{Y}}\frac{p_{1j}^{1c}}{\beta}z_{1j}^{1c}=0\\\\[14.22636pt]
&\forall
c\in\mathcal{C},\sum\limits_{a\in\mathcal{A}}\sum\limits_{j\in\mathcal{Y}}\sum\limits_{k\in\mathcal{Y}}\frac{p_{kj}^{ac}}{p_{c}}\cdot
z_{kj}^{ac}-\frac{1}{K}\sum\limits_{c\in\mathcal{C}}\sum\limits_{a\in\mathcal{A}}\sum\limits_{j\in\mathcal{Y}}\sum\limits_{k\in\mathcal{Y}}\frac{p_{kj}^{ac}}{p_{c}}\cdot
z_{kj}^{ac}=0\\\\[14.22636pt] &\forall
c\in\mathcal{C},a\in\mathcal{A},j\in\mathcal{Y},\sum\limits_{k\in\mathcal{Y}}z_{kj}^{ac}=1\\\\[14.22636pt]
&\forall k\in\mathcal{Y},j\in\mathcal{Y},a\in\mathcal{A},c\in\mathcal{C},0\leq
z_{kj}^{ac}\leq 1\par\end{array}$

Then, the outcome predictor:
$\widetilde{Y}:\mathcal{X}\times\mathcal{A}\times\mathcal{C}\rightarrow\mathcal{Y}$
that takes values:

$\begin{split}&\text{If
}\widehat{Y}(x,a,c)=j,A=a,C=c:\widetilde{Y}(x,a,c)=k\quad\text{with
probability}\quad z^{ac}_{kj}\end{split}$ (51)

is a fair outcome predictor.

Proof: We first show that the outcome predictor in (51) satisfies Equal
Opportunity:

${\rm}Pr(\tilde{Y}=1|Y=1,A=a)$ can be expressed as:

$\begin{split}{\rm
Pr}(\widetilde{Y}=1|Y=1,A=a)&=\sum_{c\in\mathcal{C}}\frac{{\rm
Pr}(\widetilde{Y}=1,Y=1,C=c,A=a)}{{\rm Pr}(Y=1,A=a)}\\\
&=\sum_{c\in\mathcal{C}}\sum_{j\in\mathcal{Y}}\frac{{\rm
Pr(\widehat{Y}}=1,Y=1,C=c,A=a)}{{\rm Pr}(Y=1,A=a)}\cdot{\rm
Pr}(\widetilde{Y}=1|\widehat{Y}=j,A=a,C=c)\\\
&=\sum_{c\in\mathcal{C}}\sum_{j\in\mathcal{Y}}\frac{p_{1j}^{ac}}{{\rm
Pr}(Y=1,A=a)}z_{1j}^{ac}\end{split}$ (52)

Thus, the first equation of the LP is:

$\begin{split}0&=\sum_{c\in\mathcal{C}}\sum_{j\in\mathcal{Y}}\frac{p_{1j}^{0c}}{\alpha}z_{1j}^{0c}-\sum_{c\in\mathcal{C}}\sum_{j\in\mathcal{Y}}\frac{p_{1j}^{1c}}{\beta}z_{1j}^{1c}\\\
&={\rm Pr}(\widetilde{Y}=1|Y=1,A=0)-{\rm
Pr}(\widetilde{Y}=1|Y=1,A=1)\end{split}$ (53)

which indicates Equal Opportunity.

We then show that the fair outcome predictor satisfies Community Fairness:

The accuracy of the predictor of community $c$ is ${\rm
Pr}(\widetilde{Y}=Y|C=c)$ and can be written as:

$\begin{split}{\rm
Pr}(\widetilde{Y}=Y|C=c)&=\sum_{a\in\mathcal{A}}\sum_{k\in\mathcal{Y}}{\rm
Pr}(\widetilde{Y}=k,Y=k,A=a|C=c)\\\
&=\sum_{a\in\mathcal{A}}\sum_{k\in\mathcal{Y}}\frac{{\rm
Pr}(\widetilde{Y}=k,Y=k,A=a,C=c)}{{\rm Pr}(C=c)}\\\
&=\sum_{a\in\mathcal{A}}\sum_{k\in\mathcal{Y}}\sum_{j\in\mathcal{Y}}\frac{{\rm
Pr}(\widehat{Y}=k,Y=k,A=a,C=c)}{{\rm Pr}(C=c)}\cdot{\rm
Pr}(\widetilde{Y}=k|\widehat{Y}=j,A=a,C=c)\\\
&=\sum_{a\in\mathcal{A}}\sum_{k\in\mathcal{Y}}\sum_{j\in\mathcal{Y}}\frac{p_{kj}^{ac}}{p_{c}}\cdot
z_{kj}^{ac}\end{split}$ (54)

Thus, the next equation of the LP is:

$\begin{split}\forall
c\in\mathcal{C},0&=\sum_{a\in\mathcal{A}}\sum_{k\in\mathcal{Y}}\sum_{j\in\mathcal{Y}}\frac{p_{kj}^{ac}}{p_{c}}\cdot
z_{kj}^{ac}-\frac{1}{K}\sum_{c\in\mathcal{C}}\sum_{a\in\mathcal{A}}\sum_{k\in\mathcal{Y}}\sum_{j\in\mathcal{Y}}\frac{p_{kj}^{ac}}{p_{c}}\cdot
z_{kj}^{ac}\\\ &={\rm
Pr}(\widetilde{Y}=Y|C=c)-\frac{1}{K}\sum_{c\in\mathcal{C}}{\rm
Pr}(\widetilde{Y}=Y|C=c)\end{split}$ (55)

which indicates community fairness.

The objective function we maximize is:

$\begin{split}\sum\limits_{c\in\mathcal{C}}\sum\limits_{a\in\mathcal{A}}\sum\limits_{j\in\mathcal{Y}}\sum\limits_{k\in\mathcal{Y}}p_{kj}^{ac}z^{ac}_{kj}&=\sum\limits_{c\in\mathcal{C}}{\rm
Pr}(\widetilde{Y}=Y|C=c)\cdot p_{c}\\\ &=\sum\limits_{c\in\mathcal{C}}{\rm
Pr}(\widetilde{Y}=Y|C=c)\cdot{\rm Pr}(C=c)\\\ &={\rm
Pr}(\widetilde{Y}=Y)\end{split}$ (56)

which is the accuracy over the global distribution.

Since the variable $z^{ac}_{kj}$ represents probability, we have:

$\begin{split}&\forall
c\in\mathcal{C},a\in\mathcal{A},j\in\mathcal{Y},\sum\limits_{k\in\mathcal{Y}}z_{kj}^{ac}=1\\\
&\forall k\in\mathcal{Y},j\in\mathcal{Y},a\in\mathcal{A},c\in\mathcal{C},0\leq
z_{kj}^{ac}\leq 1\end{split}$ (57)

which are the last two equations of the constraints.

Thus, the outcome predictor is a fair outcome predictor. $\diamondsuit$

##  Appendix C Theoretical Proofs

###  C.1 Proof of Proposition 3.2

We first show that the outcome predictor
$\widetilde{Y}_{\widehat{Y},\mathbf{z}}:\mathcal{X}\times\mathcal{A}\times\mathcal{C}\rightarrow\mathcal{Y}$
satisfies equal opportunity:

The probability ${\rm
Pr}_{D}(\widetilde{Y}_{\widehat{Y},\mathbf{z}}=1|Y=1,A=a)$ can be extended as:

$\begin{split}&{\rm
Pr}_{D}(\widetilde{Y}_{\widehat{Y},\mathbf{z}}=1|Y=1,A=a)\\\ =&\frac{{\rm
Pr}_{D}(\widetilde{Y}_{\widehat{Y},\mathbf{z}}=1,Y=1,A=a)}{{\rm
Pr}_{D}(Y=1,A=a)}\\\ =&\frac{\sum_{c=1}^{K}{\rm
Pr}_{D}(\widetilde{Y}_{\widehat{Y},\mathbf{z}}=1,Y=1,A=a,C=c)}{{\rm
Pr}_{D}(Y=1,A=a)}\\\ =&\frac{\sum_{c=1}^{K}({\rm
Pr}_{D}(\widehat{Y}=1,Y=1,A=a,C=c)\cdot{\rm
Pr}_{D}(\widetilde{Y}_{\widehat{Y},\mathbf{z}}=\widehat{Y}|\widehat{Y}=1,A=a,C=c))}{{\rm
Pr}_{D}(Y=1,A=a)}\\\ +&\frac{\sum_{c=1}^{K}({\rm
Pr}_{D}(\widehat{Y}=0,Y=1,A=a,C=c)\cdot{\rm
Pr}_{D}(\widetilde{Y}_{\widehat{Y},\mathbf{z}}\neq\widehat{Y}|\widehat{Y}=0,A=a,C=c))}{{\rm
Pr}_{D}(Y=1,A=a)}\\\ =&\frac{\sum_{c=1}^{K}({\rm
Pr}_{D}(\widehat{Y}=1,Y=1,A=a,C=c)\cdot z_{1}^{ac}}{{\rm
Pr}_{D}(Y=1,A=a)}+\frac{\sum_{c=1}^{K}({\rm
Pr}_{D}(\widehat{Y}=0,Y=1,A=a,C=c)\cdot(1-z_{0}^{ac})}{{\rm
Pr}_{D}(Y=1,A=a)}\\\ =&\frac{\sum_{c=1}^{K}{\rm TP}^{ac}\cdot z_{1}^{ac}}{{\rm
Pr}_{D}(Y=1,A=a)}+\frac{\sum_{c=1}^{K}{\rm FN}^{ac}\cdot(1-z_{0}^{ac})}{{\rm
Pr}_{D}(Y=1,A=a)}\\\ \end{split}$ (58)

We can now calculate the Equal opportunity Difference of the outcome predictor
$\widetilde{Y}_{\widehat{Y},\mathbf{z}}$, which is defined as: ${\rm
Pr}_{D}(\widetilde{Y}_{\widehat{Y},\mathbf{z}}=1|Y=1,A=0)-{\rm
Pr}_{D}(\widetilde{Y}_{\widehat{Y},\mathbf{z}}=1|Y=1,A=1)$:

$\begin{split}&{\rm
Pr}_{D}(\widetilde{Y}_{\widehat{Y},\mathbf{z}}=1|Y=1,A=0)-{\rm
Pr}_{D}(\widetilde{Y}_{\widehat{Y},\mathbf{z}}=1|Y=1,A=1)\\\
=&\frac{\sum_{c=1}^{K}{\rm TP}^{0c}\cdot z_{1}^{0c}}{{\rm
Pr}_{D}(Y=1,A=0)}+\frac{\sum_{c=1}^{K}{\rm FN}^{0c}\cdot(1-z_{0}^{0c})}{{\rm
Pr}_{D}(Y=1,A=0)}-(\frac{\sum_{c=1}^{K}{\rm TP}^{1c}\cdot z_{1}^{1c}}{{\rm
Pr}_{D}(Y=1,A=1)}+\frac{\sum_{c=1}^{K}{\rm FN}^{1c}\cdot(1-z_{0}^{1c})}{{\rm
Pr}_{D}(Y=1,A=1)})\\\ =&\frac{-\sum_{c=1}^{K}{\rm FN}^{0c}\cdot
z_{0}^{0c}}{\alpha}+\frac{\sum_{c=1}^{K}{\rm TP}^{0c}\cdot
z_{1}^{0c}}{\alpha}+\frac{\sum_{c=1}^{K}{\rm FN}^{1c}\cdot
z_{0}^{1c}}{\beta}-\frac{\sum_{c=0}^{K}{\rm TP}^{1c}\cdot
z_{1}^{1c}}{\beta}+\frac{\sum_{c=1}^{K}{\rm
FN}^{0c}}{\alpha}-\frac{\sum_{c=1}^{K}{\rm FN}^{1c}}{\beta}\end{split}$ (59)

The first linear equation of $\mathbf{Az}=\mathbf{b}$ in (16) is:

$\begin{split}0=&\sum_{c=1}^{K}\mathbf{m}_{c}^{T}\mathbf{z}_{c}-\sum_{k=1}^{K}\left(\frac{{\rm
FN}^{1k}}{\beta}-\frac{{\rm FN}^{0k}}{\alpha}\right)\\\
=&\sum_{c=0}^{K}\left[\begin{array}[]{cccc}\frac{-{\rm
FN}^{0c}}{\alpha}&\frac{{\rm TP}^{0c}}{\alpha}&\frac{{\rm
FN}^{1c}}{\beta}&\frac{-{\rm
TP}^{1c}}{\beta}\end{array}\right]^{T}\cdot\left[\begin{array}[]{cccc}z_{0}^{0c}\\\
z_{1}^{0c}\\\ z_{0}^{1c}\\\
z_{1}^{1c}\end{array}\right]-\sum_{c=1}^{K}\left(\frac{{\rm
FN}^{1c}}{\beta}-\frac{{\rm FN}^{0c}}{\alpha}\right)\\\
=&\frac{-\sum_{c=1}^{K}{\rm FN}^{0c}\cdot
z_{0}^{0c}}{\alpha}+\frac{\sum_{c=1}^{K}{\rm TP}^{0c}\cdot
z_{1}^{0c}}{\alpha}+\frac{\sum_{c=1}^{K}{\rm FN}^{1c}\cdot
z_{0}^{1c}}{\beta}-\frac{\sum_{c=0}^{K}{\rm TP}^{1c}\cdot
z_{1}^{1c}}{\beta}+\frac{\sum_{c=1}^{K}{\rm
FN}^{0c}}{\alpha}-\frac{\sum_{c=1}^{K}{\rm FN}^{1c}}{\beta}\\\ &\text{Combine
the above with the {Equal Opportunity Difference}'s expression
(\ref{eq:equal_opportunity_difference}) }:\\\ &{\rm
Pr}_{D}(\widetilde{Y}_{\widehat{Y},\mathbf{z}}=1|Y=1,A=0)-{\rm
Pr}_{D}(\widetilde{Y}_{\widehat{Y},\mathbf{z}}=1|Y=1,A=1)=0\end{split}$ (60)

We can see from (60) the first linear equation leads a outcome predictor that
satisfies equal opportunity.

Then, we show that the outcome predictor
$\widetilde{Y}_{\widehat{Y},\mathbf{z}}:\mathcal{X}\times\mathcal{A}\times\mathcal{C}\rightarrow\mathcal{Y}$
satisfies community fairness.

The condition for community fairness in Definition 2.4 is equivalent to:

$\displaystyle\forall k\in\mathcal{C},{\rm
Pr}(\widetilde{Y}_{\widehat{Y},\mathbf{z}}\neq
Y|C=k)=\frac{1}{K}\sum_{c=1}^{K}{\rm
Pr}(\widetilde{Y}_{\widehat{Y},\mathbf{z}}\neq Y|C=c)$

The error rate of community $k$: ${\rm
Pr}(\widetilde{Y}_{\widehat{Y},\mathbf{z}}\neq Y|C=k)$ can be extended as:

$\begin{split}{\rm Pr}(\widetilde{Y}_{\widehat{Y},\mathbf{z}}\neq
Y|C=k)&=\sum_{a=0}^{1}({\rm
Pr}_{D}(\widetilde{Y}_{\widehat{Y},\mathbf{z}}=0,Y=1,A=a|C=k)+{\rm
Pr}_{D}(\widetilde{Y}_{\widehat{Y},\mathbf{z}}=1,Y=0,A=a|C=k))\\\
&=\sum_{a=0}^{1}[{\rm Pr}_{D}(\widehat{Y}=0,Y=1,A=a|C=k)\cdot{\rm
Pr}_{D}(\widetilde{Y}_{\widehat{Y},\mathbf{z}}=\widehat{Y}|\widehat{Y}=0,A=a,C=k)\\\
&+{\rm Pr}_{D}(\widehat{Y}=1,Y=1,A=a|C=k)\cdot{\rm
Pr}_{D}(\widetilde{Y}_{\widehat{Y},\mathbf{z}}\neq\widehat{Y}|\widehat{Y}=1,A=a,C=k)\\\
&+{\rm Pr}_{D}(\widehat{Y}=1,Y=0,A=a|C=k)\cdot{\rm
Pr}_{D}(\widetilde{Y}_{\widehat{Y},\mathbf{z}}=\widehat{Y}|\widehat{Y}=1,A=a,C=k)\\\
&+{\rm Pr}_{D}(\widehat{Y}=0,Y=0,A=a|C=k)\cdot{\rm
Pr}_{D}(\widetilde{Y}_{\widehat{Y},\mathbf{z}}\neq\widehat{Y}|\widehat{Y}=0,A=a,C=k)]\\\
&=\sum_{a=0}^{1}({\rm FN}^{ak}\cdot z_{0}^{ak}+{\rm
TP}^{ak}\cdot(1-z_{1}^{ak})+{\rm FP}^{ak}\cdot z_{1}^{ak}+{\rm
TN}^{ak}\cdot(1-z_{0}^{ak}))/{\rm Pr}(C=k)\\\ &=\sum_{a=0}^{1}(({\rm
FN}^{ak}-{\rm TN}^{ak})\cdot z_{0}^{ak}+({\rm FP}^{ak}-{\rm TP}^{ak})\cdot
z_{1}^{ak}+({\rm TP}^{ak}+{\rm TN}^{ak}))\cdot\frac{1}{p_{k}}\\\
&=\mathbf{n}_{k}^{T}\cdot\mathbf{z}_{k}+b_{k}\end{split}$ (61)

The last $n$ linear equations of $\mathbf{A}\mathbf{z}=\mathbf{b}$ in (16)
are:

for $k=1,2,3,\cdots K$:

$\begin{split}0&=-\frac{K-1}{K}\mathbf{n}_{k}^{T}\mathbf{z}_{k}+\frac{1}{K}\sum_{(c\in\mathcal{C},c\neq
k)}\mathbf{n}_{c}^{T}\mathbf{z}_{c}-\frac{1}{K}\sum_{c=1}^{K}(b_{k}-b_{c})\\\
&=-(\mathbf{n}_{k}^{T}\mathbf{z}_{k}+b_{k})+\frac{1}{K}\sum_{c\in\mathcal{C}}(\mathbf{n}_{c}^{T}\mathbf{z}_{c}^{T}+b_{c})\\\
&=-{\rm Pr}(\widetilde{Y}_{\widehat{Y},\mathbf{z}}\neq
Y|C=k)+\frac{1}{K}\sum_{c=0}^{K}{\rm
Pr}(\widetilde{Y}_{\widehat{Y},\mathbf{z}}\neq Y|C=c)\end{split}$ (62)

The last equation is from (61).

We can see from (62) the last $K$ linear equations of
$\mathbf{A}\mathbf{z}=\mathbf{b}$ , the outcome predictor satisfies community
fairness.

From the proceeding, if $\mathbf{z}\in\mathbbm{R}^{4K}$ is the solution of the
linear program (16), the outcome predictor that satisfies (11) is a fair
outcome predictor. The outcome predictor
$\widetilde{Y}_{\widehat{Y},\mathbf{z}}$ that takes values of (3.2) has:

$\begin{split}{\rm
Pr}_{D}(\widetilde{Y}_{\widehat{Y},\mathbf{z}}=\widehat{Y}|\widehat{Y}=1,A=a,C=c)&=z_{1}^{ac}\\\
{\rm
Pr}_{D}(\widetilde{Y}_{\widehat{Y},\mathbf{z}}=\widehat{Y}|\widehat{Y}=0,A=a,C=c)&=z_{0}^{ac}\end{split}$

which satisfies (3.2).

Thus, the outcome predictor $\widetilde{Y}_{\widehat{Y},\mathbf{z}}$ is a fair
outcome predictor w.r.t. both equal opportunity and community fairness.
$\diamondsuit$

###  C.2 Proof of Theorem 3.5

We show that the linear program (40) always has solutions. Before presenting
the proof, we first present Farkas’ lemma (Goldman & Tucker, 1957):

Let $\mathbf{A}\in\mathbb{R}^{m\times n}$ and $\mathbf{b}\in\mathbb{R}^{m}$.
Then exactly one of the following two assertions is true:

  1. 1.

There exists a $\mathbf{z}\in\mathbb{R}^{n}$ such that
$\mathbf{Az}=\mathbf{b}$ and $\mathbf{z}\geq 0$.

  2. 2.

There exists a $\mathbf{y}\in\mathbb{R}^{m}$ such that
$\mathbf{A}^{T}\mathbf{y}\geq 0$ and $\mathbf{b}^{T}\mathbf{y}<0$.

Faraks’ lemma states that either the system $\mathbf{Az}=\mathbf{b}$ has a
non-negative solution or the system $\mathbf{A}^{T}\mathbf{y}\geq 0$ has a
solution with $\mathbf{b}^{T}\mathbf{y}<0$ but not both. Thus, we can show the
linear program (40) always exist a solution by showing that the set
$\\{\mathbf{y}|\mathbf{y}\in\mathbb{R}^{5K+1},\mathbf{\bar{A}}^{T}\mathbf{y}\geq
0,\mathbf{\bar{b}}^{T}\mathbf{y}<0\\}$ is always empty.

Let:
$\mathbf{y}^{T}=\left[\begin{array}[]{cc}\mathbf{y}_{1}^{T}&\mathbf{y}_{2}^{T}\end{array}\right]$,
with $\mathbf{y}_{1}\in\mathbb{R}^{K+1}$, $\mathbf{y}_{2}\in\mathbb{R}^{4K}$,
then, the condition $\mathbf{\bar{A}}^{T}\mathbf{y}\geq 0$ is:

$\begin{split}\mathbf{\bar{A}}^{T}\mathbf{y}=&\left[\begin{array}[]{cc}\mathbf{A}^{T}&\mathbf{I}\\\
\mathbf{0}&\mathbf{I}\end{array}\right]\cdot\left[\begin{array}[]{cc}\mathbf{y_{1}}\\\
\mathbf{y_{2}}\end{array}\right]\\\
&=\left[\begin{array}[]{cc}\mathbf{A}^{T}\mathbf{y_{1}}+\mathbf{I}\mathbf{y_{2}}\\\
\mathbf{y_{2}}\end{array}\right]\geq 0\\\
\rightarrow\quad&\mathbf{1}_{4K}^{T}\cdot(\mathbf{A}^{T}\mathbf{y_{1}}+\mathbf{y_{2}})\geq
0\\\ &\mathbf{1}_{4K}^{T}\cdot\mathbf{y_{2}}\geq 0\end{split}$ (63)

The condition $\mathbf{\bar{b}}^{T}\mathbf{y}<0$ is:

$\begin{split}\mathbf{\bar{b}}^{T}\mathbf{y}&=\left[\begin{array}[]{cc}\mathbf{b}^{T}&\mathbf{1}_{4K}^{T}\end{array}\right]\cdot\left[\begin{array}[]{cc}\mathbf{y_{1}}\\\
\mathbf{y_{2}}\end{array}\right]\\\
&=\mathbf{b}^{T}\mathbf{y_{1}}+\mathbf{1}_{4K}^{T}\mathbf{y_{2}}\\\
&=\frac{1}{2}\mathbf{A}^{T}\mathbf{y_{1}}+\mathbf{1}_{4K}^{T}\mathbf{y_{2}}<0\end{split}$
(64)

The last equation above is from the fact: $\frac{1}{p_{c}}({\rm TN}^{0c}+{\rm
TP}^{0c}+{\rm TN}^{1c}+{\rm TP}^{1c})=1-\frac{1}{p_{c}}({\rm FN}^{0c}+{\rm
FP}^{0c}+{\rm FN}^{1c}+{\rm FP}^{1c})$.

When $\mathbf{1}_{4K}^{T}\mathbf{y_{2}}\geq 0$, which is the second condition
in (63), the first condition in (63):
$\mathbf{1}_{4K}^{T}\cdot(\mathbf{A}^{T}\mathbf{y_{1}})\geq-\mathbf{1}_{4K}^{T}\mathbf{y_{2}}$
is always conflict with the condition (64):
$\mathbf{1}_{4K}^{T}\cdot(\mathbf{A}^{T}\mathbf{y_{1}})<-2\cdot\mathbf{1}_{4K}^{T}\mathbf{y_{2}}$,
as
$-2\cdot\mathbf{1}_{4K}^{T}\mathbf{y_{2}}\leq-\mathbf{1}_{4K}^{T}\mathbf{y_{2}}$.

Thus, the set:
$\\{\mathbf{y}|\mathbf{y}\in\mathbb{R}^{5K+1},\mathbf{\bar{A}}^{T}\mathbf{y}\geq
0,\mathbf{\bar{b}}^{T}\mathbf{y}<0\\}$ is always empty. This indicates the
system $\mathbf{\bar{A}\bar{z}}=\mathbf{\bar{b}}$ always has non-negative
solutions. The variables in the linear program represent probabilities that
are bounded in $[0,1]$. Therefore, the objective function of (40) is bounded.
The linear program always has solutions.

$\diamondsuit$

###  C.3 Proof of Theorem 3.6

Proof: The ${\rm Pr}_{D}(\widetilde{Y}\neq Y)$ in first condition can be
extended as:

$\begin{split}{\rm Pr}_{D}(\widetilde{Y}\neq
Y)&=\sum_{c=1}^{K}\sum_{a=0}^{1}({\rm
Pr}_{D}(\widetilde{Y}=0,Y=1,A=a,C=k)+{\rm
Pr}_{D}(\widetilde{Y}=1,Y=0,A=a,C=k))\\\ &=\sum_{c=1}^{K}\sum_{a=0}^{1}[{\rm
Pr}_{D}(\widehat{Y}=0,Y=1,A=a,C=k)\cdot{\rm
Pr}_{D}(\widetilde{Y}=\widehat{Y}|\widehat{Y}=0,A=a,C=k)\\\ &+{\rm
Pr}_{D}(\widehat{Y}=1,Y=1,A=a,C=k)\cdot{\rm
Pr}_{D}(\widetilde{Y}\neq\widehat{Y}|\widehat{Y}=1,A=a,C=k)\\\ &+{\rm
Pr}_{D}(\widehat{Y}=1,Y=0,A=a,C=k)\cdot{\rm
Pr}_{D}(\widetilde{Y}=\widehat{Y}|\widehat{Y}=1,A=a,C=k)\\\ &+{\rm
Pr}_{D}(\widehat{Y}=0,Y=0,A=a,C=k)\cdot{\rm
Pr}_{D}(\widetilde{Y}\neq\widehat{Y}|\widehat{Y}=0,A=a,C=k)]\\\
&=\sum_{c=1}^{K}\sum_{a=0}^{1}({\rm FN}^{ak}\cdot z_{0}^{ak}+{\rm
TP}^{ak}\cdot(1-z_{1}^{ak})+{\rm FP}^{ak}\cdot z_{1}^{ak}+{\rm
TN}^{ak}\cdot(1-z_{0}^{ak}))\\\
&=\mathbf{c}^{T}\mathbf{z}+\sum_{c=0}^{K}b_{c}p_{c}\\\
&=\mathbf{\bar{c}}^{T}\mathbf{\bar{z}}+\sum_{c=0}^{K}b_{c}p_{c}\end{split}$
(65)

As we show in proposition (3.2), the constraints of equal opportunity and
community fairness in the linear program (16) (or a standard form (40)) are:

$\begin{split}&\mathbf{\bar{A}}\mathbf{\bar{z}}=\mathbf{\bar{b}}\\\
\Rightarrow\quad&\mathbf{\bar{A}}^{T}\mathbf{\bar{A}}\mathbf{\bar{z}}=\mathbf{\bar{A}}^{T}\mathbf{\bar{b}}\end{split}$

For matrix $\mathbf{\bar{A}}^{T}\mathbf{\bar{A}}$, we have:

$\begin{split}\lambda_{\rm
min}(\mathbf{\bar{A}}^{T}\mathbf{\bar{A}})\mathbf{\bar{z}}^{T}\mathbf{\bar{z}}\leq\mathbf{\bar{z}}^{T}\mathbf{\bar{A}}^{T}\mathbf{\bar{A}}\mathbf{\bar{z}}\end{split}$
(66)

where, $\lambda_{\rm min}(\mathbf{\bar{A}}^{T}\mathbf{\bar{A}})$ is the
smallest eigenvalue of $\mathbf{\bar{A}}^{T}\mathbf{\bar{A}}$.

Then, we show the $l_{2}$ norm of $\mathbf{\bar{z}}$ is bounded:

$\begin{split}&\lambda_{\rm
min}(\mathbf{\bar{A}}^{T}\mathbf{\bar{A}})\mathbf{\bar{z}}^{T}\mathbf{\bar{z}}\leq\mathbf{\bar{z}}^{T}\mathbf{\bar{A}}^{T}\mathbf{\bar{A}}\mathbf{\bar{z}}\leq\|\mathbf{\bar{z}}\|_{2}\|\mathbf{\bar{A}}^{T}\mathbf{\bar{A}}\mathbf{\bar{z}}\|_{2}=\|\mathbf{\bar{z}}\|_{2}\|\mathbf{\bar{A}}^{T}\mathbf{\bar{b}}\|_{2}\\\
\Rightarrow\quad&\lambda_{\rm
min}(\mathbf{\bar{A}}^{T}\mathbf{\bar{A}})\|\mathbf{\bar{z}}\|_{2}\leq\|\mathbf{\bar{A}}^{T}\mathbf{\bar{b}}\|_{2}\\\
\Rightarrow\quad&\|\mathbf{z}\|_{2}\leq\frac{\|\mathbf{\bar{A}}^{T}\mathbf{\bar{b}}\|_{2}}{\underline{\sigma}^{2}}\end{split}$
(67)

where, $\underline{\sigma}$ is the smallest singular value of the matrix
$\mathbf{\bar{A}}$.

Thus, the ${\rm Pr}_{D}(\widetilde{Y}\neq Y)$ has:

$\begin{split}{\rm Pr}_{D}(\widetilde{Y}\neq
Y)&=\mathbf{\bar{c}}^{T}\mathbf{\bar{z}}+\sum_{c=0}^{K}b_{c}p_{c}\\\
&\geq-\|\mathbf{\bar{c}}\|_{\infty}\|\mathbf{\bar{z}}\|_{\infty}+\sum_{c=0}^{K}b_{c}p_{c}\quad\textit{(all
elements in c are negative)}\\\
&\geq-\|\mathbf{\bar{c}}\|_{\infty}\|\mathbf{\bar{z}}\|_{2}+\sum_{c=0}^{K}b_{c}p_{c}\quad(\|\mathbf{\bar{z}}\|_{2}\geq\|\mathbf{\bar{z}}\|_{\infty})\\\
&\geq-\|\mathbf{\bar{c}}\|_{\infty}\frac{\|\mathbf{\bar{A}}^{T}\mathbf{\bar{b}}\|_{2}}{\underline{\sigma}^{2}}+\sum_{c=0}^{K}b_{c}p_{c}\quad\textit{(the
upper bound (\ref{eq:lower_bound}}))\\\ \end{split}$ (68)

with $b_{c}p_{c}=({\rm TN}^{0c}+{\rm TP}^{0c}+{\rm TN}^{1c}+{\rm TP}^{1c})$.

When
$\Delta<-\|\mathbf{\bar{c}}\|_{\infty}\frac{\|\mathbf{\bar{A}}^{T}\mathbf{\bar{b}}\|_{2}}{\underline{\sigma}^{2}}+\sum_{c=0}^{K}b_{c}p_{c}$,
the inequality: ${\rm Pr}_{D}(\widetilde{Y}\neq
Y)\geq-\|\mathbf{\bar{c}}\|_{\infty}\frac{\|\mathbf{\bar{A}}^{T}\mathbf{\bar{b}}\|_{2}}{\underline{\sigma}^{2}}+\sum_{c=0}^{K}b_{c}p_{c}$
is conflict with the first condition in (45): ${\rm Pr}_{D}(\widetilde{Y}\neq
Y)\leq\Delta$.

Thus, if
$\Delta<-\|\mathbf{\bar{c}}\|_{\infty}\frac{\|\mathbf{\bar{A}}^{T}\mathbf{\bar{b}}\|_{2}}{\underline{\sigma}^{2}}+\sum_{c=0}^{K}b_{c}p_{c}$,
the fairness condition and $\epsilon$-accurate condition are incompatible with
each other. $\diamondsuit$

###  C.4 Proof of Theorem 3.7

The error rate of the fair outcome predictor is demonstrated in (65), which
is: ${\rm Pr}_{D}(\widetilde{Y}\neq
Y)=\mathbf{c}^{T}\mathbf{z}+\sum_{c=0}^{K}b_{c}\cdot p_{c}$.

The predictor $\widetilde{Y}$ is optimal when $\mathbf{z}=\mathbf{1}_{4k}$,
the error rate of the optimal predictor is: ${\rm Pr}_{D}(\widehat{Y}\neq
Y)=\mathbf{c}^{T}\mathbf{1}_{4K}+\sum_{c=0}^{K}b_{c}\cdot p_{c}$.

Thus, the minimum error we need to compromise for enforcing group fairness and
community fairness is:

${\rm Pr}_{D}(\widetilde{Y}\neq Y)-{\rm Pr}_{D}(\widehat{Y}\neq
Y)=\mathbf{c}^{T}\mathbf{z}-\mathbf{c}^{T}\mathbf{1}_{4K}$. $\diamondsuit$

##  Appendix D Additional Experimental Details and Results

###  D.1 Models and Hyperparameters

We provide the models and hyperparameters of post-FFL for each dataset. We run
the experiments on on our local Linux server with a 16-Core 4.00 GHz AMD RYZEN
Threadripper Pro 5955WX Processor. We implement all code in TensorFlow (Abadi
et al., 2015), simulating a federated network with one server and several
local communities.

For Adult, in each local community, we randomly divide the data into three
subsets: 60% for the training set, 20% for the validation set, and 20% for the
test set. We first implement the FedAvg algorithm. For each communication
round in FedAvg, the number of participating communities is set to $N=2$. We
set the number of local update epochs to $E=1$ with a batch size of $B=512$.
The local models are logistic regression classifiers with two layers,
containing 64 and 32 nodes, respectively. We use Relu as the activation
functions for each hidden layers. These models are trained using the Adam
optimizer with a learning rate of $\eta=0.001$. We select the number of rounds
that minimizes the validation loss, and then report the evaluation metrics on
the test dataset. We construct a linear program using the training data.
Finally, we apply post-processing to the test dataset based on the solution
from the linear program and report its evaluation metrics.

For the Diabetes dataset, we similarly split the local dataset into 60% for
training, 20% for validation, and 20% for testing. The number of participating
communities for FedAvg is set to $N=7$. We maintain the number of local update
epochs at $E=1$ with a batch size of $B=256$. We follow the same model
structure, optimization algorithm, and evaluation process as with the UCI
Adult dataset and report its evaluation metrics.

For HM 10000, we similarly split the local dataset into 60% for training, 20%
for validation, and 20% for testing. We resize the the images to $28\times
28\times 3$. We set the number of local update epochs to $E=5$ with a batch
size of $B=32$. The local models’ structure are as shown in Fig. 3 The loss
function we use for multi-class classification task is sparse categorical
cross entropy. The CNN models are trained using the Adam optimizer with a
learning rate $\eta=0.001$. We select the number of rounds that minimizes the
validation loss, and then report the evaluation metrics on the test dataset.
We construct a linear program using the training data. Finally, we apply post-
processing to the test dataset based on the solution from the linear program
and report its evaluation metrics.

Figure 3: The CNN structure used for HM10000 Dataset

###  D.2 Baselines

In Section 5.2, we use q-FedAvg (Li et al., 2019) and AFL (Mohri et al., 2019)
as baselines for community fairness, and FairFed (Ezzeldin et al., 2023) as
the baseline for group fairness. Detailed descriptions and convergence curves
of all baselines are provided below:

  * •

q-FedAvg (Li et al., 2019) improves community fairness in Federated Learning
(FL) by minimizing an aggregated reweighed loss, parameterized by $q$. The
algorithm assigns greater weight to devices with higher loss. The parameter
$q$ controls the trade-off between community fairness and model utility. In
our experiments, we set $q=4$ for Adult, following the recommendation in the
original implementation of the q-FedAvg paper and $q=1$ for HM1000.

  * •

FairFed, (Ezzeldin et al., 2023) improves equal opportunity in FL, which also
minimizes an aggregated reweighed loss, parameterized by $\beta$. The weights
are a function of the mismatch between the global EOD (on the full dataset)
and the local EOD at each community, favoring communities whose local
measurement match the global measurements. $\beta$ is the parameter that
control the tradeoff between the group fairness and model utility. We follows
the initial paper’s setting: $\beta=1$ for Adult and $\beta=2$ for HM1000.

The convergence curves of FedAvg, q-FedAvg, and FairFed are shown in Fig. 4.

Figure 4: Adult dataset: Training curves of Fedavg (left), FairFed (middle),
and q-FedAvg (right)

###  D.3 Additional Results of Different Data Heterogeneity Level

We provide results of HM10000 with various degrees of data heterogeneity in
Table 7. Similar as Adult, we introduce community heterogeneity by adjusting
the mixture of individuals with specific target and sensitive attributes.

We define class 1 as unprotected Melanocytic Nevi samples $(y=4,s=1)$, class 2
as protected Melanocytic Nevi $(y=4,s=0)$, class 3 as unprotected non-
Melanocytic Nevi $(y\neq 0,s=1)$, and class 4 as protected non-Melanocytic
Nevi $(y\neq 4,s=0)$. We sample the local communities’ datasets so that the
class proportion of each community is as shown in Fig. 5.3. For scenario 1,
Data is i.i.d. distributed across all communities. The sensitive attribute is
totally skewed across two communities in scenario 2. Both the target and
sensitive attributes are imbalanced across communities in scenario 3

(a) Scenario 1 (s1)

(b) Scenario 2 (s2)

(c) Scenario 3 (s3)

Figure 5: HM1000: The class proportion of the three scenarios Table 7: Experimental results with different degrees of heterogeneity(HM1000) Scenario | Algorithms | Avg-Acc | EOD | Acc@1 | Acc@2 | Acc@3 | Acc@4 | Acc@5 | AD | Accuracy trade for fairness
---|---|---|---|---|---|---|---|---|---|---
s1 | FedAvg | 0.695 | 0.002 | 0.694 | 0.693 | 0.714 | 0.693 | 0.680 | 0.034 | -
s1 | PostFFL | 0.688 | 0.007 | 0.699 | 0.682 | 0.719 | 0.680 | 0.664 | 0.056 | 0.007
s2 | FedAvg | 0.675 | 0.076 | 0.865 | 0.932 | 0.637 | 0.447 | 0.270 | 0.662 | -
s2 | Post-FFL | 0.330 | 0.00 | 0.344 | 0.317 | 0.318 | 0.346 | 0.334 | 0.029 | 0.345
s3 | FedAvg | 0.681 | 0.060 | 0.522 | 0.500 | 0.697 | 0.900 | 0.658 | 0.451 | -
s3 | Post-FFL | 0.509 | 0.016 | 0.533 | 0.498 | 0.516 | 0.513 | 0.476 | 0.058 | 0.172