# Addressing Polarization and Unfairness in Performative Prediction

Kun Jin
University of Michigan, Ann Arbor
<EMAIL_ADDRESS>
&Tian Xie11footnotemark: 1
the Ohio State University
<EMAIL_ADDRESS>
&Yang Liu
University of California, Santa Cruz
<EMAIL_ADDRESS>
&Xueru Zhang
the Ohio State University
<EMAIL_ADDRESS>
These authors contribute equally.

###### Abstract

When machine learning (ML) models are used in applications that involve humans
(e.g., online recommendation, school admission, hiring, lending), the model
itself may trigger changes in the distribution of targeted data it aims to
predict. Performative prediction (PP) is a framework that explicitly considers
such model-dependent distribution shifts when learning ML models. While
significant efforts have been devoted to finding performative stable (PS)
solutions in PP for system robustness, their societal implications are less
explored and it is unclear whether PS solutions are aligned with social norms
such as fairness. In this paper, we set out to examine the fairness property
of PS solutions in performative prediction. We first show that PS solutions
can incur severe polarization effects and group-wise loss disparity. Although
existing fairness mechanisms commonly used in literature can help mitigate
unfairness, they may fail and disrupt the stability under model-dependent
distribution shifts. We thus propose novel fairness intervention mechanisms
that can simultaneously achieve both stability and fairness in PP settings.
Both theoretical analysis and experiments are provided to validate the
proposed method.

##  1 Introduction

Modern supervised learning excels in many domains, especially in pattern
recognition where the target data distribution is static and independent of
the deployed model. However, in the presence of model-dependent distribution
shifts (i.e., the model itself triggers the changes in the distribution of
targeted data), most conventional training approaches will fail to find
solutions that are stable and robust to such shifts. In fact, model-dependent
distribution shifts are practical and commonly exist in real-world
applications. Examples include strategic individuals manipulating their data
(in school admission, hiring, or lending) to game the ML system into making
favorable predictions [1], consumers changing their retention and
participation choices (in digital platforms) based on their perception toward
the ML model they are subject to [2, 3], etc.

To make predictions in the presence of model-dependent distribution shifts,
Perdomo et al. [4] proposed performative prediction (PP), a framework that
explicitly considers the target data distribution
$\mathcal{D}(\boldsymbol{\theta})$ as a function of the ML model parameter
$\boldsymbol{\theta}$ to be optimized. While PP captures the impacts of the ML
model on target data, the distribution $\mathcal{D}(\boldsymbol{\theta})$ is
solely determined by the model regardless of the original data distribution. A
subsequent study [5] extended PP and proposed a more generalized state-
dependent performative prediction (SDPP) framework, which considers the
impacts of both model and initial data distribution. Specifically, given the
deployed ML model parameter $\boldsymbol{\theta}$ and initial data
distribution $\mathcal{D}$, SDPP models the resulting target data distribution
$\mathcal{D}^{\prime}=\text{T}(\boldsymbol{\theta};\mathcal{D})$ using some
transition mapping function T. Since PP is a special case of SDPP, we focus on
SDPP in this paper.

Since the target data distribution depends on the model, the learning
objective of SDPP is to minimize performative risk (PR), i.e.,

$\boldsymbol{\theta}^{\text{PO}}=\underset{\boldsymbol{\theta}}{\operatorname{argmin}}~{}\text{PR}(\boldsymbol{\theta})\stackrel{{\scriptstyle\text{def}}}{{=}}\mathbb{E}_{Z\sim\text{T}(\boldsymbol{\theta};\mathcal{D})}[\ell(\boldsymbol{\theta};Z)]$

where $\ell(\boldsymbol{\theta};Z)$ is the loss function, $Z$ is the data
sampled from the target distribution
$\text{T}(\boldsymbol{\theta};\mathcal{D})$ dependant on both model parameter
$\boldsymbol{\theta}$ to be optimized and the initial data distribution
$\mathcal{D}$. The minimizer $\boldsymbol{\theta}^{\text{PO}}$ is named as
performative optimal (PO) solution. Because the target data distribution
itself is a function of variable $\boldsymbol{\theta}$ to be optimized,
finding the PO solution is often challenging [4, 5]. Instead, existing works
have mostly focused on finding performative stable (PS) solution
$\boldsymbol{\theta}^{\text{PS}}$, which minimizes the decoupled performative
risk $\text{DPR}(\boldsymbol{\theta};\boldsymbol{\theta}^{\text{PS}})$ defined
as follows,

$\boldsymbol{\theta}^{\text{PS}}=\underset{\boldsymbol{\theta}}{\operatorname{argmin}}~{}\text{DPR}(\boldsymbol{\theta};\boldsymbol{\theta}^{\text{PS}})\stackrel{{\scriptstyle\text{def}}}{{=}}\mathbb{E}_{Z\sim\text{T}(\boldsymbol{\theta}^{\text{PS}};\mathcal{D}^{\text{PS}})}[\ell(\boldsymbol{\theta};Z)]$
(1)

where $\mathcal{D}^{\text{PS}}$ is the fixed point data distribution induced
by $\boldsymbol{\theta}^{\text{PS}}$ that satisfies
$\mathcal{D}^{\text{PS}}=\text{T}(\boldsymbol{\theta}^{\text{PS}};\mathcal{D}^{\text{PS}})$.
Unlike performative risk $\text{PR}(\boldsymbol{\theta})$ where data
distribution $\text{T}(\boldsymbol{\theta};\mathcal{D})$ depends on variable
$\boldsymbol{\theta}$ to be optimized, decoupled performative risk
$\text{DPR}(\boldsymbol{\theta};\boldsymbol{\theta}^{\text{PS}})$ decouples
the two, i.e., data distribution is induced by
$\boldsymbol{\theta}^{\text{PS}}$ while the variable to be optimized is
$\boldsymbol{\theta}$. Although in general
$\boldsymbol{\theta}^{\text{PS}}\neq\boldsymbol{\theta}^{\text{PO}}$,
$\boldsymbol{\theta}^{\text{PS}}$ is the fixed point of Eqn. (1) and
stabilizes the system: at $\boldsymbol{\theta}^{\text{PS}}$, data distribution
$\mathcal{D}^{\text{PS}}$ also remain fixed. Many algorithms have been
proposed in the literature to find $\boldsymbol{\theta}^{\text{PS}}$. A prime
example is repeated risk minimization (RRM) [4], an iterative algorithm that
finds $\boldsymbol{\theta}^{\text{PS}}$ (under certain conditions) by
repeatedly updating the model $\boldsymbol{\theta}^{(t)}$ that minimizes risk
on the fixed distribution $\mathcal{D}^{(t-1)}$ induced by the previous model
$\boldsymbol{\theta}^{(t-1)}$, i.e.,

$\boldsymbol{\theta}^{(t)}=\underset{\boldsymbol{\theta}}{\operatorname{argmin}}~{}\mathbb{E}_{Z\sim\mathcal{D}^{(t-1)}}[\ell(\boldsymbol{\theta};Z)],~{}~{}~{}\mathcal{D}^{(t)}=\text{T}(\boldsymbol{\theta}^{(t)};\mathcal{D}^{(t-1)}).$
(2)

However, the societal implications of PS solutions are less understood and it
is unclear whether PS solutions can cause harm and violate social norms such
as fairness.

In this paper, we examine the fairness properties of PS solutions
$\boldsymbol{\theta}^{\text{PS}}$. We consider scenarios where an ML model is
used to make decisions about people from multiple demographic groups, and the
population data distribution changes based on the ML decisions they are
subject to. We find that PS solutions can 1) incur severe polarization
effects: entire population $\mathcal{D}^{\text{PS}}$ is dominated by certain
groups, leaving the rest marginalized and almost diminished in the sample
pool; 2) be biased when deployed on $\mathcal{D}^{\text{PS}}$ and people from
different groups will experience different losses. However, in many
applications such as recommendation systems, school admission, and loan
applications, it is critical to ensure equal quality of ML predictions and
population diversity. Thus, we investigate under what conditions and by what
algorithms we can simultaneously achieve stability and fairness in SDPP.

Focusing on group-wise loss disparity [6, 7] and participation disparity [2,
8] fairness measures, we first explore whether existing fairness mechanisms
commonly used in supervised learning can help mitigate unfairness in SDPP
settings; this includes regularization methods (adding fairness violation as a
penalty term to the objective function of unconstrained optimization, e.g.,
[9, 10]) and re-weighting methods (adjusting weights and importance of samples
in learning objective, e.g., [11, 12, 13]). We show that common choices of
penalty terms (e.g., group-wise loss difference) and re-weighting designs
(e.g., standard distributionally robust optimization) that are effective in
traditional supervised learning may fail in SDPP settings by disrupting the
stability of the system. Using repeated risk minimization (RRM) shown in Eqn.
(2) as an example, this means that applying such fairness mechanisms at each
round of RRM can disrupt the convergence of the algorithm and
$(\boldsymbol{\theta}^{(t)},\mathcal{D}^{(t)})$ may diverge to an unexpected
state. We thus propose novel fairness mechanisms, which can be easily adopted
and incorporated into iterative algorithms such as RRM. We theoretically show
that the proposed mechanism can effectively improve fairness while maintaining
the stability of the system.

It is worth noting that although a few recent works also studied fairness
issues under model-dependent distribution shifts, they all make rather strong
assumptions about the distribution shifts and do not apply to the general SDPP
framework. For example, Zezulka and Genin [14], Hu and Zhang [15], Raab et al.
[8] assumed there exists a causal model that depicts how data distribution
would shift based on the ML model, and these causal models need to be fully
known. Raab et al. [8] studied a special type of model-dependent distribution
shift where only the group proportion/participation changes based on ML
models. In Appendix A, we discuss these works in more detail and provide a
comprehensive literature review.

The rest of the paper is organized as follows. Section 2 provides the
background of SDPP. Section 3 formulates the problem and demonstrates the
unfairness and polarization issues of PS solutions. Section 4 highlights the
difficulties of simultaneously achieving fairness and stability in SDPP, where
we first show that existing fairness mechanisms commonly used in supervised
learning may fail in SDPP settings and then propose a novel fairness
mechanism. In Section 5, we conduct the theoretical analysis and show that our
method can effectively improve fairness while maintaining stability. Finally,
Section 6 empirically validates the proposed method on both synthetic and real
data.

##  2 Preliminaries: Iterative Algorithms to Find PS Solutions in SDPP

As mentioned in Section 1, the original goal of SDPP is to find the
performative optimal solution $\boldsymbol{\theta}^{\text{PO}}$ that minimizes
the performative risk
$\text{PR}(\boldsymbol{\theta})=\mathbb{E}_{Z\sim\text{T}(\boldsymbol{\theta};\mathcal{D})}[\ell(\boldsymbol{\theta};Z)]$,
the loss over the population induced by the deployed model. However, solving
this optimization is often challenging because the data distribution
$\text{T}(\boldsymbol{\theta};\mathcal{D})$ depends on the variable
$\boldsymbol{\theta}$ to be optimized. Thus, prior studies such as [4, 5] have
mostly focused on finding performative stable solution
$\boldsymbol{\theta}^{\text{PS}}$, which is the fixed point of Eqn. (1) and
can be found through an iterative process of data sampling and model
deployment. Specifically, denote
$\mathcal{L}(\boldsymbol{\theta};\mathcal{D})=\mathbb{E}_{Z\sim\mathcal{D}}[\ell(\boldsymbol{\theta};Z)]$
and let $(\boldsymbol{\theta}^{(t)},\mathcal{D}^{(t)})$ be the model parameter
and data distribution at round $t$ of the iterative algorithm, then repeatedly
updating the model $\boldsymbol{\theta}^{(t)}$ according to Eqn. (3) could
lead $(\boldsymbol{\theta}^{(t)},\mathcal{D}^{(t)})$ converging to PS solution
$(\boldsymbol{\theta}^{\text{PS}},\mathcal{D}^{\text{PS}})$ under certain
conditions [4, 5].

$\boldsymbol{\theta}^{(t)}=\underset{\boldsymbol{\theta}}{\operatorname{argmin}}~{}\mathcal{L}(\boldsymbol{\theta};\mathcal{D}^{(t-1)}),~{}~{}~{}\mathcal{D}^{(t)}=\text{Tr}(\boldsymbol{\theta}^{(t)};\mathcal{D}^{(t-1)}).$
(3)

where Tr is not necessarily the same as transition mapping T that drives
evolution of data. Depending on how frequently the model is deployed compared
to the change of data, Tr can be defined differently based on repeated
deployment schema. Common examples include:

conventional:
$\displaystyle\text{Tr}(\boldsymbol{\theta}^{(t)};\mathcal{D}^{(t-1)})=\text{T}(\boldsymbol{\theta}^{(t)};\mathcal{D}^{(t-1)})$
$\mathbf{k}$-delayed:
$\displaystyle\text{Tr}(\boldsymbol{\theta}^{(t)};\mathcal{D}^{(t-1)})=\text{T}^{k}(\boldsymbol{\theta}^{(t)};\mathcal{D}^{(t-1)})=\underbrace{\text{T}\Big{(}\boldsymbol{\theta}^{(t)};\dots\text{T}\big{(}\boldsymbol{\theta}^{(t)};\text{T}}_{k\text{
times}}(\boldsymbol{\theta}^{(t)};\mathcal{D}^{(t-1)})\big{)}\Big{)}$ delayed:
$\displaystyle\text{Tr}(\boldsymbol{\theta}^{(t)};\mathcal{D}^{(t-1)})=\text{T}^{\lceil
r\rceil+1}(\boldsymbol{\theta}^{(t)};\mathcal{D}^{(t-1)})$

where the repeated risk minimization (RRM) [4] introduced in Section 1
corresponds to conventional deployment schema. By customizing the time
interval between two deployments, we can get variants including delayed RRM
and $k$-delayed RRM [5]. Note that the delayed deployment schema is a special
case of $k$-delayed deployment schema, where the number of repeated
deployments $r$ is chosen to ensure the output distribution
$\mathcal{D}^{(t)}$ is sufficiently close to the fixed point distribution when
$\boldsymbol{\theta}^{(t)}$ keeps being deployed on the population
$\mathcal{D}^{(t-1)}$.

Technical conditions for iterative algorithms to converge to PS solutions. As
shown in [4, 5], PS solutions exist and are unique only when $\ell$ and T
satisfy certain requirements. Moreover, iterative algorithms introduced in
Eqn. (3) can converge to the PS solution. We introduce them below, where
$\Theta$, $\mathcal{Z}$, and $\triangle(\mathcal{Z})$ denote the parameter
space, sample space, and space of distributions over samples.

######  Definition 2.1 (Strong convexity of loss).

$\ell(\boldsymbol{\theta};Z)$ is $\gamma$-strongly convex if and only if for
all $\boldsymbol{\theta},\boldsymbol{\theta}^{\prime}\in\Theta$ and
$Z\in\mathcal{Z}$, we have

$\ell(\boldsymbol{\theta};Z)\geq\ell(\boldsymbol{\theta}^{\prime};Z)+\langle\nabla_{\boldsymbol{\theta}}\ell(\boldsymbol{\theta};Z),\boldsymbol{\theta}-\boldsymbol{\theta}^{\prime}\rangle+\frac{\gamma}{2}\|\boldsymbol{\theta}-\boldsymbol{\theta}^{\prime}\|_{2}^{2}.$

######  Definition 2.2 (Joint smoothness of loss).

$\ell(\boldsymbol{\theta};Z)$ is $\beta$-jointly smooth if the gradient with
respect to $\boldsymbol{\theta}$ is $\beta$-Lipschitz in $\boldsymbol{\theta}$
and $Z$, i.e.,
$\forall\boldsymbol{\theta},\boldsymbol{\theta}^{\prime}\in\Theta$ and
$\forall Z,Z^{\prime}\in\mathcal{Z}$, we have

$\|\nabla_{\boldsymbol{\theta}}\ell(\boldsymbol{\theta};Z)-\nabla_{\boldsymbol{\theta}}\ell(\boldsymbol{\theta}^{\prime};Z)\|_{2}\leq\beta\|\boldsymbol{\theta}-\boldsymbol{\theta}^{\prime}\|_{2},~{}~{}\|\nabla_{\boldsymbol{\theta}}\ell(\boldsymbol{\theta};Z)-\nabla_{\boldsymbol{\theta}}\ell(\boldsymbol{\theta};Z^{\prime})\|_{2}\leq\beta\|Z-Z^{\prime}\|_{2}.$

######  Definition 2.3 (Joint sensitivity of transition).

Let $\mathcal{W}_{1}$ denote the Wasserstein-1 distance measure. The
transition mapping T is $\epsilon$-jointly sensitive if for all
$\boldsymbol{\theta},\boldsymbol{\theta}^{\prime}\in\Theta$ and
$\mathcal{D},\mathcal{D}^{\prime}\in\triangle(\mathcal{Z})$,

$\mathcal{W}_{1}(\text{T}(\boldsymbol{\theta};\mathcal{D}),\text{T}(\boldsymbol{\theta}^{\prime};\mathcal{D}))\leq\epsilon\|\boldsymbol{\theta}-\boldsymbol{\theta}^{\prime}\|_{2},~{}~{}\mathcal{W}_{1}(\text{T}(\boldsymbol{\theta};\mathcal{D}),\text{T}(\boldsymbol{\theta};\mathcal{D}^{\prime}))\leq\epsilon\mathcal{W}_{1}(\mathcal{D},\mathcal{D}^{\prime}).$

######  Lemma 2.4 (The existence of a unique PS solution [4, 5]).

The SDPP problem is guaranteed to have a unique PS solution if all of the
following hold: (i) Loss $\ell(\boldsymbol{\theta};Z)$ is $\gamma$-strongly
convex; (ii) Loss $\ell(\boldsymbol{\theta};Z)$ is $\beta$-joint smooth; (iii)
T is $\epsilon$-joint sensitive and $\epsilon(1+\beta/\gamma)<1$. Moreover, if
any of these conditions is violated, the iterative algorithms may fail to
converge to the PS solution.

##  3 Unfairness and Polarization in SDPP

#### Problem Formulation.

In this work, we study SDPP with different demographic groups, where an ML
model $\boldsymbol{\theta}$ is trained to make predictions about individuals
from multiple groups distinguished by a sensitive attribute $s\in\mathcal{S}$
(e.g., gender, age, race), whose data distribution changes based on the
deployed ML model and such model-dependent distribution shift can be captured
by transition mapping T. Suppose individuals from group $s$ follow the
identical data distribution $\mathcal{D}_{s}^{(t)}$ at the round $t$ of an
iterative algorithm, and let $p_{s}^{(t)}$ be the size of group $s$ as the
fraction of entire population at $t$. Then the data distribution of the entire
population is
$\mathcal{D}^{(t)}=\sum_{s\in\mathcal{S}}p_{s}^{(t)}\mathcal{D}_{s}^{(t)}$
with $\sum_{s\in\mathcal{S}}p_{s}^{(t)}=1$.

Note that the above SDPP with multiple groups is a general framework. By
specifying the transition mapping T, many problems studied in prior works can
be regarded as a special case. This includes:

  1. 1.

Strategic classification with multiple groups [16, 17]: individuals in
applications such as lending, hiring, and admission may manipulate their data
based on ML model strategically to increase their chances of receiving
favorable decisions, leading to changes in group distribution
$\mathcal{D}_{s}^{(t)}$.

  2. 2.

Decision-making systems under user retention dynamics [2, 12, 18]: ML models
used in recognition or recommendation systems may attract more users if they
experience high accuracy but drive away those with less satisfaction, which
may cause group proportion $p_{s}^{(t)}$ to change.

In this paper, we first explore the fairness properties of PS solutions in
SDPP, i.e., examining whether $\boldsymbol{\theta}^{\text{PS}}$ in Eqn. (1)
have disparate impacts on different demographic groups. Specifically, we
consider two fairness metrics: group-wise loss disparity
$\triangle_{\mathcal{L}}^{(t)}$ [6, 19] and participation disparity
$\triangle_{p}^{(t)}$ [8] measuring the difference of loss
$\mathcal{L}(\boldsymbol{\theta};\mathcal{D}_{s}^{(t)})$ and fraction
$p_{s}^{(t)}$ across different groups at round $t$ of an iterative algorithm.
In examples with two groups $\mathcal{S}=\\{a,b\\}$, the unfairness can be
quantified as

$\triangle_{\mathcal{L}}^{(t)}:=\left|\mathcal{L}(\boldsymbol{\theta}^{(t)};\mathcal{D}_{a}^{(t)})-\mathcal{L}(\boldsymbol{\theta}^{(t)};\mathcal{D}_{b}^{(t)})\right|,~{}~{}~{}~{}~{}\triangle_{p}^{(t)}:=\left|p_{a}^{(t)}-p_{b}^{(t)}\right|.$
(4)

#### Unfairness & polarization effects in SDPP.

Figure 1: Dynamics of the group fraction in Example 3.1 (left) and group-wise
accuracy in Example 3.2 (right) under RRM: the system converges to PS solution
$(\boldsymbol{\theta}^{\text{PS}};\mathcal{D}^{\text{PS}})$ that is unfair.

We first show (through two toy examples) that PS solutions
$\boldsymbol{\theta}^{\text{PS}}$ in SDPP may have disparate impacts on
different groups. Specifically, when finding $\boldsymbol{\theta}^{\text{PS}}$
using iterative algorithms introduced in Section 2, the process may incur
severe polarization effects and exhibit unfairness, i.e., certain groups may
get marginalized and diminish from the system, and group-wise loss disparity
gets exacerbated during the iterative process.

######  Example 3.1 (Polarization effects of
$\boldsymbol{\theta}^{\text{PS}}$).

Consider individuals from two groups $a,b$ whose participation in an ML system
depends on their perceived loss, i.e., group fraction $p_{s}^{(t)}$ changes
based on the deployed ML model. Suppose individuals from group $a$ and $b$
have fixed data $Z=z_{a}=1$ and $Z=z_{b}=0$, respectively. Their initial group
fractions are $p_{a}^{(0)}=0.7,p_{b}^{(0)}=0.3$. Consider conventional RRM
with mean squared error
$\mathcal{L}(\boldsymbol{\theta};\mathcal{D}^{(t)})=\sum_{s\in\\{a,b\\}}p_{s}^{(t)}(\theta-
z_{s})^{2}$ and transition T that satisfies
$p_{a}^{(t+1)}=p_{a}^{(t)}+0.1\cdot\left[\mathcal{L}(\boldsymbol{\theta}^{(t)};\mathcal{D}_{b}^{(t)})-\mathcal{L}(\boldsymbol{\theta}^{(t)};\mathcal{D}_{a}^{(t)})\right],p_{b}^{(t+1)}=1-p_{a}^{(t+1)}$
(i.e., group fraction decreases if the group has higher loss). It is easy to
see that $p_{a}^{(t)}$ (resp. $p_{b}^{(t)}$) monotonically increases (resp.
decreases) in $t$, and the PS solution solely contains people from group $a$
(see Fig. 1).

######  Example 3.2 (Exacerbated group-wise loss disparity).

Consider individuals from two groups $a,b$ who are subject to certain ML
decisions; each has an initial feature $X\sim\text{Uniform}(0,1)$ and a binary
label $Y=\mathbbm{1}(X\geq 0.5)\in\\{0,1\\}$. Suppose the population has fixed
group fractions $p_{a}=0.7,p_{b}=0.3$, but individuals may strategically
manipulate their features to increase their chances of receiving favorable ML
decisions, i.e., distribution of each group $\mathcal{D}_{s}^{(t)}$ changes
based on ML model. Following the individual response model in [20, 16], we
suppose individuals from two groups have certain effort budgets
$\eta_{a}=0.2,\eta_{b}=0.01$ that can be used to improve their features
$X_{s}^{(t+1)}=X_{s}^{(t)}+\eta_{s}\cdot\boldsymbol{\theta}^{(t)}$. Consider
RRM iterative algorithm where the model parameter $\boldsymbol{\theta}^{(t)}$
is updated to maximize prediction accuracy
$\Pr(\mathbbm{1}(X\geq\boldsymbol{\theta}^{(t)})=Y^{(t)})$. Given an initial
model $\boldsymbol{\theta}^{(0)}=0.5$, it is trivial to see that
$\boldsymbol{\theta}^{(t)}$ increases over time to be robust against
manipulation until converges to PS solution
$\boldsymbol{\theta}^{\text{PS}}=0.625$ (see Fig. 1). However, at the PS
solution, the accuracy for group $a$ is 1 but is only $0.88$ for group $b$.

##  4 Fair-PS Solutions and Fairness Mechanisms

Section 3 shows that without fairness consideration, PS solution of SDPP may
incur polarization effects and have disparate impacts on different groups,
i.e., when finding $\boldsymbol{\theta}^{\text{PS}}$ using iterative
algorithms such as RRM, group-wise loss disparity
$\triangle_{\mathcal{L}}^{(t)}$ and participation disparity
$\triangle_{p}^{(t)}$ may get exacerbated and converge to an unfair state. In
this section, we address unfairness issues in SDPP. One straightforward idea
is to directly apply the fairness mechanisms at every round of the iterative
algorithms introduced in Section 2. However, we will show that although such
methods are effective in conventional supervised learning, they can disrupt
the stability and the iterative algorithms may no longer converge.

###  4.1 Fairness mechanisms and Fair-PS solutions

Many fairness mechanisms have been proposed in supervised learning to mitigate
group-wise loss disparity and participation disparity. We consider two
categories commonly used in the literature: regularization method and sample
re-weighting method, as detailed below.

  1. 1.

Fairness via regularization: It adds a regularization/penalty term to the
original learning objective function
$\mathcal{L}(\boldsymbol{\theta};\mathcal{D})$, which penalizes the violation
of fairness [9, 10]. The fair objective function is

$\mathcal{L}_{\textsf{fair}}(\boldsymbol{\theta};\mathcal{D},\rho):=\mathcal{L}(\boldsymbol{\theta};\mathcal{D})+\mathcal{P}(\boldsymbol{\theta};\mathcal{D},\rho),$
(5)

where $\mathcal{P}(\boldsymbol{\theta};\mathcal{D},\rho)$ is the fair penalty
term and the scalar $\rho>0$ controls the strength of the penalty.

  2. 2.

Fairness via sample re-weighting: It adjusts the weights of samples (possibly
adversarially) and increases sample weights for disadvantaged groups [11, 12,
13]. One example is distributionally robust optimization (DRO) [18], which
minimizes the worst-case loss and the fair objective is

$\textstyle\mathcal{L}_{\textsf{fair}}(\boldsymbol{\theta};\mathcal{D},\rho):=\max_{\tilde{\mathcal{D}}\in\mathcal{B}(\mathcal{D},r(\rho))}\mathcal{L}(\boldsymbol{\theta};\tilde{\mathcal{D}}),$
(6)

where
$\mathcal{B}(\mathcal{D},r(\rho)):=\\{\tilde{\mathcal{D}}|d(\mathcal{D},\tilde{\mathcal{D}})\leq
r(\rho)\\}$ denotes a distribution ball centered at $\mathcal{D}$ with radius
$r(\rho)$ derived from the fair mechanism strength $\rho$, and $d$ is a
distribution distance metric.

By optimizing a fair objective
$\mathcal{L}_{\textsf{fair}}(\boldsymbol{\theta};\mathcal{D},\rho)$, existing
fairness mechanisms can effectively mitigate unfairness in supervised learning
with static data distribution $\mathcal{D}$. However, it remains unclear how
these methods would perform in SDPP when the model itself causes the data
distribution shifts. Specifically, consider iterative algorithms introduced in
Eqn. (3) that find PS solutions (e.g., RRM). Suppose we apply the above
fairness mechanism at every round when updating the model parameter
$\boldsymbol{\theta}$, i.e., replacing
$\boldsymbol{\theta}^{(t)}=\operatorname{argmin}_{\boldsymbol{\theta}}\mathcal{L}(\boldsymbol{\theta};\mathcal{D}^{(t-1)})$
with fair version
$\boldsymbol{\theta}^{(t)}=\operatorname{argmin}_{\boldsymbol{\theta}}\mathcal{L}_{\textsf{fair}}(\boldsymbol{\theta};\mathcal{D}^{(t-1)},\rho)$
in iterative algorithms. We ask: can such new iterative algorithms mitigate
group-wise loss and participation disparity in SDPP and converge to a fair and
stable solution?

Before answering the above question, we first define Fair-PS solutions for
SDPP, at which both ML system and population distribution reach stability and
unfairness is mitigated.

######  Definition 4.1 (Fair-PS solution).

We define
$(\mathcal{D}^{\text{PS}}_{\textsf{fair}},\boldsymbol{\theta}^{\text{PS}}_{\textsf{fair}})$
as the Fair-PS solution to
$\mathcal{L}_{\textsf{fair}}(\boldsymbol{\theta};\mathcal{D},\rho)$ if

$\mathcal{D}^{\text{PS}}_{\textsf{fair}}=\text{T}(\boldsymbol{\theta}^{\text{PS}}_{\textsf{fair}};\mathcal{D}^{\text{PS}}_{\textsf{fair}}),~{}~{}~{}~{}\boldsymbol{\theta}^{\text{PS}}_{\textsf{fair}}=\underset{\boldsymbol{\theta}}{\operatorname{argmin}}~{}\mathcal{L}_{\textsf{fair}}(\boldsymbol{\theta};\mathcal{D}^{\text{PS}}_{\textsf{fair}},\rho).$

###  4.2 Existing designs fail to converge to Fair-PS solutions

We will use two examples to illustrate that the popular choices of fairness
mechanisms used in previous literature may fail to achieve stability and
fairness in SDPP. This includes (i) regularization method [9, 10] with group
loss variance
$\mathcal{P}(\boldsymbol{\theta};\mathcal{D},\rho):=\rho\sum_{s\in\mathcal{S}}p_{s}\cdot[\mathcal{L}(\boldsymbol{\theta};\mathcal{D}_{s})-\mathcal{L}(\boldsymbol{\theta};\mathcal{D})]^{2}$
as the penalty term in Eqn. (5); and (ii) distributionally robust optimization
(DRO) method [19, 21] with $\chi^{2}$-distance metric
$d(\mathcal{D},\tilde{\mathcal{D}}):=\int\left(\frac{d\mathcal{D}}{d\tilde{\mathcal{D}}}-1\right)^{2}d\tilde{\mathcal{D}}$
in Eqn. (6).

######  Example 4.2 (Group loss variance as penalty term).

Consider two groups $a,b$ with data $Z=(X,Y)$ and fixed group fractions
$p_{a}=p_{b}=0.5$. Suppose all samples in group $a$ are $(1,-1)$ and all
samples in group $b$ are $(2,1)$. Consider squared loss function
$\ell(z;\theta)=(y-h_{\theta}(x))^{2}=(y-\theta x)^{2}$ which is strongly
convex and jointly smooth. Under group loss variance penalty
$\mathcal{P}(\boldsymbol{\theta};\mathcal{D},\rho)$, we have
$\mathcal{L}_{\textsf{fair}}(\boldsymbol{\theta};\mathcal{D},\rho)=2.5\theta^{2}-\theta+1+\rho\cdot(2.25\theta^{4}+9\theta^{2}-9\theta^{3})$.
When $\rho=0.6$, the second-order derivative
$\nabla^{2}_{\theta}\mathcal{L}_{\textsf{fair}}=16.2\theta^{2}-32.4\theta+15.8$
and is negative when $\theta=1$. Because convexity of
$\mathcal{L}_{\textsf{fair}}$ is a necessary condition for iterative
algorithms such as RRM to converge to a stable solution (by Lemma 2.4), adding
group loss variance as a penalty at each round will disrupt the stability and
the algorithm fails to find Fair-PS solutions. Appendix C.4 provides an
empirical illustration of this.

######  Example 4.3 (Repeated DRO with $\chi^{2}$-distance metric).

Consider two groups $a,b$ with fixed data $z_{a}=1$ and $z_{b}=-1$ for all
samples but group fractions $p_{a}^{(t)}=0.5\cdot(1+\theta^{(t)})$ and
$p_{b}^{(t)}=0.5\cdot(1-\theta^{(t)})$. $p_{a}^{(0)}=0.4,p_{b}^{(0)}=0.6$.
Consider a mean estimation task where the model parameter
${\theta}^{(t+1)}:=\arg\min_{\boldsymbol{\theta}}\max_{\tilde{\mathcal{D}}\in\mathcal{B}(\mathcal{D}^{(t)},r)}\mathcal{L}({\theta};\tilde{\mathcal{D}})$
is updated using DRO with mean squared error and $\chi^{2}$-distance bound
$r=1/6$. Let $q_{a}^{(t)},q_{b}^{(t)}$ denote the group fractions of "worst-
case" distribution $\tilde{\mathcal{D}}$. We have
$q_{a}^{(0)}=0.6,q_{b}^{(0)}=0.4$ and
$\theta^{(1)}=\arg\min_{\theta}q_{a}^{(0)}(1-\theta)^{2}+q_{b}^{(0)}(1+\theta)^{2}=0.2$,
which results in $p_{a}^{(1)}=0.6,p_{b}^{(1)}=0.4$. Since
$\mathcal{L}_{a}(\theta^{(1)};z_{a})<\mathcal{L}_{b}(\theta^{(1)};z_{b})$, DRO
should minimize the risk of the "worst-case" distribution with
$q_{a}^{(1)}=0.4,q_{b}^{(1)}=0.6$, i.e.,
$\theta^{(2)}=\arg\min_{\theta}q_{a}^{(1)}(1-\theta)^{2}+q_{b}^{(1)}(1+\theta)^{2}=-0.2$.
Repeating the procedure we will get $p_{a}^{(2)}=0.4,p_{b}^{(2)}=0.6$ and
$q_{a}^{(2)}=0.6,q_{b}^{(2)}=0.4$, $\theta^{(3)}=0.2$. It turns out that
repeated DRO results in $\theta^{(t)}$ oscillating between $0.2$ and $-0.2$
and it never converges.

It is worth noting that DRO methods have been used in Hashimoto et al. [19] to
mitigate group fraction disparity in repeated optimizations. However, it only
improves fairness without any convergence guarantees to stable solutions.
Peet-Pare et al. [21] repeatedly used DRO to improve fairness under PP
settings, it only converges to a PS solution under strict assumptions that are
hard to verify. Under milder conditions in Lemma 2.4, it may fail to converge
as Example 4.3 illustrated.

###  4.3 Novel designs for fairness mechanism

Next, we introduce three novel fair objective functions
$\mathcal{L}_{\textsf{fair}}(\boldsymbol{\theta};\mathcal{D},\rho)$ for
fairness mechanisms, of which two belong to regularization method and one is a
sample re-weighting method. By replacing
$\boldsymbol{\theta}^{(t)}=\operatorname{argmin}_{\boldsymbol{\theta}}\mathcal{L}(\boldsymbol{\theta};\mathcal{D}^{(t-1)})$
with the proposed fair update
$\boldsymbol{\theta}^{(t)}=\operatorname{argmin}_{\boldsymbol{\theta}}\mathcal{L}_{\textsf{fair}}(\boldsymbol{\theta};\mathcal{D}^{(t-1)},\rho)$
in Eqn. (3), the resulting iterative algorithms can converge to Fair-PS
solutions.

Proposed fair regularization (with and without demographics). Depending on
whether sensitive attributes $S$ are accessible during training, we propose
two fairness penalty terms, as detailed below.

  1. 1.

Group level fairness penalty: It updates model parameter
$\boldsymbol{\theta}^{(t)}$ at round $t$ by the following

$\textstyle\boldsymbol{\theta}^{(t)}=\operatorname{argmin}_{\boldsymbol{\theta}}\mathcal{L}_{\textsf{fair}}(\boldsymbol{\theta};\mathcal{D}^{(t-1)},\rho):=\mathcal{L}(\boldsymbol{\theta};\mathcal{D}^{(t-1)})+\rho\sum_{s\in\mathcal{S}}p^{(t-1)}_{s}[\mathcal{L}(\boldsymbol{\theta};\mathcal{D}_{s}^{(t-1)})]^{2}$
(7)

  2. 2.

Sample level fairness penalty without demographics: It updates model parameter
$\boldsymbol{\theta}^{(t)}$ at round $t$ as follows, which does not need the
knowledge of sensitive attributes.

$\textstyle\boldsymbol{\theta}^{(t)}=\operatorname{argmin}_{\boldsymbol{\theta}}\mathcal{L}_{\textsf{fair}}(\boldsymbol{\theta};\mathcal{D}^{(t-1)},\rho):=\mathcal{L}(\boldsymbol{\theta};\mathcal{D}^{(t-1)})+\rho\mathbb{E}_{Z\sim\mathcal{D}^{(t-1)}}\big{[}[\ell(\boldsymbol{\theta};Z)]^{2}\big{]}.$
(8)

Proposed fair sample re-weighting. It updates model parameter
$\boldsymbol{\theta}^{(t)}$ at round $t$ as follows.

$\displaystyle\boldsymbol{\theta}^{(t)}=\operatorname{argmin}_{\boldsymbol{\theta}}\mathcal{L}_{\textsf{fair}}(\boldsymbol{\theta};\mathcal{D}^{(t-1)},\rho):=\sum_{s\in\mathcal{S}}q_{s}^{(t-1)}\mathcal{L}(\boldsymbol{\theta};\mathcal{D}_{s}^{(t-1)}),$
(9) $\displaystyle\text{with
}~{}\boldsymbol{q}^{(t-1)}=\left[q^{(t-1)}_{s}\right]_{s\in\mathcal{S}}:=\frac{\boldsymbol{p}^{(t-1)}+\rho\boldsymbol{l}^{(t-1)}}{\|\boldsymbol{p}^{(t-1)}+\rho\boldsymbol{l}^{(t-1)}\|_{1}}\text{
and
}~{}\boldsymbol{l}^{(t-1)}:=\left[p_{s}^{(t-1)}\mathcal{L}(\boldsymbol{\theta}^{(t-1)};\mathcal{D}_{s}^{(t-2)})\right]_{s\in\mathcal{S}}$

Unlike DRO methods in [22, 19] that require solving a min-max optimization at
the current round, our re-weighting method only adjusts the weights for each
group based on the group-wise losses in the previous round, which is more
computationally efficient.

Comparison & discussion. Intuitively, compared to original
$\mathcal{L}(\boldsymbol{\theta};\mathcal{D}^{(t-1)})$, all three proposed
fair objective functions
$\mathcal{L}_{\textsf{fair}}(\boldsymbol{\theta};\mathcal{D}^{(t-1)},\rho)$
improves fairness at each round by assigning more weights to disadvantaged
groups/samples (i.e., the groups/samples experiencing higher losses) in the
upcoming update. Indeed, both sample level fairness penalty and fair sample
re-weighting can be regarded as modifications of group level fairness penalty.

Comparing Eqn. (7) and (8), the two penalty terms get more similar when most
individual samples in the disadvantaged (resp. advantaged) groups are also
similarly disadvantaged (resp. advantaged). This is more likely to happen when
each demographic group has a distribution with a small variance. For example,
if the distribution of each group is a point mass, Eqn. (7) and (8) are
identical.

Comparing Eqn. (7) and (9), we can rewrite Eqn. (9) as the following:

$\textstyle\|\boldsymbol{p}^{(t-1)}+\rho\boldsymbol{l}^{(t-1)}\|_{1}\mathcal{L}_{\textsf{fair}}(\boldsymbol{\theta};\mathcal{D}^{(t-1)},\rho)=~{}\sum_{s\in\mathcal{S}}p_{s}^{(t-1)}(1+\rho)\mathcal{L}(\boldsymbol{\theta}^{(t-1)};\mathcal{D}_{s}^{(t-2)})\mathcal{L}(\boldsymbol{\theta};\mathcal{D}_{s}^{(t-1)}).$

We can see that the right-hand side will be a multiple of Eqn. (7) if we
replace $\mathcal{L}(\boldsymbol{\theta}^{(t-1)};\mathcal{D}_{s}^{(t-2)})$
with $\mathcal{L}(\boldsymbol{\theta};\mathcal{D}_{s}^{(t-1)})$. This means
both equations yield the same $\theta^{(t)}$ when the population distribution
does not change from $t-2$ to $t-1$, suggesting that the two approaches become
more similar when the sensitivity of the transition mapping T is smaller, or
equivalently, the distribution shift is milder. Finally, we also discuss
designing fair objective functions generally in App. B.4.

##  5 Theoretical Analysis

Algorithm 1 Fair repeated risk minimization (Fair-RRM)

$t=0$, initial data distribution $\mathcal{D}^{(0)}$, strength of fair
mechanism $\rho$, initial model parameter $\boldsymbol{\theta}^{(0)}$,
stopping criteria $\tau$

Choose repeated deployment schema and fair mechanism;

repeat

$\boldsymbol{\theta}^{(t+1)}\leftarrow\arg\min_{\boldsymbol{\theta}}\mathcal{L}_{\textsf{fair}}(\boldsymbol{\theta};\mathcal{D}^{(t)},\rho)$;

Get
$\mathcal{D}^{(t+1)}=\text{Tr}(\boldsymbol{\theta}^{(t+1)};\mathcal{D}^{(t)})$
from the chosen schema;

$t\leftarrow t+1$;

until $\|\boldsymbol{\theta}^{(t)}-\boldsymbol{\theta}^{(t-1)}\|_{2}\leq\tau$

Next, we show that by replacing update
$\boldsymbol{\theta}^{(t)}=\operatorname{argmin}_{\boldsymbol{\theta}}\mathcal{L}(\boldsymbol{\theta};\mathcal{D}^{(t-1)})$
in Eqn. (3) with the fair update
$\boldsymbol{\theta}^{(t)}=\operatorname{argmin}_{\boldsymbol{\theta}}\mathcal{L}_{\textsf{fair}}(\boldsymbol{\theta};\mathcal{D}^{(t-1)},\rho)$
we proposed in Section 4.3, Fair-PS solutions (Definition 4.1) exist under
certain conditions and the resulting iterative algorithms (see Algorithm 1)
can converge to such Fair-PS solutions. We assume conditions in Lemma 2.4 hold
in this section and there exists a unique PS solution in the original SDPP
problem.

We first define a parameter $\tilde{\beta}$ which will be frequently used in
the theorems introduced below.

$\tilde{\beta}:=\begin{cases}(2\rho\overline{\ell}+1)\beta,~{}~{}~{}\text{for
fair regularization method with group level
\eqref{eq:squared_group_loss_penalty} or sample level penalty
\eqref{eq:fair_loss_sample_level} }\\\
(\rho\overline{\ell}+1)\beta,~{}~{}~{}\text{for fair sample re-weighting
method \eqref{eq:fair_reweight} }\end{cases}$

where
$\overline{\ell}:=\sup_{\boldsymbol{\theta},Z}\ell(\boldsymbol{\theta};Z)$. We
can identify conditions under which a unique Fair-PS solution exists.

######  Proposition 5.1 (Existence of unique Fair-PS solution).

For a given population with initial distribution $\mathcal{D}^{(0)}$ and the
proposed fair mechanism $\mathcal{L}_{\textsf{fair}}$ with strength $\rho$,
there is a unique Fair-PS solution if $\epsilon(1+\tilde{\beta}/\gamma)<1$.
Moreover,
$(\mathcal{D}^{\text{PS}}_{\textsf{fair}},\boldsymbol{\theta}^{\text{PS}}_{\textsf{fair}})$
is independent of the choice of repeated deployment schema.

Although the choice of repeated deployment schema does not affect the Fair-PS
solution
$(\mathcal{D}^{\text{PS}}_{\textsf{fair}},\boldsymbol{\theta}^{\text{PS}}_{\textsf{fair}})$,
it influences the convergence rate of the iterative algorithms as stated in
Theorem 5.2.

######  Theorem 5.2 (Convergence of Fair-RRM).

Under conventional deployment schema, Algorithm 1 converges to the Fair-PS
solution at a linear rate if $\epsilon(1+\tilde{\beta}/\gamma)<1$; under
$k$-delayed deployment schema, Algorithm 1 converges to the Fair-PS solution
at a linear rate for any $k$ if $\epsilon(1+\tilde{\beta}/\gamma)<1-\epsilon$;
Particularly, under delayed deployment schema when
$r=\log^{-1}\left(\frac{1}{\epsilon}\right)\log\left(\frac{\mathcal{W}_{1}(\mathcal{D}^{(0)},\mathcal{D}^{(1)})}{\delta}\right)$,
Algorithm 1 converges to a radius $\delta$ of the Fair-PS solution (i.e.,
$\|\boldsymbol{\theta}^{(t)}-\boldsymbol{\theta}^{\text{PS}}_{\textsf{fair}}\|_{2}\leq\delta$
and
$\mathcal{W}_{1}(\mathcal{D}(\boldsymbol{\theta}^{(t)}),\mathcal{D}^{\text{PS}}_{\textsf{fair}})\leq\delta$)
in $\mathcal{O}(\log^{2}\frac{1}{\delta})$ steps if
$\epsilon(1+\tilde{\beta}/\gamma)<1$.

In Appendix B.3, we extend the Algorithm 1 to practical scenarios when data
distribution is inaccessible. We provide the algorithm fair repeated empirical
risk minimization (Fair-RERM) where only limited data samples are available
from $\mathcal{D}^{(t)}$ and analyze its sample complexity in Theorem B.3.

Impacts of strength of fair mechanism $\rho$. Theorem 5.2 and B.3 show that
repeatedly minimizing
$\mathcal{L}_{\textsf{fair}}(\boldsymbol{\theta};\mathcal{D}^{(t-1)},\rho)$ on
evolving data sequence can lead the system converging to a Fair-PS solution.
Note that $\rho$ controls the strength of fairness and different $\rho$ could
result in different
$(\boldsymbol{\theta}^{\text{PS}}_{\textsf{fair}},\mathcal{D}^{\text{PS}}_{\textsf{fair}})$.
In conventional supervised learning with static data distribution
$\mathcal{D}$, it is trivial to see that larger $\rho$ in
$\mathcal{L}_{\textsf{fair}}(\boldsymbol{\theta};\mathcal{D},\rho)$ will lead
to a fairer solution [6]. However, in SDPP with model-dependent distribution
shifts, the impact of $\rho$ on unfairness is less straightforward. Because
both data distribution $\mathcal{D}^{\text{PS}}_{\textsf{fair}}$ and model
$\boldsymbol{\theta}^{\text{PS}}_{\textsf{fair}}$ depend on $\rho$, analyzing
how group-wise disparity would change as $\rho$ varies can be highly non-
trivial and has not been studied in PP literature (Appendix D.4 provides more
discussion).

Next, we initiate the study for fair mechanism in Eqn. (7) with group-level
fairness penalty and rigorously show that the larger $\rho$ can lead to
smaller group-wise loss disparity at the Fair-PS solution. We will focus on a
special case of user retention dynamics [19, 2] with two groups
$s\in\\{a,b\\}$, where the group distribution $\mathcal{D}_{s}$ is fixed but
the fraction $p_{s}^{(t)}$ changes based on group loss
$\mathcal{L}(\boldsymbol{\theta}^{(t)};\mathcal{D}_{s})$ during repeated risk
minimization process.

######  Assumption 5.3.

At each round, the group that is majority also experiences lower expected
loss, i.e.,
$\arg\max_{s\in\\{a,b\\}}p_{s}^{t}=\arg\min_{s\in\\{a,b\\}}\mathcal{L}(\boldsymbol{\theta}^{(t)};\mathcal{D}_{s})$.
Moreover, for any two models deployed on population $\mathcal{D}^{(t)}$, the
model with larger loss disparity $\triangle_{\mathcal{L}}^{(t)}$ leads to
higher group fraction disparity $\triangle^{(t+1)}_{p}$ at time $t+1$.

Assumption 5.3 is natural: in fields such as recognition or recommendation
systems, the minority group contributing less training data suffers from
higher loss and has a lower retention rate.

######  Theorem 5.4 (Larger $\rho$ leads to stronger fairness).

Denote Fair-PS solution
$\left(\boldsymbol{\theta}^{\text{PS}}_{\textsf{fair}}\left(\rho\right),\mathcal{D}^{\text{PS}}_{\textsf{fair}}\left(\rho\right)\right)$
as a function of $\rho\geq 0$. Let
$\triangle^{\text{PS}}_{\textsf{fair},\mathcal{L}}(\rho)$ be the group-wise
loss disparity of
$\boldsymbol{\theta}^{\text{PS}}_{\textsf{fair}}\left(\rho\right)$ evaluated
over distribution $\mathcal{D}^{\text{PS}}_{\textsf{fair}}\left(\rho\right)$
as defined in Eqn. (4). Under Assumption 5.3,
$\triangle^{\text{PS}}_{\textsf{fair},\mathcal{L}}(\rho)$ is non-increasing in
$\rho$.

##  6 Numerical Results

This section empirically evaluates the proposed methods on synthetic and real-
world data (including credit data [4, 23] and MNIST data [24]) under semi-
synthesized performative shifts. We run all experiments with multiple random
seeds and visualize the standard error with the shaded area. Due to page
limits, more experiments are presented in Appendix C.

Performative Gaussian mean estimation. We generate a synthetic dataset of
$10000$ samples from two groups $s\in\\{a,b\\}$ with initial group fractions
$p_{a}^{(0)}=0.3,p_{b}^{(0)}=0.7$ and target values
$y_{a}=0.3+\epsilon,y_{b}=0.7+\epsilon$, where
$\epsilon\sim\mathcal{N}(0,0.05)$. We consider user retention dynamics where
the group fraction
$p^{(t+1)}_{s}=\frac{\mathcal{R}(s,t)}{\sum_{s^{\prime}\in\\{a,b\\}}\mathcal{R}(s^{\prime},t)}$
changes based on group-wise loss. Here
$\mathcal{R}(s,t)=\left(1-\sum_{s^{\prime}\in\\{a,b\\}}p^{\min}_{s^{\prime}}\right)\times\frac{1}{2}\left(p_{s}^{t}+\frac{\mathcal{L}(\boldsymbol{\theta}^{(t)};\mathcal{D}_{-s}^{(t)})}{\mathcal{L}(\boldsymbol{\theta}^{(t)};\mathcal{D}_{-s}^{(t)})+\mathcal{L}(\boldsymbol{\theta}^{(t)};\mathcal{D}_{s}^{(t)})}\right)+p_{s}^{\min}$
where $p_{s}^{\min}=0.02$ is the minimum group fraction that ensures the
sensitivity of the transition mapping T is bounded, and $-s=\\{a,b\\}\setminus
s$. We perform the mean estimation task and train multiple linear regression
models using RERM and Fair-RERM, including regularization methods with group-
level penalty (Fair-RERM-GLP), sample-level penalty (Fair-RERM-SLP) and sample
re-weighting method (Fair-RERM-RW). We perform $30$ rounds of empirical risk
minimization on $7$ different random seeds. Fig. 2(a) illustrates the
evolution of group-wise loss disparity $\triangle_{\mathcal{L}}^{(t)}$ and
Fig. 2(b) shows the evolution of the minority group fraction (i.e., the group
with the lower fraction at the stable point). The blue lines in both figures
demonstrate that the PS solution of the regular RERM has the highest
unfairness and the most polarized group fractions, while the Fair-PS solution
is fairer and the higher $\rho$ results in stronger fairness, implying Fair-
RERM is effective in mitigating polarization effects and unfairness. We also
note that among all three methods, the sample re-weighting method (Fair-RERM-
RW) seems to yield better fairness control than others under this setting.

(a) Dynamics of group-wise loss disparity.

(b) Dynamics of the minority group fraction.

Figure 2: Dynamics of unfairness under Synthetic data when
$\rho\in\\{0,0.3,0.7\\}$ ($\rho=0$ is RERM): Fair-RERM-RW (left plot), Fair-
RERM-GLP (middle plot), Fair-RERM-SLP (right plot)

Credit data retention dynamics with strategic behaviors. We use the Give me
some credit data [23] consisting of features $X\in\mathbb{R}^{10}$ to measure
individuals’ creditworthiness $Y\in\\{0,1\\}$ which has been widely used in
performative prediction and strategic classification literature [4, 15]. We
preprocessed the data similarly to Perdomo et al. [4] and divided individuals
into two groups $s\in\\{a,b\\}$ based on the age attribute. Next, we assume
there is a newly established credit rating agency performing RERM and Fair-
RERM with logistic classification models to predict individuals’
creditworthiness. Similar to the previous experiment, we assume the group-wise
loss in round $t$ will affect the group fraction at $t+1$. Meanwhile, we
assume there is a subset of features $X_{s}\in X$ which individuals can change
strategically to $X_{s}^{\prime}$ based on the current model parameters
$\theta$. Specifically, $X_{s}^{\prime}=X_{s}-\epsilon\cdot\theta_{s}$, where
$\theta_{s}$ is the subset of $\theta$ with respect to $X_{s}$ and
$\epsilon=0.1$. With the dynamics involving both retention and strategic
behaviors, we can visualize the dynamics of unfairness under RERM and Fair-
RERM in Fig. 3. All results demonstrate the effectiveness of our methods. The
regularization method with sample level penalty (Fair-RERM-SLP) seems to be
more effective under this setting.

(a) Dynamics of group-wise loss disparity.

(b) Dynamics of the minority group fraction.

Figure 3: Dynamics of unfairness under Credit data when
$\rho\in\\{0,1.0,5.0\\}$ ($\rho=0$ is RERM): Fair-RERM-RW (left plot), Fair-
RERM-GLP (middle plot), Fair-RERM-SLP (right plot)

Performative MNIST classification. We next consider MNIST data [24] consisting
of handwritten digits images. We randomly select 1000 images as the training
set and divide them into 2 groups, where the first group contains all images
with digits from $0$ to $4$ and the second includes digits from $5$ to $9$. We
consider the same group fraction dynamics as before with $p_{s}^{\min}=0.1$
for both groups. Using a 2-layer MLP (the loss function violates conditions in
Lemma 2.4) for risk minimization, we perform RERM and Fair-RERM for $50$
rounds. Fig. 4(a) and 4(b) verify that Fair-RERM can still improve fairness at
the PS solution. Both plots demonstrate that unfairness is the largest without
fairness interventions and Fair-RERM is more effective with larger $\rho$.
Unlike the experiments on synthetic and credit data, this set of experiments
does not have a convergence guarantee because conditions for theorems are
violated under 2-layer MLP, e.g., the black and red lines ($\rho=0.3$) of
Fair-RERM-RW and Fair-RERM-GLP are unstable. However, the results suggest that
our fairness mechanisms may still be useful in practice with deep learning
models.

(a) Dynamics of group-wise loss disparity.

(b) Dynamics of the minority group fraction.

Figure 4: Dynamics of unfairness under MNIST data when
$\rho\in\\{0,0.1,0.3\\}$ ($\rho=0$ is RERM): Fair-RERM-RW (left plot), Fair-
RERM-GLP (middle plot), Fair-RERM-SLP (right plot)

##  7 Conclusions & Societal Impacts

Our work reveals the unfairness issues of the PS solutions of PP. We then
propose novel fairness-aware algorithms to find Fair-PS solutions with the
convergence holds under mild assumptions, which will facilitate trustworthy
machine learning since PP has broad applications on human-related decisions
ranging from college admission and loan approval to hiring practice.
Meaningful future directions include relaxing the conditions for the
convergence of fairness mechanisms or expanding the mechanisms to deep
learning settings.

## References

  * Hardt et al. [2015] Moritz Hardt, Nimrod Megiddo, Christos Papadimitriou, and Mary Wootters.  Strategic Classification, November 2015.  URL http://arxiv.org/abs/1506.06980.  Number: arXiv:1506.06980 arXiv:1506.06980 [cs].
  * Zhang et al. [2019] Xueru Zhang, Mohammad Mahdi Khalili, Cem Tekin, and Mingyan Liu.  _Group Retention When Using Machine Learning in Sequential Decision Making: The Interplay between User Dynamics and Fairness_.  Curran Associates Inc., Red Hook, NY, USA, 2019.
  * Chi et al. [2022] Jianfeng Chi, Jian Shen, Xinyi Dai, Weinan Zhang, Yuan Tian, and Han Zhao.  Towards return parity in markov decision processes.  In _International Conference on Artificial Intelligence and Statistics_ , pages 1161–1178. PMLR, 2022.
  * Perdomo et al. [2021] Juan C. Perdomo, Tijana Zrnic, Celestine Mendler-Dünner, and Moritz Hardt.  Performative Prediction.  _arXiv:2002.06673 [cs, stat]_ , February 2021.  URL http://arxiv.org/abs/2002.06673.  arXiv: 2002.06673.
  * Brown et al. [2022] Gavin Brown, Shlomi Hod, and Iden Kalemaj.  Performative prediction in a stateful world.  In Gustau Camps-Valls, Francisco J. R. Ruiz, and Isabel Valera, editors, _Proceedings of The 25th International Conference on Artificial Intelligence and Statistics_ , volume 151 of _Proceedings of Machine Learning Research_ , pages 6045–6061. PMLR, 28–30 Mar 2022.  URL https://proceedings.mlr.press/v151/brown22a.html.
  * Martinez et al. [2020] Natalia Martinez, Martin Bertran, and Guillermo Sapiro.  Minimax pareto fairness: A multi objective perspective.  In _International conference on machine learning_ , pages 6755–6764. PMLR, 2020.
  * Diana et al. [2021] Emily Diana, Wesley Gill, Michael Kearns, Krishnaram Kenthapadi, and Aaron Roth.  Minimax group fairness: Algorithms and experiments.  In _Proceedings of the 2021 AAAI/ACM Conference on AI, Ethics, and Society_ , pages 66–76, 2021.
  * Raab et al. [2024] Reilly Raab, Ross Boczar, Maryam Fazel, and Yang Liu.  Fair participation via sequential policies.  _Proceedings of the AAAI Conference on Artificial Intelligence_ , pages 14758–14766, 2024.
  * Khan et al. [2023] Falaah Arif Khan, Denys Herasymuk, and Julia Stoyanovich.  On fairness and stability: Is estimator variance a friend or a foe?  _arXiv preprint arXiv:2302.04525_ , 2023.
  * Zhang et al. [2021] Fengda Zhang, Kun Kuang, Yuxuan Liu, Long Chen, Chao Wu, Fei Wu, Jiaxun Lu, Yunfeng Shao, and Jun Xiao.  Unified group fairness on federated learning.  _arXiv preprint arXiv:2111.04986_ , 2021.
  * Jung et al. [2023] Sangwon Jung, Taeeon Park, Sanghyuk Chun, and Taesup Moon.  Re-weighting based group fairness regularization via classwise robust optimization, 2023.
  * Duchi and Namkoong [2018] John Duchi and Hongseok Namkoong.  Learning models with uniform performance via distributionally robust optimization.  _arXiv preprint arXiv:1810.08750_ , 2018.
  * Duchi et al. [2023] John Duchi, Tatsunori Hashimoto, and Hongseok Namkoong.  Distributionally robust losses for latent covariate mixtures.  _Operations Research_ , 71(2):649–664, 2023.
  * Zezulka and Genin [2023] Sebastian Zezulka and Konstantin Genin.  Performativity and prospective fairness.  _arXiv preprint arXiv:2310.08349_ , 2023.
  * Hu and Zhang [2022] Yaowei Hu and Lu Zhang.  Achieving long-term fairness in sequential decision making.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 36, pages 9549–9557, 2022.
  * Jin et al. [2022] Kun Jin, Xueru Zhang, Mohammad Mahdi Khalili, Parinaz Naghizadeh, and Mingyan Liu.  Incentive mechanisms for strategic classification and regression problems.  In David M. Pennock, Ilya Segal, and Sven Seuken, editors, _EC ’22: The 23rd ACM Conference on Economics and Computation, Boulder, CO, USA, July 11 - 15, 2022_ , pages 760–790. ACM, 2022.  doi: 10.1145/3490486.3538300.  URL https://doi.org/10.1145/3490486.3538300.
  * Zhang et al. [2022] Xueru Zhang, Mohammad Mahdi Khalili, Kun Jin, Parinaz Naghizadeh, and Mingyan Liu.  Fairness interventions as (Dis)Incentives for strategic manipulation.  In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato, editors, _Proceedings of the 39th International Conference on Machine Learning_ , volume 162 of _Proceedings of Machine Learning Research_ , pages 26239–26264. PMLR, 17–23 Jul 2022.  URL https://proceedings.mlr.press/v162/zhang22l.html.
  * Hashimoto et al. [2018a] Tatsunori Hashimoto, Megha Srivastava, Hongseok Namkoong, and Percy Liang.  Fairness without demographics in repeated loss minimization.  In Jennifer Dy and Andreas Krause, editors, _Proceedings of the 35th International Conference on Machine Learning_ , volume 80 of _Proceedings of Machine Learning Research_ , pages 1929–1938. PMLR, 10–15 Jul 2018a.  URL https://proceedings.mlr.press/v80/hashimoto18a.html.
  * Hashimoto et al. [2018b] Tatsunori Hashimoto, Megha Srivastava, Hongseok Namkoong, and Percy Liang.  Fairness without demographics in repeated loss minimization.  In _International Conference on Machine Learning_ , pages 1929–1938. PMLR, 2018b.
  * Kleinberg and Raghavan [2019] Jon Kleinberg and Manish Raghavan.  How do classifiers induce agents to invest effort strategically?, 2019.
  * Peet-Pare et al. [2022] Liam Peet-Pare, Nidhi Hegde, and Alona Fyshe.  Long term fairness for minority groups via performative distributionally robust optimization, 2022.
  * Peet-Pare et al. [2023] Garnet Liam Peet-Pare, Nidhi Hegde, and Alona Fyshe.  Long term fairness via performative distributionally robust optimization, 2023.  URL https://openreview.net/forum?id=YvrAyFZq0ID.
  * Kaggle [2012] Kaggle.  Give me some credit.  https://www.kaggle.com/c/GiveMeSomeCredit/data, 2012.
  * Deng [2012] Li Deng.  The mnist database of handwritten digit images for machine learning research.  _IEEE Signal Processing Magazine_ , 29(6):141–142, 2012.
  * Raab and Liu [2021] Reilly Raab and Yang Liu.  Unintended selection: Persistent qualification rate disparities and interventions.  _Advances in Neural Information Processing Systems_ , 34, 2021.
  * Xie et al. [2024a] Tian Xie, Xuwei Tan, and Xueru Zhang.  Algorithmic decision-making under agents with persistent improvement, 2024a.
  * Xie et al. [2024b] Tian Xie, Zhiqun Zuo, Mohammad Mahdi Khalili, and Xueru Zhang.  Learning under imitative strategic behavior with unforeseeable outcomes, 2024b.
  * Ensign et al. [2018] Danielle Ensign, Sorelle A Friedler, Scott Neville, Carlos Scheidegger, and Suresh Venkatasubramanian.  Runaway feedback loops in predictive policing.  In _Conference on fairness, accountability and transparency_ , pages 160–171. PMLR, 2018.
  * Mendler-Dünner et al. [2020] Celestine Mendler-Dünner, Juan Perdomo, Tijana Zrnic, and Moritz Hardt.  Stochastic optimization for performative prediction.  In _Advances in neural information processing systems_ , pages 4929–4939. Curran Associates, Inc., 2020.
  * Mofakhami et al. [2023] Mehrnaz Mofakhami, Ioannis Mitliagkas, and Gauthier Gidel.  Performative prediction with neural networks.  In _International Conference on Artificial Intelligence and Statistics_ , pages 11079–11093. PMLR, 2023.
  * Zhao [2022] Yulai Zhao.  Optimizing the performative risk under weak convexity assumptions.  _arXiv preprint arXiv:2209.00771_ , 2022.
  * Miller et al. [2021] John Miller, Juan C. Perdomo, and Tijana Zrnic.  Outside the Echo Chamber: Optimizing the Performative Risk.  _arXiv:2102.08570 [cs, stat]_ , June 2021.  URL http://arxiv.org/abs/2102.08570.  arXiv: 2102.08570.
  * Izzo et al. [2021] Zachary Izzo, Lexing Ying, and James Zou.  How to learn when data reacts to your model: Performative gradient descent.  _CoRR_ , 2021.  arXiv: 2102.07698.
  * Hardt and Mendler-Dünner [2023] Moritz Hardt and Celestine Mendler-Dünner.  Performative prediction: Past and future.  _arXiv preprint arXiv:2310.16608_ , 2023.
  * Kamishima et al. [2011] Toshihiro Kamishima, Shotaro Akaho, and Jun Sakuma.  Fairness-aware learning through regularization approach.  In _2011 IEEE 11th International Conference on Data Mining Workshops_ , pages 643–650, 2011.  doi: 10.1109/ICDMW.2011.83.
  * Zafar et al. [2017] Muhammad Bilal Zafar, Isabel Valera, Manuel Gomez Rodriguez, and Krishna P Gummadi.  Fairness beyond disparate treatment & disparate impact: Learning classification without disparate mistreatment.  In _Proceedings of the 26th international conference on world wide web_ , pages 1171–1180, 2017.
  * Guldogan et al. [2022] Ozgur Guldogan, Yuchen Zeng, Jy-yong Sohn, Ramtin Pedarsani, and Kangwook Lee.  Equal improvability: A new fairness notion considering the long-term impact.  _arXiv preprint arXiv:2210.06732_ , 2022.
  * Milli et al. [2018] Smitha Milli, John Miller, Anca D. Dragan, and Moritz Hardt.  The social cost of strategic classification, 2018.
  * Hu et al. [2019] Lily Hu, Nicole Immorlica, and Jennifer Wortman Vaughan.  The disparate effects of strategic manipulation.  In _ACM Conference on Fairness, Accountability, and Transparency_ , Atlanta, Georgia, 2019.
  * Zhang et al. [2020] Xueru Zhang, Ruibo Tu, Yang Liu, Mingyan Liu, Hedvig Kjellström, Kun Zhang, and Cheng Zhang.  How do fair decisions fare in long-term qualification?  In _Proceedings of the 34th International Conference on Neural Information Processing Systems_ , NIPS’20, Red Hook, NY, USA, 2020. Curran Associates Inc.  ISBN 9781713829546.
  * Bubeck [2015] Sébastien Bubeck.  Convex optimization: Algorithms and complexity.  _Found. Trends Mach. Learn._ , 8(3–4):231–357, nov 2015.  ISSN 1935-8237.  doi: 10.1561/2200000050.  URL https://doi.org/10.1561/2200000050.
  * Fournier and Guillin [2015] Nicolas Fournier and Arnaud Guillin.  On the rate of convergence in Wasserstein distance of the empirical measure.  _Probability Theory and Related Fields_ , 162(3-4):707, August 2015.  URL https://hal.science/hal-00915365.

##  Appendix A Related Works

Performative Prediction. Proposed by Perdomo et al. [4], Performative
prediction focuses on machine learning problems where the model deployments
influence the data distribution, and the common application scenarios include
strategic classification [1, 25, 26, 27] and predictive policing [28]. Perdomo
et al. [4] formulated the problem and proposed repeated risk minimization
(RRM) to ensure the convergence of model parameters to a stable point under a
set of sufficient and necessary conditions. Mendler-Dünner et al. [29]
presented convergence results on stochastic performative optimization.
Subsequent work either strived to relax the convergence condition [30, 31] or
develop methods to ensure the convergence to performative optimal points under
special cases [32, 33]. Brown et al. [5] extended performative prediction to
stateful settings where the current data distribution is determined by both
the previous states and the deployed model. For more related works on PP, we
refer to this survey [34].

Long-term fairness. There is a large line of work on long-term fairness in
machine learning, where we mainly refer to distributionally robust
optimization (DRO) [12, 13] and soft fair regularizers [35, 36, 37]. DRO
refers to the optimization problem where the loss is minimized on the worst-
case distribution around current data distribution [12, 13], while soft fair
regularizers are often used in traditional fair optimization frameworks to
penalize unfairness. Only a few pieces of literature touched on fairness
problems under performative prediction settings. [38, 39, 17, 40] focused on
long-term fairness settings under strategic classification similar to Example
3.2. Zezulka and Genin [14] pointed out fairness issues in performative
prediction and formulated it within causal graphs. Hu and Zhang [15] also used
causality-based models to formulate and ensure short-term and long-term
fairness in performative prediction, incurring strong assumptions and
expensive computational costs. Raab et al. [8] studied a special case where
only the agents’ retention rates are performative. Peet-Pare et al. [21]
proposed to use distributionally robust optimization (DRO) to promote fairness
in performative prediction, but they proposed assumptions that are hard to
verify and can not be derived from other commonly accepted assumptions in PP.

##  Appendix B Further Elaboration on the Concepts

Here we include the notation table and a Venn diagram to help the readers
better understand the technical details of our paper.

###  B.1 Notation Table

Notation |  Meanings
---|---
$\boldsymbol{\theta}$ |  Model parameters
$h_{\boldsymbol{\theta}}$ |  The decision model parameterized by $\boldsymbol{\theta}$
$\Theta$ |  The parameter space
$Z$ |  Data sample
$X$ |  Feature in the data sample
$Y$ |  Label in the data sample
$\mathcal{D}$ |  Sample distribution
$\triangle(\mathcal{Z})$ |  Support of sample distribution
T |  Transition mapping
$\text{T}^{k}$ |  $k$-Delayed transition mapping
$\text{T}^{DL}$ |  Delayed transition mapping where $k=\lceil r\rceil+1$
$\ell$ |  Loss function
$s$ |  Sensitive attribute, where group $s$ means the set of samples with attribute $s$
$\mathcal{S}$ |  The set of sensitive attributes
$\mathcal{L}_{s}$ |  The expected loss of group $s$
$\mathcal{D}^{(t)}_{s}$ |  Sample distribution of group $s$ at time $t$
$p^{(t)}_{s}$ |  Population fraction of group $s$ at time $t$
$\mathcal{W}_{1}$ |  The 1-Wasserstein distance
$\triangle_{DP},\triangle_{EO},\triangle_{\mathcal{L}}$ |  Demographic Parity, Equal Opportunity, Loss Disparity penalty
$\mathcal{L}_{\textsf{fair}}$ |  Fairness-aware objective
$\mathcal{P}$ |  The penalty term in fairness aware objective
$\mathcal{B}$ |  Distribution ball, used to limit the choices of re-weighting
$\boldsymbol{l}^{(t)}$ |  Loss-guided re-weighting vector for time step $t$
$q^{(t)}_{s}$ |  Group weight of group $s$ at time $t$ in the fair reweighting mechanism
$\rho$ |  Strength of fair mechanism
$\gamma$ |  Strong convexity coefficient of the loss
$\beta$ |  Joint smoothness coefficient of the loss
$\epsilon$ |  Joint sensitivity coefficient of the transition mapping
$\tilde{\beta}$ |  Joint smoothness coefficient of the fairness-aware objective
$\overline{\ell}$ |  Maximum loss value given $\Theta$ and $\triangle(\mathcal{Z})$
Table 1: Summary of notation.

###  B.2 Venn Diagram of Concepts in PP

We present a Venn diagram of different PP cases in Figure 5. Within the broad
concept of PP, we specifically characterize 3 practical concepts in real-world
problems, namely the (1) state-dependent performative shifts, (2) performative
retention dynamics, and (3) performative distribution shifts. These concepts
represent different dimensions to partition the PP problems.

Figure 5: A Venn diagram of the PP cases.

#### Performative Retention Dynamics (PRD).

Previous works that study long-term fairness [2, 40] mostly assume there to be
model-dependent retention rate/population fraction $p_{s}$ changes, which can
all be formulated as PRD problems. Recommendation systems are typical
application scenarios of SDPP and PRD since the population fraction in the
next iteration depends on both the current population and the current model.
The better recommendation model captures a certain user group’s interest, the
more likely this user group will have high retention rate.

######  Example B.1.

(User retention) Suppose two demographic groups $a,b$ each follow a static
distribution $\mathcal{D}_{a}$ and $\mathcal{D}_{b}$, but their fraction in
the population changes over time, and thus the overall data distribution is
dynamic. Specifically, let $p_{s}^{min}$ be control variables to limit the
minimum fraction of group $s$, and their retention rate is determined by a
retention function $\pi_{s}(\boldsymbol{\theta}^{(t)})$. Then we have

$p^{(t)}_{s}:=\frac{p^{(t-1)}_{s}\pi_{s}(\boldsymbol{\theta}^{(t)})+p_{s}^{min}}{\sum_{s^{\prime}}(p^{(t-1)}_{s^{\prime}}\pi_{s^{\prime}}(\boldsymbol{\theta}^{(t)})+p_{s^{\prime}}^{min})},~{}~{}\mathcal{D}^{(t)}=\sum_{s}p^{(t)}_{s}\mathcal{D}_{s},$
(10)

which can be modeled by PP in the SDPP setting.

#### Performative Distribution Shifts (PDS).

In this paper, PDS specifically means in each group, the data distribution
$\mathcal{D}_{s}$ shifts with the decision models, e.g., in strategic
classification, users strategically manipulate their features for better
decision outcomes. In recommendation systems, where creators strategically
manipulate their features for better decision outcomes from the model [1], and
users’ interests can be shifted by the recommended items.

We present a practical example of PP in addition to the one in the main
article.

$S$$X_{0}$$X_{1}$$X_{2}$$Y_{0}$$Y_{1}$$Y_{2}$$D_{0}$$D_{1}$$D_{2}$ Figure 6:
POMDP

######  Example B.2.

(Partially observable Markov decision process (POMDP) as PDS [40]) The
population fractions of the two groups $p_{s}$ are static, i.e.,
$\mathcal{D}^{(t)}=\sum_{s}p_{s}\mathcal{D}_{s}^{(t)}$, but the feature
distribution changes with the deployed decision model, and such changes follow
a POMDP as shown in Figure 6.

Specifically, within each group, there are two sub-populations, qualified and
disqualified, e.g., the qualified sub-population in group $a$ satisfies
$y=1,s=a$. Each sub-population has a static distribution, $\mathcal{D}_{s,y}$,
but each group’s distribution is dynamic and determined by

$\mathcal{D}_{s}^{(t)}=\sum_{y}\alpha^{(t)}_{s,y}\mathcal{D}_{s,y},~{}~{}\alpha^{(t)}_{s,y}:=\mathbb{P}(Y^{(t)}=1|S=s),$
(11)

where $Y^{(t)}$ is the random variable of the agent’s true label at time step
$t$. The POMDP assumes the decision model and the sensitive attribute jointly
determine the distribution of the true label distribution at the next time
step, and we have

$\alpha^{(t)}_{s,1}=\sum_{y=0}^{1}\alpha^{(t-1)}_{s,y}\underbrace{\mathbb{P}(Y^{(t)}=1|Y^{(t-1)}=y,\boldsymbol{\theta}=\boldsymbol{\theta}^{(t)},S=s)}_{\text{from
POMDP}},$ (12)

and we can similarly write out the dynamics of all the $\alpha^{(t)}_{s,y}$
terms and thus the transition mapping $T$ as a PDS problem.

###  B.3 Fair-RERM

Here we provide the algorithm for the Fair-RERM class and the results of its
sample complexity.

Algorithm 2 Fair-RERM

$t=0$, $\mathcal{D}^{(0)}$, $\rho$, $\boldsymbol{\theta}^{(0)}$,
$\delta_{\theta}$, choose fair mechanism

repeat

Sample $\mathcal{Z}^{(t)}$ from $\mathcal{D}^{(t)}$

$\boldsymbol{\theta}^{(t+1)}\leftarrow\arg\min_{\boldsymbol{\theta}}\mathcal{L}_{\textsf{fair}}(\boldsymbol{\theta};\mathcal{Z}^{(t)},\rho)$

Get the samples from $\mathcal{D}^{(t+1)}$ changing according to different
schema

$t\leftarrow t+1$

until
$\|\boldsymbol{\theta}^{(t)}-\boldsymbol{\theta}^{(t-1)}\|_{2}\leq\delta_{\theta}$

######  Theorem B.3 (Convergence of fair-RERM).

Suppose $\exists\alpha>1,\mu>0$ such that
$\int_{\mathbb{R}^{m}}e^{\mu|x|^{\alpha}}Zdx$ is finite $\forall
Z\in\triangle(\mathcal{Z})$. For a given convergence radius $\delta\in(0,1)$,
take
$n_{t}=\mathcal{O}\left(\frac{\log(t/p)}{(\epsilon(1+\tilde{\beta}/\gamma)\delta)^{m}}\right)$
samples at $t$. If $2\epsilon(1+\tilde{\beta}/\gamma)<1$, then with
probability $1-p$, the iterates of fair-RERM are within a radius $\delta$ of
the Fair-PS solution for
$t\geq(1-2\epsilon(1+\tilde{\beta}/\gamma)O(\log(1/\delta))$.

###  B.4 General guidance of designing fairness objectives under the SDPP
setting

The key to designing a fairness objective while ensuring the convergence of
the iterative algorithm is to ensure the convexity of the fairness penalty.
Example 4.2 shows that group loss variance cannot preserve the convexity of
$\mathcal{L}_{\textsf{fair}}$, so it fails to be a plausible objective. This
implies that each penalty term in terms of $P=g(\mathcal{L})$ where the
convexity of $P$ is ensured can be a fairness objective. However, it can still
be highly non-trivial to design a fair objective in this form due to the
following reasons: (i) it is hard to design an objective as interpretable as
the ones we mentioned in Section 4. The squared loss as a penalty term is
well-motivated and directly penalizes the groups/samples with the higher
losses; (ii) It becomes more difficult to obtain the concrete parameters for
the convergence guarantee. For example, $\bar{\ell}$ in Section 5 becomes the
upper bound of $\frac{\partial g}{\partial\ell}$ and this may be hard to
obtain and interpret. Overall, we see the formulations in Section 4 as more
appropriate choices.

###  B.5 Only Measure Fairness at PS Solution

We provide an example to illustrate that fairness is not guaranteed even if we
ensure instantaneous fairness without stability being achieved.

######  Example B.4.

(Fairness violation due to performative shifts) Consider a binary strategic
classification problem with two groups $a,b$ and is a threshold model
$h_{\theta}(X)=\mathbbm{1}\\{X\geq\theta\\}$. $p_{a},p_{b}$ are fixed and both
groups satisfy $\mathbb{P}(Y^{(t)}=1)=\min\\{0,\max\\{X^{(t)},1\\}\\}$, and
the transitions satisfy
$X^{(t)}=X^{(0)}+(0.1+0.1\cdot\boldsymbol{1}\\{s=a\\})\theta^{(t)}$ but do not
result in any changes in labels. If at $t=0$, both groups have features
$X^{(0)}$ subject to uniform distribution on $[0,1]$, then any $\theta=0.5$
satisfies accuracy parity. However, at $t=1$, group $a$ has a shifted
distribution, resulting in $\theta=0.5$ to be unfair.

##  Appendix C Additional Experiments

All experiments are run on the CPU of a Macbook Pro with Apple M1 Pro chip and
16GB memory. We use Python 3.9 for all tasks. For datasets, Yann LeCun and
Corinna Cortes hold the copyright of MNIST, which is a derivative work from
original NIST datasets. MNIST dataset is made available under the terms of the
Creative Commons Attribution-Share Alike 3.0 license; the credit dataset has
been published by Kaggle [23]; In Appendix C.1, we visualize the convergence
of performative loss for all the above experiments. In Appendix C.3, we
perform experiments on a performative Gaussian data classification task. In
Appendix C.2, we conduct experiments on 3 groups. In Appendix C.4, we
visualize the unconvergence of the fairness penalty using group loss variance
as a complementary to Example 4.2; Finally, we examine the k-delayed schema on
all our fairness mechanisms on Credit data in Appendix C.5 and obtain the
similar results.

###  C.1 Model Convergence in Main Experiments

In this section, we provide visualizations of the convergence of performative
loss for all experiments of the main paper in Fig. 12. Importantly, Fig. 12(d)
demonstrates the unconvergence of Fair-RERM-RW and Fair-RERM-GLP when
$\rho=0.3$.

###  C.2 Gaussian Mean Estimation with Multiple Groups

In this section, we present the experimental results on the Gaussian mean
estimation task with 3 groups $s\in\\{a,b,c\\}$ where
$p_{a}^{(0)}=0.15,p_{b}^{(0)}=0.25,p_{c}^{(0)}=0.6$ with different target
values. We let $y_{a}=0.3+\epsilon,y_{b}=0.5+\epsilon,y_{c}=0.7+\epsilon$
where $\epsilon\sim\mathcal{N}(0,0.05)$. At the beginning, the Group fraction
$p_{a}^{(0)}=0.3,p_{b}^{(0)}=0.7$, and the minimum group fraction for each
group is $p^{min}=\\{0.1,0.1\\}$. At each time $t$, denote
$\mathcal{R}(s,t)=\left(1-\sum_{s^{\prime}\in\\{a,b\\}}p^{min}_{s^{\prime}}\right)\times\frac{1}{2}\left(p_{s}^{t}+\frac{\mathcal{L}(\boldsymbol{\theta}^{(t)};\mathcal{D}_{i_{s}}^{(t)})}{\sum_{s^{\prime}}\mathcal{L}(\boldsymbol{\theta}^{(t)};\mathcal{D}_{s^{\prime}}^{(t)})}\right)+p_{s}^{min}$.
$-s$ is the group other than $s$, while $i_{s}$ is found by first ranking all
group-wise losses in ascending order and then selecting the $(n+1-i)-th$
largest loss if group $s$ has the $i-th$ largest loss. This retention dynamic
is a direct generalization of the two-group case. Next, we show the retention
of group $p^{(t+1)}_{s}$ at time $t+1$ is shown as Eqn. (13), resulting in the
new data distribution $D^{(t+1)}$.

$p^{(t+1)}_{s}:=\frac{\mathcal{R}(s,t)}{\sum_{s^{\prime}\in\\{a,b\\}}\mathcal{R}(s,t)}$
(13)

We perform the mean estimation task for the whole data distribution with both
RERM and Fair-RERM using the linear regression model. For Fair-RERM, we use
RERM, Fair-RERM-RW and Fair-RERM to perform $30$ rounds of risk minimization
where the loss is mean squared error (MSE), and name them as Fair-RERM-GLP
(group-level penalty), Fair-RERM-SLP (sample-level penalty) and Fair-RERM-RW
(reweighting). We first verify the convergence of performative loss of the
above methods in Fig. 7 where all Fair-RERM methods have $\rho=0.1$. The
results demonstrate all methods successfully converge to the PS point.

Next, we verify the effectiveness of Fair-RERM by visualizing the dynamics of
performative loss disparity between the groups while varying $\rho$ in Fig. 8,
where the higher $\rho$ still results in lower loss disparity at the stable
point, revealing that Fair-RERM-RW and Fair-RERM are effective.

Figure 7: Dynamics of the performative loss for Gaussian mean estimation task
with multiple groups when $\rho=0.3$: Fair-RERM-RW (left plot), Fair-RERM-GLP
(middle plot), Fair-RERM-SLP (right plot). Figure 8: Dynamics of the
performative loss disparity under different $\rho$: Fair-RERM-RW (left plot),
Fair-RERM-GLP (middle plot), Fair-RERM-SLP (right plot).

###  C.3 Performative Gaussian data classification.

We use a synthetic dataset consisting of $1000$ samples from 2 demographic
groups $s\in\\{a,b\\}$ with features $X=\\{X_{1},X_{2}\\}$ and labels
$Y\in\\{0,1\\}$. For group $a$, $Y=\mathbbm{1}\\{x_{1}-0.5x_{2}\geq 0.5\\}$.
For group $b$, $Y=\mathbbm{1}\\{0.5x_{1}+0.5x_{2}\geq 0.5\\}$. The initial
group fraction and the retention mapping are the same as in the previous
experiment. Using a logistic classification model for risk minimization, we
first verify the convergence of performative loss in Fig. 9 and the
effectiveness of Fair-RERM-RW and Fair-RERM in Fig.13(a) and Fig. 13(b). All
plots demonstrate the same trends as the previous experiment.

Figure 9: Dynamics of the performative loss for Gaussian data classification
task when $\rho=0.3$: Fair-RERM-RW (left plot), Fair-RERM-GLP (middle plot),
Fair-RERM-SLP (right plot). Figure 10: Dynamics of the performative loss for
k-delayed Credit task when $\rho=0.3$: Fair-RERM-RW (left plot), Fair-RERM-GLP
(middle plot), Fair-RERM-SLP (right plot).

###  C.4 Gaussian Mean Estimation Using Group Loss Variance

In Example 4.2, we already prove that group loss variance as a fair penalty
term violates the strong convexity assumption. In this section, we show its
unconvergence while performing the Gaussian mean estimation task under the
same setting mentioned in Section 6 when $\rho=0.5$. The dynamics of
$\|\theta_{t}-\theta_{t-1}\|$ as well as performative loss are shown as
follows. Fig. 11 shows the unconvergence, which is contradicted to Fig. 12(a)
where we show the convergence of Fair-RERM.

###  C.5 K-delayed RERM on Credit Data

We examine the effectiveness of k-delayed RERM schema on Credit Data [23]
which is the same dataset used by Brown et al. [5]. Specifically, we use $k=3$
and $\epsilon=1$ to form equal-sized agent groups uniformly in the whole
population to let each subgroup best respond with different speed (Example 1
in Brown et al. [5]). We also let the retention dynamic be k-delayed, adding
additional challenges compared to the previous work. We examine
$\rho\in\\{0.3,0.7\\}$ while all other settings are the same as the Credit
Data experiment in Section 6.

Then we first verify the convergence of performative loss in Fig. 9 and the
effectiveness of k-delayed Fair-RERM-RW and Fair-RERM in Fig.13(a) and Fig.
13(b). All plots demonstrate the same trends as the previous experiment with
RRM schema.

Figure 11: Gaussian mean estimation using group loss variance

(a) Dynamics of the performative loss for Gaussian mean estimation task when
$\rho=0.1$: Fair-RERM-RW (left plot), Fair-RERM-GLP (middle plot), Fair-RERM-
SLP (right plot).

(b) Dynamics of the performative loss for Credit data task when $\rho=0.1$:
Fair-RERM-RW (left plot), Fair-RERM-GLP (middle plot), Fair-RERM-SLP (right
plot).

(c) Dynamics of the performative loss for MNIST classification task when
$\rho=0.1$: Fair-RERM-RW (left plot), Fair-RERM-GLP (middle plot), Fair-RERM-
SLP (right plot).

(d) Dynamics of the performative loss for MNIST classification task when
$\rho=0.3$: Fair-RERM-RW (left plot), Fair-RERM-GLP (middle plot), Fair-RERM-
SLP (right plot).

Figure 12: Peformative loss dynamics under different $\rho$

(a) Dynamics of the loss disparity under different $\rho$: Fair-RERM-RW (left
plot), Fair-RERM-GLP (middle plot), Fair-RERM-SLP (right plot).

(b) Dynamics of the minority group fraction under different $\rho$: Fair-RERM-
RW (left plot), Fair-RERM-GLP (middle plot), Fair-RERM-SLP (right plot).

Figure 13: Fairness dynamics of Performative Gaussian Classification where
$\rho\in\\{0,0.3,0.7\\}$ ($\rho=0$ is equivalent to RERM)

##  Appendix D Proofs for the Theoretical Results

###  D.1 Proof of Proposition 5.1

We will first present lemmas for this proposition.

######  Lemma D.1.

(First order optimality condition of convex functions [41]).

If $f$ is convex and $\Omega$ is a closed convex set on which $f$ is
differentiable, then

$x^{*}\in\arg\min_{x\in\Omega}f(x),$ (14)

if and only if $(y-x^{*})^{\top}\nabla g(x^{*})\geq 0$ for all $y\in\Omega$.

######  Lemma D.2.

($\mathcal{L}_{\textsf{fair}}$ under fair penalty mechanisms is
$\gamma$-strongly convex)

Under the conditions in Lemma 2.4, the loss aware objective
$\mathcal{L}_{\textsf{fair}}$ in Eqn (7) and (8) are $\gamma$-strongly convex.

###### Proof.

We will show this for the sample level fair penalty Eqn (8) first.

From conditions in Lemma 2.4, we know that $\ell$ is $\gamma$-strongly convex,
and by definition $\ell\geq 0$, we will show that
$\ell^{2}(\boldsymbol{\theta};Z)$ is also convex in $\boldsymbol{\theta}$. For
simplicity of notation, we will derive for an arbitrary fixed $Z$ and omit $Z$
in the following derivation and use $\ell(\boldsymbol{\theta})$.

From the definition of convexity, we have
$\forall\alpha\in(0,1),\forall\boldsymbol{\theta}_{1},\boldsymbol{\theta}_{2}\in\Theta$,

$\ell((1-\alpha)\boldsymbol{\theta}_{1}+\alpha\boldsymbol{\theta}_{2})\leq(1-\alpha)\ell(\boldsymbol{\theta}_{1})+\alpha\ell(\boldsymbol{\theta}_{2}).$
(15)

Squaring both sides in the above gives us

$\displaystyle\ell^{2}((1-\alpha)\boldsymbol{\theta}_{1}+\alpha\boldsymbol{\theta}_{2})\leq$
$\displaystyle~{}(1-\alpha)^{2}\ell^{2}(\boldsymbol{\theta}_{1})+\alpha^{2}\ell^{2}(\boldsymbol{\theta}_{2})+2\alpha(1-\alpha)\ell(\boldsymbol{\theta}_{1})\ell(\boldsymbol{\theta}_{2})$
(16) $\displaystyle=$
$\displaystyle~{}(1-\alpha)^{2}\ell^{2}(\boldsymbol{\theta}_{1})+\alpha^{2}\ell^{2}(\boldsymbol{\theta}_{2})+2\alpha(1-\alpha)\ell(\boldsymbol{\theta}_{1})\ell(\boldsymbol{\theta}_{2})$
$\displaystyle~{}-(1-\alpha)\ell^{2}(\boldsymbol{\theta}_{1})-\alpha\ell^{2}(\boldsymbol{\theta}_{2})+(1-\alpha)\ell^{2}(\boldsymbol{\theta}_{1})+\alpha\ell^{2}(\boldsymbol{\theta}_{2})$
$\displaystyle=$
$\displaystyle~{}-\alpha(1-\alpha)[\ell(\boldsymbol{\theta}_{1})-\ell^{2}(\boldsymbol{\theta}_{1})]^{2}+(1-\alpha)\ell^{2}(\boldsymbol{\theta}_{1})+\alpha\ell^{2}(\boldsymbol{\theta}_{2})$
$\displaystyle\leq$
$\displaystyle~{}(1-\alpha)\ell^{2}(\boldsymbol{\theta}_{1})+\alpha\ell^{2}(\boldsymbol{\theta}_{2}),$

which shows the convexity of $\ell^{2}$.

Therefore, $\ell(\boldsymbol{\theta})+\rho\ell^{2}(\boldsymbol{\theta})$ is a
sum of a $\gamma$-strongly convex function and a convex function and thus is
$\gamma$-strongly convex. Then since $\mathcal{L}_{\textsf{fair}}$ is an
affine combination of $\gamma$-strongly convex functions, it is also
$\gamma$-strongly convex.

For Eqn (7), since $\mathcal{L}_{s}$ is $\gamma$-strongly convex for $\forall
s$, we can similarly show $\mathcal{L}_{\textsf{fair}}$ is $\gamma$-strongly
convex. ∎

######  Lemma D.3.

($\mathcal{L}_{\textsf{fair}}$ under fair penalty mechanisms is
$\tilde{\beta}$-jointly smooth)

Under conditions in Lemma 2.4, the loss aware objective
$\mathcal{L}_{\textsf{fair}}$ in Eqn (7) and (8) are $\tilde{\beta}$-jointly
smooth, where $\tilde{\beta}=(2\rho\overline{\ell}+1)\beta$.

###### Proof.

Denote $g:=\ell^{2}$, then we have
$\nabla_{\boldsymbol{\theta}}g=2\ell\cdot\nabla_{\boldsymbol{\theta}}\ell$,
and thus we have

$\displaystyle~{}\|\nabla_{\boldsymbol{\theta}}g(\boldsymbol{\theta};Z)-\nabla_{\boldsymbol{\theta}}g(\boldsymbol{\theta}^{\prime};Z)\|_{2}\leq
2\beta\max\\{\ell(\boldsymbol{\theta};Z),\ell(\boldsymbol{\theta}^{\prime};Z)\\}\|\boldsymbol{\theta}-\boldsymbol{\theta}^{\prime}\|_{2},$
(17)
$\displaystyle~{}\|\nabla_{\boldsymbol{\theta}}g(\boldsymbol{\theta};Z)-\nabla_{\boldsymbol{\theta}}g(\boldsymbol{\theta};Z^{\prime})\|_{2}\leq
2\beta\max\\{\ell(\boldsymbol{\theta};Z),\ell(\boldsymbol{\theta};Z^{\prime})\\}\|Z-Z^{\prime}\|_{2},$

which implies $(2\rho\overline{\ell}+1)\beta$-joint smoothness of
$\mathcal{L}_{\textsf{fair}}$ in Eqn (7) and (8). ∎

######  Lemma D.4.

For fair re-weighting mechanisms,

$\boldsymbol{\theta}^{(t+1)}=\arg\min_{\boldsymbol{\theta}}\mathcal{L}_{\textsf{fair}}=\arg\min_{\boldsymbol{\theta}}\sum_{s}p_{s}^{(t)}(1+\rho\mathcal{L}_{s}(\boldsymbol{\theta}^{(t)});\mathcal{D}^{(t-1)}_{s})\mathcal{L}_{s}(\boldsymbol{\theta});\mathcal{D}^{(t)}_{s},$
(18)

where
$\sum_{s}p_{s}^{(t)}(1+\rho\mathcal{L}_{s}(\boldsymbol{\theta}^{(t)};\mathcal{D}^{(t-1)}_{s})\mathcal{L}_{s}(\boldsymbol{\theta};\mathcal{D}^{(t)}_{s})$
is $\gamma$-strongly convex and $(1+\rho\overline{\ell})$-jointly smooth.

###### Proof.

At a high level,
$(1+\rho\mathcal{L}_{s}(\boldsymbol{\theta}^{(t)});\mathcal{D}^{(t-1)}_{s})$
acts like a scalar that may scale the strong convexity and joint smoothness
coefficient.

Since $\mathcal{L}_{s}(\boldsymbol{\theta}^{(t)});\mathcal{D}^{(t-1)}_{s})\geq
0$, we know the $\gamma$-strong convexity part holds.

Similarly, since
$\mathcal{L}_{s}(\boldsymbol{\theta}^{(t)});\mathcal{D}^{(t-1)}_{s})\leq\overline{\ell}$,
we know the $(1+\rho\overline{\ell})$-joint smoothness holds. ∎

This lemma shows that we can treat
$\mathcal{L}_{s}(\boldsymbol{\theta}^{(t)};\mathcal{D}^{(t-1)}_{s})\mathcal{L}_{s}(\boldsymbol{\theta};\mathcal{D}^{(t)}_{s})$
as the fair objective in fair er-weighting mechanisms, where this objective
has very similar properties as the fair objectives using the fair penalty
mechanism.

Based on the above lemmas, we present a result that bounds the fair-aware loss
minimization solution distance from two different input distributions, where
[4] and [5] derived similar bounds in the PP cases without fairness penalties.

######  Lemma D.5.

(Bounding the fair objective minimizers)

Given fair-aware loss function $\mathcal{L}_{\textsf{fair}}$ that is
$\gamma$-strongly convex and $\tilde{\beta}$-jointly smooth. Then for two
distributions $\mathcal{D},\tilde{\mathcal{D}}\in\triangle(\mathcal{Z})$,
denote

$\boldsymbol{\theta}_{\textsf{fair}}^{*}=G(\mathcal{D};\mathcal{L}_{\textsf{fair}}):=\arg\min_{\boldsymbol{\theta}}\mathcal{L}_{\textsf{fair}}(\boldsymbol{\theta};\mathcal{D}),~{}~{}~{}\tilde{\boldsymbol{\theta}}_{\textsf{fair}}^{*}=G(\tilde{\mathcal{D}};\mathcal{L}_{\textsf{fair}}):=\arg\min_{\boldsymbol{\theta}}\mathcal{L}_{\textsf{fair}}(\boldsymbol{\theta};\tilde{\mathcal{D}}),$
(19)

we have

$\|\boldsymbol{\theta}_{\textsf{fair}}^{*}-\tilde{\boldsymbol{\theta}}_{\textsf{fair}}^{*}\|_{2}\leq\frac{\tilde{\beta}}{\gamma}\mathcal{W}_{1}(\mathcal{D},\tilde{\mathcal{D}}).$
(20)

###### Proof.

Using the strong convexity property and the fact that
$G(\mathcal{D};\mathcal{L}_{\textsf{fair}})$ is the unique minimizer of
$\mathcal{L}_{\textsf{fair}}(\boldsymbol{\theta};\mathcal{D})$, we can derive
that

$-\gamma\|G(\mathcal{D};\mathcal{L}_{\textsf{fair}})-G(\tilde{\mathcal{D}};\mathcal{L}_{\textsf{fair}})\|_{2}^{2}\geq(G(\mathcal{D};\mathcal{L}_{\textsf{fair}})-G(\tilde{\mathcal{D}};\mathcal{L}_{\textsf{fair}}))^{\top}\nabla_{\boldsymbol{\theta}}\mathcal{L}_{\textsf{fair}}(\boldsymbol{\theta};\mathcal{D}).$
(21)

Then for Eqn (8), we observe that

$(G(\mathcal{D};\mathcal{L}_{\textsf{fair}})-G(\tilde{\mathcal{D}};\mathcal{L}_{\textsf{fair}}))^{\top}\nabla_{\boldsymbol{\theta}}\ell(\boldsymbol{\theta};Z)$
(22)

is
$\|G(\mathcal{D};\mathcal{L}_{\textsf{fair}})-G(\tilde{\mathcal{D}};\mathcal{L}_{\textsf{fair}})\|_{2}\beta$-Lipschitz
in $Z$, and

$(G(\mathcal{D};\mathcal{L}_{\textsf{fair}})-G(\tilde{\mathcal{D}};\mathcal{L}_{\textsf{fair}}))^{\top}\nabla_{\boldsymbol{\theta}}\ell^{2}(\boldsymbol{\theta};Z)$
(23)

is
$2\overline{\ell}\|G(\mathcal{D};\mathcal{L}_{\textsf{fair}})-G(\tilde{\mathcal{D}};\mathcal{L}_{\textsf{fair}})\|_{2}\beta$-Lipschitz
in $Z$, which follows from applying the Cauchy Schwartz inequality and the
fact that $\ell$ is $\beta$-jointly smooth.

Then we can derive that

$(G(\mathcal{D};\mathcal{L}_{\textsf{fair}})-G(\tilde{\mathcal{D}};\mathcal{L}_{\textsf{fair}}))^{\top}\nabla_{\boldsymbol{\theta}}\mathcal{L}_{\textsf{fair}}(\boldsymbol{\theta};\mathcal{D})\geq-(2\rho\overline{\ell}+1)\beta\mathcal{W}_{1}(\mathcal{D},\tilde{\mathcal{D}}),$
(24)

and thus

$-\gamma\|G(\mathcal{D};\mathcal{L}_{\textsf{fair}})-G(\tilde{\mathcal{D}};\mathcal{L}_{\textsf{fair}})\|_{2}^{2}\geq-(2\rho\overline{\ell}+1)\beta\mathcal{W}_{1}(\mathcal{D},\tilde{\mathcal{D}}),$
(25)

we get the proof for Eqn (8), and we can similarly prove this for Eqn (7) and
(9). ∎

######  Lemma D.6.

(Bounding the fixed point distribution distance using parameter distance [5])

Suppose the transition mapping $T$ is $\epsilon$-jointly sensitive with
$\epsilon\in(0,1)$, then for $\boldsymbol{\theta}_{1},\boldsymbol{\theta}_{2}$
and their corresponding fixed point distributions
$\mathcal{D}_{1},\mathcal{D}_{2}$, it holds that

$\mathcal{W}_{1}(\mathcal{D}_{1},\mathcal{D}_{2})\leq\frac{\epsilon}{1-\epsilon}\|\boldsymbol{\theta}_{1}-\boldsymbol{\theta}_{2}\|_{2}$
(26)

Proposition 5.1. (Unique Fair-PS solution) Under Conditions in Lemma 2.4, if
$\epsilon(1+\tilde{\beta}/\gamma)<1$, then for a given combination of (1)
initial distribution $\mathcal{D}^{(0)}$, and (2) fair mechanism with strength
$\rho$, there is a unique Fair-PS solution.

###### Proof.

We define the fixed point transition mapping as

$\text{T}^{\text{FP}}(\boldsymbol{\theta};\mathcal{D}):=\mathcal{D}_{\boldsymbol{\theta}}=\text{T}^{\text{FP}}(\boldsymbol{\theta})$
(27)

the mapping returning the model’s fixed point distribution.

Then using the results in Lemma D.2, D.3, D.5, D.4, D.6, we can see that

$\boldsymbol{\theta}^{(t+1)}=G(\text{T}^{\text{FP}}(\boldsymbol{\theta}^{(t)});\mathcal{L}_{\textsf{fair}})$
(28)

is a contraction mapping when conditions in Lemma 2.4 hold since
$\epsilon(1+\tilde{\beta}/\gamma)<1$. Therefore, using the Banach fixed-point
theorem, we know that there is a unique Fair-PS pair. ∎

###  D.2 Proof of Theorem 5.2

In this part, we provide the convergence of the class of Fair-RRM algorithms
in Algorithm 1.

######  Lemma D.7.

([5]) Under conditions in Lemma 2.4, given a decision model with parameter
$\boldsymbol{\theta}$, denote the parameter returned by Delayed Deployment
Scheme as
$\hat{\mathcal{D}}_{\theta}:=\text{T}^{DL}(\boldsymbol{\theta};\mathcal{D})$
and the fixed point distribution of $\boldsymbol{\theta}$ as
$\mathcal{D}_{\boldsymbol{\theta}}$, then

$\mathcal{W}_{1}(\hat{\mathcal{D}}_{\boldsymbol{\theta}},\mathcal{D}_{\boldsymbol{\theta}})\leq\frac{\epsilon}{1-\epsilon}\delta$
(29)

###### Proof.

111Due to different notations, we present the proof in [5] to help the
readers.

For a fixed $\boldsymbol{\theta}$ and $\epsilon<1$, the map
$\text{T}(\boldsymbol{\theta};\cdot)$ is contracting with Lipschitz
coefficient $\epsilon$ and has a unique fixed point
$\mathcal{D}_{\boldsymbol{\theta}}$. Note that
$\hat{\mathcal{D}}_{\boldsymbol{\theta}}=\text{T}^{\lceil r\rceil+1}$, denote
$\mathcal{D}^{1}=T(\boldsymbol{\theta};\mathcal{D}^{0})$, then

$\mathcal{W}_{1}(\hat{\mathcal{D}}_{\boldsymbol{\theta}},\mathcal{D}_{\boldsymbol{\theta}})\leq\frac{\epsilon^{\lceil
r\rceil}}{1-\epsilon}\mathcal{W}_{1}(\mathcal{D}^{0},\mathcal{D}^{1}),$ (30)

then since
$r=\log^{-1}\left(\frac{1}{\epsilon}\right)\log\left(\frac{\mathcal{W}_{1}(\mathcal{D}^{0},\mathcal{D}^{1})}{\delta}\right)$,
we have $\epsilon^{\lceil
r\rceil}<\epsilon^{r}=\frac{\delta}{\mathcal{W}_{1}(\mathcal{D}^{0},\mathcal{D}^{1})}$,
which completes the proof. ∎

Theorem 5.2. (Fair-RRM Convergence) Under conditions in Lemma 2.4:

(i) If $\epsilon(1+\tilde{\beta}/\gamma)<1$, Algorithm 1 under the
Conventional Schema converges to the Fair-PS pair at a linear rate.

(ii) If $\epsilon(1+\tilde{\beta}/\gamma)<1-\epsilon$, Algorithm 1 under the
$k$-Delayed Schema converges to the Fair-PS pair at a linear rate for any $k$.

(iii) If $\epsilon(1+\tilde{\beta}/\gamma)<1$, Algorithm 1 under the
Conventional Schema converges to a $\delta$ neighborhood of the Fair-PS pair
in $O(\log^{2}\frac{1}{\delta})$ steps.

###### proof of (i).

We will define a distance metric

$d_{\text{pair}}((\boldsymbol{\theta}_{1},\mathcal{D}_{1}),(\boldsymbol{\theta}_{2},\mathcal{D}_{2})):=\mathcal{W}_{1}(\mathcal{D}_{1},\mathcal{D}_{2})+\|\boldsymbol{\theta}_{1}-\boldsymbol{\theta}_{2}\|_{2}.$
(31)

Denote the Fair-RRM mapping as

$F_{\textsf{fair}}(\boldsymbol{\theta},\mathcal{D}):=(G_{\textsf{fair}}(\boldsymbol{\theta},\mathcal{D}),\text{T}(\boldsymbol{\theta};\mathcal{D}))$
(32)

where
$G_{\textsf{fair}}(\boldsymbol{\theta},\mathcal{D}):=G(\text{T}(\boldsymbol{\theta};\mathcal{D});\mathcal{L}_{\textsf{fair}})$.
Then

$d_{\text{pair}}(F_{\textsf{fair}}(\boldsymbol{\theta},\mathcal{D}),F_{\textsf{fair}}(\boldsymbol{\theta}^{\prime},\mathcal{D}^{\prime}))=\mathcal{W}_{1}(\text{T}(\boldsymbol{\theta};\mathcal{D}),\text{T}(\boldsymbol{\theta}^{\prime};\mathcal{D}^{\prime}))+\|G_{\textsf{fair}}(\boldsymbol{\theta},\mathcal{D})-G_{\textsf{fair}}(\boldsymbol{\theta}^{\prime},\mathcal{D}^{\prime})\|_{2}.$
(33)

The $\epsilon$-jointly sensitivity of the transition map T yields

$\mathcal{W}_{1}(\text{T}(\boldsymbol{\theta};\mathcal{D}),\text{T}(\boldsymbol{\theta}^{\prime};\mathcal{D}^{\prime}))\leq\epsilon\mathcal{W}_{1}(\mathcal{D},\mathcal{D}^{\prime})+\epsilon\|\boldsymbol{\theta}-\boldsymbol{\theta}^{\prime}\|_{2},$
(34)

and using Lemma D.5, we get

$\|G_{\textsf{fair}}(\boldsymbol{\theta},\mathcal{D})-G_{\textsf{fair}}(\boldsymbol{\theta}^{\prime},\mathcal{D}^{\prime})\|_{2}\leq\frac{\tilde{\beta}}{\gamma}\mathcal{W}_{1}(\text{T}(\boldsymbol{\theta};\mathcal{D}),\text{T}(\boldsymbol{\theta}^{\prime};\mathcal{D}^{\prime}))\leq\epsilon\frac{\tilde{\beta}}{\gamma}\mathcal{W}_{1}(\mathcal{D},\mathcal{D}^{\prime})+\epsilon\frac{\tilde{\beta}}{\gamma}\|\boldsymbol{\theta}-\boldsymbol{\theta}^{\prime}\|_{2}.$
(35)

Combining the above two equations, we get that under conditions in Lemma 2.4,
the Fair-RRM mapping is a contraction mapping that has a unique fixed point,
where the fixed point satisfies the criteria of being the PS solution.

The proof of this part referenced [5] Theorem 4. ∎

###### proof of (ii).

We can derive the sensitivity of $T^{k}(\mathcal{D},\boldsymbol{\theta})$ as
follows

$\displaystyle\mathcal{W}_{1}(T^{k}(\mathcal{D},\boldsymbol{\theta}),T^{k}(\mathcal{D}^{\prime},\boldsymbol{\theta}^{\prime}))$
(36) $\displaystyle\leq$
$\displaystyle\epsilon\mathcal{W}_{1}(T^{k-1}(\mathcal{D},\boldsymbol{\theta}),T^{k-1}(\mathcal{D}^{\prime},\boldsymbol{\theta}^{\prime}))+\epsilon\|\boldsymbol{\theta}-\boldsymbol{\theta}^{\prime}\|_{2}$
$\displaystyle\leq$
$\displaystyle\epsilon^{2}\mathcal{W}_{1}(T^{k-2}(\mathcal{D},\boldsymbol{\theta}),T^{k-2}(\mathcal{D}^{\prime},\boldsymbol{\theta}^{\prime}))+(\epsilon+\epsilon^{2})\|\boldsymbol{\theta}-\boldsymbol{\theta}^{\prime}\|_{2}$
$\displaystyle\leq$ $\displaystyle\dots$ $\displaystyle<$
$\displaystyle\epsilon^{k}\mathcal{W}_{1}(\mathcal{D},\mathcal{D}^{\prime})+\frac{\epsilon}{1-\epsilon}\|\boldsymbol{\theta}-\boldsymbol{\theta}^{\prime}\|_{2}$
$\displaystyle<$
$\displaystyle\frac{\epsilon}{1-\epsilon}\mathcal{W}_{1}(\mathcal{D},\mathcal{D}^{\prime})+\frac{\epsilon}{1-\epsilon}\|\boldsymbol{\theta}-\boldsymbol{\theta}^{\prime}\|_{2}$

So $T^{k}(\mathcal{D},\boldsymbol{\theta})$ is
$(\frac{\epsilon}{1-\epsilon})$-jointly sensitive.

Using the proof of contraction mapping in part (i), we complete the proof of
part (ii). ∎

###### proof of (iii).

Similar to the above, we denote the parameter returned by the Delayed
Deployment Scheme as
$\hat{\mathcal{D}}_{\boldsymbol{\theta}}=\text{T}^{DL}(\boldsymbol{\theta};\cdot)$.
We have
$\boldsymbol{\theta}^{(t+1)}=G(\hat{\mathcal{D}}_{\boldsymbol{\theta}^{(t)}};\mathcal{L}_{\textsf{fair}})$.

Recall that
$\boldsymbol{\theta}^{\text{PS}}_{\textsf{fair}}=G(\mathcal{D}^{\text{PS}}_{\textsf{fair}};\mathcal{L}_{\textsf{fair}})$.
Then Lemma D.5 indicates that

$\|\boldsymbol{\theta}^{(t+1)}-\boldsymbol{\theta}^{\text{PS}}_{\textsf{fair}}\|_{2}=\|G(\hat{\mathcal{D}}_{\boldsymbol{\theta}^{(t)}};\mathcal{L}_{\textsf{fair}})-G(\mathcal{D}^{\text{PS}}_{\textsf{fair}};\mathcal{L}_{\textsf{fair}})\|_{2}\leq\frac{\tilde{\beta}}{\gamma}\cdot\mathcal{W}_{1}(\hat{\mathcal{D}}_{\boldsymbol{\theta}^{(t)}},\mathcal{D}^{\text{PS}}_{\textsf{fair}}).$
(37)

Using the triangle inequality, we have

$\mathcal{W}_{1}(\hat{\mathcal{D}}_{\boldsymbol{\theta}},\mathcal{D}^{\text{PS}}_{\textsf{fair}})\leq\mathcal{W}_{1}(\hat{\mathcal{D}}_{\boldsymbol{\theta}},\mathcal{D}_{\boldsymbol{\theta}^{(t)}})+\mathcal{W}_{1}(\mathcal{D}_{\boldsymbol{\theta}^{(t)}},\mathcal{D}^{\text{PS}}_{\textsf{fair}}),$
(38)

where $\mathcal{D}_{\boldsymbol{\theta}^{(t)}}$ is the fixed point
distribution of $\boldsymbol{\theta}^{(t)}$.

We can use Lemma D.7 to get
$\mathcal{W}_{1}(\hat{\mathcal{D}}_{\boldsymbol{\theta}},\mathcal{D}_{\boldsymbol{\theta}^{(t)}})\leq\frac{\epsilon\delta}{1-\epsilon}$
and use Lemma D.6 and the sensitivity definition to get
$\mathcal{W}_{1}(\mathcal{D}_{\boldsymbol{\theta}^{(t)}},\mathcal{D}^{\text{PS}}_{\textsf{fair}})\leq\frac{\epsilon}{1-\epsilon}\|\boldsymbol{\theta}^{(t)}-\boldsymbol{\theta}^{\text{PS}}_{\textsf{fair}}\|_{2}$.

Therefore,

$\mathcal{W}_{1}(\hat{\mathcal{D}}_{\boldsymbol{\theta}},\mathcal{D}^{\text{PS}}_{\textsf{fair}})\leq\frac{\epsilon}{1-\epsilon}(\delta+\|\boldsymbol{\theta}^{(t)}-\boldsymbol{\theta}^{\text{PS}}_{\textsf{fair}}\|_{2}).$
(39)

When
$\|\boldsymbol{\theta}^{(t)}-\boldsymbol{\theta}^{\text{PS}}_{\textsf{fair}}\|_{2}>\delta$,
we have

$\|\boldsymbol{\theta}^{(t+1)}-\boldsymbol{\theta}^{\text{PS}}_{\textsf{fair}}\|_{2}<\frac{2\epsilon}{1-\epsilon}\frac{\tilde{\beta}}{\gamma}\|\boldsymbol{\theta}^{(t)}-\boldsymbol{\theta}^{\text{PS}}_{\textsf{fair}}\|_{2}\leq\|\boldsymbol{\theta}^{(t)}-\boldsymbol{\theta}^{\text{PS}}_{\textsf{fair}}\|_{2}.$
(40)

On the other hand, when
$\|\boldsymbol{\theta}^{(t)}-\boldsymbol{\theta}^{\text{PS}}_{\textsf{fair}}\|_{2}\leq\delta$,
we have

$\|\boldsymbol{\theta}^{(t+1)}-\boldsymbol{\theta}^{\text{PS}}_{\textsf{fair}}\|_{2}\leq\frac{2\epsilon}{1-\epsilon}\frac{\tilde{\beta}}{\gamma}\delta\leq\delta$
(41)

Combining the two cases together, we know that for
$t\geq\left(1-\frac{2\epsilon\tilde{\beta}}{\gamma(1-\epsilon)}\right)^{-1}\log\left(\frac{\boldsymbol{\theta}^{(0)}-\boldsymbol{\theta}^{\text{PS}}_{\textsf{fair}}}{\delta}\right)$,
we have

$\|\boldsymbol{\theta}^{(t)}-\boldsymbol{\theta}^{\text{PS}}_{\textsf{fair}}\|_{2}\leq\left(\frac{2\epsilon}{1-\epsilon}\frac{\tilde{\beta}}{\gamma}\right)^{t}\delta\leq\delta,$
(42)

which completes the proof for part (iii).

The proof of this part referenced [5] Theorem 8. ∎

###  D.3 Proof of Theorem B.3

In this part, we provide the convergence of the class of fair-RERM algorithms
in Algorithm 2.

Theorem B.3 (Fair RERM Convergence) Under conditions in Lemma 2.4, suppose
$\exists\alpha>1,\mu>0$ such that
$\int_{\mathbb{R}^{m}}e^{\mu|x|^{\alpha}}Zdx$ is finite $\forall
Z\in\triangle(\mathcal{Z})$.

For given a convergence radius $\delta\in(0,1)$, take
$n_{t}=O\left(\frac{\log(t/p)}{(\epsilon(1+\tilde{\beta}/\gamma)\delta)^{m}}\right)$
samples at $t$. If $2\epsilon(1+\tilde{\beta}/\gamma)<1$, then with
probability $1-p$, the iterates of fair-RERM are within a radius $\delta$ of
the Fair-PS pair for
$t\geq(1-2\epsilon(1+\tilde{\beta}/\gamma)O(\log(1/\delta))$.

###### Proof.

Given $n$ samples from $\mathcal{D}$, denote $\hat{\mathcal{D}}^{n}$ the
empirical distribution obtained from them. Denote

$\hat{G}^{n}_{\textsf{fair}}(\boldsymbol{\theta},\mathcal{D}):=G(\text{T}(\boldsymbol{\theta};\hat{\mathcal{D}}^{n}),$
(43)

(recall
$G_{\textsf{fair}}(\boldsymbol{\theta},\mathcal{D}):=G(\text{T}(\boldsymbol{\theta};\mathcal{D});\mathcal{L}_{\textsf{fair}})$
in Eqn (32)). And also denote the Fair-RERM mapping as

$\hat{F}_{\textsf{fair}}(\boldsymbol{\theta},\mathcal{D}):=(\hat{G}^{n}_{\textsf{fair}}(\boldsymbol{\theta},\mathcal{D}),\text{T}(\boldsymbol{\theta};\mathcal{D}))$
(44)

By Theorem 2 of [42], since $\exists\alpha>1,\mu>0$ such that
$\int_{\mathbb{R}^{m}}e^{\mu|x|^{\alpha}}Zdx$ is finite $\forall
Z\in\triangle(\mathcal{Z})$, then if
$n_{t}=\mathcal{O}\left(\frac{1}{\epsilon(1+\tilde{\beta}/\gamma)^{m}}\log(t/p)\right)$,
where $m$ is the dimension of the sample, we have
$\mathcal{W}_{1}(\mathcal{D},\hat{\mathcal{D}}^{n})\geq\epsilon(1+\tilde{\beta}/\gamma)\delta$
with probability at most $\frac{6p}{\pi^{2}t^{2}}$.

Therefore,

$\mathbb{P}\big{(}\mathcal{W}_{1}(\mathcal{D},\hat{\mathcal{D}}^{n})\leq\epsilon(1+\tilde{\beta}/\gamma)\delta\big{)},\forall
t)=1-\sum_{t=1}^{\infty}\mathbb{P}\big{(}\mathcal{W}_{1}(\mathcal{D},\hat{\mathcal{D}}^{n_{t}})>\epsilon(1+\tilde{\beta}/\gamma)\delta\big{)}\geq
1-\sum_{t=1}^{\infty}\frac{6p}{\pi^{2}t^{2}}=1-p$ (45)

i.e., with probability at least $1-\sum_{t=1}^{\infty}1-p$ we have that for
each time step $t$, it holds that

$\mathcal{W}_{1}(\mathcal{D},\hat{\mathcal{D}}^{n})\leq\epsilon(1+\tilde{\beta}/\gamma)\delta.$
(46)

Then if
$d_{\text{pair}}\big{(}(\boldsymbol{\theta},\mathcal{D}),(\boldsymbol{\theta}^{\text{PS}}_{\textsf{fair}},\mathcal{D}^{\text{PS}}_{\textsf{fair}})\big{)}\geq\delta$,
and Eqn (46) holds, we have

$\displaystyle~{}d_{\text{pair}}(\hat{F}_{\textsf{fair}}(\boldsymbol{\theta},\mathcal{D}),(\boldsymbol{\theta}^{\text{PS}}_{\textsf{fair}},\mathcal{D}^{\text{PS}}_{\textsf{fair}}))$
$\displaystyle=$
$\displaystyle~{}\mathcal{W}_{1}(\text{T}(\boldsymbol{\theta};\mathcal{D}),\mathcal{D}^{\text{PS}}_{\textsf{fair}})+\|\hat{G}^{n}_{\textsf{fair}}(\boldsymbol{\theta},\mathcal{D})-\boldsymbol{\theta}^{\text{PS}}_{\textsf{fair}}\|_{2}$
$\displaystyle\leq$
$\displaystyle~{}\mathcal{W}_{1}(\text{T}(\boldsymbol{\theta};\mathcal{D}),\text{T}(\boldsymbol{\theta}^{\text{PS}}_{\textsf{fair}};\mathcal{D}^{\text{PS}}_{\textsf{fair}}))+\|\hat{G}^{n}_{\textsf{fair}}(\boldsymbol{\theta},\mathcal{D})-G_{\textsf{fair}}(\boldsymbol{\theta},\mathcal{D})\|_{2}+\|G_{\textsf{fair}}(\boldsymbol{\theta},\mathcal{D})-G_{\textsf{fair}}(\boldsymbol{\theta}^{\text{PS}}_{\textsf{fair}};\mathcal{D}^{\text{PS}}_{\textsf{fair}})\|_{2}$
$\displaystyle\leq$
$\displaystyle~{}\epsilon\mathcal{W}_{1}(\mathcal{D},\mathcal{D}^{\text{PS}}_{\textsf{fair}})+\epsilon\|\boldsymbol{\theta}-\boldsymbol{\theta}^{\text{PS}}_{\textsf{fair}}\|_{2}+\frac{\tilde{\beta}}{\gamma}\mathcal{W}_{1}(\hat{\text{T}}^{n}(\boldsymbol{\theta};\mathcal{D}),\text{T}(\boldsymbol{\theta};\mathcal{D}))+\frac{\tilde{\beta}}{\gamma}(\text{T}(\boldsymbol{\theta};\mathcal{D})),\text{T}(\boldsymbol{\theta}^{\text{PS}}_{\textsf{fair}};\mathcal{D}^{\text{PS}}_{\textsf{fair}})))$
$\displaystyle\leq$
$\displaystyle~{}\epsilon\mathcal{W}_{1}(\mathcal{D},\mathcal{D}^{\text{PS}}_{\textsf{fair}})+\epsilon\|\boldsymbol{\theta}-\boldsymbol{\theta}^{\text{PS}}_{\textsf{fair}}\|_{2}+\frac{\tilde{\beta}}{\gamma}\epsilon\bigg{(}1+\frac{\tilde{\beta}}{\gamma}\bigg{)}\delta+\frac{\tilde{\beta}}{\gamma}\big{(}\epsilon\mathcal{W}_{1}(\mathcal{D},\mathcal{D}^{\text{PS}}_{\textsf{fair}})+\epsilon\|\boldsymbol{\theta}-\boldsymbol{\theta}^{\text{PS}}_{\textsf{fair}}\|_{2}\big{)}$
$\displaystyle=$
$\displaystyle~{}\bigg{(}1+\frac{\tilde{\beta}}{\gamma}\bigg{)}d_{\text{pair}}\big{(}(\boldsymbol{\theta},\mathcal{D}),(\boldsymbol{\theta}^{\text{PS}}_{\textsf{fair}},\mathcal{D}^{\text{PS}}_{\textsf{fair}})\big{)}+\epsilon\bigg{(}1+\frac{\tilde{\beta}}{\gamma}\delta\bigg{)}$
$\displaystyle\leq$
$\displaystyle~{}2\epsilon\bigg{(}1+\frac{\tilde{\beta}}{\gamma}\bigg{)}d_{\text{pair}}\big{(}(\boldsymbol{\theta},\mathcal{D}),(\boldsymbol{\theta}^{\text{PS}}_{\textsf{fair}},\mathcal{D}^{\text{PS}}_{\textsf{fair}})\big{)}$
(47)

where the third line uses triangle inequality, fourth line uses Lemma D.5, and
fifth line uses Eqn (46). In other words, the above shows that if the current
pair is more than $\delta$ away from the Fair PS solution, then as long as Eqn
(46) is true, the Fair RERM mapping is a contraction.

Similarly, if
$d_{\text{pair}}\big{(}(\boldsymbol{\theta},\mathcal{D},(\boldsymbol{\theta}^{\text{PS}}_{\textsf{fair}},\mathcal{D}^{\text{PS}}_{\textsf{fair}})\big{)}<\delta$,
and Eqn (46) holds, we can show that

$\displaystyle
d_{\text{pair}}(\hat{F}_{\textsf{fair}}(\boldsymbol{\theta},\mathcal{D}),(\boldsymbol{\theta}^{\text{PS}}_{\textsf{fair}},\mathcal{D}^{\text{PS}}_{\textsf{fair}}))\leq\bigg{(}1+\frac{\tilde{\beta}}{\gamma}\bigg{)}d_{\text{pair}}\big{(}(\boldsymbol{\theta},\mathcal{D}),(\boldsymbol{\theta}^{\text{PS}}_{\textsf{fair}},\mathcal{D}^{\text{PS}}_{\textsf{fair}})\big{)}+\epsilon\bigg{(}1+\frac{\tilde{\beta}}{\gamma}\delta\bigg{)}\leq
2\epsilon\bigg{(}1+\frac{\tilde{\beta}}{\gamma}\bigg{)}\delta<\delta,$ (48)

which means the pair will stay in the $\delta$ radius ball once an iterate
goes in the ball.

Then we move on to show when
$t\geq\bigg{(}1-2\epsilon\bigg{(}1+\frac{\tilde{\beta}}{\gamma}\bigg{)}\log\bigg{(}\frac{d_{\text{pair}}\big{(}(\boldsymbol{\theta}^{(1)},\mathcal{D}^{(0)}),(\boldsymbol{\theta}^{\text{PS}}_{\textsf{fair}},\mathcal{D}^{\text{PS}}_{\textsf{fair}})\big{)}}{\delta}\bigg{)}$
the fair RERM mapping hits the $\delta$ radius ball centered at the Fair PS
solution. Again, if Eqn (46) holds, then denote the initial pair as
$(\boldsymbol{\theta}^{(1)},\mathcal{D}^{(0)})$, then we can use similar
arguments as above to show that

$\displaystyle
d_{\text{pair}}((\boldsymbol{\theta}^{(t+1)},\mathcal{D}^{(t)}),(\boldsymbol{\theta}^{\text{PS}}_{\textsf{fair}},\mathcal{D}^{\text{PS}}_{\textsf{fair}}))\leq$
$\displaystyle~{}2\epsilon\bigg{(}1+\frac{\tilde{\beta}}{\gamma}\bigg{)}^{t}d_{\text{pair}}\big{(}(\boldsymbol{\theta}^{(1)},\mathcal{D}^{(0)}),(\boldsymbol{\theta}^{\text{PS}}_{\textsf{fair}},\mathcal{D}^{\text{PS}}_{\textsf{fair}})\big{)}$
$\displaystyle\leq$
$\displaystyle~{}exp\bigg{(}-t\bigg{(}1-2\epsilon\bigg{(}1+\frac{\tilde{\beta}}{\gamma}\bigg{)}\bigg{)}d_{\text{pair}}\big{(}(\boldsymbol{\theta}^{(1)},\mathcal{D}^{(0)}),(\boldsymbol{\theta}^{\text{PS}}_{\textsf{fair}},\mathcal{D}^{\text{PS}}_{\textsf{fair}})\big{)}$
$\displaystyle\leq$ $\displaystyle~{}\delta.$ (49)

This completes the proof.

For the $k$-Delayed RERM, we can follow the proof of part (ii) in Theorem 5.2
that the transition $\text{T}^{k}$ is
$\tilde{\epsilon}:=\frac{\epsilon}{1-\epsilon}$ jointly sensitive, and if we
replace the $\epsilon$ terms with $\tilde{\epsilon}$ and times a $k$ scalar in
the number of iterations, we can get the similar result.

The proof of this part referenced Theorem 5 in [5] ∎

###  D.4 Proof of the Fairness Guarantee

Discussion of the intricate nature of proving the effectiveness of $\rho$
under the general PP setting. We first note that it is non-trivial to find out
whether fairness at PS solution increases as $\rho$ increases under the
general setting where both the group fractions and the group-wise feature-
label distributions change. Consider an example where the agents in the
minority group are influenced by the majority group, i.e., when their group
fraction becomes less than a threshold, their tastes are shaped by the
mainstream culture. Then they can change their feature-label distributions to
be more similar to the one of the majority group. This will possibly make the
loss disparity smaller even when $\rho$ becomes larger. However, in majority
of previous work on the retention of recommendation system [2, 12], the group-
wise distributions are assumed to be static.

Proof of Theorem 5.4. With Assumption 5.3, we state Lemma D.8.

######  Lemma D.8 (fairness guarantee at a single step).

At each single step, the following results hold:

(i) Given $\mathcal{D}^{(t)}$ fixed (i.e., $p_{a}^{(t)},p_{b}^{(t)}$ stay
fixed), increasing $\rho$ in Eqn. (7) leads to lower or equal
$\triangle^{t}_{\textsf{fair},\mathcal{L}}(\rho)$ ;

(ii) Given the optimization objective fixed (i.e., $\rho$ stays fixed), lower
fraction disparity $\triangle_{p}^{(t)}$ leads to lower or equal
$\triangle^{t}_{\textsf{fair},\mathcal{L}}(\rho)$ when the minority group
incurs higher loss.

###### Proof of (i).

We prove (i) by contradiction.

Assume $\rho_{1}<\rho_{2}$, and denote the the optimized model parameters as
$\theta_{\rho_{1}},\theta_{\rho_{2}}$. Since $\mathcal{D}_{s}$ does not change
over time, we can know the group-wise loss under $\rho_{1},\rho_{2}$ at both
rounds $L_{s,\rho_{1}}^{t}=L_{s,\rho_{1}}^{t-1}=L_{s,\rho_{1}}$
$L_{s,\rho_{2}}^{t}=L_{s,\rho_{2}}^{t-1}=L_{s,\rho_{2}}$. Thus, we can
interchange the superscript arbitrarily (i.e., if the deployed models are the
same, $L_{s}^{t}=L_{s}^{t-1}$). Wlog, assume
$L_{a,\rho_{1}}^{t}>L_{b,\rho_{1}}^{t}$. Then consider all possible scenarios
where the loss disparity may be larger:

  * •

$L_{a,\rho_{1}}^{t}<L_{a,\rho_{2}}^{t}$ and
$L_{b,\rho_{1}}^{t}<L_{b,\rho_{2}}^{t}$: if this holds, then we can just shift
$\theta_{\rho_{2}}$ to $\theta_{\rho_{1}}$ to guarantee smaller
$L_{a,\rho_{2}}^{t},L_{b,\rho_{2}}^{t}$ and therefore smaller
$L_{a,\rho_{2}}^{t-1},L_{b,\rho_{2}}^{t-1}$, resulting in a smaller loss
specified by Eqn. (7). This produces a contradiction since $\theta_{\rho_{2}}$
is the minimizer;

  * •

$L_{a,\rho_{1}}^{t}>L_{a,\rho_{2}}^{t}$ and
$L_{b,\rho_{1}}^{t}>L_{b,\rho_{2}}^{t}$: In the same way, we can shift
$\theta_{\rho_{1}}$ to $\theta_{\rho_{2}}$ to trivially decrease both
$L_{a,\rho_{1}}^{t},L_{b,\rho_{1}}^{t}$, violating the condition that
$\theta_{\rho_{1}}$ is the minimizer;

  * •

$L_{a,\rho_{1}}^{t}<L_{a,\rho_{2}}^{t}$ and
$L_{b,\rho_{1}}^{t}>L_{b,\rho_{2}}^{t}$. According to the optimality at
$\rho_{1},\rho_{2}$, we have:

$p_{a}\cdot\left(L_{a,\rho_{2}}^{t}-L_{a,\rho_{1}}^{t}\right)+p_{b}\cdot\left(L_{b,\rho_{2}}^{t}-L_{b,\rho_{1}}^{t}\right)+p_{a}\cdot\rho_{2}\cdot\left((L_{a,\rho_{2}}^{t})^{2}-(L_{a,\rho_{1}}^{t})^{2}\right)+p_{b}\cdot\rho_{2}\cdot\left((L_{b,\rho_{2}}^{t})^{2}-(L_{b,\rho_{1}}^{t})^{2}\right)<0$
(50)
$p_{a}\cdot\left(L_{a,\rho_{2}}^{t}-L_{a,\rho_{1}}^{t}\right)+p_{b}\cdot\left(L_{b,\rho_{2}}^{t}-L_{b,\rho_{1}}^{t}\right)+p_{a}\cdot\rho_{1}\cdot\left((L_{a,\rho_{2}}^{t})^{2}-(L_{a,\rho_{1}}^{t})^{2}\right)+p_{b}\cdot\rho_{1}\cdot\left((L_{b,\rho_{2}}^{t})^{2}-(L_{b,\rho_{1}}^{t})^{2}\right)>0$
(51)

Subtract Eqn. (50) from Eqn. (51), we get

$\displaystyle
p_{a}\cdot\left((L_{a,\rho_{2}}^{t})^{2}-(L_{a,\rho_{1}}^{t})^{2}\right)+p_{b}\cdot\left((L_{b,\rho_{2}}^{t})^{2}-(L_{b,\rho_{1}}^{t})^{2}\right)<0$
(52) $\displaystyle\Leftrightarrow~{}$ $\displaystyle
p_{a}\cdot\left(L_{a,\rho_{2}}^{t}+L_{a,\rho_{1}}^{t}\right)\cdot\left(L_{a,\rho_{2}}^{t}-L_{a,\rho_{1}}^{t}\right)+p_{b}\cdot\left(L_{b,\rho_{2}}^{t}+L_{b,\rho_{1}}^{t}\right)\cdot\left(L_{b,\rho_{2}}^{t}-L_{b,\rho_{1}}^{t}\right)<0$

From Eqn. (52) and Eqn. (51), we can immediately get:

$p_{a}\cdot\left(L_{a,\rho_{2}}^{t}-L_{a,\rho_{1}}^{t}\right)+p_{b}\cdot\left(L_{b,\rho_{2}}^{t}-L_{b,\rho_{1}}^{t}\right)>0$
(53)

Otherwise Eqn. (51) would be smaller than $0$. We have by assumption
$L_{a,\rho_{2}}^{t}>L_{a,\rho_{1}}^{t}>L_{b,\rho_{1}}^{t}>L_{b,\rho_{2}}^{t}$.
Then
$L_{a,\rho_{1}}^{t}+L_{a,\rho_{2}}^{t}>L_{b,\rho_{1}}^{t}+L_{b,\rho_{2}}^{t}$.
Next, noticing that $L_{b,\rho_{2}}^{t}-L_{b,\rho_{1}}^{t}<0$ and
$L_{a,\rho_{2}}^{t}-L_{a,\rho_{1}}^{t}>0$, then if we divide
$L_{a,\rho_{1}}^{t}+L_{a,\rho_{2}}^{t}$ at both sides of Eqn. (52), then we
will get:

$p_{a}\cdot\left(L_{a,\rho_{2}}^{t}-L_{a,\rho_{1}}^{t}\right)+p_{b}\cdot\frac{\left(L_{b,\rho_{2}}^{t}+L_{b,\rho_{1}}^{t}\right)}{\left(L_{a,\rho_{2}}^{t}+L_{a,\rho_{1}}^{t}\right)}\cdot\left(L_{b,\rho_{2}}^{t}-L_{b,\rho_{1}}^{t}\right)<0$
(54)

However, the LHS of Eqn. (54) is larger than the LHS of Eqn. (53), while the
LHS requires the opposite, producing a contradiction. Finally, note that it is
impossible to let loss of one group stays fixed while the other one changes
where we can easily prove with similar contradictions.

Since all the above scenarios do not hold, we have proved (i). Moreover, if
for any $\rho_{2}>\rho_{1}$, the loss disparities are equal, it means that
both groups achieve minimal loss with a same $\theta^{*}$, which is very
uncommon considering the difference of demographic groups. Thus, increasing
$\rho$ commonly leads to lower loss disparity $\Delta_{\mathcal{L}}^{(t)}$. ∎

###### proof of (ii).

Next, we prove (ii) similarly. Denote the optimized group-wise loss under the
two group fractions as $L_{s}^{(t)}$ and $L_{s^{\prime}}^{(t)}$. Wlog, assume
$L_{a}^{(t)}>L_{b}^{(t)}$. We will have the following equations:

$p_{a^{\prime}}^{(t)}\cdot\left(L_{a^{\prime}}^{(t)}-L_{a}^{(t)}\right)+p_{b^{\prime}}^{(t)}\cdot\left(L_{b^{\prime}}^{(t)}-L_{b}^{(t)}\right)<0$
(55)

$p_{a}^{(t)}\cdot\left(L_{a^{\prime}}^{(t)}-L_{a}^{(t)}\right)+p_{b}^{(t)}\cdot\left(L_{b^{\prime}}^{(t)}-L_{b}^{(t)}\right)>0$
(56)

To prove by contradiction, we need to consider the situations where the group
fraction discrepancy becomes smaller. This can be either
$p_{a}^{(t)}<p_{b}^{(t)},p_{a^{\prime}}^{(t)}>p_{a}^{(t)}$ or
$p_{a}^{(t)}>p_{b}^{(t)},p_{a^{\prime}}^{(t)}<p_{a}^{(t)}$. Then consider all
possible scenarios where the loss disparity may be larger:

  * •

$L_{a}^{(t)}<L_{a^{\prime}}^{(t)}$ and $L_{b}^{(t)}<L_{b^{\prime}}^{(t)}$:
Eqn. (55) does not hold;

  * •

$L_{a}^{(t)}>L_{a^{\prime}}^{(t)}$ and $L_{b}^{(t)}>L_{b^{\prime}}^{(t)}$:
Eqn. (56) does not hold;

  * •

$L_{a}^{(t)}<L_{a^{\prime}}^{(t)}$ and $L_{b}^{(t)}>L_{b^{\prime}}^{(t)}$:
Subtract Eqn. (55) from Eqn. (56), we can get:

$\left(p_{a}^{(t)}-p_{a^{\prime}}^{(t)}\right)\cdot\left(L_{a^{\prime}}^{(t)}-L_{a}^{(t)}\right)+\left(p_{b}^{(t)}-p_{b^{\prime}}^{(t)}\right)\cdot\left(L_{b^{\prime}}^{(t)}-L_{b}^{(t)}\right)>0$
(57)

Noticing that
$p_{a}^{(t)}-p_{a^{\prime}}^{(t)}=-\left(p_{b}^{(t)}-p_{b^{\prime}}^{(t)}\right)$,
then only when $p_{a}^{(t)}-p_{a^{\prime}}^{(t)}>0$ we can make the above
inequality holds. According to the situations where the group fraction
discrepancy becomes smaller, we know $p_{a}^{(t)}>p_{b}^{(t)}$ must hold and
$a$ is the majority group. However, this contradicts the initial condition
$L_{a}^{(t)}>L_{b}^{(t)}$, i.e, the majority group should not have higher
group-wise loss.

Finally, it is easy to see the cases where losses stay fixed cannot satisfy
Eqn. (55) and Eqn. (56) simultaneously. Thus, we prove (ii). ∎

With Lemma D.8, we can easily prove Thm. 5.4. What we need to prove is
$\triangle^{\text{PS}}_{\textsf{fair},\mathcal{L}}(\rho_{1})\geq\triangle^{\text{PS}}_{\textsf{fair},\mathcal{L}}(\rho_{2})$.
Now we know at $t$, higher $\rho$ results in lower or equal
$\triangle^{t}_{\textsf{fair},\mathcal{L}}(\rho)$ ((i) of Lemma D.8). Then the
lower or equal $\triangle^{t}_{\textsf{fair},\mathcal{L}}(\rho)$ results in
lower group fraction disparity at $t+1$ (Assumption 5.3), and further causes
lower loss disparity at $t+1$ ((ii) of Lemma D.8). This enables a forward
induction to prove that $\triangle^{t}_{\textsf{fair},\mathcal{L}}(\rho)$ is
non-decreasing with $\rho$ at each time step to infinity, which completes the
whole proof of Thm. 5.4.

###  D.5 Discussion on Performative Optimal (PO) Solutions

The PO solution is defined as

$\boldsymbol{\theta}^{\text{PO}}:=\mathbb{E}_{Z\sim\mathcal{D}_{\boldsymbol{\theta}}}\ell(\boldsymbol{\theta};Z),$
(58)

$\mathcal{D}_{\boldsymbol{\theta}}$ is the fixed point distribution.

At a high level, the PO solution and the approximation between PS and PO
solution largely follows the analysis in [4, 5], where Theorem 6 in [5] states
that if conditions in Lemma 2.4 and $\ell(\cdot;\cdot)$ is $L_{z}$-Lipschitz
in the second argument, then the PS and Po solution satisfies

$\|\boldsymbol{\theta}^{\text{PO}}-\boldsymbol{\theta}^{\text{PS}}\|_{2}\leq\frac{2L_{z}\epsilon}{\gamma(1-\epsilon)}.$

We note that the corresponding proof and the bound both only depend on the
strong convexity coefficient $\gamma$ and sensitivity coefficient $\epsilon$,
where the fair objective and the original objective have the same values, but
the fair objective did change the Lipschitz coefficient to
$\tilde{L}_{z}:=(1+\rho\overline{\ell}^{2})L_{z}$ and
$\tilde{L}_{z}:=(1+\rho\overline{\ell})L_{z}$ when using fair penalty and fair
reweighting mechanisms, respectively. Therefore, as long as we replace $L_{z}$
with the corresponding new value $\tilde{L}_{z}$, we can use the same proof
steps to show that

$\|\boldsymbol{\theta}^{\text{PO}}_{\textsf{fair}}-\boldsymbol{\theta}^{\text{PS}}_{\textsf{fair}}\|_{2}\leq\frac{2\tilde{L}_{z}\epsilon}{\gamma(1-\epsilon)},$

where

$\boldsymbol{\theta}^{\text{PO}}_{\textsf{fair}}:=\arg\min_{\boldsymbol{\theta}}\mathcal{L}_{\textsf{fair}}(\boldsymbol{\theta};\mathcal{D}_{\boldsymbol{\theta}})$

But as we show previously, the fairness metrics are only stable and meaningful
in PP when measured at the PS and Fair-PS solutions, so there isn’t much
practical value in finding the FPO solution.