# Long-Term Fairness Inquiries and Pursuits in Machine Learning:
A Survey of Notions, Methods, and Challenges

Usman Gohar1, Zeyu Tang2, Jialu Wang3, Kun Zhang2, Peter L. Spirtes2 Yang
Liu3, Lu Cheng4

###### Abstract

The widespread integration of Machine Learning systems in daily life,
particularly in high-stakes domains, has raised concerns about the fairness
implications. While prior works have investigated static fairness measures,
recent studies reveal that automated decision-making has long-term
implications and that off-the-shelf fairness approaches may not serve the
purpose of achieving long-term fairness. Additionally, the existence of
feedback loops and the interaction between models and the environment
introduces additional complexities that may deviate from the initial fairness
goals. In this survey, we review existing literature on long-term fairness
from different perspectives and present a taxonomy for long-term fairness
studies. We highlight key challenges and consider future research directions,
analyzing both current issues and potential further explorations.

##  1 Introduction

As Machine Learning (ML) algorithms assume increasingly influential roles in
high-stake domains traditionally steered by human judgments, an extensive body
of research has brought attention to the challenges of bias and discrimination
against marginalized groups (Mehrabi et al. 2021; Cheng, Varshney, and Liu
2021). These issues are pervasive and manifest in different settings,
including finance, legal (e.g., pretrial bail decisions), aviation, and
healthcare practices, among others (Gohar et al. 2024; Barocas, Hardt, and
Narayanan 2023). The community has led tremendous research efforts toward
measuring and mitigating algorithmic unfairness (Mehrabi et al. 2021).
However, the majority of such fairness approaches quantify unfairness based on
predefined statistical or causal criteria, often assuming a constant
environment and system, defined as _static fairness_. This myopic
conceptualization of fairness usually focuses on _short-term_ outcomes and
assesses only the instantaneous impact of interventions at a single snapshot,
overlooking system dynamics (_dynamic fairness_) and/or _long-term_
consequences over a time horizon (Zhang et al. 2020; Liu et al. 2018).

Recent works have brought attention to the misalignment of long-term fairness
considerations with the fairness objectives optimized in static settings and
shown that imposing static fairness criteria often does not guarantee long-
term fairness and may even amplify discrimination (Hu, Immorlica, and Vaughan
2019; Liu et al. 2018). One way static fairness approaches fall short is by
failing to account for the future implications of current decisions on
individuals or groups, undermining their effectiveness. For example, in
predictive policing, Ensign et al. (2018) observed how an initial higher
allocation of police in a specific area leads to more reported incidents,
perpetuating increased surveillance and exacerbating the marginalization of
those communities over time. To this end, a large body of work has proposed
various methods to measure, mitigate, and evaluate different aspects of
fairness in the _long-term_ setting rather than achieving fairness for a
single time step.

Simply put, _long-term fairness_ constitutes the settings outside of _static
fairness_ framework and _short-term_ outcomes by addressing fairness over
extended periods rather than focusing solely on immediate outcomes. While
_dynamic fairness_ aligns with this concept by considering evolving dynamics
over time (Li et al. 2023), long-term fairness has a much broader scope. This
umbrella term has different facets, including _sequential fairness_ (where
sequential decisions impact fairness) and fairness over multiple time steps,
among others (as depicted in Fig:1). In this work, we aim to unify the
different strands of literature on long-term fairness under a common
framework. Through this effort, we identify various dimensions and settings of
long-term fairness and provide a rich review of existing research to explore
diverse approaches and considerations for achieving fair outcomes in dynamic
and non-static contexts.

Figure 1: A high-level taxonomy for long-term fairness, including notions,
common modeling frameworks, and fair learning.

Difference from existing surveys. Several extensive surveys on ML fairness
have been conducted. A subset of these surveys (Mehrabi et al. 2021; Gohar and
Cheng 2023; Pessach and Shmueli 2022; Chouldechova and Roth 2018; Finocchiaro
et al. 2021) predominantly focus on static fairness or a specific vision of
fairness (e.g., intersectional techniques), with only brief and cursory
discussions on long-term fairness in some. Meanwhile, other works have
incorporated some aspects of long-term fairness. Gajane et al. (2022) reviewed
fairness approaches in Reinforcement Learning (RL), with overlap limited to
very brief coverage of RL techniques for long-term fairness. Separately, Patro
et al. (2022) critically examined the literature on Fair Ranking, discussing
the limitations of static settings and exploring modeling frameworks, like
simulations, within Ranking Systems only. The survey by Zhang and Liu (2021)
focused only on sequential decision algorithms, representing one facet of
long-term fairness inquiries, without a critical comparative analysis of
definitions, methods, and frameworks. Finally, Tang, Zhang, and Zhang (2023)
reviewed the fairness concepts in ML, drawing connections to moral and
political philosophy. They provide overviews of modeling frameworks and
choices in dynamic settings without making them the primary focus. In
comparison to these works, our survey specifically concentrates on long-term
fairness and offers a comprehensive and up-to-date overview of the field,
introducing the taxonomy encompassing long-term fairness notions, mitigation
techniques, and evaluation methods. Additionally, we critically examine
existing techniques, highlighting key challenges and open research questions.
Our literature search methodology is detailed in Appendix A.

Contributions and Outline. Our main contributions are: (1) propose a taxonomy
(Fig. 1) for long-term fairness, including notions, problem settings,
mitigation approaches, and modeling frameworks, (2) examine long-term fair
learning methods in multiple standard problem settings and evaluations, and
(3) highlight key challenges and future directions. The rest of the paper is
organized as follows. Section 2 introduces long-term fairness definition,
problem settings, and modeling frameworks. Section 3 discusses fairness
notions, while Section 4 covers mitigation techniques in dynamic settings.
Section 5 outlines application-specific works, including Recommender Systems,
and Section 6 explores alternative long-term fairness settings. Finally,
Section 7 discusses open challenges and future directions.

##  2 Long-Term Fairness in ML: An Overview

In this section, we first attempt to define long-term fairness and then
proceed to detail the different but intricately woven aspects that form this
concept.

### What Is Long-Term Fairness?

Given the dynamic nature of real-world scenarios, long-term fairness emerges
as a concept focused on achieving and maintaining fairness over a period of
time rather than within isolated decisions or instances (Hu and Zhang 2022).
Long-term fairness has been described using various terms, often used
interchangeably, including temporal, sequential, non-static, and dynamic
fairness. However, these encompass different aspects of the overarching
concept under complementary but orthogonal settings. Therefore, our first
contribution is to identify and define these problem settings within a unified
high-level taxonomy (Figure 1) for understanding the literature on long-term
fairness.

### Problem Setting

Long-term fairness was first studied within pipelines, where multiple
decisions are required. For instance, a two-stage hiring model involves a
candidate selection from the applicant pool, followed by hiring decisions
(Dwork and Ilvento 2018; Bower et al. 2017). However, long-term fairness has
since expanded into a multifaceted concept, encompassing various problem
settings. In Figure 1 (red box), we identify the four key problem settings
that underpin inquiries into long-term fairness. _Dynamic Modeling_ is the
primary setting where the majority of the long-term fairness considerations
have been explored. It addresses dynamic factors in the environment to
maintain fairness over time, including cases of sequential fairness where
fairness isn’t achieved over multiple decision rounds due to evolving system
dynamics or the failure of static fairness notions when used at each time step
(Yin et al. 2023; Chouldechova and Roth 2018; Cheng et al. 2021, 2022).
Another facet that captures the real-world dynamics is the _Distribution
Shift_ setting, where deployment (testing) environments systematically differ
from the training environment. This phenomenon can arise due to various
factors, such as data non-stationarity (Barrainkua et al. 2023).

_Delayed impact_ is a special setting of long-term fairness where the impact
of the decisions is not immediately observable but manifests gradually or
after a significant time lag (Liu et al. 2018). It focuses on a model of
delayed outcomes, without which one cannot foresee the impact a fairness
criterion would have if enforced as a constraint on a classification system.
Finally, _Performative Prediction_ refers to the causal influence that
predictions have on their intended targets (Hardt and Mendler-Dünner 2023).
This phenomenon can trigger a self-reinforcing cycle where predictions shape
future decisions, subsequently influencing outcomes. Perdomo et al. (2020)
describe it as a form of _distribution shift_ , but it uniquely focuses on
distribution shift resulting _solely_ from model deployment. While the impact
of decisions on the environment has been explored in the dynamic modeling
setting, performative prediction operates as a distinct framework (see Section
6). Apart from distribution shift, all these settings intersect with various
techniques like bandits, reinforcement learning, performative prediction, and
strategic classification, and hence, not clearly separable, making it
challenging to write this survey and develop the taxonomy. To address this
complexity and capture these interactions, we identify common modeling
frameworks that accommodate these dynamics while offering flexibility in
inquiry settings, as detailed below.

### Dynamic Modeling For Long-Term Fairness

The study of long-term fairness dynamics in literature involves various
approaches shaped by interactions with the environment and feedback
mechanisms. Typically, these works (1) propose a dynamics model tailored to a
specific domain, (2) expose unfairness from prolonged use of biased policies,
and (3) suggest a “fair” policy to mitigate biases. As such, _modeling
frameworks_ (Fig: 1 green box) play a pivotal role in addressing the long-term
fairness challenge. In this section, we outline commonly utilized frameworks
for modeling dynamics in long-term fairness.

  * •

Pólya Urn: The Pólya Urn (Mahmoud 2008) model simulates a stochastic process
of drawing balls from an urn that increases the probability of observing
certain events. At each time step, a ball is drawn and replaced with two of
the same color, capturing the rich-get-richer dynamics (Akpinar et al. 2022).
It is a simple yet powerful framework to model self-reinforcing dynamics and
cumulative advantages, making it particularly suitable for scenarios where
preferential attachment dynamics (Barabási and Albert 1999) are at play, e.g.,
resource allocation, social networks, and recommendation.

  * •

One-Step Feedback: It explores the impact of decision-making on the underlying
population after only a single step of feedback, distinct from works that
capture feedback over multiple time steps. It considers the dynamic response
of the population at deployment, influencing fairness without model updates.
This single-step evaluation is driven by practical considerations,
acknowledging that other variables may dominate over extended periods in real-
world scenarios (Liu et al. 2018).

  * •

Reinforcement Learning: Long-term fairness involves the model’s interaction
with the (possibly unknown) environment over time, a dynamic well-suited for
RL (Liu et al. 2021). Previous works have applied RL techniques within both
the Bandit and Markov Decision Process (MDP) frameworks to capture these
dynamics. In both settings, the goal is to derive an optimal policy that
maximizes cumulative rewards while meeting fairness criteria like Demographic
Parity (Calders, Kamiran, and Pechenizkiy 2009). This approach enables the
exploration of complex scenarios, balancing the exploitation of existing
knowledge (e.g., hiring from a known population) with the exploration of sub-
optimal solutions to gather additional data (e.g., hiring from diverse
backgrounds).

  * •

Causal Modeling and Reasoning: Focusing on principled learning and reasoning
about underlying data-generating processes, causality (Pearl 2009; Guo et al.
2020) has been recognized as a unique tool for better understanding and
mitigating bias in different contexts. Previous works have proposed to model
and reason about causal relations among variables to characterize
discrimination in static settings (Kilbertus et al. 2017; Kusner et al. 2017;
Nabi and Shpitser 2018; Chiappa and Isaac 2018). Going beyond static towards
dynamic and long-term settings, causal modeling of dynamics has also been
explored in the literature to varying extents of detail (Creager et al. 2020;
Zhang et al. 2020; Tang et al. 2023).

Apart from these commonly used frameworks, relatively fewer works have also
captured long-term fairness dynamics in social settings, (Heidari, Nanda, and
Gummadi 2019), online learning (Bechavod et al. 2019) strategic behavior (Dong
et al. 2018; Hu, Immorlica, and Vaughan 2019; Milli et al. 2019) and
algorithmic recourse (Ustun, Spangher, and Liu 2019; Von Kügelgen et al.
2022).

##  3 Long-Term Fairness Notions

Static fairness notions often focus on immediate fairness, overlooking long-
term equity risks, potentially exacerbating bias over time (D’Amour et al.
2020; Liu et al. 2018). In contrast, in the long-term fairness setting, the
notions capture non-static, dynamic nuances of fairness over time. In this
section, we present various long-term fairness notions used in literature in
different settings, as shown in Figure 2. Some of these notions can still be
used in static settings but have been adopted for long-term fairness using the
dynamic modeling frameworks discussed in the previous section to capture
dynamics. A summary of the main notations used in the paper is provided in the
Appendix (Table 2).

Figure 2: Taxonomy of fairness notions used in long-term settings. The dotted
boxes denote the adopted modeling frameworks

### Effort-based Fairness

Static notions of fairness predominantly center on ensuring similar outcome
probabilities across all protected groups. (Heidari, Nanda, and Gummadi 2019;
Mehrabi et al. 2021). However, these notions often operate under the
assumption of a static dataset, treating individuals as immutable entities
within the given data context. These approaches fail to consider that
disadvantaged groups may need to exert more effort over time than advantaged
groups to achieve similar outcomes, contradicting the principle of Equal
Opportunity (Roemer and Trannoy 2015; Von Kügelgen et al. 2022). This
oversight persists because the distance to the decision boundary is typically
greater for disadvantaged groups. Inspired by this, Heidari, Nanda, and
Gummadi (2019) proposed “effort unfairness”, which captures the disparity in
average effort required by disadvantaged group members compared to the
advantaged groups. It acknowledges that individuals can adjust their
qualifications over time to achieve positive outcomes, highlighting its long-
term and dynamic perspective on fairness. They propose Bounded-Effort
unfairness as a measure to quantify this disparity while constraining it
within a fixed level of effort. Given a data sample denoted by a tuple $(x,y)$
where $x\in\mathcal{X}$ $\subseteq\mathbb{R}^{d}$ and
$y\in\mathcal{Y}=\\{0,1\\}$ denote the input vector and ground-truth label,
respectively. Formally111For ease of reading and comparison, we use notations
defined in (Guldogan et al. 2022) for all effort-based definitions.:

###### Definition 1

Bounded-Effort (Heidari, Nanda, and Gummadi 2019). Given a constant
$\delta>0$, a classifier $f(x)$ satisfies effort fairness with $\delta-$effort
if

$\mathbb{P}\left(\max_{\mu(\Delta x)\leq\delta}f(x+\Delta x)\geq
0.5\,,\,f(x)<0.5\mid\mathsf{g}=g\right)=\\\ \mathbb{P}\left(\max_{\mu(\Delta
x)\leq\delta}f(x+\Delta x)\geq 0.5\,,\,f(x)<0.5\right)$ (1)

holds $\forall g\in\mathcal{G}$, $\Delta x$ represents the effort (change)
required to improve the feature $x$ to $x^{\prime}$,
$\mu:\mathbb{R}^{d}\to[0,\infty]$ a norm which assigns a non-negative value to
input vector, and $\mu(\Delta x)\leq\delta$ constraints effort to be small.

Recognize that the condition $f(x)<0.5$ denotes an unfavorable outcome,
signifying the individual’s unqualified status. In contrast, condition
$f(x+\Delta x)\geq 0.5$ denotes a positive outcome, signifying successful
effort $(\Delta x)$ to qualify the individual. For simplicity, the features
are assumed to be numerical and monotone (Duivesteijn and Feelders 2008). The
parameter $\delta$ constraints the maximum effort to ensure that individuals
or groups are not required to make disproportionately high efforts for
improvement. In contrast to the Bounded-Effort approach, Threshold-Reward
unfairness (Heidari, Nanda, and Gummadi 2019) shifts the focus from limiting
effort to setting a lower bound on the reward. This perspective assesses how
the minimum effort required to surpass a defined reward threshold varies among
protected groups. Intuitively, this notion captures the idea that a
disadvantaged group has to exert greater effort to get the same reward.
Finally, Effort-Reward (Heidari, Nanda, and Gummadi 2019) unfairness is
defined as the difference in maximum utility (difference between reward and
effort) for each protected group after additional effort, avoiding reliance on
specific thresholds to prevent fairness gerrymandering (Kearns et al. 2018)
and reduce result variability.

A closely related notion termed Equal Recourse quantifies the effort to attain
desirable outcomes by measuring the average distance of individuals in
different groups from the classifier’s decision boundary (Gupta et al. 2019).
Unlike bounded-effort unfairness, Equal Recourse aims to equalize average
efforts across protected groups without imposing limits on effort.

###### Definition 2

Equal-Recourse (Gupta et al. 2019). Given the distance (effort) $\Delta x$,
$f(x)$ is said to achieve equal recourse if $\forall g\in\mathcal{G}$

$\mathbb{E}\left[\underset{f(x+\Delta x)\geq 0.5}{\min}\mu(\Delta x)\mid
f(x)<0.5,\mathsf{g}=g\right]\\\ =\mathbb{E}\left[\underset{f(x+\Delta x)\geq
0.5}{\min}\mu(\Delta x)\mid f(x)<0.5\right].$ (2)

One drawback of this definition is its vulnerability to outliers. Given that
Equal Recourse computes the minimum required efforts by taking an average
across all samples, the presence of outliers can distort the overall fairness
measure. To address this, Guldogan et al. (2022) introduced Equal
Improvability, akin to bounded-effort fairness, aiming to equalize average
rewards for each group with a constrained effort. Formally:

###### Definition 3

Equal Improvability (Guldogan et al. 2022). Given a norm $\mu$ and a constant
$\delta$, $f(x)$ achieves equal-improvability fairness with $\delta$-bounded-
effort if $\forall g\in\mathcal{G}$

$\mathbb{P}\left(\max_{\mu(\Delta x)\leq\delta}f(x+\Delta x)\geq
0.5\,\mid\,f(x)<0.5,\mathsf{g}=g\right)\\\ =\mathbb{P}\left(\max_{\mu(\Delta
x)\leq\delta}f(x+\Delta x)\geq 0.5\,\mid\,f(x)<0.5\right).$ (3)

However, equal improvability differs from bounded-effort fairness in the
conditional part $f(x)<0.5$, i.e., it only focuses on equalizing the
probability of rejected samples being qualified after applying a limited
amount of effort. Von Kügelgen et al. (2022) build on the effort-based notions
by introducing a causal version of Equal Recourse called Individual Fair
Causal Recourse, focusing solely on rejected samples. They argue that the
efforts to attain favorable decisions capture causal relations among features
(Karimi et al. 2020; Karimi, Schölkopf, and Valera 2021).

###### Definition 4

Fair Causal Recourse (Von Kügelgen et al. 2022). $f(x)$ is fair if the
following holds for all latent variable $u$ and groups $g,g^{\prime}$

$\min_{f(x^{\prime})\geq 0.5}\mu(x^{\prime}-x(g,u))=\min_{f(x^{\prime})\geq
0.5}\mu(x^{\prime}-x(g^{\prime},u)).$ (4)

Finally, Huan et al. (2020) extends this framework to introduce a causal-based
notion that enforces equality of effort. However, it does not capture the
dynamics of the environment and model.

### Cumulative Group Fairness

Another line of work (Chi et al. 2021; Wen, Bastani, and Topcu 2021; Yin et
al. 2023) addressed the long-term nature of fairness by formalizing surrogate
fairness notions grounded in static fairness notions, mirroring approaches
found in other fairness aspects such as intersectionality (Gohar and Cheng
2023). These studies define long-term bias as the difference of the cumulative
sum of group fairness (e.g., allocation rates) at each time step between
different protected groups. These works have operationalized most of these
notions within the MDP framework, leveraging RL techniques — a prevalent
strategy for addressing long-term fairness dynamics (Zhang and Liu 2021). An
MDP is defined by a tuple $(S,A,\rho,\mathbf{T},r,\gamma)$, where
$\mathcal{S}$ is the state space (e.g., income levels), $\mathcal{A}$ is the
action space (accept/reject), $\rho$ is the initial state distribution,
$\mathbf{T}:S\times A\rightarrow\Delta(S)$ is the state transition function,
$R:S\times A\rightarrow\mathbb{R}$ is the immediate reward function (e.g.,
bank’s earned profits), and $\gamma$ is the discount factor. The goal is to
find a policy $\pi:S\rightarrow\Delta(A)$ that maximizes cumulative reward
$\eta(\pi):=\mathbb{E}_{\pi}\left[\sum_{t=0}^{\infty}\gamma^{t}R(s_{t},a_{t})\right],\text{
where }s_{0}\sim\rho,\,a_{t}\sim\pi(\cdot|s_{t}),\,s_{t+1}\sim
T(\cdot|s_{t},a_{t})$. Chi et al. (2021) propose Return Parity, which
stipulates that MDPs from distinct demographic groups, while sharing common
state and action spaces, should aim to attain roughly equivalent expected
rewards under a policy. Formally:

###### Definition 5

Return Parity (Chi et al. 2021). Given distinct initial distributions
$\rho_{0}$ and $\rho_{1}$ of two protected groups, $g\in\\{0,1\\}$ denoting
membership in the two groups with policies $\pi_{0},\pi_{1}$ then two MDPs
satisfy $\epsilon$-return parity if

$\eta(\pi_{0})-\eta(\pi_{1})\leq\epsilon.$ (5)

In other words, $\epsilon$-return parity ensures that the difference in
expected long-term rewards for two demographics modeled using MDPs does not
exceed a specified threshold of $\epsilon$, indicating similar outcomes. The
reward function can be adapted to model various fairness notions. Similarly,
Wen, Bastani, and Topcu (2021) extends other fairness notions, such as
Demographic Parity and Equal Opportunity, to this MDP setting of equalizing
long-term rewards for different protected groups. Finally, Yin et al. (2023)
follows the same principle, but instead of equalizing long-term reward, their
approach focuses on minimizing the violation of the sum of static bias at each
time step.

While these notions are promising for modeling fairness beyond a single time
step, Xu et al. (2023) highlights that they fail to capture the variation in
temporal importance. To address this, the authors propose the Equal Long-term
Benefit Rate (ELBERT) (Xu et al. 2023) fairness notion, which considers long-
term fairness as the ratio of group supply and group demand. They adapt static
fairness notion ratios, e.g., Equal Opportunity, by formulating them as the
ratio of group supply (qualified and accepted individuals) to group demand
(qualified individuals). Unlike previous adaptations of static notions, they
first take the sum of group supply and group demand separately before taking a
ratio. They highlight multiple cases (lending, medical treatment allocation)
where temporal variations in group supply and demand lead to a false sense of
fairness.

###### Definition 6

Long-Term Benefit Rate (Xu et al. 2023). Given distinct initial distributions
$\rho_{0}$ and $\rho_{1}$ of two protected groups, an MDP is said to have
achieved a Long-Term Benefit Rate if

$\frac{\eta^{S_{g}}(\pi)}{\eta^{D_{g}}(\pi)}$ (6)

is equalized across the protected groups.

Here, $\eta^{S_{g}}(\pi)$ and $\eta^{D_{g}}(\pi)$ represent the cumulative
group supply and group demand, respectively, which are analogous to the reward
function ($R$) and serve as supply $S_{g}(s_{t},a_{t})$ and demand functions
$D_{g}(s_{t},a_{t})$ to the MDP at each time step.

### Meritocratic Fairness

A body of research leverages bandit settings to model long-term fairness.
Joseph et al. (2016) initially identified how no-regret algorithms (those
avoiding negative feedback) in bandit settings may exhibit increasing
unfairness over time. In response, they introduced an individual notion of
fairness called Meritocratic Fairness, which posits that it is unjust to
preferentially select one individual (e.g., for a loan) over another if the
former is less qualified than the latter (Joseph et al. 2016), modeled in the
contextual bandit setting.

In a typical bandit framework, an agent chooses an arm $A_{t}$ from a set of
$\mathcal{K}$ arms, denoted by $k\in[\mathcal{K}]$ at each time step $t$, and
receives a stochastic reward $R_{t}$. These rewards are assumed to be drawn
from unknown distributions specific to each arm. In a contextual setting,
however, before making a decision at each time step $t$, the learner observes
contextual information $x_{t}^{j}$ associated with each arm $j$. In terms of
fairness, each arm is associated with a protected group, where $x_{t}^{j}$
provides information about an individual from a protected group. Each
population is associated with its own underlying function $f_{j}$, mapping
contexts to expected payoffs. Formally:

###### Definition 7

Meritocratic Fairness (Joseph et al. 2016). For any pair of arms $j,j_{0}$ at
time $t$, if,

$f_{j}(x_{j}^{t})\geq f_{j_{0}}(x_{j_{0}}^{t}),$ (7)

the algorithm is considered discriminatory, i.e., if it preferentially chooses
the lower quality arm $j_{0}$. Conversely, the algorithm is fair if it
ensures, with high probability over all rounds and for all pairs of arms
$j,j_{0}$, that whenever $f_{j}(x_{j}^{t})\geq f_{j_{0}}(x_{j_{0}}^{t})$, the
algorithm chooses arm $j$ with a probability at least as high as it chooses
arm $j_{0}$.

Liu et al. (2017) complement the aforementioned work by Joseph et al. (2018,
2016) by incorporating a smoothness constraint and protecting higher
qualifications over lower qualifications in an on-average manner. Meritocratic
Fairness assumes that $k$ distinct groups, each with unique mapping from
features to expected rewards, are already known. Moreover, it assumes one
group member is available and always selected in each round, which is
unrealistic(Joseph et al. 2018). To relax this assumption, Joseph et al.
(2018) introduces the notion of weakly-meritocratic fairness, which does not
assume knowledge of protected group membership.

###### Definition 8

$\delta$-Weakly Meritocratic Fairness (Joseph et al. 2018) A model is
$\delta$-fair if, for all sequences of contexts $x_{1},\ldots,x_{t}$, with
probability at least $1-\delta$ over the realization of the history $h$, for
all rounds $t\in[T]$ and all pairs of arms $j,j_{0}\in[k]$,

$\pi_{j\mid h}^{t}>\pi_{j_{0}\mid h}^{t}\quad\text{only if}\quad
f_{j}(x_{j}^{t})>f_{j_{0}}(x_{j_{0}}^{t})$ (8)

These notions, however, define fairness with respect to one-step rewards. To
capture the desired interaction and evolution of the environment, Jabbari et
al. (2017) extends Meritocratic Fairness to the MDP formulation, where it
requires that an algorithm never probabilistically favors an action with lower
long-term reward over an action with higher long-term rewards. Due to the
exponential complexity of satisfying this, they propose two relaxations of
this notion: 1) Approximate-choice and 2) Approximate-action fairness.
Approximate-choice fairness prevents equally good actions from being chosen at
very different rates, while approximate-action fairness prevents substantially
worse actions from being chosen over better ones. Grazzi et al. (2022) build
upon these works to propose the Group Meritocratic Fairness notion in the
contextual bandit setting. Specifically, they introduce the idea of highest
relative rank, which evaluates the reward’s quality relative to other
candidates within the same group. This approach ensures that the chosen
candidates are not only selected based on their absolute rewards but also
considering their position within their group’s reward distribution. The aim
is to address fairness disparities in scenarios with diverse group reward
distributions.

### Causality-Motivated Long-Term Fairness Inquiry

Causal modeling of underlying dynamics in long-term settings has been
recognized as beneficial for analyzing social implications of automated
decision-making (Creager et al. 2020; Zhang et al. 2020). To achieve long-term
fairness, understanding the interplay of various processes is crucial (Tang,
Zhang, and Zhang 2023). Tang et al. (2023) present a detailed causal model, in
terms of a directly acyclic graph (DAG) for two key dynamics in decision-
distribution interplay: (1) the decision-making process based on data at each
time step and (2) the underlying data generating process influencing future
distributions. Rather than enforcing fairness criteria at each time step, they
propose setting a goal of _achieving_ long-term fairness and evaluating it
alongside.

###### Definition 9

$K$-Step Tier Balancing (Tang et al. 2023) A sequence of $K$ decision-making
strategies $D_{T:T+K-1}\coloneqq\\{D_{T},\ldots,D_{T+K-1}\\}$ (empty set if
$K=0$) satisfies $K$_-Step Tier Balancing_ if at the time step $T+K$ the
following independence relation holds true (where “$\perp\\!\\!\\!\perp$”
denotes statistical independence, and $A$ denotes the protected feature):

$H_{T+K}\perp\\!\\!\\!\perp A_{T+K},$ (9)

where $H_{T+K}$ is induced by $K$-step dynamics.

This notion extends beyond observed variables to include latent causal
factors, i.e., “tiers”, that carry on the influence of current decisions to
future data distribution through the interplay between dynamics. Through a
detailed causal modeling of the dynamics and the corresponding analysis of
their characteristics, Tang et al. (2023) formulate the one-step tier
imbalance reduction (STIR) term and present possibility and impossibility
results to illustrate the feasibility of setting _Tier Balancing_ as a long-
term fairness goal.

### Discussion

Existing long-term fairness notions differ based on the modeling framework
used and what aspect (e.g., effort, merit) of fairness they capture
dynamically. Cumulative fairness, for instance, extends previous static
fairness notions to the long-term context by aggregating fairness measures at
each time step using RL. However, recurrent RL policy deployments that enforce
static fairness notions at each time step may not be universally suitable for
real-world scenarios (Henderson et al. 2018), necessitating the development of
lightweight techniques. Recourse and effort-based notions, adapted from static
settings, are only one-step analyses of long-term fairness applied iteratively
to address equality of effort. One limitation is that they measure the
anticipated effort in response to algorithmic decisions, neglecting the legal
(e.g., affirmative action) and philosophical emphasis on actual historical
effort. To bridge this gap, future work could focus on ensuring parity in
outcomes based on the effort already put in and developing algorithms and
datasets to capture it in long-term settings. Moreover, some notions, like
meritocratic and effort fairness, are only applicable in specific applications
such as hiring, limiting their use. While Tier Balancing is a step towards a
generalized natural notion from the dynamic and long-term perspective through
causal dynamic modeling, it’s imperative that such notions find support in
effective and efficient learning algorithms. Additionally, current notions
often fail to support multiple protected groups, which fails to fully capture
the nuances of fairness (Gohar and Cheng 2023). Incorporating multiple
dimensions of intersecting identities is an important challenge to solve.
Finally, these notions are strictly limited to tabular data, and developing
long-term notions in other domains (e.g., image, video, and language) is a
promising direction.

##  4 Improving Long-Term Fairness in Dynamic Setting

Several approaches have emerged to address bias in dynamic settings,
leveraging interactions with the environment to maintain fairness during
learning. Table 1 outlines the representative mitigation methods. Broadly,
these approaches are categorized based on whether the decision-making
influences the environment and, consequently, future actions. Most mitigation
methods consider the dynamics in a multi-step sequential learning framework.

Example Works | Metric of Interest | Modeling | Time Horizon | Dynamics | Application
---|---|---|---|---|---
Liu et al. (2018) | demographic parity | - | single-step | not impacted | lending practice
Joseph et al. (2016) | meritocratic fairness | bandit | sequential | not impacted | -
Heidari and Krause (2018); Bechavod, Jung, and Wu (2020) | individual fairness | online learning | sequential | not impacted | -
Hashimoto et al. (2018) | risk disparity | online learning | sequential | not impacted | -
Gillen et al. (2018) | individual fairness | bandit | sequential | not impacted | -
Patil et al. (2021) | return parity | bandit | sequential | not impacted | -
Jabbari et al. (2017) | meritocratic fairness | reinforcement learning | sequential | impacted | -
Yin et al. (2023); Wen, Bastani, and Topcu (2021) | demographic parity | reinforcement learning | sequential | impacted | -
Puranik, Madhow, and Pedarsani (2022) | return parity | reinforcement learning | sequential | impacted | -
Siddique, Weng, and Zimmer (2020) | Gini social welfare function | reinforcement learning | sequential | impacted | -
Liu et al. (2021) | proportional fairness | reinforcement learning | sequential | impacted | ranking, allocation
Tang, Ho, and Liu (2020) | delayed impact | bandit | sequential | not impacted | -
Weber et al. (2022) | delayed impact | reinforcement learning | single-step | not impacted | -

Table 1: A comparative view of long-term fairness learning methods.

### Decisions Decoupled from Environment

In this setting, decision-making does not impact the dynamics of the
environment, and most of the works assume an online learning setting where the
data arrives sequentially and the model learns the dynamics on the go
(Bechavod et al. 2019). The seminal work of Joseph et al. (2016) proposed a
no-regret algorithm, based on chained confidence intervals, for dynamic
fairness in the stochastic and contextual bandits problem for the meritocratic
fairness notion. They prove that the task of learning a provably fair
contextual bandit algorithm can be transformed into a “Knows What It Knows”
(KWIK) learning algorithm (Li, Littman, and Walsh 2008) and propose an
efficient learning algorithm. Utilizing the MAB framework, Liu et al. (2017)
propose a Thompson-Sampling-based algorithm to achieve calibrated fairness
where each arm is selected with the probability equal to that of its reward
being the largest while satisfying the smoothness constraint for each round
(See Sec 3), with a reward distribution in Bernoulli. Wang et al. (2021)
further extends their work to propose a more efficient Thompson-Sampling-based
algorithm by enforcing merit fairness across rounds instead of for each round
and an arbitrary reward function. Heidari and Krause (2018) model the
sequential individual fairness in an online learning setting. They propose a
Consistently Follow the Leader algorithm that always picks the outcome label
closest to the prediction among the labels satisfying the consistency
constraint. The labels generated in such schema are proved to follow the
optimal hypothesis in bounded time steps. Also targeting individual fairness
in online learning, Bechavod, Jung, and Wu (2020) reduces the constrained
learning into the standard online batch classification problem. Thus, the
common Follow-The-Perturbed-Leader algorithm can be applied oracle-efficiently
to achieve sublinear Lagrangian regret. Similarly, Gillen et al. (2018)
proposes an algorithm where the learner aims to satisfy a fairness constraint
defined using an unknown distance metric in an online linear contextual bandit
setting. They assume access to only weak feedback where a regulator can flag
unfairness but cannot quantify it across individuals. Finally, Patil et al.
(2021) proposes a meta-algorithm, which can be applied to any MAB algorithm
(e.g., UCB1) to satisfy a fairness constraint that each arm is pulled at least
some pre-specified fraction of the times.

Beyond the bandit setting, Hashimoto et al. (2018) presents a distributionally
robust optimization (DRO) procedure to mitigate the disparity amplification
over time. The core idea is to constrain the group-wise worst-case loss in
each iteration; thus, the data examples with high risk are up-weighted.
Specifically, let $P$ denote the distribution of data examples and
$\mathcal{B}(P,r)$ denote the chi-squared ball around $P$ of radius $r$,
measured by a certain $f$-divergence. The DRO loss parameterized by $\theta$
around all possible perturbation with the maximal radius $r$ around $P$ is
${R}_{\text{DRO}}(\theta;r)=\sup_{Q\in\mathcal{B}(P,r)}\mathbb{E}_{Q}\ell(\theta).$
There are two solutions to the above DRO risk. The first solution assumes the
$\chi^{2}$-divergence and solves the dual form of the DRO risk in the
following form
$\hat{\theta}_{\lambda}=\min_{\theta}\mathbb{E}_{P}[\ell(\theta)-\lambda]_{+}^{2}.$,
where $\lambda$ is a dual parameter. The other solution assumes that one can
compute the worst case probability distribution
$Q^{*}(\theta)\in\operatorname*{arg\,max}_{Q\in\mathcal{B}(P,r)}\mathbb{E}_{Q}\ell(\theta)$
for a given parameter $\theta$ through projected gradient ascent and alternate
the optimal
$\theta^{*}(Q)\in\operatorname*{arg\,min}_{\theta}\mathbb{E}_{Q}\ell(\theta)$.
The final solution $\theta^{*}$ and $Q^{*}$ will be given by the saddle point
of the optimization problem. Moreover, the authors demonstrate that utilizing
a one-step minimizer during each iteration, reduces the online learning
problem into the standard learning problem. Similarly, Hu and Zhang (2022)
proposed a repeated risk minimization framework to sequentially mitigate long-
term fairness on post-intervention data samples.

### Decision Impacts Environment Dynamics

A series of works (Yin et al. 2023; Chi et al. 2021) model the long-term
fairness issue in the context of RL. These works typically focus on how the
deployment of the decision policy influences the environment and future
rewards. In this context, Jabbari et al. (2017) propose a fair polynomial time
algorithm using the MDP framework to enforce the notion of approximate
meritocratic fairness. Here, the distribution of individuals is considered as
the state $s$ of the environment, and the decision model $f$ is considered as
the action $a$. The decision model is evaluated by the risk $\ell(s,a)$ and
the fairness violation $G(s,a)$ on the data observation. The utility function
for the RL agent is the negative of risk and fairness violation subject to the
observed state and the selected decision policy, i.e., $r(s,a)=1-\ell(s,a)$
and $g(s,a)=1-G(s,a)$, respectively. The authors assume an unknown state
transition probability such that $s_{t+1}\sim P(s_{t},a_{t})$. In the RL
context, the goal of long-term fairness can be viewed as maximizing the
cumulative reward $\max_{\pi}\mathbb{E}[\sum_{t=0}^{T}r(s_{t},a_{t})\mid
s_{0}]$ while preserving the fairness violation over time
$\mathbb{E}[\sum_{t=0}^{T}g(s_{t},a_{t})\mid s_{0}]\geq c.$

Yin et al. (2023) show that a modified variant of the Upper-Confidence Bound
algorithm can address the long-term fairness with continuous state and action
spaces. In particular, the solution is built on the assumption that the
$Q$-function can be parameterized as a linear form with respect to some weight
vector $w$ so that $w$ can be precisely solved by a least square problem
instead. Wen, Bastani, and Topcu (2021) proposed a slightly different MDP for
modeling long-term fairness. Instead of using a shared reward function for the
policymaker, they assumed an additional reward function for individuals. Then,
the fairness is measured as the difference of the expected individual reward
between groups with the deployed model policy $\pi$. To mitigate fairness,
Wen, Bastani, and Topcu (2021) propose prioritizing the policies closer to
holding the fairness constraints and ranking the candidates in terms of their
rewards. The sampled policies are then used to further update the decision
model’s parameters. The algorithm is proven to be near optimal while enforcing
the static fairness constraints. On the other hand, Puranik, Madhow, and
Pedarsani (2022) propose maximizing applicants’ accumulated qualification
scores with policy learning. Lastly, Siddique, Weng, and Zimmer (2020)
enforces the fairness constraint that maximizes the utility of the worst of
individuals by formulating it as the generalized Gini social welfare function
(Weymark 1981). Instead of MDP, they adopt multi-objective MDPs, where rewards
take the form of vector instead of scalar, to impose the specific notion of
fairness.

### Discussion

Compared with the standard static fairness interventions, the summarized
mitigation methods mainly contribute to formulating the dynamics of human-
model interactions and establishing the corresponding solutions based on the
group utility shifts. Long-term fairness under unknown dynamics and/or without
leveraging demographic information remains largely unexplored but promising,
especially considering privacy laws (Chen et al. 2019) that limit access to
such data. From the perspective of temporal learning, it is positive that
long-term fairness is focused on the multi-step sequential learning setting.
However, the current research typically only focuses on optimizing the model
learner at each time step. Understanding the tensions between ensuring
fairness at each time step and cumulatively at the final step needs more
investigation. Finally, while RL methods are flexible and learn the dynamics
of the environment well, they are data-intensive (Dulac-Arnold et al. 2021;
Henderson et al. 2018) and often unsuitable for real-world scenarios. Hence,
developing techniques that can efficiently estimate the dynamics is crucial.
Notably, the recent advance in performative prediction (Perdomo et al. 2020)
provides a new perspective on off-policy learning for modeling the interplay
between the model policy and agents.

##  5 Evaluation of Long-Term Fairness

Practical applications offer a unique context for long-term fairness
considerations, depending on which one would expect context-dependent
interpretations of technical findings. Therefore in this section, we present
application-specific fairness inquiries motivated by empirical scenarios.

### Application-Specific Studies

Credit Application.  Liu et al. (2018) focus on lending practices to quantify
delayed impacts of decisions (selections) made by institutes (e.g., the bank)
on different groups. They represent each group through a score distribution,
where higher scores indicate a greater likelihood of positive outcomes.
Assuming access to a function that provides the expected score change for
individuals, they introduce a one-step feedback model and construct outcome
curves, which describe the relation between the expected difference in the
mean score after the one-step feedback and the natural parameter regimes
(e.g., selection rate of the policy). They found that both Demographic Parity
and Equal Opportunity can lead to all possible outcomes, i.e., long-term
improvement, stagnation, and decline, in the natural parameter regimes. This
study emphasizes the impossibility of foreseeing a fairness criterion’s impact
without carefully modeling the delayed outcome.

Labor Market.  The seminal work of (Hu and Chen 2018) considers a two-stage
dynamic reputational labor market model to capture the long-term and
reinforcing nature of disparate outcomes. They propose imposing demographic
parity within a temporary labor market to achieve long-term equilibrium in the
permanent reputational labor market based on affirmative action. Separately,
Celis et al. (2021) investigate the long-term impact of the Rooney Rule
(Collins 2007), a hiring policy aimed at mitigating implicit bias by mandating
decision-makers to include at least one candidate from an underrepresented
group. They employ a mathematical model of implicit bias, featuring two
candidate groups, one of which is underrepresented. Each candidate possesses
both a true, latent utility and an observed utility, subject to bias by a
multiplicative factor. Candidates are then shortlisted by a selection panel
based on observed utility. Their findings demonstrate that the rule
progressively enhances minority hiring while maintaining overall utility.

Predictive Policing Ensign et al. (2018) explore resource allocation in
predictive policing (Mohler et al. 2015), which deploys patrol officers based
on historical crime data. They identify a feedback phenomenon present in
similar algorithms across contexts like recidivism prediction and lending,
where prediction outcomes heavily influence algorithm feedback. Using the
Pólya urn model, they explain this feedback occurrence and propose black-box
solutions, such as reweighing input incidents. Elzayn et al. (2019), go one
step further by proposing an algorithm which, under simplification
assumptions, converges to an optimally fair resource allocation, even in the
absence of known stationary ground-truth crime rates, avoiding the runaway
feedback loop effect.

### Long-Term Fairness in Recommender Systems

Long-term fairness considerations naturally align with Recommender Systems due
to evolving user interactions and item popularity, impacting system
performance (Liu et al. 2021). Consequently, the RL framework is favored for
its ability to model interactive dynamics. The works mostly focus on 1) _user-
side fairness_ , addressing equitable treatment for users, and 2) _item-side
fairness_ , ensuring unbiased item recommendation stemming from popularity
bias due to disproportionate exposure (Chen et al. 2023).

#### Item-side fairness.

Long-term fairness efforts in recommendation systems primarily target item-
side fairness, addressing the challenge by modeling the sequential
interactions between consumers and recommender systems using an MDP framework.
A few works in this direction adopt an Actor-Critic RL algorithm leveraging
the policy-based method (actor) with the value-based approach (critic) to
learn the policy and value-function simultaneously (Grondman et al. 2012). In
this setup, the actor learns an optimal policy through environment
exploration, while the critic evaluates actions to determine long-term rewards
(Liu et al. 2021). Utilizing this, Liu et al. (2021) propose FairRec that
dynamically maintains accuracy and user fairness in the long term by jointly
representing the user preferences (at the item and group level) as the states
in an MDP model. They use the Weighted-Proportional Fairness concept,
allocating resources (recommendations) proportionally to diverse entities’
demands using a weighting factor. This dual-reward system strategically
optimizes both accuracy and fairness in the long term. Separately, Ge et al.
(2021) study the long-term fairness of item exposure, focusing on group item
labels. They address the challenge of items categorized into groups based on
popularity, which dynamically change with user interaction over time, leading
to shifting group labels. Using a Demographic Parity-based fairness-
constrained policy optimization method, the authors propose an MDP
recommendation model based on the actor-critic architecture. However, they
introduce an additional critic designed for the demographic parity fairness
constraint. On a related note, Morik et al. (2020) explored the rich-get-
richer phenomenon in dynamic Learning-to-Rank approaches (Yang and Ai 2021).
Their solution, FairCo, ensures meritocratic fairness by allocating exposure
to items proportional to their average relevance. FairCo integrates user
feedback and dynamically adjusts its ranking based on the fairness constraint,
employing a P-Controller approach for modeling, a popular feedback control
mechanism (Bequette 2003). In another work, Saito et al. (2020) tackles self-
selection bias (Chen et al. 2023), where popular items tend to receive more
clicks regardless of actual interest. They propose an ideal loss function
optimized for relevance rather than the highest click probability. In this
regard, uniform data has also been proven to be an effective approach (Akpinar
et al. 2022). This method involves randomly selecting items and ranking them
using a uniform distribution. Chen et al. (2023) (Section 4.8) summarizes the
various methods that use this approach. Lastly, Ferraro, Serra, and Bauer
(2021) investigate gender fairness in collaborative filtering, revealing
disparities in exposure between female and male artists. They introduce an
iterative re-ranking method that simulates feedback loops and penalizes male
artists, resulting in adjusted rankings without significant performance
impact.

#### User-Side Fairness.

Relatively fewer works have focused on long-term user-side fairness. Akpinar
et al. (2022) employ a simulation framework and Pólya urns to study the long-
term impacts of fairness interventions in social network connection
recommendations. They argue that static fairness notions fail to maintain
equity in network sizes and utility across different protected groups in
dynamic settings.

### Discussion

The majority of the long-term fairness evaluations have either been context-
specific (e.g., hiring) or in recommendation systems. In recommendation
systems, RL methods are favored for modeling dynamics. However, a notable
drawback of RL methods is their vulnerability to user tampering (Kasirzadeh
and Evans 2023), where recommender systems manipulate user opinions and
preferences to boost long-term user engagement through its recommendations.
Furthermore, assessing long-term fairness in a multi-stakeholder
(Abdollahpouri and Burke 2019) setting characterized by competing interests
remains largely unexplored. Some other promising applications include text,
where the advent of Large Language Models (LLMs) has facilitated dynamic
conversations in various settings like chatbots and healthcare assistants
(Gilbert et al. 2023). Studies have indicated that model outputs can be
influenced through iterative feedback (Zamfirescu-Pereira et al. 2023; Logan
IV et al. 2021), raising fairness concerns. This, coupled with contextual
interactions (Zhang et al. 2021), underscores the need to develop evaluation
methods capable of assessing long-term fairness to capture these evolving
dynamics.

##  6 Long-Term Fairness Beyond Dynamic Modeling

Besides addressing long-term fairness in dynamic modeling contexts, various
problem settings that require distinct consideration have also tackled the
problem. This section provides a brief overview of these alternative settings.

### Performative Prediction

Performative prediction refers to the dynamic influence of model decisions on
future data distribution. At its core is the concept of a distribution map
$D:\Theta\rightarrow\mathcal{P}(X\times Y)$, which captures the dependence of
data-generating distribution on the model parameters $\theta\in\Theta$,
ignoring other reasons for distribution shift (Hardt and Mendler-Dünner 2023).
This abstraction facilitates the modeling of any mechanism for the
distribution shift. Miller, Perdomo, and Zrnic (2021) propose a two-stage
approach where the learner first estimates a model of the distribution map to
capture the unknown parameters of the performative effects and then uses the
estimated model to construct the proxy of perturbed performative loss. Next,
Mendler-Dünner et al. (2020) categorize the stochastic optimization in
performative prediction into greedy deploy and lazy deploy. Greedy deployment
involves a sequential program that continually updates model parameters based
on current data observations and deploys the updated model. In contrast, lazy
deployment progressively approximates repeated risk minimization, collecting
multiple rounds of observations to update the model between deployments. The
survey by Hardt and Mendler-Dünner (2023) offers a comprehensive review of
approaches, which can be extended to encompass long-term fairness settings.

### Delayed Impact

Delayed impact represents how the model decisions under fairness interventions
may affect the long-term well-being of the groups it aims to protect for (Liu
et al. 2018). It can be seen as a case of performative prediction without
adopting the formal framework. A couple of works have been brought up to
mitigate the delayed impact in the context of multi-armed bandits (Tang, Ho,
and Liu 2020) or RL (Weber et al. 2022). The proposed algorithms include two
common steps to mitigate the delayed impact. In the first step, the model
learns from the historical data through UCB or optimization as a
classification problem. In the second step, the delayed impact will be
estimated through importance sampling on the realized future data. The
estimated delayed impact will be used as a reward signal that can be further
used to select the arms or determine the classifier.

### Distribution Shift

An alternative research avenue explores dynamic learning environments where
data distributions evolve over time. For instance, the profile of loan
applicants may shift due to macroeconomic trends or changes in self-selection
criteria. This dynamic necessitates continuous fairness maintenance rather
than a one-time requirement. A representative work (Almuzaini et al. 2022)
proposes a dynamic learning method that proactively corrects the classifier,
estimating future data properties and retraining accordingly without direct
model-environment interaction. Within this framework, two approaches emerge 1)
_Adaptive_ , adapting the classifier to a known target environment, and 2)
_Robust_ , training classifiers to ensure fairness under perturbations when no
target environment information is available (Barrainkua et al. 2023). This
problem setting differs from other works due to the absence of direct
environmental feedback. For an in-depth review of works in this area, we refer
readers to the survey on fairness under domain shift (Barrainkua et al. 2023).

##  7 Open Challenges and Future Works

Drawing on the limitations of prior work, we conclude by outlining several
important research gaps and future avenues that are yet to be explored.

Evaluating long-term and short-term fairness tension. Evaluating the tension
and developing techniques for achieving fairness immediately and maintaining
it over an extended period presents a significant challenge. Additionally,
while the fairness-utility trade-off has been thoroughly examined in fairness
literature (Mehrabi et al. 2021), assessing this long-term trade-off and
establishing benchmarks to evaluate different methods remain important
directions.

Complexity of real-world dynamics. As we have seen in Sections 2 and 5, long-
term fairness necessitates modeling and characterization of dynamics. However,
the complexity of real-world scenarios, including limited access to
demographic data, presents significant challenges for practitioners to fully
understand the interplay of various dynamics and effectively address the
discrimination involved. Translating insights from studies focused on specific
applications to broader contexts and bridging the gap between empirical
fairness evaluations (Gohar, Biswas, and Rajan 2023) and theoretical
guarantees (Tang and Zhang 2022) are important and ongoing challenges in the
field.

Intersectional identities. Current long-term fairness research has primarily
concentrated on single-attribute group identities, such as gender or age.
However, numerous studies reveal that bias is a nuanced phenomenon that spans
multiple protected groups and intersecting identities (Gohar and Cheng 2023).
This complexity poses unique challenges, notably the exponential number of
subgroups. Future endeavors should focus on developing methodologies and
frameworks that capture and mitigate bias at the intersection of various
attributes in long-term settings.

Explainability over time. Explanability in AI has gained tremendous attention
due to the need for transparency, which significantly affects acceptance
within the broader community (Gross 2007; Shin 2021). Long-term fairness
notions, such as effort-based fairness, necessitate using explainable methods.
It is vital to empower the impacted population to understand how decisions are
made and determine strategies to enhance their qualifications in subsequent
instances. Furthermore, incorporating explainability methods in dynamic
fairness-aware recommendation environments is another direction (Chen, Zhang,
and Qin 2019).

Long-term dynamics in other AI domains. Studies have shown that prompt
engineering and fine-tuning in LLMs directly influence the model toward
generating the desired outputs (Zamfirescu-Pereira et al. 2023; Logan IV et
al. 2021). In real-world scenarios, user interactions are dynamic and may even
be strategic, guiding the LLMs in tailoring responses to their needs through
repeated feedback. An important research direction is developing evaluation
methods that capture these dynamics and assess bias and fairness in LLM (and
other large models) outputs. On the other hand, it is also crucial to steer
the response of LLMs to consistently align with human values represented by
different demographics and cultures (Solaiman et al. 2023) in multi-round
dialogues.

Alignment with policy and regulatory framework in the long run. _Trustworthy
AI_ has drawn increasing attention from policy and regulatory efforts. For
example, the European Commission High-Level Expert Group on AI presented the
Ethical Guidelines (European Commission 2019) that put forward a set of 7 key
requirements an AI system should meet to be deemed trustworthy. The
Organisation for Economic Cooperation and Development also proposed a
framework to compare implementation tools for promoting _Trustworthy AI_
(Organisation for Economic Co-operation and Development (2020) OECD).
Consequently, it is important to consider long-term fairness together with
other aspects of _Trustworthy AI_.

##  8 Conclusion

Recent research highlights the inadequacy of static one-shot fairness
approaches in capturing unfairness over extended periods. To offer researchers
an understanding of the field, we present a unifying review of long-term
fairness in multiple problem settings and frameworks. First, we provide
readers with a high-level overview of the conceptual frameworks employed to
model long-term fairness problems. Next, we propose the first taxonomy on
long-term fairness, wherein we explored long-term fairness definitions,
mitigation methods, and representative evaluation techniques across various
applications. We also discuss briefly other problem settings that tackle this
issue. Finally, we discuss open challenges and opportunities of long-term
fairness research. Ultimately, we hope our survey serves as a foundational
resource for those new to the field, fostering an understanding of the
complexities associated with long-term fairness and drawing attention to the
potential societal consequences that may arise without effective long-term
fairness measures.

## Ethical Statement

Throughout the process of conducting the project, all authors are aware of and
committed to rigorously adhering to AIES Ethics Guidelines. In this work, we
review the literature on long-term fairness, examining long-term fairness
methods, notions, and evaluations. We also highlight the limitations of
current methods and highlight avenues for future research. We hope our work
can serve as an informative guide, encouraging researchers to explore the
nuances of long-term fairness. We have reviewed the potential ethical
implications of our work, and based on our assessment, no foreseeable ethical
concerns have been identified.

## References

  * Abdollahpouri and Burke (2019) Abdollahpouri, H.; and Burke, R. 2019.  Multi-stakeholder recommendation and its connection to multi-sided fairness.  _arXiv preprint arXiv:1907.13158_.
  * Akpinar et al. (2022) Akpinar, N.-J.; DiCiccio, C.; Nandy, P.; and Basu, K. 2022.  Long-term Dynamics of Fairness Intervention in Connection Recommender Systems.  In _Proceedings of the 2022 AAAI/ACM Conference on AI, Ethics, and Society_ , 22–35.
  * Almuzaini et al. (2022) Almuzaini, A. A.; Bhatt, C. A.; Pennock, D. M.; and Singh, V. K. 2022.  Abcinml: Anticipatory bias correction in machine learning applications.  In _Proceedings of the 2022 ACM Conference on Fairness, Accountability, and Transparency_ , 1552–1560.
  * Barabási and Albert (1999) Barabási, A.-L.; and Albert, R. 1999.  Emergence of scaling in random networks.  _science_ , 286(5439): 509–512.
  * Barocas, Hardt, and Narayanan (2023) Barocas, S.; Hardt, M.; and Narayanan, A. 2023.  _Fairness and machine learning: Limitations and opportunities_.  MIT Press.
  * Barrainkua et al. (2023) Barrainkua, A.; Gordaliza, P.; Lozano, J. A.; and Quadrianto, N. 2023.  Preserving the Fairness Guarantees of Classifiers in Changing Environments: a Survey.  _ACM Computing Surveys_.
  * Bechavod, Jung, and Wu (2020) Bechavod, Y.; Jung, C.; and Wu, Z. S. 2020.  Metric-Free Individual Fairness in Online Learning.  _ArXiv_ , abs/2002.05474.
  * Bechavod et al. (2019) Bechavod, Y.; Ligett, K.; Roth, A.; Waggoner, B.; and Wu, S. Z. 2019.  Equal opportunity in online classification with partial feedback.  _Advances in Neural Information Processing Systems_ , 32.
  * Bequette (2003) Bequette, B. W. 2003.  _Process control: modeling, design, and simulation_.  Prentice Hall Professional.
  * Bower et al. (2017) Bower, A.; Kitchen, S. N.; Niss, L.; Strauss, M. J.; Vargas, A.; and Venkatasubramanian, S. 2017.  Fair pipelines.  _arXiv preprint arXiv:1707.00391_.
  * Calders, Kamiran, and Pechenizkiy (2009) Calders, T.; Kamiran, F.; and Pechenizkiy, M. 2009.  Building classifiers with independency constraints.  In _2009 IEEE International Conference on Data Mining Workshops_ , 13–18. IEEE.
  * Celis et al. (2021) Celis, L. E.; Hays, C.; Mehrotra, A.; and Vishnoi, N. K. 2021.  The effect of the Rooney Rule on implicit bias in the long term.  In _Proceedings of the 2021 ACM conference on fairness, accountability, and transparency_ , 678–689.
  * Chen et al. (2023) Chen, J.; Dong, H.; Wang, X.; Feng, F.; Wang, M.; and He, X. 2023.  Bias and debias in recommender system: A survey and future directions.  _ACM Transactions on Information Systems_ , 41(3): 1–39.
  * Chen et al. (2019) Chen, J.; Kallus, N.; Mao, X.; Svacha, G.; and Udell, M. 2019.  Fairness Under Unawareness: Assessing Disparity When Protected Class Is Unobserved.  In _Proceedings of the Conference on Fairness, Accountability, and Transparency_ , FAT* ’19, 339–348. New York, NY, USA: Association for Computing Machinery.  ISBN 9781450361255.
  * Chen, Zhang, and Qin (2019) Chen, X.; Zhang, Y.; and Qin, Z. 2019.  Dynamic explainable recommendation based on neural attentive models.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 33, 53–60.
  * Cheng et al. (2021) Cheng, L.; Mosallanezhad, A.; Silva, Y. N.; Hall, D. L.; and Liu, H. 2021.  Mitigating bias in session-based cyberbullying detection: A non-compromising approach.  In _The Joint Conference of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing (ACL-IJCNLP)_ , volume 1.
  * Cheng et al. (2022) Cheng, L.; Mosallanezhad, A.; Silva, Y. N.; Hall, D. L.; and Liu, H. 2022.  Bias mitigation for toxicity detection via sequential decisions.  In _Proceedings of the 45th International ACM SIGIR Conference on Research and Development in Information Retrieval_ , 1750–1760.
  * Cheng, Varshney, and Liu (2021) Cheng, L.; Varshney, K. R.; and Liu, H. 2021.  Socially responsible ai algorithms: Issues, purposes, and challenges.  _Journal of Artificial Intelligence Research_ , 71: 1137–1181.
  * Chi et al. (2021) Chi, J.; Shen, J.; Dai, X.; Zhang, W.; Tian, Y.; and Zhao, H. 2021.  Towards return parity in markov decision processes.  _arXiv preprint arXiv:2111.10476_.
  * Chiappa and Isaac (2018) Chiappa, S.; and Isaac, W. S. 2018.  A causal Bayesian networks viewpoint on fairness.  In _IFIP International Summer School on Privacy and Identity Management_ , 3–20. Springer.
  * Chouldechova and Roth (2018) Chouldechova, A.; and Roth, A. 2018.  The frontiers of fairness in machine learning.  _arXiv preprint arXiv:1810.08810_.
  * Collins (2007) Collins, B. W. 2007.  Tackling unconscious bias in hiring practices: The plight of the Rooney rule.  _NYUL Rev._ , 82: 870.
  * Creager et al. (2020) Creager, E.; Madras, D.; Pitassi, T.; and Zemel, R. 2020.  Causal modeling for fairness in dynamical systems.  In _International Conference on Machine Learning_ , 2185–2195. PMLR.
  * D’Amour et al. (2020) D’Amour, A.; Srinivasan, H.; Atwood, J.; Baljekar, P.; and Halpern, Y. 2020.  Fairness is not static: deeper understanding of long term fairness via simulation studies.  In _Proceedings of the 2020 Conference on Fairness, Accountability, and Transparency_ , 525–534.
  * Desolda et al. (2021) Desolda, G.; Ferro, L. S.; Marrella, A.; Catarci, T.; and Costabile, M. F. 2021.  Human factors in phishing attacks: a systematic literature review.  _ACM Computing Surveys (CSUR)_ , 54(8): 1–35.
  * Dong et al. (2018) Dong, J.; Roth, A.; Schutzman, Z.; Waggoner, B.; and Wu, Z. S. 2018.  Strategic classification from revealed preferences.  In _Proceedings of the 2018 ACM Conference on Economics and Computation_ , 55–70.
  * Duivesteijn and Feelders (2008) Duivesteijn, W.; and Feelders, A. 2008.  Nearest neighbour classification with monotonicity constraints.  In _Machine Learning and Knowledge Discovery in Databases: European Conference, ECML PKDD 2008, Antwerp, Belgium, September 15-19, 2008, Proceedings, Part I 19_ , 301–316. Springer.
  * Dulac-Arnold et al. (2021) Dulac-Arnold, G.; Levine, N.; Mankowitz, D. J.; Li, J.; Paduraru, C.; Gowal, S.; and Hester, T. 2021.  Challenges of real-world reinforcement learning: definitions, benchmarks and analysis.  _Machine Learning_ , 110(9): 2419–2468.
  * Dwork and Ilvento (2018) Dwork, C.; and Ilvento, C. 2018.  Fairness under composition.  _arXiv preprint arXiv:1806.06122_.
  * Elzayn et al. (2019) Elzayn, H.; Jabbari, S.; Jung, C.; Kearns, M.; Neel, S.; Roth, A.; and Schutzman, Z. 2019.  Fair algorithms for learning in allocation problems.  In _Proceedings of the 2019 Conference on Fairness, Accountability, and Transparency_ , 170–179.
  * Ensign et al. (2018) Ensign, D.; Friedler, S. A.; Neville, S.; Scheidegger, C.; and Venkatasubramanian, S. 2018.  Runaway feedback loops in predictive policing.  In _Proceedings of the 2018 Conference on Fairness, Accountability, and Transparency_ , 160–171. PMLR.
  * European Commission (2019) European Commission. 2019.  Ethical Guidelines for Trustworthy AI.  https://ec.europa.eu/newsroom/dae/document.cfm?doc˙id=60419.
  * Ferraro, Serra, and Bauer (2021) Ferraro, A.; Serra, X.; and Bauer, C. 2021.  Break the loop: Gender imbalance in music recommenders.  In _Proceedings of the 2021 conference on human information interaction and retrieval_ , 249–254.
  * Finocchiaro et al. (2021) Finocchiaro, J.; Maio, R.; Monachou, F.; Patro, G. K.; Raghavan, M.; Stoica, A.-A.; and Tsirtsis, S. 2021.  Bridging machine learning and mechanism design towards algorithmic fairness.  In _Proceedings of the 2021 ACM Conference on Fairness, Accountability, and Transparency_ , 489–503.
  * Gajane et al. (2022) Gajane, P.; Saxena, A.; Tavakol, M.; Fletcher, G.; and Pechenizkiy, M. 2022.  Survey on fair reinforcement learning: Theory and practice.  _arXiv preprint arXiv:2205.10032_.
  * Ge et al. (2021) Ge, Y.; Liu, S.; Gao, R.; Xian, Y.; Li, Y.; Zhao, X.; Pei, C.; Sun, F.; Ge, J.; Ou, W.; et al. 2021.  Towards long-term fairness in recommendation.  In _Proceedings of the 14th ACM international conference on web search and data mining_ , 445–453.
  * Gilbert et al. (2023) Gilbert, S.; Harvey, H.; Melvin, T.; Vollebregt, E.; and Wicks, P. 2023.  Large language model AI chatbots require approval as medical devices.  _Nature Medicine_ , 29(10): 2396–2398.
  * Gillen et al. (2018) Gillen, S.; Jung, C.; Kearns, M.; and Roth, A. 2018.  Online learning with an unknown fairness metric.  _Advances in neural information processing systems_ , 31.
  * Gohar, Biswas, and Rajan (2023) Gohar, U.; Biswas, S.; and Rajan, H. 2023.  Towards understanding fairness and its composition in ensemble machine learning.  In _2023 IEEE/ACM 45th International Conference on Software Engineering (ICSE)_ , 1533–1545. IEEE.
  * Gohar and Cheng (2023) Gohar, U.; and Cheng, L. 2023.  A Survey on Intersectional Fairness in Machine Learning: Notions, Mitigation, and Challenges.  _arXiv preprint arXiv:2305.06969_.
  * Gohar et al. (2024) Gohar, U.; Hunter, M. C.; Marczak-Czajka, A.; Lutz, R. R.; Cohen, M. B.; and Cleland-Huang, J. 2024.  Towards Engineering Fair and Equitable Software Systems for Managing Low-Altitude Airspace Authorizations.  _arXiv preprint arXiv:2401.07353_.
  * Grazzi et al. (2022) Grazzi, R.; Akhavan, A.; Falk, J. I.; Cella, L.; and Pontil, M. 2022.  Group meritocratic fairness in linear contextual bandits.  _Advances in Neural Information Processing Systems_ , 35: 24392–24404.
  * Grondman et al. (2012) Grondman, I.; Busoniu, L.; Lopes, G. A.; and Babuska, R. 2012.  A survey of actor-critic reinforcement learning: Standard and natural policy gradients.  _IEEE Transactions on Systems, Man, and Cybernetics, Part C (Applications and Reviews)_ , 42(6): 1291–1307.
  * Gross (2007) Gross, C. 2007.  Community perspectives of wind energy in Australia: The application of a justice and community fairness framework to increase social acceptance.  _Energy Policy_ , 35: 2727–2736.
  * Guldogan et al. (2022) Guldogan, O.; Zeng, Y.; yong Sohn, J.; Pedarsani, R.; and Lee, K. 2022.  Equal Improvability: A New Fairness Notion Considering the Long-term Impact.  _ArXiv_ , abs/2210.06732.
  * Guo et al. (2020) Guo, R.; Cheng, L.; Li, J.; Hahn, P. R.; and Liu, H. 2020.  A survey of learning causality with data: Problems and methods.  _ACM Computing Surveys (CSUR)_ , 53(4): 1–37.
  * Gupta et al. (2019) Gupta, V.; Nokhiz, P.; Roy, C. D.; and Venkatasubramanian, S. 2019.  Equalizing recourse across groups.  _arXiv preprint arXiv:1909.03166_.
  * Hardt and Mendler-Dünner (2023) Hardt, M.; and Mendler-Dünner, C. 2023.  Performative prediction: Past and future.  _arXiv preprint arXiv:2310.16608_.
  * Hashimoto et al. (2018) Hashimoto, T.; Srivastava, M.; Namkoong, H.; and Liang, P. 2018.  Fairness Without Demographics in Repeated Loss Minimization.  In Dy, J.; and Krause, A., eds., _Proceedings of the 35th International Conference on Machine Learning_ , volume 80 of _Proceedings of Machine Learning Research_ , 1929–1938. PMLR.
  * Heidari and Krause (2018) Heidari, H.; and Krause, A. 2018.  Preventing Disparate Treatment in Sequential Decision Making.  In _International Joint Conference on Artificial Intelligence_.
  * Heidari, Nanda, and Gummadi (2019) Heidari, H.; Nanda, V.; and Gummadi, K. 2019.  On the Long-term Impact of Algorithmic Decision Policies: Effort Unfairness and Feature Segregation through Social Learning.  In _36th International Conference on Machine Learning_ , 2692–2701.
  * Henderson et al. (2018) Henderson, P.; Islam, R.; Bachman, P.; Pineau, J.; Precup, D.; and Meger, D. 2018.  Deep reinforcement learning that matters.  In _Proceedings of the AAAI conference on artificial intelligence_ , volume 32.
  * Hu and Chen (2018) Hu, L.; and Chen, Y. 2018.  A short-term intervention for long-term fairness in the labor market.  In _Proceedings of the 2018 World Wide Web Conference_ , 1389–1398.
  * Hu, Immorlica, and Vaughan (2019) Hu, L.; Immorlica, N.; and Vaughan, J. W. 2019.  The disparate effects of strategic manipulation.  In _Proceedings of the Conference on Fairness, Accountability, and Transparency_ , 259–268.
  * Hu and Zhang (2022) Hu, Y.; and Zhang, L. 2022.  Achieving Long-Term Fairness in Sequential Decision Making.  In _AAAI Conference on Artificial Intelligence_.
  * Huan et al. (2020) Huan, W.; Wu, Y.; Zhang, L.; and Wu, X. 2020.  Fairness through equality of effort.  In _Companion Proceedings of the Web Conference 2020_ , 743–751.
  * Jabbari et al. (2017) Jabbari, S.; Joseph, M.; Kearns, M.; Morgenstern, J.; and Roth, A. 2017.  Fairness in reinforcement learning.  In _International conference on machine learning_ , 1617–1626. PMLR.
  * Joseph et al. (2018) Joseph, M.; Kearns, M.; Morgenstern, J.; Neel, S.; and Roth, A. 2018.  Meritocratic fairness for infinite and contextual bandits.  In _Proceedings of the 2018 AAAI/ACM Conference on AI, Ethics, and Society_ , 158–163.
  * Joseph et al. (2016) Joseph, M.; Kearns, M.; Morgenstern, J.; and Roth, A. 2016.  Fairness in Learning: Classic and Contextual Bandits.  In _Neural Information Processing Systems_.
  * Karimi, Schölkopf, and Valera (2021) Karimi, A.-H.; Schölkopf, B.; and Valera, I. 2021.  Algorithmic recourse: from counterfactual explanations to interventions.  In _Proceedings of the 2021 ACM conference on fairness, accountability, and transparency_ , 353–362.
  * Karimi et al. (2020) Karimi, A.-H.; Von Kügelgen, J.; Schölkopf, B.; and Valera, I. 2020.  Algorithmic recourse under imperfect causal knowledge: a probabilistic approach.  _Advances in neural information processing systems_ , 33: 265–277.
  * Kasirzadeh and Evans (2023) Kasirzadeh, A.; and Evans, C. 2023.  User tampering in reinforcement learning recommender systems.  In _Proceedings of the 2023 AAAI/ACM Conference on AI, Ethics, and Society_ , 58–69.
  * Kearns et al. (2018) Kearns, M.; Neel, S.; Roth, A.; and Wu, Z. S. 2018.  Preventing fairness gerrymandering: Auditing and learning for subgroup fairness.  In _International conference on machine learning_ , 2564–2572. PMLR.
  * Kilbertus et al. (2017) Kilbertus, N.; Rojas-Carulla, M.; Parascandolo, G.; Hardt, M.; Janzing, D.; and Schölkopf, B. 2017.  Avoiding discrimination through causal reasoning.  In _Proceedings of the 31st International Conference on Neural Information Processing Systems_ , 656–666.
  * Kusner et al. (2017) Kusner, M. J.; Loftus, J.; Russell, C.; and Silva, R. 2017.  Counterfactual fairness.  In _Advances in Neural Information Processing Systems_ , 4066–4076.
  * Li, Littman, and Walsh (2008) Li, L.; Littman, M. L.; and Walsh, T. J. 2008.  Knows what it knows: a framework for self-aware learning.  In _Proceedings of the 25th international conference on Machine learning_ , 568–575.
  * Li et al. (2023) Li, Y.; Chen, H.; Xu, S.; Ge, Y.; Tan, J.; Liu, S.; and Zhang, Y. 2023.  Fairness in recommendation: Foundations, methods, and applications.  _ACM Transactions on Intelligent Systems and Technology_ , 14(5): 1–48.
  * Liu et al. (2018) Liu, L. T.; Dean, S.; Rolf, E.; Simchowitz, M.; and Hardt, M. 2018.  Delayed impact of fair machine learning.  In _International Conference on Machine Learning_ , 3150–3158. PMLR.
  * Liu et al. (2021) Liu, W.; Liu, F.; Tang, R.; Liao, B.; Chen, G.; and Heng, P.-A. 2021.  Balancing Accuracy and Fairness for Interactive Recommendation with Reinforcement Learning.  _ArXiv_ , abs/2106.13386.
  * Liu et al. (2017) Liu, Y.; Radanovic, G.; Dimitrakakis, C.; Mandal, D.; and Parkes, D. C. 2017.  Calibrated fairness in bandits.  _arXiv preprint arXiv:1707.01875_.
  * Logan IV et al. (2021) Logan IV, R. L.; Balažević, I.; Wallace, E.; Petroni, F.; Singh, S.; and Riedel, S. 2021.  Cutting down on prompts and parameters: Simple few-shot learning with language models.  _arXiv preprint arXiv:2106.13353_.
  * Mahmoud (2008) Mahmoud, H. 2008.  _Pólya urn models_.  Chapman and Hall/CRC.
  * Mehrabi et al. (2021) Mehrabi, N.; Morstatter, F.; Saxena, N.; Lerman, K.; and Galstyan, A. 2021.  A survey on bias and fairness in machine learning.  _ACM computing surveys (CSUR)_ , 54(6): 1–35.
  * Mendler-Dünner et al. (2020) Mendler-Dünner, C.; Perdomo, J. C.; Zrnic, T.; and Hardt, M. 2020.  Stochastic Optimization for Performative Prediction.  _ArXiv_ , abs/2006.06887.
  * Miller, Perdomo, and Zrnic (2021) Miller, J. P.; Perdomo, J. C.; and Zrnic, T. 2021.  Outside the Echo Chamber: Optimizing the Performative Risk.  In Meila, M.; and Zhang, T., eds., _Proceedings of the 38th International Conference on Machine Learning_ , volume 139 of _Proceedings of Machine Learning Research_ , 7710–7720. PMLR.
  * Milli et al. (2019) Milli, S.; Miller, J.; Dragan, A. D.; and Hardt, M. 2019.  The social cost of strategic classification.  In _Proceedings of the Conference on Fairness, Accountability, and Transparency_ , 230–239.
  * Mohler et al. (2015) Mohler, G. O.; Short, M. B.; Malinowski, S.; Johnson, M.; Tita, G. E.; Bertozzi, A. L.; and Brantingham, P. J. 2015.  Randomized controlled field trials of predictive policing.  _Journal of the American Statistical Association_ , 110(512): 1399–1411.
  * Morik et al. (2020) Morik, M.; Singh, A.; Hong, J.; and Joachims, T. 2020.  Controlling fairness and bias in dynamic learning-to-rank.  In _Proceedings of the 43rd international ACM SIGIR conference on research and development in information retrieval_ , 429–438.
  * Nabi and Shpitser (2018) Nabi, R.; and Shpitser, I. 2018.  Fair inference on outcomes.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 32.
  * Organisation for Economic Co-operation and Development (2020) (OECD) Organisation for Economic Co-operation and Development (OECD). 2020.  Tools for Trustworthy AI: A Framework to Compare Implementation Tools for Trustworthy AI Systems.  https://www.oecd.org/going-digital/ai/tools-for-trustworthy-ai-a-framework-to-compare-implementation-tools-for-trustworthy-ai-systems.pdf.
  * Patil et al. (2021) Patil, V.; Ghalme, G.; Nair, V.; and Narahari, Y. 2021.  Achieving fairness in the stochastic multi-armed bandit problem.  _The Journal of Machine Learning Research_ , 22(1): 7885–7915.
  * Patro et al. (2022) Patro, G. K.; Porcaro, L.; Mitchell, L.; Zhang, Q.; Zehlike, M.; and Garg, N. 2022.  Fair ranking: a critical review, challenges, and future directions.  In _Proceedings of the 2022 ACM Conference on Fairness, Accountability, and Transparency_ , FAccT ’22, 1929–1942. New York, NY, USA: Association for Computing Machinery.  ISBN 9781450393522.
  * Pearl (2009) Pearl, J. 2009.  _Causality_.  Cambridge University Press.
  * Perdomo et al. (2020) Perdomo, J.; Zrnic, T.; Mendler-Dünner, C.; and Hardt, M. 2020.  Performative prediction.  In _International Conference on Machine Learning_ , 7599–7609. PMLR.
  * Pessach and Shmueli (2022) Pessach, D.; and Shmueli, E. 2022.  A review on fairness in machine learning.  _ACM Computing Surveys (CSUR)_ , 55(3): 1–44.
  * Puranik, Madhow, and Pedarsani (2022) Puranik, B.; Madhow, U.; and Pedarsani, R. 2022.  A Dynamic Decision-Making Framework Promoting Long-Term Fairness.  In _Proceedings of the 2022 AAAI/ACM Conference on AI, Ethics, and Society_ , AIES ’22, 547–556. New York, NY, USA: Association for Computing Machinery.  ISBN 9781450392471.
  * Roemer and Trannoy (2015) Roemer, J. E.; and Trannoy, A. 2015.  Chapter 4 - Equality of Opportunity.  In Atkinson, A. B.; and Bourguignon, F., eds., _Handbook of Income Distribution_ , volume 2 of _Handbook of Income Distribution_ , 217–300. Elsevier.
  * Saito et al. (2020) Saito, Y.; Yaginuma, S.; Nishino, Y.; Sakata, H.; and Nakata, K. 2020.  Unbiased recommender learning from missing-not-at-random implicit feedback.  In _Proceedings of the 13th International Conference on Web Search and Data Mining_ , 501–509.
  * Shin (2021) Shin, D. 2021.  The effects of explainability and causability on perception, trust, and acceptance: Implications for explainable AI.  _International Journal of Human-Computer Studies_ , 146: 102551.
  * Siddique, Weng, and Zimmer (2020) Siddique, U.; Weng, P.; and Zimmer, M. 2020.  Learning fair policies in multi-objective (deep) reinforcement learning with average and discounted rewards.  In _International Conference on Machine Learning_ , 8905–8915. PMLR.
  * Snyder (2019) Snyder, H. 2019.  Literature review as a research methodology: An overview and guidelines.  _Journal of business research_ , 104: 333–339.
  * Solaiman et al. (2023) Solaiman, I.; Talat, Z.; Agnew, W.; Ahmad, L.; Baker, D.; Blodgett, S. L.; Daumé III, H.; Dodge, J.; Evans, E.; Hooker, S.; et al. 2023.  Evaluating the social impact of generative ai systems in systems and society.  _arXiv preprint arXiv:2306.05949_.
  * Tang, Ho, and Liu (2020) Tang, W.; Ho, C.-J.; and Liu, Y. 2020.  Bandit Learning with Delayed Impact of Actions.  In _Neural Information Processing Systems_.
  * Tang et al. (2023) Tang, Z.; Chen, Y.; Liu, Y.; and Zhang, K. 2023.  Tier Balancing: Towards dynamic fairness over underlying causal factors.  In _International Conference on Learning Representations_.
  * Tang, Zhang, and Zhang (2023) Tang, Z.; Zhang, J.; and Zhang, K. 2023.  What-is and How-to for Fairness in Machine Learning: A Survey, Reflection, and Perspective.  _ACM Computing Surveys_ , 55(13s): 1–37.
  * Tang and Zhang (2022) Tang, Z.; and Zhang, K. 2022.  Attainability and optimality: The equalized odds fairness revisited.  In _Conference on Causal Learning and Reasoning_ , volume 177, 754–786. PMLR.
  * Ustun, Spangher, and Liu (2019) Ustun, B.; Spangher, A.; and Liu, Y. 2019.  Actionable recourse in linear classification.  In _Proceedings of the conference on fairness, accountability, and transparency_ , 10–19.
  * Von Kügelgen et al. (2022) Von Kügelgen, J.; Karimi, A.-H.; Bhatt, U.; Valera, I.; Weller, A.; and Schölkopf, B. 2022.  On the fairness of causal algorithmic recourse.  In _Proceedings of the AAAI conference on artificial intelligence_ , volume 36, 9584–9594.
  * Wang et al. (2021) Wang, L.; Bai, Y.; Sun, W.; and Joachims, T. 2021.  Fairness of exposure in stochastic bandits.  In _International Conference on Machine Learning_ , 10686–10696. PMLR.
  * Weber et al. (2022) Weber, A.; Metevier, B.; Brun, Y.; Thomas, P. S.; and da Silva, B. C. 2022.  Enforcing Delayed-Impact Fairness Guarantees.  _ArXiv_ , abs/2208.11744.
  * Wen, Bastani, and Topcu (2021) Wen, M.; Bastani, O.; and Topcu, U. 2021.  Algorithms for fairness in sequential decision making.  In _International Conference on Artificial Intelligence and Statistics_ , 1144–1152. PMLR.
  * Weymark (1981) Weymark, J. A. 1981.  Generalized Gini inequality indices.  _Mathematical Social Sciences_ , 1(4): 409–430.
  * Xu et al. (2023) Xu, Y.; Deng, C.; Sun, Y.; Zheng, R.; Wang, X.; Zhao, J.; and Huang, F. 2023.  Equal Long-term Benefit Rate: Adapting Static Fairness Notions to Sequential Decision Making.  _arXiv preprint arXiv:2309.03426_.
  * Yang and Ai (2021) Yang, T.; and Ai, Q. 2021.  Maximizing Marginal Fairness for Dynamic Learning to Rank.  _Proceedings of the Web Conference 2021_.
  * Yin et al. (2023) Yin, T.; Raab, R.; Liu, M.; and Liu, Y. 2023.  Long-Term Fairness with Unknown Dynamics.  _arXiv preprint arXiv:2304.09362_.
  * Zamfirescu-Pereira et al. (2023) Zamfirescu-Pereira, J.; Wong, R. Y.; Hartmann, B.; and Yang, Q. 2023.  Why Johnny can’t prompt: how non-AI experts try (and fail) to design LLM prompts.  In _Proceedings of the 2023 CHI Conference on Human Factors in Computing Systems_ , 1–21.
  * Zhang et al. (2021) Zhang, C.; Chen, Y.; D’Haro, L. F.; Zhang, Y.; Friedrichs, T.; Lee, G.; and Li, H. 2021.  DynaEval: Unifying Turn and Dialogue Level Evaluation.  In Zong, C.; Xia, F.; Li, W.; and Navigli, R., eds., _Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing (Volume 1: Long Papers)_ , 5676–5689. Online: Association for Computational Linguistics.
  * Zhang and Liu (2021) Zhang, X.; and Liu, M. 2021.  Fairness in learning-based sequential decision algorithms: A survey.  In _Handbook of Reinforcement Learning and Control_ , 525–555. Springer.
  * Zhang et al. (2020) Zhang, X.; Tu, R.; Liu, Y.; Liu, M.; Kjellstrom, H.; Zhang, K.; and Zhang, C. 2020.  How do fair decisions fare in long-term qualification?  _Advances in Neural Information Processing Systems_ , 33: 18457–18469.

##  Appendix A Survey Methodology

We employed several established approaches to conduct a comprehensive search
for relevant papers under the umbrella of long-term fairness. Initially, we
curated a set of seed papers that have discussed and evaluated long-term
fairness problems (Zhang and Liu 2021; Liu et al. 2018; Hu and Chen 2018;
D’Amour et al. 2020; Zhang and Liu 2021; Zhang et al. 2020). Following common
practice (Desolda et al. 2021; Snyder 2019), we used these papers and domain
knowledge to identify and develop a set of keywords to search for relevant
work: “long-term fairness,” “dynamic fairness,” “(non-)static fairness,” and
“sequential fairness.” Primarily, we searched proceedings of relevant
conferences and journals that were likely to publish work that fit the
definition of long-term fairness. These included but were not limited to
FAccT, NeurIPS, AAAI, ICML, AIES, ICLR, and IJCAI. We also followed citation
trails to and from these widely cited papers and querying across Google
Scholar and Arxiv to identify additional related work.

Framework | Symbols | Description
---|---|---
Classification | $f$ | A decision model parameterized by a vector $\theta\in\Theta$
$x$ |  $x\in\mathcal{X}$ $\subseteq\mathbb{R}^{d}$ input features
$y$ |  $y\in\mathcal{Y}=\\{0,1\\}$ ground truth label
$g$ |  $g\in\mathcal{G}$ sensitive groups
| $\Delta x$ | Effort (change) required to improve the feature $x$ to $x^{\prime}$
MDP | $S$ | State Space (e.g., income levels)
$\mathcal{A}$ | Action space (e.g., accept/reject)
$R$ |  $R:S\times A\rightarrow\mathbb{R}$ reward function (e.g., bank’s profits)
$\rho$ | Initial state distribution
$\mathbf{T}$ |  $\mathbf{T}:S\times A\rightarrow\Delta(S)$ State transition function
$\gamma$ | Discount factor
$\pi$ |  $\pi:S\rightarrow\Delta(A)$ is policy
| $\eta(\pi)$ | Cumulative Reward
MAB | $\mathcal{K}$ | Set of arms
$t$ | Time step
$A_{t}$ |  $A_{t}\in\mathcal{K}$ action (arm) selected at time $t$
$R_{t}$ | Stochastic reward at time $t$.
Table 2: Table of Notations