###### Abstract

Privacy and Fairness both are very important nowadays. For most of the cases
in the online service providing system, users have to share their personal
information with the organizations. In return, the clients not only demand a
high privacy guarantee to their sensitive data but also expected to be treated
fairly irrespective of their age, gender, religion, race, skin color, or other
sensitive protected attributes. Our work introduces a novel architecture that
is balanced among the privacy-utility-fairness trade-off. The proposed
mechanism applies Group Tagging Method  and Fairly Iterative Shuffling (FIS)
that amplifies the privacy through random shuffling and prevents linkage
attack. The algorithm introduces a fair classification problem by Relation
Impact based on Equalized Minimal FPR-FNR among the protected tagged group.
For the count report generation, the aggregator uses TF-IDF to add noise for
providing longitudinal Differential Privacy guarantee. Lastly, the mechanism
boosts the utility through risk minimization function and obtain the optimal
privacy-utility budget of the system. In our work, we have done a case study
on gender equality in the admission system and helps to obtain a satisfying
result which implies that the proposed architecture achieves the group
fairness and optimal privacy-utility trade-off for both the numerical and
decision making Queries.

Fairly Private Through Group Tagging
---
and Relation Impact
Poushali Sengupta |  Subhankar Mishra
Department of Statistics |  School of Computer Sciences
University of Kalyani |  National Institute of Science, Education and Research
Kalyani, West Bengal |  Bhubaneswar, India -752050
India - 741235 |  Homi Bhabha National Institute,
|  Anushaktinagar, Mumbai - 400094, India
<EMAIL_ADDRESS>|<EMAIL_ADDRESS>
ORCID: 0000-0002-6974-5794 |  ORCID: 0000-0002-9910-7291

##  1 Introduction

To deal with information leakage [1] [2], nowadays the organizations and
industries have all concentration on the ”privacy” of the dataset which is the
most important and necessary thing to protect the dataset from some unexpected
attacks by the attackers that causes data breach. The main aim of a
statistical disclosure control is to protect the ”privacy” of ”individuals” in
a database from the sudden attack. To solve this problem, in 2006, Dwork
introduces the notion of ”Differential Privacy”(DP) [3], [4] [5]. Some of the
important works on DP have been summarized in table 1.

Paper | Year |  Brief Summary
---|---|---
Differential Privacy [5] | 2006 |  Initial work on DP
RAPPOR [7] | 2014 |  Fastest implementation of LDP
Deep Learning with Differential Privacy[8] | 2016 |  Introduces a refined analysis of privacy costs within DP
Communication-Efficient Learning of Deep Networks from Decentralized Data [9] | 2016 |  Introduces practical method for the federated learning of deep networks based on iterative model averaging
PROCHLO [10] | 2017 |  Encode Shuffle and Analyse (ESA) for strong CDP
Adding DP to Iterative Training Procedures [11] | 2018 |  Introduces an algorithm with the modular approach to minimize the changes on training algorithm, provides a variety of configuration strategies for the privacy mechanism.
Amplification by Shuffling [12] | 2018 |  $\mathcal{O}(\epsilon\sqrt{\log{\frac{1}{\delta}/n},\delta})$ centralized differential privacy(CDP) guarantee
Controlled Noise [13] | 2019 |  duel algorithm based on average consensus (AC)
Capacity Bounded DP [14] | 2019 |  Location Privacy with matrix factorization
ARA [15] | 2020 |  Aggregration of privacy reports & fastest CDP.
Privacy at Scale[16] | 2020 |  Privatization, ingestion and aggregation
ESA Revisited [35] | 2020 |  Improved [12] with longitudinal privacy
BUDS[17] | 2020 |  Optimize the privacy-utility trade-off by Iterative Shuffling and Risk Minimizer.
Table 1: Related works on Differential Privacy

Adding to the importance of trade-off between privacy-Utility guarantee to the
sensitive data, the demand for fairness also belongs to the clients’ top
priority list. Nowadays, in most online service systems, users not only ask
for high privacy but also expect to be treated fairly irrespective of
religion, skin color, native language, gender, cast, and other sensitive
classes. Table 2 shows some existing algorithms on fairness mechanism.

Paper | Year |  Brief Summary
---|---|---
Fairness Beyond Disparate Treatment Disparate Impact [19] | 2017 |  Introduces Disparate Mistreatment for group fairness.
Algorithmic decision making and the cost of fairness [20] | 2017 |  Deals with a tension between constraint and unconstrained algorithms.
On Fairness and Calibration[21] | 2017 |  Explore the stress between minimizing error discrepancy across different population groups while maintaining calibrated probability estimates.
An Information-Theoretic Perspective Fairness and Accuracy [22] | 2019 |  Provide trade-off between fairness and accuracy.
Fairness Through the Lens of Proportional Equality [23] | 2019 |  Measure the fairness of a classifier and provide group fairness through proportional equality
FACT: A Diagnostic for Group Fairness Trade-offs [24] | 2020 |  Enable systematic characterization of performance-fairness trade-offs among the group.
Fair Learning with Private Demographic Data [25] | 2020 |  allows individuals to release their sensitive information privately while allowing the downstream entity to learn predictors which are non-discriminatory giving theoretical guarantees on fairness.
Fairness, Equality, and Power in Algorithmic Decision-Making [26] | 2021 |  Focuses on inequality and the causal impact of algorithms and the distribution of power between and within groups.
Table 2: Related works on Fairness

In their 2012 work [18] Dwork et al. have explicitly shown that individual
fairness is a generalization of $\epsilon-$differential privacy. There is a
distinction in fair ML research between ‘group’ & ‘individual’ fairness
measures. Much existing research assumes that both have importance, but
conflicting. [34] argues that this seeming conflict is based on a
misconception and shows that individual and group fairness are not
fundamentally in conflict.[28, 29, 30, 31, 32, 33] are some state-of-the-art
algorithms on Fairness with Differential Privacy. However, none of them
provide either the tight bounds on privacy & loss function or an optimal
trade-off between privacy-utility-fairness. Our proposed mechanism aims to
achieve both.

In this work, the idea is to introduce a group fairness mechanism along with a
differential privacy mechanism with the help of the Fairly Iterative Shuffling
technique which provides optimal privacy-utility trade-off. The main aim of
this work is to make the balance among privacy-utility-fairness during the
process. The contributions of this work are:

  1. 1.

Group Tagging method tags every individual by their protected attribute class
so that the $FIS$ can not change their protected data during the shuffling. If
it will change, the classifier’s decision will not be fair as the system wants
to generate group fairness among the protected attribute class in the
decision-making problem.

  2. 2.

$FIS$ itself posses a strong privacy guarantee to the data that prevents all
types of linkage attack

  3. 3.

The proposed architecture applies the notion of Relation Impact for
maintaining group fairness to decide the allowance or giving the chance of
participation of the individuals in any particular event without the leakage
of their protective attributes.

  4. 4.

Here, every individual is treated according to their due rather than only
”merit”. So, the mechanism not only focuses on the directly related attribute
but also considers the highly related background factor which affects the
results indirectly.

  5. 5.

Risk Minimzer amplifies the utility by minimizing expected loss of the model
and helps to achieve the optimal privacy-utility trade-off through
regularization parameter.

##  2 Methodology

The goal of work is to develop an unbiased secured mechanism bringing fairness
which is also differentially private. To achieve, before fairness is
implemented, the collected data must differentially private without hampering
the number of persons corresponding to the respected protected groups, i.e the
data will be divided into separate groups according to the variety of
protected class.
Let assume we have a data set with the records of $n$ individuals and the
number of dependent attributes is $m$. Among the $n$ individuals, let there be
$n_{i}$ number of individual having $i^{th};i=1(1)n_{p}$ protected attribute.
The whole mechanism is divided into seven parts, they are One-hot Encoding of
collected data, Query Function, Group tagging, Correlation Matrix, Fairly
Iterative Shuffling (FIS), 2-Layers Fair Classification through Relation
Impact and Boosting Utility through Risk Minimizer & Count Report Generation.

###  2.1 One-Hot Encoding

One hot encoding [17] [4] is a method of converting categorical variables into
a structured form that could be used in ML algorithms to do better performance
in prediction. Now, the correct choice of encoding has a great impression on
the utility guarantee. In this architecture, the preference is one-hot
encoding instead of any other process of encoding to generate a fair &
privatized report with the least noise insertion and provides maximum utility.

###  2.2 Query Function

In the first phase of this architecture, a query function [17] is used on the
dataset to get the important attributes related to a particular query as shown
in table 3. Though our proposed DP mechanism works for generalized group
fairness problems, we have taken Example 2 as our case study and analyzed the
case of gender unbiasedness more elaborately in upcoming sections. Also, it is
to be noted, This mechanism performs for both (Example 1 & 2) type of Queries;
related to numerical and decision-making problems and always provide the
privatized DP report against user’s protected attributes.

Query |  Analysis
---|---
Example 1: How many Hindus live in the urban area with the score in maths greater than ninety percent? |  The attributes ’Religion’, ’living area’, and ’marks in maths’ will be delivered as answers from the query function. This implies that only these three attributes are important for generating the final report to that particular numerical (count-related) query. This type of Question does not need any fair decision but should be privatized against the protected attribute ”Religion”.
Example 2: Which students are eligible the admission based on the marks of maths? |  Now for this type of question, not only the attribute ’marks of maths’ is important, but also the gender of the students matter as we want to develop a fair mechanism. For this, it is necessary to give special importance to the attribute ’sex’ in every case which is achievable by the attribute tagging method that is discussed later. For this mechanism, the query function considers the attribute ’sex’ as the important attribute and returns it no matter what the question is just to maintain a fair balance between male and female candidates.
Table 3: Query Function: Assume the database is structured with records of
individuals where name, age, sex, marks of maths, marks of physics, marks of
computer science, annual family income, living area, religion are ten
attributes.

###  2.3 Correlation Matrix

After the query function[17], the mechanism calculates a correlation matrix
that measures the relation distance of each attribute with the required
events. The previously given Examples 2 concentrate on the decision that
should fair related to gender in the admission system based on the maths
score. But in reality, other sensitive background factors are indirectly
related to the examination results that are obtained by the students. For
example, the economical status, electricity facility, tuition opportunity,
etc. It is obvious that the students came from the strong economical
background or high-class society usually take more than one tuition or extra
classes to improve scores. On the other hand, the poor students can’t afford
such facilities. Not only that, in some cases, they don’t have the proper
environment to study like electricity, proper living area, etc. Now, these
factors have a great effect on their results and should not be avoided. So,
here, the correlation matrix is used to get the highly related background
factors that have a great impact on the required event.

For the general case in, having a dataset with $n$ rows and $k$ attributes,
the applied query function returns $c$ the number of attributes which are
required to generate the answer along with protected attribute (such as skin
color, religion, gender, etc) and the correlation matrix returns $d$ number of
related background factors that affects the results. If $m=c+d$ (excluding
protected attribute) number of total attributes are important for generating
the final report, then these $m$ attributes will tie up together to represent
a single attribute and the reduced number of attributes will be $g=k-m$. Let
assume, there are $2S(S>1)$ number of shufflers and if $g$ is divisible by
$S$, these attributes are divided into $S$ group with $g/S$ attributes in each
group. Now, If $g$ is not divisible by $S$, then extra elements will choose a
group randomly without replacement. After that, the group tagging method is
applied which helps to preserve the individuals’ protected attributes after
fairly iterative shuffling [17] method. As the tied-up attributes include the
highly related background attribute to the given event, the following group
tagging method assists the fair classification in the future.

###  2.4 Group Tagging Method

Group tagging is a method to classify the individuals based on their protected
attribute where each tagged group contains $S$ group of attributes each. This
process can be happened by tagging each row with their corresponding protected
class. If we consider the given Example 2 which concentrates on fairness
between gender groups (we have taken male and female groups for case study)
for admission, the method will work as follow. If the first row contains a
record of a female candidate, then this row is tagged by its gender group
’female’. For the male candidates, the rows are tagged by ’male’. Now rows
having the same tagging element will shuffle among each other i.e In the case
of female candidates, the iterative shuffling will occur only with the rows
tagged as ’female’ and on the other hand, rows tagged with ’male’ goes for
iterative shuffling separately. In this way, the records of male and female
candidates never exchange with each other and help to maintain their gender in
the generated report. This process never hampers the accuracy of the
classifiers for taking a fair decision based on their gender group in the
given problem. Also, the iterative shuffle technique establishes a strong
privacy guarantee which shuffles all the records of female and male candidates
separately among their tagged group. In this way, the probability of belonging
the record of a particular individual to their unique ID becomes very low, and
the unbiased randomization shuffles technique keeps the data secured. This
technique prevents all types of linkage attacks, similarity attacks,
background knowledge attacks and also reduces the exposure of user data
attributes.

###  2.5 Fairly Iterative Shuffling (FIS)

A randomized mechanism is applied with Fairly Iterative Shuffling which occurs
repeatedly to the given data for producing the randomized unbiased report to a
particular query. Let’s have a dataset with $n$ rows containing the records of
$n$ individuals among which $n_{1}$ persons are female and $n_{2}=n-n_{1}$
persons are male. That means after the group tagging method, there are exactly
$n_{1}$ rows tagged as ’female’ whereas $n_{2}$ rows are tagged as ’male’. In
this stage of our proposed architecture, each row of ’male’ and ’female’
groups is shuffled iteratively by the $2S,(S>1)$ number of shufflers. Before
shuffling each gender group is divided into some batches containing $S$
attribute groups and every attribute group of each batch chooses a shuffler
from the $S$ number of shufflers randomly without replacement for independent
shuffling. Now the female tagged group contain $n_{1}$ individuals and assume
that it is divided into $t_{F}$ batches where $1,2,....,t_{F}$ batches have
$n_{11},n_{12},....,n_{1t_{F}};(n_{11}\simeq n_{12}\simeq....\simeq
n_{1t_{F}})$ number of rows respectively. Similarly, let assume the male
tagged group have $n_{2}$ individuals’ records and it is divided into
$1,2,....,t_{M}$ batches having $n_{21},n_{22},....,n_{2t_{M}};(n_{21}\simeq
n_{22}\simeq....\simeq n_{2t_{M}})$ rows respectively. Now for one gender
tagged group, each attribute group of every batch chooses a shuffler randomly
without replacement from any $S$ number of shufflers. On the other hand, For
another gender-tagged group, each group of attributes chooses a shuffler
similarly from the remaining $S$ number of shufflers. This shuffling technique
occurs repeatedly or iteratively until the last batches of both the gender
tagged group goes for independent shuffling.

This architecture is applicable in the generalized case also and not only
limited to gender unbiasedness problem If there is $i$ number of variety for a
protected attribute (skin color, religion, etc), the individuals tagged with
their considerable protected class and then divided into $i$ number of groups.
Each group divided into batches ($t_{i}$ number of batches for $ith$ group)
with approximately same batch size ($n_{i}1\simeq n_{i}2\simeq...\simeq
n_{it_{i}}$) and go for shuffling [35] [17].

###  2.6 2-Layers Fair Classification through Relation Impact.

This mechanism uses $2$ layer classifications. After $FIS$, firstly the
classifiers use the group classifications that classify the individuals into
gender groups (male and female) from the shuffled data sets. After that, the
classifiers make the subgroup-classifications between the groups depends on
the Relation Impact (details in section 3.2).

####  2.6.1 Group Classification:

After $FIS$ the classifiers divided the shuffled data into the number of
classes according to their gender. In our problem setting, the mechanism
focuses on the gender unbiasedness between males and females. This step is the
1st layer of classification where the classifiers use the tagged gender label
to classify the data. As in the group tagging method each individual is tagged
with his gender category, the classifiers concentrate on this tagged label for
classification. This classification is made based on user-given gender
information which cannot be affected or changed by the shuffling as it is tied
up before going for $IS$. So, the chance of miss classification error is very
less (in fact negligible) here.

####  2.6.2 Subgroup-Classification

This is the second layer of classification where the classifier classifies the
groups into positive and negative subgroups by the notion of Relation Impact.
The classifiers decide the eligibility, i.e if an individual should be allowed
to be admitted to the course based on their related background information.
For example $2$, the classifiers make the decision based on the student’s math
score, their economical background, living area (rural/ urban), electricity
facility, etc. The positive class of each gender group contains the eligible
individuals and the negative class contains the rejected individuals for the
admission.

###  2.7 Risk Minimization and Count Report Generation

This is an important stage of this architecture where the report is generated
from a shuffled and unbiased dataset for a given q query related to sum or
count aggregation i.e.numerical answer (consider the Example 1). The report is
generated by average count calculation by an aggregator function that uses TF-
IDF[15] [17] calculation to add minimum noise to the report. But, before the
final report generation, the loss function [17] is calculated, and risk
minimizing assessment [17] is done to obtain the optimal solution. This
optimal solution refers to the situation where the architecture achieves a
strong privacy guarantee, as well as maximum utility[27] measure while
providing an unbiased report against a protected class. The details of risk
minimization technique is discussed in section 3.3.

##  3 Analysis

Considering a data set containing $n$ rows and $g$ attributes and there exists
a $iS$ number of shufflers. The attributes are divided into $S$ groups as
described previously. Now there is $n_{i}$ number of individuals tagged as
$i^{it}$ protected attribute; $i=1,2,..n_{p}$ where each row of the dataset
has the records of individuals corresponding to their crowd ID. The tagged
attributes divide the data sets into groups, For example, if there is $i$
number of variety in a protected attribute, tagged individuals will be divided
into $i$ groups. Now, Each tagged group are divided into some batches
containing approximately the same rows i.e. $1,2,...,t_{i}$ number of batches
for group tagged with $i^{th}$;$i=1(1)n_{p}$ attribute. After that, each group
of attribute from every batch chooses a random shuffler and go for shuffling.

###  3.1 FIS Randomised Response Ratio and Privacy Budget

To proceed further with the proof, we will consider the following theorem from
BUDS[17]:

######  Theorem 3.1.

(Iterative Shuffling : IS [17]) A randomisation function $\mathcal{R^{*}_{S}}$
applied by $S\ (S>1)$ number of shuffler providing iterative shuffling to a
data set $X$ with $n$ rows and $g$ attributes, where the data base is divided
into $1,2,...,t$ batches containing $n_{1},n_{2},...,n_{t}$ number of rows
respectively, will provide $\epsilon$-differential privacy to the data with
privacy budget-

$\epsilon=\ln{(RR_{\infty})}=\ln{\bigg{[}\frac{t}{(n_{1}-1)^{S}}\bigg{]}}$ (1)

only when, $n_{1}\simeq n_{2}\simeq.....\simeq n_{t}$.
Here $RR_{\infty}$= Randomised Response Ratio, and

$RR=\frac{P(Response=YES\ |\ Truth=YES)}{P(Response=YES\ |\ Truth=NO)}$ (2)

######  Lemma 1.

The Randomised Response Ration of Iterative Shuffling($RR_{IS}$) [4] [5]=
$\frac{P(Row\ belongs\ to\ its\ own\ unique\ ID)}{P(Row\ does\ not\ belongs\
to\ its\ own\ unique\ ID)}$ satisfy the condition of Differential Privacy.

Now, the proposed architecture provides a fair mechanism along with a strong
privacy budget to secure the sensitive information of individuals. This
algorithm is the non-discriminant of biases regarding different groups based
on protected attributes (For example gender, skin color, etc). Now the help of
theorem 1, the privacy budget of FIS is developed next.

######  Theorem 3.2.

(Fairly Iterative Shuffling- FIS) A randomisation function
$\mathcal{R^{*}}_{iS}$ applied by $iS\ (S>1)$ number of shuffler providing
iterative shuffling to a data set $X$ with $n$ rows and $g$ attributes among
which $n_{i}$ number of individuals are tagged with $i$th protected class
($i=1,2,...n_{p}$); i.e. there are $n_{p}$ number of user groups according to
their protected class where tagged groups are divided into $1,2,...,t_{i}$
batches containing $n_{i1},n_{i2},...,n_{it_{i}}$ number of rows for $i$th
group, will provide $\epsilon$-differential privacy to the data with privacy
budget-

$\epsilon_{Fair}=\ln\bigg{[}\frac{1}{n_{p}!}{\Sigma_{i=1}^{n_{p}}\frac{t_{i}}{(n_{it_{i}}-1)^{S}}}\bigg{]}$
(3)

only when, $n_{i1}\simeq n_{i2}\simeq.....\simeq n_{it_{i}}$;
$i=1,2,...,n_{p}$

###### Proof.

The records in the group of attributes for the different tagged groups go for
independent shuffling separately. According to the theorem 3.1 [17] we can say
that, For the records tagged with $i$th group,

$\displaystyle RR_{i}$ $\displaystyle=\frac{P(Row\ belongs\ to\ its\ own\
unique\ ID\ tagged\ with\ ith\ group)}{P(Row\ does\ not\ belongs\ to\ its\
own\ unique\ ID\ tagged\ with\ ith\ group)}$ (4)
$\displaystyle=\frac{t_{i}}{(n_{it_{i}}-1)^{S}}$ (5)

as,$n_{i1}\simeq n_{i2}\simeq.....\simeq n_{it_{i}}$; $i=1,2,...,n_{p}$. So,
For the whole architecture the fair randomized response will be:

$RR_{\infty}=\frac{1}{n_{p}!}\bigg{[}\frac{t_{1}}{(n_{1t_{1}}-1)^{S}}+\frac{t_{2}}{(n_{2t_{2}}-1)^{S}}+...+\frac{t_{n_{p}}}{(n_{n_{p}t_{n_{p}}}-1)^{S}}\bigg{]}$
(6)

Now the privacy budget for this proposed architecture is:

$\epsilon_{Fair}=\ln\frac{1}{n_{p}!}{\bigg{[}\frac{t_{1}}{(n_{1t_{1}}-1)^{S}}+\frac{t_{2}}{(n_{2t_{2}}-1)^{S}}+...+\frac{t_{n_{p}}}{(n_{n_{p}t_{n_{P}}}-1)^{S}}\bigg{]}}$
(7)

That means,

$\epsilon_{Fair}=\ln\bigg{[}\frac{1}{n_{p}!}{\Sigma_{i=1}^{n_{p}}\frac{t_{i}}{(n_{it_{i}}-1)^{S}}}\bigg{]}$
(8)

∎

In our case study, we focuses on the decision problem of gender unbiasedness
between male and female groups for allowing them to take admission in a
particular course (considering example 2). For this case, the $FIS$ posses a
privacy budget of :

$\epsilon=\ln\frac{1}{2}{\bigg{[}\frac{t_{F}}{(n_{1t_{F}}-1)^{S}}+\frac{t_{M}}{(n_{2t_{M}}-1)^{S}}\bigg{]}}$
(9)

Where, $S>1$, $n_{1}$is the number of female in database, $n_{2}=(n-n_{1})$ is
number of male in database, $t_{F}$ is the number of batches in female group,
$t_{M}$ is the number of batches in male group, $n_{1t_{F}}$ is the average
female batch size, $n_{2t_{M}}$ is average male batch size and
$\epsilon_{Fair}$ is the privacy parameter of this mechanism. The small value
of $\epsilon_{Fair}$ refers to a better privacy guarantee.

###  3.2 Fair Classifiers and Relation Impact

After $FIS$, we introduce the notion of Relation Impact that helps the
classifiers to take a fair decision. This mechanism applies fair classifiers
that use the principle of Relation Impact to avoid the miss classification
error and able to create unbiased classes or groups to consider for giving
chance in an event.

######  Definition 3.3.

Relation Impact: The aim of a set of classifiers is to study a classification
function $\hat{h}_{c}:\mathcal{X}\longrightarrow\mathcal{Y}$, defined in a
hypothesis space $\mathcal{H}$ where $\hat{h}_{c}$ minimizes some aimed loss
function to reduce miss-classification error based on the related background
attribute class $\mathcal{A}=(a_{1},a_{2},....,a_{m})$ :

$\hat{h}_{c}:=\operatornamewithlimits{argmin}_{h_{c}\in\mathcal{H}}E_{(\mathcal{X},\mathcal{Y})\sim
P}L[{h_{c}(\mathcal{X}|\mathcal{A}),\mathcal{Y}}]$ (10)

The Efficiency of the classifier will be estimated using testing dataset
$\mathcal{D}_{tst}={{(x_{j_{t}},y_{j_{t}})}^{n_{t}}}_{j=1(1)n_{t}}$,based on
the observation that how accurate the predicted labels
$\hat{h}_{c}(x_{j_{t}}|\mathcal{A})$’s, are corresponds to the true labels
$y_{j}$’s.

Therefore, it means the decision regarding the relevant persons or groups is
taken according to their due based on all the highly related factors to that
particular event. This implies that distribution will not possess numerical
equality whereas it will be influenced by the relation distance of important
background factors and consider the individuals according to their rightful
needs. For example, in the classroom, this might mean the teacher spending
more time with male students at night classes rather than female students
because most of the time female students do not choose to take the night
classes for safety issues. Not only that, the students (irrespective of
gender) who came from the weaker economical background cannot always
participate in the extra classes or cannot afford any extra books or study
material. So, it is clear that, in the admission system, if someone wants to
choose the students fairly, not only the sex group matters, but also the
economical background, and other factors like appropriate subject scores,
living locations, electricity facility, etc also matters. So, these types of
factors which are directly and indirectly highly related to the final exam
score of the students should be taken to account. The notion of Relation
Impact exactly does that, where it trains the model by considering all the
highly related attributes for taking the decision and minimizes the expected
error of the classification by Equalizing Minimal FPR-FNR of different groups.

In our work, the idea is to provide a fair decision with the help of an
unbiased classification based on the correlation of the attributes to the
required event. The mechanism first calculates the correlation matrix and any
attributes which have the higher (usually greater than 0.5 or less than -0.5)
positive and negative correlation to the required events are only taken to be
accountable for the final decision-making procedure. Here the classifiers use
the Relation Impact where the main aim is to build a model that can minimize
the expected decision loss to reach the maximum accuracy. The classifiers
attend that minimum loss, i.e minimum miss classification error, by achieving
the Minimal Equalised FPR-FNR of the different groups; FPR: False Positive
Rate, FNR: False Negative Rate.

######  Definition 3.4.

Equalized Minimal FPR-FNR: Let’s have a set of classifiers
$\hat{h_{c}}\\{h_{c1},h_{c2},...h_{ci}\\}:\mathcal{X}\rightarrow\mathcal{Y}$
based on the hypothesis space $\mathcal{H}$ where $i=1,2..n_{p}$ denotes the
number of groups, and $\mathcal{A}=\\{A_{1},A_{2},...A_{m}\\}$ is the set of
related background attributes, then the classifier is said to satisfy the
condition of Equalised Minimal FPR-FNR ratio if :

$\operatornamewithlimits{argmin}_{h_{c}\epsilon\mathcal{H}}FPR_{1}(\mathcal{A})=\operatornamewithlimits{argmin}_{h_{c}\epsilon\mathcal{H}}FPR_{2}(\mathcal{A})=..........=\operatornamewithlimits{argmin}_{h_{c}\epsilon\mathcal{H}}FPR_{n_{p}}(\mathcal{A})$
(11)

and,

$\operatornamewithlimits{argmin}_{h_{c}\epsilon\mathcal{H}}FNR_{1}(\mathcal{A})=\operatornamewithlimits{argmin}_{h_{c}\epsilon\mathcal{H}}FNR_{2}(\mathcal{A})=..........=\operatornamewithlimits{argmin}_{h_{c}\epsilon\mathcal{H}}FNR_{n_{p}}(\mathcal{A})$
(12)

Here, $\hat{h_{c}}(\mathcal{X})$ is the predicted label by the classifier,
$\mathcal{Y}$ is the true label and both of them take the label value either
$y_{1}$ or $Y_{0}$ where $y_{1}$ denotes the positive label, $y_{0}$ denotes
the negative label and

$FPR_{i}(\mathcal{A})=P_{i}(\hat{h_{c}}(\mathcal{X})=y_{1}|\mathcal{Y}=y_{0},\mathcal{A})$
(13)

and

$FNR_{i}(\mathcal{A})=P_{i}(\hat{h_{c}}(\mathcal{X})=y_{0}|\mathcal{Y}=y_{1},\mathcal{A})$
(14)

For our mentioned problem in example $2$, the classifier will achieve the
higher accuracy for predicting the positive and negative subgroups for both
the gender groups (Male and Female), by minimizing the target loss when ,

$\operatornamewithlimits{argmin}_{h_{c}\epsilon\mathcal{H}}FPR_{F}(\mathcal{A})=\operatornamewithlimits{argmin}_{h_{c}\epsilon\mathcal{H}}FPR_{M}(\mathcal{A})$
(15)

and

$\operatornamewithlimits{argmin}_{h_{c}\epsilon\mathcal{H}}FNR_{F}(\mathcal{A})=\operatornamewithlimits{argmin}_{h_{c}\epsilon\mathcal{H}}FNR_{M}(\mathcal{A})$
(16)

######  Remark 1.

FIS does not hamper the Equalised Minimal FPR-FNR (Detailed discussion is in
appendix)

###  3.3 Boosting Utility Through Risk Minimization

The real information which can be gained from the data by a particular query
or set of queries is defined as the utility [27] of the system. The goal of
this section is to discuss the gained utility from the data by applying Fair-
BUDS and provide a tight bound for loss function between input and output
average-count. This bound has a great impact on the utility of the system and
this depends on the previously obtained privacy budget. Before obtaining the
final result, an optimization function with a risk assessment technique[17] is
applied to get the maximum utility from the data. Let’s assume, before $FIS$
shuffling, the true data set will give a average count report for a time
horizon $[d]=\\{1,..d\\}$ which is denoted as
$\mathcal{C_{T}}=\sum_{i=1}^{n}\sum_{j\epsilon\mathcal{Q}}\sum_{T\epsilon[d]}x_{ij}[T]$;
where, $x_{ij}$ is the jth record of the ith individual from the true data set
for the time horizon $[d]$ and $\mathcal{Q}=\\{a_{1},a_{2},...\\}$ is the set
of attributes given by the query function for a particular set query or set of
queries. Now,
$\mathcal{C_{FS}}=\sum_{i=1}^{n}\sum_{j\epsilon\mathcal{Q}}\sum_{T\epsilon[d]}x^{FS}_{ij}[d]$;
where $x^{FS}_{ij}$ is the jth record of the ith individual from the $FIS$
data set for the time horizon $[d]$. The calculated loss function [17]
regarding the input and output count will be:

$\mathcal{L}(\mathcal{C_{T}},\mathcal{C_{FS}})\leq\mathcal{C_{FS}}\times\bigg{|}e^{\ln\bigg{[}\frac{1}{n_{p}!}{\Sigma_{i=1}^{n_{p}}\frac{t_{i}}{(n_{it_{i}}-1)^{S}}}\bigg{]}}-1\bigg{|}$
(17)

When, $e^{\epsilon}\rightarrow 0$, the Utility
$\mathcal{U}(\mathcal{C_{T}},\mathcal{C_{FS}}|\mathcal{X},\mathcal{Y})\rightarrow
1$ as $\mathcal{L}(\mathcal{C_{T}},\mathcal{C_{FS}})\rightarrow 0$. Now the
aim of this architecture is not only to be fair and secured but also it should
pose a high utility guarantee which can be obtained by risk-minimizing
assessment [17]. Proceeding with risk minimization technique, a mechanism
$\mathcal{R^{*}}(iS)$ can be found (when there is $i$ number of tagged groups)
which minimizes the risk [17], where

$\mathcal{R^{*}}(iS)=\operatornamewithlimits{argmin}_{\text{$\mathcal{R^{*}}(iS)\epsilon\mathcal{H}$}}Risk_{\text{(Ep)}}(\mathcal{R^{*}}(iS))$
(18)

##  4 Conclusion And Future Scope

The Proposed architecture provides group fairness to the user based on their
protected attribute class while giving a strong privacy guarantee to their
sensitive attribute. The Risk Minimizer amplifies the utility Guarantee to the
system which makes the algorithm possess an optimal balance between privacy-
utility-fairness. This balanced architecture full-filled user’s top priorities
related to fairness and Privacy in the Online Service system. Though the
mechanism shows good performance in privacy-utility trade-off for all kinds of
Queries and generates unbiased classification for decision-making problems,
the use of One-Hot encoding is one kind of constraint for big data analysis.
Trying other encoding option (which does not depend on data dimension) is our
future target. On the other hand, the work performance and both the privacy-
utility upper bounds are given on theoretical aspects only. So, various
experiments with different benchmark datasets for both online and offline
settings are also in our plan.

## References

  * [1] Chatzikokolakis, Konstantinos, Tom Chothia, and Apratim Guha. ”Statistical measurement of information leakage.” International Conference on Tools and Algorithms for the Construction and Analysis of Systems. Springer, Berlin, Heidelberg, 2010.
  * [2] M’rio, S. Alvim, et al. ”Measuring information leakage using generalized gain functions.” 2012 IEEE 25th Computer Security Foundations Symposium. IEEE, 2012.
  * [3] Dwork, Cynthia. ”Differential privacy: A survey of results.” International conference on theory and applications of models of computation. Springer, Berlin, Heidelberg, 2008.
  * [4] Sengupta, Poushali, Sudipta Paul, and Subhankar Mishra. ”Learning With Differential Privacy.” Handbook of Research on Cyber Crime and Information Privacy. IGI Global, 2021. 372-395.
  * [5] Dwork, Cynthia, and Aaron Roth. ”The algorithmic foundations of differential privacy.” Foundations and Trends in Theoretical Computer Science 9.3-4 (2014): 211-407.
  * [6] Cormode, Graham, et al. ”Privacy at scale: Local differential privacy in practice.” Proceedings of the 2018 International Conference on Management of Data. 2018.
  * [7] Erlingsson, Úlfar, Vasyl Pihur, and Aleksandra Korolova. ”Rappor: Randomized aggregatable privacy-preserving ordinal response.” Proceedings of the 2014 ACM SIGSAC conference on computer and communications security. 2014.
  * [8] Abadi, Martin, et al. ”Deep learning with differential privacy.” Proceedings of the 2016 ACM SIGSAC conference on computer and communications security. 2016.
  * [9] McMahan, Brendan, et al. ”Communication-efficient learning of deep networks from decentralized data.” Artificial Intelligence and Statistics. PMLR, 2017.
  * [10] Bittau, Andrea, et al. ”Prochlo: Strong privacy for analytics in the crowd.” Proceedings of the 26th Symposium on Operating Systems Principles. 2017.
  * [11] McMahan, H. Brendan, et al. ”A general approach to adding differential privacy to iterative training procedures.” arXiv preprint arXiv:1812.06210 (2018).
  * [12] Erlingsson, Úlfar, et al. ”Amplification by shuffling: From local to central differential privacy via anonymity.” Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics, 2019.
  * [13] Hanzely, Filip, et al. ”A privacy preserving randomized gossip algorithm via controlled noise insertion.” arXiv preprint arXiv:1901.09367 (2019).
  * [14] Chaudhuri, Kamalika, Jacob Imola, and Ashwin Machanavajjhala. ”Capacity bounded differential privacy.” arXiv preprint arXiv:1907.02159 (2019).
  * [15] Paul, Sudipta, and Subhankar Mishra. ”ARA: Aggregated RAPPOR and Analysis for Centralized Differential Privacy.” SN Computer Science 1.1 (2020): 1-10.
  * [16] Cormode, Graham, et al. ”Privacy at scale: Local differential privacy in practice.” Proceedings of the 2018 International Conference on Management of Data. 2018.
  * [17] Sengupta, Poushali, Sudipta Paul, and Subhankar Mishra. ”BUDS: Balancing Utility and Differential Privacy by Shuffling.” 2020 11th International Conference on Computing, Communication and Networking Technologies (ICCCNT). IEEE, 2020.
  * [18] Dwork, Cynthia, et al. ”Fairness through awareness.” Proceedings of the 3rd innovations in theoretical computer science conference. 2012.
  * [19] Zafar, Muhammad Bilal, et al. ”Fairness beyond disparate treatment & disparate impact: Learning classification without disparate mistreatment.” Proceedings of the 26th international conference on world wide web. 2017.
  * [20] Corbett-Davies, Sam, et al. ”Algorithmic decision making and the cost of fairness.” Proceedings of the 23rd acm sigkdd international conference on knowledge discovery and data mining. 2017.
  * [21] Pleiss, Geoff, et al. ”On fairness and calibration.” arXiv preprint arXiv:1709.02012 (2017).
  * [22] Dutta, Sanghamitra, et al. ”An information-theoretic perspective on the relationship between fairness and accuracy.” arXiv preprint arXiv:1910.07870 (2019).
  * [23] Biswas, Arpita, and Suvam Mukherjee. ”Fairness Through the Lens of Proportional Equality.” AAMAS. 2019.
  * [24] Kim, Joon Sik, Jiahao Chen, and Ameet Talwalkar. ”Fact: A diagnostic for group fairness trade-offs.” International Conference on Machine Learning. PMLR, 2020.
  * [25] Mozannar, Hussein, Mesrob Ohannessian, and Nathan Srebro. ”Fair learning with private demographic data.” International Conference on Machine Learning. PMLR, 2020.
  * [26] Kasy, Maximilian, and Rediet Abebe. ”Fairness, equality, and power in algorithmic decision-making.” Proceedings of the 2021 ACM Conference on Fairness, Accountability, and Transparency. 2021.
  * [27] Li, Tiancheng, and Ninghui Li. ”On the tradeoff between privacy and utility in data publishing.” Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining. 2009.
  * [28] Hardt, Moritz. ”A study of privacy and fairness in sensitive data analysis.” (2011).
  * [29] Cummings, Rachel, et al. ”On the compatibility of privacy and fairness.” Adjunct Publication of the 27th Conference on User Modeling, Adaptation and Personalization. 2019.
  * [30] Xu, Depeng, Shuhan Yuan, and Xintao Wu. ”Achieving differential privacy and fairness in logistic regression.” Companion Proceedings of The 2019 World Wide Web Conference. 2019.
  * [31] Bagdasaryan, Eugene, and Vitaly Shmatikov. ”Differential privacy has disparate impact on model accuracy.” arXiv preprint arXiv:1905.12101 (2019).
  * [32] Farrand, Tom, et al. ”Neither Private Nor Fair: Impact of Data Imbalance on Utility and Fairness in Differential Privacy.” Proceedings of the 2020 Workshop on Privacy-Preserving Machine Learning in Practice. 2020.
  * [33] Ekstrand, Michael D., Rezvan Joshaghani, and Hoda Mehrpouyan. ”Privacy for all: Ensuring fair and equitable privacy protections.” Conference on Fairness, Accountability and Transparency. PMLR, 2018.
  * [34] Binns, Reuben. ”On the apparent conflict between individual and group fairness.” Proceedings of the 2020 Conference on Fairness, Accountability, and Transparency. 2020.
  * [35] Erlingsson, Úlfar, et al. ”Encode, shuffle, analyze privacy revisited: Formalizations and empirical evaluation.” arXiv preprint arXiv:2001.03618 (2020).

##  Appendix A Appendix

###  A.1 Proof of Lemma 1 in Section 3

###### Proof.

According to the concept of Differential Privacy [5] [4], the generated report
from two neighboring datasets will be almost the same.Dwork has already shown
in her privacy book that the randomized response ratio i.e; after applying the
randomized function to the input dataset the ratio between changed and
unchanged rows of two neighboring datasets (input and output datasets)
satisfies all the notion of Differential Privacy. Dwork considered the coin
toss mechanism as the randomize function which was implemented on the input
dataset and the ratio between probabilities to change or unchanged of a
particular response by the occurring of heads and tails, was denoted as the
randomized response ratio that not only helps to derive the privacy budget but
also satisfies the condition of DP, where ;

$RR=\frac{P(Response=YES\ |\ Truth=YES)}{P(Response=YES\ |\ Truth=NO)}$ (19)

Now, the main idea is to prove that the intentions of Dwork’s Randomised
response ratio and the IS Randomised response Ratio(RR) are almost the same.
By proving this, it can be said that IS Randomised response Ratio also
satisfies all the notion of DP [5] [4].
In this work, the randomized function uses the Fairly Iterative Shuffling
algorithm to make secured and unbiased reports from the input dataset. For
this, if we can prove that the Iterative Shuffling[17] randomized technique
itself reassures the condition of DP; it will work for a Fair shuffle
algorithm. For sake of simplicity, let’s assume the Randomised function with
IS algorithm is applied on the input data set and it only interchange two rows
of the input data set. Then it is obvious that the input and output datasets
now only differ from two rows and it can be said that these two datasets are
neighboring. Then after applying IS, the ratio between the probabilities of
change and unchanged of a single row must be denoted as the randomized
response ratio which has the same intention as the coin toss randomized
response ratio has. That means This is also a ratio between the probabilities
of changed and unchanged reply after implementation of the randomized
function. Then, surely, IS randomized Response Technique must satisfy all the
notions of DP.
∎

###  A.2 Remark 1 in Section 4 - Discussion

$FIS$ shuffles the data set in a way that does not change the position of the
related background factors of the individuals which are used to decide to
choose an individual in an event. Before FIS, query function is applied and
Correlation Matrix is calculated which helps to extract the related attributes
to an event and tied them up together to behave like a single attribute. Now
if we only consider these tied up attributes, that can be denoted as the sub-
database, Let, assume the input database is $\mathcal{X}$ and
$x\subset\mathcal{X}$ is the generated subset by query function and
Correlation Function which contains all the related background factors/
attributes along with their tagged groups (In our case study, gender groups:
male and female). Now, FIS does not change these related attributes record
positions after shuffling,i.e the related attributes records belong to their
user-id corresponds to their tagged group. Whereas, FIS changes the record
position of unrelated attributes only which prevents the linkage attack and
minimizes the exposure of data attributes. So, after $FIS$, the individual
posses all the true records of related attributes and own tagged group for
consideration, whereas it posses all the false and changed records of those
attributes which are not related to taking the decision. So, the sub-database
$x$ does not change after $FIS$ and that helps the fair classifiers to take
the decision correctly, The fair classifiers classify the data based on the
sub-database $x$ and their corresponding tagged groups. As FIS does not change
$x$ and tagged group of individuals, it doesn’t hamper the FPR-FNR of the
different groups.

###  A.3 Utility Guarantee and Risk Minimizer in Section 5

The real information which can be gained from the data by a particular query
or set of queries is defined as the utility of the system. The goal of this
section is to discuss the gained utility from the data by applying Fair-BUDS
and provide a tight bound for loss function between input and output average-
count. This bound has a great impact on the Utility of the system and this
depends on the previously obtained privacy budget. Before obtaining the final
result, an optimization function with a risk assessment technique is applied
to get the maximum Utility from the data. All the necessary calculation
regarding this is done in this section. At the end of this section, an optimum
upper bound of the loss function can be achieved by which the utility will be
highest while having a strong privacy budget.
we have $n$ number of individual’s records tagged with two separate groups
based on their protected attribute class $n_{i};i=i(1)n_{p}$ rows for $ith$
class. Now the proposed architecture generates a fairly iterative shuffling
($FIS$) method to produce the desire reports. This method, not only provides a
strong privacy guarantee but also gives higher utility measures. To, prove
this, the following calculations will show, how the true data average count
reports are very close to the $FIS$ data average count. Let’s assume, before
$FIS$ shuffling, the true data set will give a average count report for a time
horizon $[d]=\\{1,..d\\}$ which is denoted as
$\mathcal{C_{T}}=\sum_{i=1}^{n}\sum_{j\epsilon\mathcal{Q}}\sum_{T\epsilon[d]}x_{ij}[T]$;
where, $x_{ij}$ is the jth record of the ith individual from the true data set
for the time horizon $[d]$ and $\mathcal{Q}=\\{a_{1},a_{2},...\\}$ is the set
of attributes given by the query function for a particular set query or set of
queries. Now,
$\mathcal{C_{FS}}=\sum_{i=1}^{n}\sum_{j\epsilon\mathcal{Q}}\sum_{T\epsilon[d]}x^{FS}_{ij}[d]$;
where $x^{FS}_{ij}$ is the jth record of the ith individual from the $FIS$
data set for the time horizon $[d]$. For the query in Example 2, we can take a
attribute set $\mathcal{A}=\\{a_{1},...,a_{m}\\}$ that is highly related to
the admission decisions. This set not only contains the ”Maths Score” but also
has other related factors like ”Annual Income”, ”Electricity Facility” etc.
All the attributes belonging to set $\mathcal{A}$ is the eligibility criteria
for the students and these attributes will be tied up together to present a
single attribute. Every individual from the data set will be tagged with their
gender group to keep a fair balance between male and female. After $FIS$, the
average count will show how many students (irrespective of gender) are
eligible for admission. The fairness algorithm will be applied after that to
choose the deserving students for admission based on background factors by
keeping fairness among gender groups. At the time of $FIS$, the important
attributes stay together always and do not shuffle among their shelves as they
behave like single attributes. On the other hand, each row of a particular
batch from the tagged gender groups gets shuffled and at the end records of
their individuals do not belong to their unique ID. But, as the only source of
noise is one-hot encoding here which is minimum, and also the tied attribute
records do not break their tie at the time of shuffling it can be said that
the shuffled dataset must be a neighboring dataset of the true one. Using this
agenda, it also can be said that the difference between $\mathcal{C_{T}}$ and
$\mathcal{C_{FS}}$ is negligible and these two average count results belong to
the neighborhood of each other;i.e. so close to each other. By the idea of the
neighboring data set, we can express the relation between two average count
reports by the following bound for generalized case:

$\mathcal{C_{T}}\leq e^{\text{$\epsilon_{Fair}$}}\mathcal{C_{FS}}$ (20)

where $\epsilon_{Fair}$ is the proposed privacy budget. when $\epsilon_{Fair}$
= 0 $\implies$ $\mathcal{C_{T}}=\mathcal{C_{FS}}$; i.e. The utility
$\mathcal{U}(X,X^{FS})$ is maximum; where $X$ is the true data set or input
dataset and $X^{FS}$ is the $FIS$ dataset or output dataset. If the range of
utility is taken as $[0,1]$; when $\epsilon_{Fair}$ = 0 then
$\mathcal{U}(X,X^{FS})=1$. Here,

$\mathcal{C_{T}}\leq
e^{\ln\bigg{[}\frac{1}{n_{p}!}{\Sigma_{i=1}^{n_{p}}\frac{t_{i}}{(n_{it_{i}}-1)^{S}}}\bigg{]}}\mathcal{C_{FS}}$
(21)

By subtracting $\mathcal{C_{FS}}$ from both sides and taking absolute value of
the equation 21 we get.

$|\mathcal{C_{T}}-\mathcal{C_{FS}}|\leq\mathcal{C_{FS}}\times\bigg{|}e^{\ln\bigg{[}\frac{1}{n_{p}!}{\Sigma_{i=1}^{n_{p}}\frac{t_{i}}{(n_{it_{i}}-1)^{S}}}\bigg{]}}-1\bigg{|}$
(22)

In our case study based on gender unbiasedness problem, for the Given query in
Example 2 we will have :

$|\mathcal{C_{T}}-\mathcal{C_{FS}}|\leq\mathcal{C_{FS}}\times\bigg{|}e^{\ln{\frac{1}{2}\bigg{[}\frac{t_{F}}{(n_{1t_{F}}-1)^{S}}+\frac{t_{M}}{(n_{2t_{M}}-1)^{S}}\bigg{]}}}-1\bigg{|}$
(23)

Where, $S>1$, $t_{F}$ is the number of batches in the female group, $t_{M}$ is
the number of batches in the male group, $n_{1t_{F}}$ is the average female
batch size, and $n_{2t_{M}}$ is average male batch size. Now, define the loss
function $\mathcal{L}(\mathcal{C_{T}},\mathcal{C_{FS}})$ =
$|\mathcal{C_{T}}-\mathcal{C_{FS}}|$ and get bound on loss function as
following:

$\mathcal{L}(\mathcal{C_{T}},\mathcal{C_{FS}})\leq\mathcal{C_{FS}}\times\bigg{|}e^{\ln{\frac{1}{2}\bigg{[}\frac{t_{F}}{(n_{1t_{F}}-1)^{S}}+\frac{t_{M}}{(n_{2t_{M}}-1)^{S}}\bigg{]}}}-1\bigg{|}$
(24)

Now the aim of this architecture is not only to be fair and secured but also
it should pose a high utility guarantee which can be obtained by risk-
minimizing assessment. So the next target is to derive the risk function and
minimize it to achieve the desired goal.

Here a hypothesis class $\mathcal{H}$ must exist containing all possible
Randomisation function which we are searching for. According to the concept of
decision theory, the main idea is to minimizing the risk function to find the
best randomization function that will help us to map best from input to
output. Here the risk function can be stated as:

$Risk(\mathcal{R^{*}}(iS))=E[\mathcal{L}(\mathcal{C_{T}},\mathcal{C_{FS}})]=\int\int
P(\mathcal{C_{T}},\mathcal{C_{FS}})\mathcal{L}(\mathcal{C_{T}},\mathcal{C_{FS}})\
d\mathcal{C_{T}}\ d\mathcal{C_{FS}}$ (25)

Where , $i$= Number of variety in protected attribute class,
$P(\mathcal{C_{T}},\mathcal{C_{FS}})$ is the sample dataset distribution which
contain $n$ data points that are drawn randomly from a population that follows
the distribution $\mu(\mathcal{Z})$ over
$\mathcal{Z}=\mathcal{C_{T}}.\mathcal{C_{FS}}:(\mathcal{C}_{\mathcal{T}1},\mathcal{C}_{\mathcal{T}1}),(\mathcal{C}_{\mathcal{T}2},\mathcal{C}_{\mathcal{FT}2}),....,(\mathcal{C}_{\mathcal{T}n},\mathcal{C}_{\mathcal{FS}n})$
and

$P(\mathcal{C_{T}},\mathcal{C_{FS}})=P(\mathcal{C_{FS}}|\mathcal{C_{T}}).P(\mathcal{C_{T}})$
(26)

Here the empirical risk function is:

$Risk_{\text{(Ep)}}(\mathcal{R^{*}}(iS))=\frac{1}{n}\Sigma_{1}^{n}\mathcal{L}(\mathcal{C}_{\mathcal{T}i},\mathcal{C}_{\mathcal{FS}i})\leq\frac{1}{n}\Sigma_{1}^{n}e^{\text{$\epsilon_{Fair}$}}\mathcal{C}_{\mathcal{FS}i}$
(27)

Now a regularization parameter $\mathbf{G}$ will be added in order to impose
the complexity penalty on the loss function and prevent over fitting in the
following way:

$Risk_{\text{(Ep)}}(\mathcal{R^{*}}(iS))=\frac{1}{n}\Sigma_{1}^{n}\mathcal{L}(\mathcal{C}_{\mathcal{T}i},\mathcal{C}_{\mathcal{FS}i})+\lambda\mathbf{G}(\mathcal{R^{*}}(iS))$
(28)
$Risk_{\text{(Ep)}}(\mathcal{R^{*}}(iS))\leq\frac{1}{n}\Sigma_{1}^{n}e^{\text{$\epsilon_{Fair}$}}\mathcal{C}_{\mathcal{FS}i}+{\lambda}\mathbf{G}(\mathcal{R^{*}}(iS))$
(29)

where ${\lambda}$ manages the strength of complexity penalty. Now the
mechanism $\mathcal{R^{*}}(iS)$ can be found which minimizes the risk, where

$\mathcal{R^{*}}(iS)=\operatornamewithlimits{argmin}_{\text{$\mathcal{R^{*}}(2S)\epsilon\mathcal{H}$}}Risk_{\text{(Ep)}}(\mathcal{R^{*}}(iS))$
(30)

For our case study the equation will be :

$\mathcal{R^{*}}(iS)=\operatornamewithlimits{argmin}_{\text{$\mathcal{R^{*}}(2S)\epsilon\mathcal{H}$}}Risk_{\text{(Ep)}}(\mathcal{R^{*}}(iS))$
(31)

As there are $2$ types of a protected class in related attributes (Gender):
Female and Male.