# Graph Learning from Multivariate Dependent Time Series via a Multi-Attribute
Formulation

###### Abstract

We consider the problem of inferring the conditional independence graph (CIG)
of a high-dimensional stationary multivariate Gaussian time series. In a time
series graph, each component of the vector series is represented by distinct
node, and associations between components are represented by edges between the
corresponding nodes. We formulate the problem as one of multi-attribute graph
estimation for random vectors where a vector is associated with each node of
the graph. At each node, the associated random vector consists of a time
series component and its delayed copies. We present an alternating direction
method of multipliers (ADMM) solution to minimize a sparse-group lasso
penalized negative pseudo log-likelihood objective function to estimate the
precision matrix of the random vector associated with the entire multi-
attribute graph. The time series CIG is then inferred from the estimated
precision matrix. A theoretical analysis is provided. Numerical results
illustrate the proposed approach which outperforms existing frequency-domain
approaches in correctly detecting the graph edges.

Keywords: Sparse graph learning; graph estimation; time series; undirected
graph; multi-attribute graphs.

##  1 Introduction

Graphical models are an important and useful tool for analyzing multivariate
data [2]. Given a collection of random variables, one wishes to assess the
relationship between two variables, conditioned on the remaining variables. In
graphical models, graphs are used to display the conditional independence
structure of the variables. Consider a graph ${\cal G}=\left(V,{\cal
E}\right)$ with a set of $p$ vertices (nodes) $V=\\{1,2,\cdots,p\\}=[p]$, and
a corresponding set of (undirected) edges ${\cal E}\subseteq[p]\times[p]$.
Also consider a stationary (real-valued), zero-mean, $p-$dimensional
multivariate Gaussian time series ${\bm{x}}(t)$, $t=0,\pm 1,\pm 2,\cdots$,
with $i$th component $x_{i}(t)$. Given $\\{{\bm{x}}(t)\\}$, in the
corresponding graph ${\cal G}$, each component series $\\{x_{i}(t)\\}$ is
represented by a node ($i$ in $V$), and associations between components
$\\{x_{i}(t)\\}$ and $\\{x_{j}(t)\\}$ are represented by edges between nodes
$i$ and $j$ of ${\cal G}$. In a conditional independence graph (CIG), there is
no edge between nodes $i$ and $j$ if and only if (iff) $x_{i}(t)$ and
$x_{j}(t)$ are conditionally independent given the remaining $p$-$2$ scalar
series $x_{\ell}(t)$, $\ell\in[p]$, $\ell\neq i$, $\ell\neq j$ [3].

Graphical models were originally developed for random vectors (whose
statistics are estimated via multiple independent realizations) [4, p. 234].
Such models have been extensively studied, and found to be useful in a wide
variety of applications [5, 6, 7, 8, 9]. Graphical modeling of real-valued
time-dependent data (stationary time series) originated with [10], followed by
[3]. A key insight in [3] was to transform the series to the frequency domain
and express the graph relationships in the frequency domain. Nonparametric
approaches for graphical modeling of real time series in high-dimensional
settings ($p$ is large and/or sample size $n$ is of the order of $p$) have
been formulated in the form of group-lasso penalized log-likelihood in
frequency-domain in [11]. Sparse-group lasso penalized log-likelihood approach
in frequency-domain has been considered in [12, 13, 14].

In this paper we investigate graph structure estimation for stationary
Gaussian multivariate time series using a time-domain approach, unlike [11,
12, 13] who, as noted earlier, use a frequency-domain approach. After
reviewing some graphical modeling background in Sec. 2, we first reformulate
the problem in Sec. 3 as one of multi-attribute graph estimation for random
vectors where a vector is associated with each node of the graph. Then in Sec.
4 we exploit the results of [15] to provide an alternating direction method of
multipliers (ADMM) solution to minimize a sparse-group lasso penalized
negative pseudo log-likelihood objective function for multi-attribute graph
precision matrix estimation. A theoretical analysis is provided in Sec. 5.
Numerical results in Sec. 6 illustrate the proposed approach.

Notation: We use ${\bm{S}}\succeq 0$ and ${\bm{S}}\succ 0$ to denote that the
symmetric matrix ${\bm{S}}$ is positive semi-definite and positive definite,
respectively. For a set $V$, $|V|$ or $\mbox{card}(V)$ denotes its
cardinality. $\mathbb{Z}$ is the set of integers. Given
${\bm{A}}\in\mathbb{R}^{p\times p}$, we use $\phi_{\min}({\bm{A}})$,
$\phi_{\max}({\bm{A}})$, $|{\bm{A}}|$ and $\mbox{tr}({\bm{A}})$ to denote the
minimum eigenvalue, maximum eigenvalue, determinant and trace of ${\bm{A}}$,
respectively. For ${\bm{B}}\in\mathbb{R}^{p\times q}$, we define
$\|{\bm{B}}\|=\sqrt{\phi_{\max}({\bm{B}}^{\top}{\bm{B}})}$,
$\|{\bm{B}}\|_{F}=\sqrt{\mbox{tr}({\bm{B}}^{\top}{\bm{B}})}$ and
$\|{\bm{B}}\|_{1}=\sum_{i,j}|B_{ij}|$, where $B_{ij}$ is the $(i,j)$-th
element of ${\bm{B}}$ (also denoted by $[{\bm{B}}]_{ij}$). Given
${\bm{A}}\in\mathbb{R}^{p\times p}$, ${\bm{A}}^{+}=\mbox{diag}({\bm{A}})$ is a
diagonal matrix with the same diagonal as ${\bm{A}}$, and
${\bm{A}}^{-}={\bm{A}}-{\bm{A}}^{+}$ is ${\bm{A}}$ with all its diagonal
elements set to zero.

##  2 Graphical Models

Here we provide some background material for graphical models for random
vectors and for multivariate time series.

###  2.1 Random Vectors

Consider a graph ${\cal G}=\left(V,{\cal E}\right)$ with a set of $p$ vertices
(nodes) $V=\\{1,2,\cdots,p\\}=[p]$, and a corresponding set of (undirected)
edges ${\cal E}\subseteq V\times V$. Let
${\bm{x}}=[x_{1}\;x_{2}\;\cdots\;x_{p}]^{\top}\in\mathbb{R}^{p}$ denote a
Gaussian random vector that is zero-mean with covariance
${\bm{\Sigma}}=E\\{{\bm{x}}{\bm{x}}^{\top}\\}\succ{\bm{0}}$. The conditional
independence relationships among $x_{i}$’s are encoded in ${\cal E}$ where
edge $\\{i,j\\}$ between nodes $i$ and $j$ exists if and only if (iff) $x_{i}$
and $x_{j}$ are conditionally dependent given the remaining $p$-$2$ variables
$x_{\ell}$, $\ell\in[p]$, $\ell\neq i$, $\ell\neq j$. Let

${\bm{x}}_{-ij}=\\{x_{k}\,:\,k\in
V\textbackslash\\{i_{,}j\\}\\}\in\mathbb{R}^{p-2}$ (1)

denote the vector ${\bm{x}}$ after deleting $x_{i}$ and $x_{j}$ from it. Let
$\bm{\Omega}=\bm{\Sigma}^{-1}$ denote the precision matrix. Define

$e_{i|-ij}=x_{i}-E\\{x_{i}|{\bm{x}}_{-ij}\\}\,,\;\;e_{j|-ij}=x_{j}-E\\{x_{j}|{\bm{x}}_{-ij}\\}\,.$
(2)

Then we have the following equivalence [2]

$\\{i,j\\}\not\in{\cal
E}\;\Leftrightarrow\;\Omega_{ij}=0\;\Leftrightarrow\;E\\{e_{i|-ij}e_{j|-ij}\\}=0\,.$
(3)

Note that $E\\{x_{i}|{\bm{x}}_{-ij}\\}$ is linear in ${\bm{x}}_{-ij}$ since
${\bm{x}}$ is zero-mean Gaussian, and furthermore it minimizes the conditional
mean-square error

$E\\{x_{i}|{\bm{x}}_{-ij}\\}=\arg\min_{b}E\\{(x_{i}-b({\bm{x}}_{-ij}))^{2}|{\bm{x}}_{-ij}\\}\,.$
(4)

Similar comments apply to $E\\{x_{j}|{\bm{x}}_{-ij}\\}$.

###  2.2 Multivariate Time Series

Consider stationary Gaussian time series ${\bm{x}}(t)\in\mathbb{R}^{p}$,
$t\in\mathbb{Z}$, with $E\\{{\bm{x}}(t)\\}=0$ and
${\bm{R}}_{xx}(\tau)=\mathbb{E}\\{{\bm{x}}(t+\tau){\bm{x}}^{T}(t)\\}$,
$\tau\in\mathbb{Z}$. The conditional independence relationships among time
series components $\\{x_{i}(t)\\}$’s are encoded in edge set ${\cal E}$ of
${\cal G}=\left(V,{\cal E}\right)$, $V=[p]$, ${\cal E}\subseteq V\times V$,
where edge $\\{i,j\\}\not\in{\cal E}$ iff $\\{x_{i}(t),\,t\in\mathbb{Z}\\}$
and $\\{x_{j}(t),\,t\in\mathbb{Z}\\}$ are conditionally independent given the
remaining $p$-$2$ components

${\bm{x}}_{-ij,\mathbb{Z}}=\\{x_{k}(t)\,:\,k\in
V\textbackslash\\{i_{,}j\\},\,t\in\mathbb{Z}\\}\,.$ (5)

Define

$\displaystyle e_{i|-ij}(t)=$ $\displaystyle
x_{i}(t)-E\\{x_{i}(t)|{\bm{x}}_{-ij,\mathbb{Z}}\\}$ (6) $\displaystyle
e_{j|-ij}(t)=$ $\displaystyle
x_{j}(t)-E\\{x_{j}(t)|{\bm{x}}_{-ij,\mathbb{Z}}\\}\,,$ (7)

and the power spectral density (PSD) matrix ${\bm{S}}_{x}(f)$

${\bm{S}}_{x}(f)=\sum_{\tau=-\infty}^{\infty}{\bm{R}}_{xx}(\tau)e^{-j2\pi
f\tau}\,.$ (8)

Then we have the following equivalence [3]

$\displaystyle\\{i,j\\}\not\in{\cal E}$
$\displaystyle\;\Leftrightarrow\;[{\bm{S}}_{x}^{-1}(f)]_{ij}=0\;\forall
f\in[0,1]$
$\displaystyle\;\Leftrightarrow\;E\\{e_{i|-ij}(t+\tau)e_{j|-ij}(t)\\}=0\;\forall\tau\in\mathbb{Z}\,.$
(9)

###  2.3 Multi-Attribute Graphical Models for Random Vectors

Now consider $p$ jointly Gaussian vectors ${\bm{z}}_{i}\in\mathbb{R}^{m}$,
$i\in[p]$. We associate ${\bm{z}}_{i}$ with the $i$th node of graph ${\cal
G}=\left(V,{\cal E}\right)$, $V=[p]$, ${\cal E}\subseteq V\times V$. We now
have $m$ attributes per node. Now $\\{i,j\\}\not\in{\cal E}$ iff vectors
${\bm{z}}_{i}$ and ${\bm{z}}_{j}$ are conditionally independent given the
remaining $p$-$2$ vectors $\\{{\bm{z}}_{\ell}\,,\ell\in
V\textbackslash\\{i_{,}j\\}\\}$. Let

${\bm{x}}=[{\bm{z}}_{1}^{\top}\;{\bm{z}}_{2}^{\top}\;\cdots\;{\bm{z}}_{p}^{\top}]^{\top}\in\mathbb{R}^{mp}\,.$
(10)

Let ${\bm{\Omega}}=(E\\{{\bm{x}}{\bm{x}}^{\top}\\})^{-1}$ assuming
$E\\{{\bm{x}}{\bm{x}}^{\top}\\}\succ{\bm{0}}$. Define the $m\times m$ subblock
${\bm{\Omega}}^{(ij)}$ of ${\bm{\Omega}}$ as

$[{\bm{\Omega}}^{(ij)}]_{rs}=[{\bm{\Omega}}]_{(i-1)m+r,(j-1)m+s}\,,\;r,s=1,2,\cdots,m\,.$
(11)

Let

${\bm{z}}_{-ij}=\\{{\bm{z}}_{k}\,:\,k\in
V\textbackslash\\{i_{,}j\\}\\}\in\mathbb{R}^{m(p-2)}$ (12)

denote the vector ${\bm{x}}$ in (10) after deleting vectors ${\bm{z}}_{i}$ and
${\bm{z}}_{j}$ from it. Define

${\bm{e}}_{i|-ij}={\bm{z}}_{i}-E\\{{\bm{z}}_{i}|{\bm{z}}_{-ij}\\}\,,\;\;{\bm{e}}_{j|-ij}={\bm{z}}_{j}-E\\{{\bm{z}}_{j}|{\bm{z}}_{-ij}\\}\,.$
(13)

Then we have the following equivalence [16]

$\\{i,j\\}\not\in{\cal
E}\;\Leftrightarrow\;{\bm{\Omega}}^{(ij)}={\bm{0}}\;\Leftrightarrow\;E\\{{\bm{e}}_{i|-ij}{\bm{e}}_{j|-ij}^{\top}\\}={\bm{0}}\,,$
(14)

where the first equivalence in (14) is given in [16, Sec. 2.1] and the second
equivalence is given in [16, Appendix B.3].

##  3 Multi-Attribute Formulation for Time Series Graphical Modeling

Consider time series $\\{\bm{x}(t)\\}$ as in Sec. 2.2. For some $d\geq 1$, let

$\displaystyle{\bm{z}}_{i}(t)=$
$\displaystyle[x_{i}(t)\;x_{i}(t-1)\;\cdots\;x_{i}(t-d)]^{\top}\in\mathbb{R}^{d+1}$
(15) $\displaystyle{\bm{y}}(t)=$
$\displaystyle[{\bm{z}}_{1}^{\top}(t)\;{\bm{z}}_{2}^{\top}(t)\;\cdots\;{\bm{z}}_{p}^{\top}(t)]^{\top}\in\mathbb{R}^{(d+1)p}\,.$
(16)

Let ${\bm{\Omega}}_{y}=(E\\{{\bm{y}}(t){\bm{y}}^{\top}(t)\\})^{-1}$. With
$m=d+1$, define the $m\times m$ subblock ${\bm{\Omega}}_{y}^{(ij)}$ of
${\bm{\Omega}}_{y}$ as

$[{\bm{\Omega}}_{y}^{(ij)}]_{rs}=[{\bm{\Omega}}_{y}]_{(i-1)m+r,(j-1)m+s}\,,\;s,t=1,2,\cdots,m\,.$
(17)

Let

${\bm{z}}_{-ij}(t)=\\{{\bm{z}}_{k}(t)\,:\,k\in
V\textbackslash\\{i_{,}j\\}\\}\,,$ (18) $\displaystyle{\bm{e}}_{i|-ij}(t)=$
$\displaystyle{\bm{z}}_{i}(t)-E\\{{\bm{z}}_{i}(t)|{\bm{z}}_{-ij}(t)\\}$ (19)
$\displaystyle{\bm{e}}_{j|-ij}(t)=$
$\displaystyle{\bm{z}}_{j}(t)-E\\{{\bm{z}}_{j}(t)|{\bm{z}}_{-ij}(t)\\}\,.$
(20)

Then by Sec. 2.3,

$\\{i,j\\}\not\in{\cal
E}\;\Leftrightarrow\;{\bm{\Omega}}_{y}^{(ij)}={\bm{0}}\,.$ (21)

Define

$\tilde{\bm{x}}_{-ij;t,d}=\\{{\bm{x}}_{k}(s)\,:\,k\in
V\textbackslash\\{i_{,}j\\}\,,t-d\leq s\leq t\\}\,,$ (22) $\displaystyle
e_{xi|-ij}(t^{\prime})=$ $\displaystyle
x_{i}(t^{\prime})-E\\{x_{i}(t^{\prime})|\tilde{\bm{x}}_{-ij;t,d}\\}$ (23)
$\displaystyle e_{xj|-ij}(t^{\prime})=$ $\displaystyle
x_{j}(t^{\prime})-E\\{x_{j}(t^{\prime})|\tilde{\bm{x}}_{-ij;t,d}\\}\,.$ (24)

Notice that $e_{xi|-ij}(t^{\prime})$ above is an element of
${\bm{e}}_{i|-ij}(t)$ defined in (19) for any $t-d\leq t^{\prime}\leq t$. Then
by (14) and (21), we have

${\bm{\Omega}}_{y}^{(ij)}={\bm{0}}\;\Leftrightarrow\;E\\{e_{xi|-ij}(t_{1})e_{xj|-ij}(t_{2})\\}=0,\;\;t-d\leq
t_{1},t_{2}\leq t.$ (25)

It follow from (25) that if we let $d\uparrow\infty$, then checking if
${\bm{\Omega}}_{y}^{(ij)}={\bm{0}}$ to ascertain (21) becomes a surrogate for
checking if the last equivalence in (9) holds true for time series graph
structure estimation without using frequency-domain methods.

##  4 Sparse-Group Graphical Lasso Solution to Multi-Attribute Formulation

We now consider a finite set of data comprised of $n$ zero-mean observations
${\bm{x}}(t)$, $t=0,1,2,\cdots,n-1$. Pick $d>1$ and as in (16), construct
${\bm{y}}(t)$ for $t=d,d+1,\cdots,n-1$ with sample size $\bar{n}=n-d$. Define
the sample covariance
$\hat{\bm{\Sigma}}_{y}=\frac{1}{\bar{n}}\sum_{t=d}^{n-1}{\bm{y}}(t){\bm{y}}^{\top}(t)$.
If the vector sequence $\\{{\bm{y}}(t)\\}_{t=d}^{n-1}$ were i.i.d., the log-
likelihood (up to some constants) would be given by
$\ln(|\bm{\Omega}_{y}|)-{\rm tr}(\hat{\bm{\Sigma}}_{y}\bm{\Omega}_{y})$ [15].
In our case the sequence is not i.i.d., but we will still use this expression
as a pseudo log-likelihood and following [15], consider the penalized negative
pseudo log-likelihood

$\displaystyle L_{SGL}({\bm{\Omega}}_{y})=-\ln(|\bm{\Omega}_{y}|)+{\rm
tr}(\hat{\bm{\Sigma}}_{y}\bm{\Omega}_{y})+P(\bm{\Omega}_{y}),$ (26)
$\displaystyle
P(\bm{\Omega}_{y})=\alpha\lambda\,\|\bm{\Omega}_{y}^{-}\|_{1}+(1-\alpha)\lambda\sum_{j\neq
k}^{p}\|\bm{\Omega}_{y}^{(jk)}\|_{F}\,,$ (27)

where $P(\bm{\Omega}_{y})$ is a sparse-group lasso penalty [5, 15, 17, 18],
with group lasso penalty $(1-\alpha)\lambda\sum_{j\neq
k}^{p}\|\bm{\Omega}_{y}^{(jk)}\|_{F}$, $\lambda>0$ and lasso penalty
$\alpha\lambda\,\|\bm{\Omega}_{y}^{-}\|_{1}$, $\lambda>0$ is a tuning
parameter, and $0\leq\alpha\leq 1$ yields a convex combination of lasso and
group lasso penalties. The function $L_{SGL}({\bm{\Omega}}_{y})$ is strictly
convex in ${\bm{\Omega}}_{y}\succ{\bm{0}}$.

As in [15], we use the ADMM approach [19] with variable splitting. Using
variable splitting, consider

$\displaystyle\min_{\bm{\Omega}_{y}\succ{\bm{0}},{\bm{W}}}$
$\displaystyle\Big{\\{}{\rm
tr}(\hat{\bm{\Sigma}}_{y}\bm{\Omega}_{y})-\ln(|\bm{\Omega}_{y}|)+P({\bm{W}})\Big{\\}}\mbox{
subject to }\bm{\Omega}_{y}={\bm{W}}\,.$ (28)

The scaled augmented Lagrangian for this problem is [19]

$\displaystyle L_{\rho}={\rm
tr}(\hat{\bm{\Sigma}}_{y}\bm{\Omega}_{y})-\ln(|\bm{\Omega}_{y}|)+P({\bm{W}})+\frac{\rho}{2}\|\bm{\Omega}_{y}-{\bm{W}}+{\bm{U}}\|^{2}_{F}$
(29)

where ${\bm{U}}$ is the dual variable, and $\rho>0$ is the penalty parameter.
Given the results $\bm{\Omega}^{(i)},{\bm{W}}^{(i)},{\bm{U}}^{(i)}$ of the
$i$th iteration, in the $(i+1)$st iteration, an ADMM algorithm executes the
following three updates:

  * (a)

$\bm{\Omega}_{y}^{(i+1)}\leftarrow\arg\min_{\bm{\Omega}_{y}}\,L_{a}(\bm{\Omega}_{y}),\;\;L_{a}(\bm{\Omega}_{y}):={\rm
tr}(\hat{\bm{\Sigma}}_{y}\bm{\Omega}_{y})-\ln(|\bm{\Omega}_{y}|)+\frac{\rho}{2}\|\bm{\Omega}_{y}-{\bm{W}}^{(i)}+{\bm{U}}^{(i)}\|^{2}_{F}$

  * (b)

${\bm{W}}^{(i+1)}\leftarrow\arg\min_{{\bm{W}}}L_{b}({\bm{W}}),\;\;L_{b}({\bm{W}}):=\alpha\lambda\,\|{\bm{W}}^{-}\|_{1}+(1-\alpha)\lambda\sum_{i\neq
j}^{p}\|{\bm{W}}^{(ij)}\|_{F}+\frac{\rho}{2}\|\bm{\Omega}_{y}^{(i+1)}-{\bm{W}}+{\bm{U}}^{(i)}\|^{2}_{F}$

  * (c)

${\bm{U}}^{(i+1)}\leftarrow{\bm{U}}^{(i)}+\left(\bm{\Omega}_{y}^{(i+1)}-{\bm{W}}^{(i+1)}\right)$

Remark 1. We follow the detailed ADMM algorithm given in [15] for the above
updates; details may be found therein (where we need to replace
${\bm{\Omega}}$ with ${\bm{\Omega}}_{y}$). The parameter tuning (selection of
$\lambda$ and $\alpha$) approach given in [15] does not apply (strictly
speaking) in our case since our $\\{{\bm{y}}(t)\\}$ is not an i.i.d. sequence.
$\quad\Box$

##  5 Theoretical Analysis

In this section we analyze consistency (Theorem 1) by invoking some results
from [15]. The difference from [15] is that while the observations in [15] are
i.i.d., here $\\{{\bm{x}}(t)\\}$, and $\\{{\bm{y}}(t)\\}$ constructed from it,
are dependent sequences. Therefore, we need a model for this dependence. This
influences concentration inequality regarding convergence of sample covariance
$\hat{\bm{\Sigma}}$. Once this aspect is accounted for, [15, Theorem 1]
applies immediately.

To quantify the dependence structure of $\\{{\bm{x}}(t)\\}$, we will follow
[20]; other possibilities include [21, 22].

  * (A0)

Assume $\\{{\bm{x}}(t)\\}$ obeys

${\bm{x}}(t)=\sum_{i=0}^{\infty}{\bm{A}}_{i}{\bm{e}}(t-i)\,,$ (30)

where $\\{{\bm{e}}(t)\\}$ is i.i.d., Gaussian, zero-mean with identity
covariance, ${\bm{e}}(t)\in\mathbb{R}^{p}$,
$\,{\bm{A}}_{i}\in\mathbb{R}^{p\times p}$, and

$\max_{1\leq q\leq
p}\sqrt{\sum_{k=1}^{p}([{\bm{A}}_{i}]_{qk})^{2}}\leq\frac{c_{a}}{(\max(1,i))^{\gamma}}$
(31)

for all $i\geq 0$, some $c_{a}\in(0,\infty)$, and $\gamma>1$.

Assumption (A0) is satisfied if ${\bm{x}}(t)$ is generated by an
asymptotically stable vector ARMA (autoregressive moving average) model with
distinct “poles,” satisfying
${\bm{x}}(t)=-\sum_{i=1}^{q}{\bm{\Phi}}_{i}{\bm{x}}(t-i)+\sum_{i=0}^{r}{\bm{\Psi}}_{i}{\bm{e}}(t-i)$,
because in that case $\|{\bm{A}}_{i}\|_{F}\leq a|\lambda_{0}|^{i}$ for some
$0<a<\infty$ where $|\lambda_{0}|<1$ is the largest magnitude “pole” (root of
$c(z):=\big{|}{\bm{I}}+\sum_{i=1}^{q}{\bm{\Phi}}_{i}z^{-i}\big{|}=0$) of the
model. It can be shown that there exist $0<b<\infty$ and $1<\gamma<\infty$
such that $a|\lambda_{0}|^{i}\leq b\,i^{-\gamma}$ for $i\geq 1$, thereby
satisfying assumption (A0).

By Assumption (A0), it follows that
${\bm{y}}(t)=\sum_{i=0}^{\infty}{\bm{B}}_{i}\bar{\bm{e}}(t-i)$,
$\bar{\bm{e}}(t)\in\mathbb{R}^{mp}$ is i.i.d., Gaussian, zero-mean with
identity covariance, $m=d+1$, $\,{\bm{B}}_{i}\in\mathbb{R}^{(mp)\times(mp)}$,
for some ${\bm{B}}_{i}$’s such that

$\max_{1\leq q\leq
mp}\sqrt{\sum_{k=1}^{mp}([{\bm{B}}_{i}]_{qk})^{2}}\leq\frac{{c}_{a}}{(\max(1,i))^{\gamma}}$
(32)

for all $i\geq 0$, with ${c}_{a}$, and $\gamma$ as in Assumption (A0). Then we
have Lemma 1, following [20, Lemma VI.2, supplementary] for the case
$\gamma>1$ ($\gamma$ is called $\beta$ in [20]).
Lemma 1: Under Assumption (A0), the sample covariance $\hat{\bm{\Sigma}}_{y}$
satisfies the tail bound

$P\left(\Big{|}[\hat{\bm{\Sigma}}_{y}-\bm{\Sigma}_{y0}]_{kl}\Big{|}\geq\delta\right)\leq
2\,\exp(-C_{u}\bar{n}\min(\delta^{2},\delta))$ (33)

for any $\delta>0$ and for any $k,l$, where $C_{u}\in(0,\infty)$ is an
absolute (universal) constant. $\quad\bullet$
Constant $C_{u}$ results from the application of the Hanson-Wright inequality
[23].

In rest of this section we allow $p$ and $\lambda$ to be a functions of sample
size $n$, denoted as $p_{n}$ and $\lambda_{n}$, respectively. Lemma 1 leads to
Lemma 2.
Lemma 2: Under Assumption (A0), the sample covariance $\hat{\bm{\Sigma}}_{y}$
satisfies the tail bound

$P\left(\max_{k,l}\Big{|}[\hat{\bm{\Sigma}}_{y}-\bm{\Sigma}_{y0}]_{kl}\Big{|}>C_{0}\sqrt{\frac{\ln(mp_{n})}{\bar{n}}}\right)\leq\frac{1}{(mp_{n})^{\tau-2}}$
(34)

for $\tau>2$, if the sample size
$\bar{n}=n-d>N_{1}=\ln(2(mp_{n})^{\tau})/C_{u}$, where $m=d+1$ and
$C_{0}=\sqrt{N_{1}/\ln(mp_{n})}$. $\quad\bullet$

Lemma 2 above replaces [15, Lemma 2] for dependency in observations. Further
assume

  * (A1)

Let $\bm{\Sigma}_{y0}=E\\{{\bm{y}}(t){\bm{y}}^{\top}(t)\\}\succ{\bm{0}}$
denote the true covariance of ${\bm{y}}(t)$. Define ${\cal
E}_{y0}=\\{\\{i,j\\}~{}:~{}{\bm{\Omega}}_{y0}^{(ij)}\neq{\bm{0}},~{}i\neq
j\\}$ where $\bm{\Omega}_{y0}=\bm{\Sigma}_{y0}^{-1}$. Assume that card$({\cal
E}_{y0})=|({\cal E}_{0})|\leq s_{n0}$.

  * (A2)

The minimum and maximum eigenvalues of $\bm{\Sigma}_{y0}$ satisfy

$0<\beta_{\min}\leq\phi_{\min}(\bm{\Sigma_{y0}})\leq\phi_{\max}(\bm{\Sigma_{y0}})\leq\beta_{\max}<\infty\,.$

Here $\beta_{\min}$ and $\beta_{\max}$ are not functions of $n$.

Let
$\hat{\bm{\Omega}}_{y\lambda}=\arg\min_{\bm{\Omega}_{y}\succ{\bm{0}}}L_{SGL}({\bm{\Omega}}_{y})$.
Theorem 1 establishes consistency of $\hat{\bm{\Omega}}_{y\lambda}$ and it
follows by replacing [15, Lemma 2] with Lemma 2 of this paper in the proof of
[15, Theorem 1].
Theorem 1 (Consistency): For $\tau>2$, let $m=d+1$ and

$C_{0}=\sqrt{\ln(2(mp_{n})^{\tau})/(C_{u}\ln(mp_{n}))}\,.$ (35)

Given real numbers $\delta_{1}\in(0,1)$, $\delta_{2}>0$ and $C_{1}>0$, let
$C_{2}=\sqrt{m}+1+C_{1}$, and

$\displaystyle M=$
$\displaystyle(1+\delta_{1})^{2}(2C_{2}+\delta_{2})C_{0}/\beta_{\min}^{2},$
(36) $\displaystyle r_{n}=$
$\displaystyle\sqrt{\frac{(mp_{n}+m^{2}s_{n0})\ln(mp_{n})}{\bar{n}}}=o(1)\,,$
(37) $\displaystyle N_{1}=$ $\displaystyle\ln(2(mp_{n})^{\tau})/C_{u},$ (38)
$\displaystyle N_{2}=$
$\displaystyle\arg\min\left\\{\bar{n}\,:\,r_{n}\leq\frac{\delta_{1}\beta_{\min}}{(1+\delta_{1})^{2}(2C_{2}+\delta_{2})C_{0}}\right\\}\,.$
(39)

Suppose the regularization parameter $\lambda_{n}$ and $\alpha\in[0,1]$
satisfy

$\displaystyle\frac{C_{1}C_{0}}{1+\alpha(m-1)}\sqrt{\Big{(}1+\frac{p_{n}}{ms_{n0}}\Big{)}\frac{\ln(mp_{n})}{\bar{n}}}$
$\displaystyle\geq\frac{\lambda_{n}}{m}$ $\displaystyle\geq
C_{0}\sqrt{\frac{\ln(mp_{n})}{\bar{n}}}\,.$ (40)

Then if the sample size $\bar{n}=n-d>\max\\{N_{1},N_{2}\\}$ and assumptions
(A0)-(A2) hold true, $\hat{\bm{\Omega}}_{y\lambda}$ satisfies

$\|\hat{\bm{\Omega}}_{y\lambda}-\bm{\Omega}_{y0}\|_{F}\leq Mr_{n}$ (41)

with probability greater than $1-1/(mp_{n})^{\tau-2}$. In terms of rate of
convergence, $\|\hat{\bm{\Omega}}_{y\lambda}-\bm{\Omega}_{y0}\|_{F}={\cal
O}_{P}\left(r_{n}\right)$ $\quad\bullet$

Fig. 1: $F_{1}$-scores based on 100 runs for 4 approaches. In the proposed
approach lag=3 refers to $d=3$. IID model may be viewed as proposed approach
with lag=$d=0$.

##  6 Numerical Example

Consider $p=128$, 16 clusters (communities) of 8 nodes each, where nodes
within a community are not connected to any nodes in other communities. Within
any community of 8 nodes, the data are generated using a vector autoregressive
(VAR) model of order 3. Consider community $q$, $q=1,2,\cdots,16$. Then
${\bm{x}}^{(q)}(t)\in\mathbb{R}^{8}$ is generated as

${\bm{x}}^{(q)}(t)=\sum_{i=1}^{3}{\bm{A}}^{(q)}_{i}{\bm{x}}^{(q)}(t-i)+{\bm{w}}^{(q)}(t)$

with ${\bm{w}}^{(q)}(t)$ as i.i.d. zero-mean Gaussian with identity covariance
matrix. Only 10% of entries of ${\bm{A}}^{(q)}_{i}$’s are nonzero and the
nonzero elements are independently and uniformly distributed over
$[-0.8,0.8]$. We then check if the VAR(3) model is stable with all eigenvalues
of the companion matrix $\leq 0.95$ in magnitude; if not, we re-draw randomly
till this condition is fulfilled. The overall data ${\bm{x}}(t)$ is given by
${\bm{x}}(t)=[\,{\bm{x}}^{(1)\top}(t)\;\cdots\;{\bm{x}}^{(16)\top}(t)\,]^{\top}\in\mathbb{R}^{p}$.
First 100 samples are discarded to eliminate transients. This set-up leads to
approximately 3.5% connected edges. The true edge set ${\cal E}_{0}$ for the
time series graph is determined as follows. In each run, we calculated the
true PSD ${\bm{S}}(f)$ for $f\in[0,0.5]$ at intervals of 0.01, and then take
$\\{i,j\\}\in{\cal E}_{0}$ if $\sum_{f}|S_{ij}^{-1}(f)|>10^{-6}$, else
$\\{i,j\\}\not\in{\cal E}_{0}$.

Simulation results based on 100 runs are shown in Figs. 1 and 2. The
performance measure is $F_{1}$-score for efficacy in edge detection. The
$F_{1}$-score is defined as
$F_{1}=2\times\mbox{precision}\times\mbox{recall}/(\mbox{precision}+\mbox{recall})$
where $\mbox{precision}=|\hat{\cal E}\cap{\cal E}_{0}|/|\hat{\cal E}|$,
$\mbox{recall}=|\hat{\cal E}\cap{\cal E}_{0}|/|{\cal E}_{0}|$, and ${\cal
E}_{0}$ and $\hat{\cal E}$ denote the true and estimated edge sets,
respectively. Four approaches were tested: (i) Proposed multi-attribute graph
based approach with lags (delays) $d=1$ or $d=3$, labeled “proposed, lag=1” or
“proposed, lag=3” in the figures. (ii) Frequency-domain sparse-group lasso
approach of [12, 13, 14], optimized using ADMM, using varying number $M$ (=2,4
or 6) of smoothed PSD estimators in frequency range (0,0.5), labeled “freq:
M=2”, “freq: M=4” “freq: M=6”. (iii) An i.i.d. modeling approach that exploits
only the sample covariance
$\frac{1}{n}\sum_{t=0}^{n-1}{\bm{x}}(t){\bm{x}}^{\top}(t)$ (labeled “IID
model”), implemented via the ADMM lasso approach ([19, Sec. 6.4]). In this
approach, as discussed in Sec. 2.1, edge $\\{i,j\\}$ exists in the CIG iff
$\Omega_{ij}\neq 0$ where precision matrix
${\bm{\Omega}}={\bm{R}}_{xx}^{-1}(0)$. (iv) The frequency-domain ADMM approach
of [11], labeled “GMS” (graphical model selection), which was applied with
$F=4$ (four frequency points, corresponds to $M=4$ in [12, 13, 14]) and all
other default settings of [11] to compute the PSDs. The tuning parameters,
$(\alpha,\lambda)$ for proposed and frequency-domain sparse-group lasso
approach of[12, 13, 14], and lasso parameter $\lambda$ for IID and GMS, were
selected via an exhaustive search over a grid of values to maximize the
$F_{1}$-score (which requires knowledge of the true edge-set). The results
shown in Figs. 1 and 2 are based on these optimized tuning parameters. (In
practice, one would use an information criterion or cross-validation to select
the tuning parameters.)

The $F_{1}$-scores are shown in Fig. 1 and average timings per run are shown
in Fig. 2 for sample sizes $n=128,256,512,1024,2048$. It is seen that with
$F_{1}$-score as the performance metric, our proposed method with lag $d=3$
significantly outperforms other approaches while also being faster than
frequency-domain approaches.

Fig. 2: Average timing per run based on 100 runs for 4 approaches.

##  7 Conclusions

Graphical modeling of dependent Gaussian time series was considered. We
formulated the problem as one of multi-attribute graph estimation for random
vectors where a vector is associated with each node of the graph. At each
node, the associated random vector consists of a time series component and its
delayed copies. We exploited the results of [15] to provide an ADMM solution
to minimize a sparse-group lasso penalized negative pseudo log-likelihood
objective function for multi-attribute graph precision matrix estimation. A
theoretical analysis was provided. Numerical results were provided to
illustrate the proposed approach which outperforms the approaches of [11, 12,
13, 14] with $F_{1}$-score as the performance metric for graph edge detection.

## References

  * [1]
  * [2] S.L. Lauritzen, Graphical models. Oxford, UK: Oxford Univ. Press, 1996.
  * [3] R. Dahlhaus, “Graphical interaction models for multivariate time series,” Metrika, vol. 51, pp. 157-172, 2000.
  * [4] M. Eichler, “Graphical modelling of multivariate time series,” Probability Theory and Related Fields, vol. 153, issue 1-2, pp. 233-268, June 2012.
  * [5] P. Danaher, P. Wang and D.M. Witten, “The joint graphical lasso for inverse covariance estimation across multiple classes,” J. Royal Statistical Society, Series B (Methodological), vol. 76, pp. 373-397, 2014.
  * [6] N. Friedman, “Inferring cellular networks using probabilistic graphical models,” Science, vol 303, pp. 799-805, 2004.
  * [7] S.L. Lauritzen and N.A. Sheehan, “Graphical models for genetic analyses,” Statistical Science, vol. 18, pp. 489-514, 2003.
  * [8] N. Meinshausen and P. Bühlmann, “High-dimensional graphs and variable selection with the Lasso,” Ann. Statist., vol. 34, no. 3, pp. 1436-1462, 2006.
  * [9] K. Mohan, P. London, M. Fazel, D. Witten and S.I. Lee, “Node-based learning of multiple Gaussian graphical models,” J. Machine Learning Research, vol. 15, pp. 445-488, 2014.
  * [10] D.R. Brillinger, “Remarks concerning graphical models of times series and point processes,” Revista de Econometria (Brazilian Rev. Econometr.), vol. 16, pp. 1-23, 1996.
  * [11] A. Jung, G. Hannak and N. Goertz, “Graphical LASSO based model selection for time series,” IEEE Signal Process. Lett., vol. 22, no. 10, pp. 1781-1785, Oct. 2015.
  * [12] J.K. Tugnait, “Graphical modeling of high-dimensional time series,” in Proc. 52nd Asilomar Conference on Signals, Systems and Computers, Pacific Grove, CA, Oct. 29 - Oct. 31, 2018, pp. 840-844.
  * [13] J.K. Tugnait, “Consistency of sparse-group lasso graphical model selection for time series,” in Proc. 54th Asilomar Conference on Signals, Systems and Computers, Pacific Grove, CA, Nov. 1-4, 2020, pp. 589-593.
  * [14] J.K. Tugnait, “New results on graphical modeling of high-dimensional dependent time series,” in Proc. 55th Asilomar Conference on Signals, Systems and Computers, Pacific Grove, CA, Oct. 31 - Nov. 3, 2021.
  * [15] J.K. Tugnait, “Sparse-group lasso for graph learning from multi-attribute data,” IEEE Trans. Signal Process., vol. 69, pp. 1771-1786, 2021. (Corrections, vol. 69, p. 4758, 2021.)
  * [16] M. Kolar, H. Liu and E.P. Xing, “Graph estimation from multi-attribute data,” J. Machine Learning Research, vol. 15, pp. 1713-1750, 2014.
  * [17] J. Friedman, T. Hastie and R. Tibshirani, “A note on the group lasso and a sparse group lasso,” arXiv:1001.0736v1 [math.ST], 5 Jan 2010.
  * [18] N. Simon, J. Friedman, T. Hastie and R. Tibshirani, “A sparse-group lasso,” J. Computational Graphical Statistics, vol. 22, pp. 231-245, 2013.
  * [19] S. Boyd, N. Parikh, E. Chu, B. Peleato and J. Eckstein, “Distributed optimization and statistical learning via the alternating direction method of multipliers,” Foundations and Trends in Machine Learning, vol. 3, no. 1, pp. 1-122, 2010.
  * [20] X. Chen, M. Xu and W.B. Wu, “Regularized estimation of linear functionals of precision matrices for high-dimensional time series,” IEEE Trans. Signal Process., vol. 64, no. 24, pp. 6459-6470, Dec. 15, 2016. (Supplementary material available online, 18 pages.)
  * [21] S. Basu and G. Michailidis, “Regularized estimation in sparse high-dimensional time series models,” Annals Statistics, vol. 43, no. 4, pp. 1535-1567, 2015.
  * [22] H. Shu and B. Nan, “Estimation of large covariance and precision matrices from temporally dependent observations,” Annals Statistics, vol. 47, no. 3, pp. 1321-1350, 2019.
  * [23] M. Rudelson and R. Vershynin, “Hanson-Wright inequality and sub-gaussian concentration,” Electronic Communications Probability, vol. 18, no. 82, pp. 1-9, 2013.
  * [24]


/csteps/inner color=white /csteps/outer color=black /csteps/fill color=black

# Setting the Right Expectations: Algorithmic Recourse Over Time

Joao Fonseca  NOVA University LisbonLisbonPortugal<EMAIL_ADDRESS>,
Andrew Bell  New York UniversityNew York, NYUSA<EMAIL_ADDRESS>,  Carlo
Abrate  CENTAITurinItaly<EMAIL_ADDRESS>,  Francesco Bonchi  CENTAI,
Turin, ItalyEurecat, Barcelona, Spain<EMAIL_ADDRESS>and  Julia Stoyanovich
New York UniversityNew York, NYUSA<EMAIL_ADDRESS>
(2023)

###### Abstract.

Algorithmic systems are often called upon to assist in high-stakes decision
making. In light of this, _algorithmic recourse_ , the principle wherein
individuals should be able to take action against an undesirable outcome made
by an algorithmic system, is receiving growing attention. The bulk of the
literature on algorithmic recourse to-date focuses primarily on how to provide
recourse to a single individual, overlooking a critical element: the effects
of a continuously changing context. Disregarding these effects on recourse is
a significant oversight, since, in almost all cases, recourse consists of an
individual making a first, unfavorable attempt, and then being given an
opportunity to make one or several attempts _at a later date_ — when the
context might have changed. This can create false expectations, as initial
recourse recommendations may become less reliable over time due to model drift
and competition for access to the favorable outcome between individuals.

In this work we propose an agent-based simulation framework for studying the
effects of a continuously changing environment on algorithmic recourse. In
particular, we identify two main effects that can alter the _reliability of
recourse_ for individuals represented by the agents: (1) competition with
other agents acting upon recourse, and (2) competition with new agents
entering the environment. Our findings highlight that only a small set of
specific parameterizations result in algorithmic recourse that is reliable for
agents over time. Consequently, we argue that substantial additional work is
needed to understand recourse reliability over time, and to develop recourse
methods that reward agents’ effort.

††journalyear: 2023††copyright: rightsretained††conference: Equity and Access
in Algorithms, Mechanisms, and Optimization; October 30-November 1, 2023;
Boston, MA, USA††booktitle: Equity and Access in Algorithms, Mechanisms, and
Optimization (EAAMO ’23), October 30-November 1, 2023, Boston, MA, USA††doi:
10.1145/3617694.3623251††isbn: 979-8-4007-0381-2/23/11

##  1\. Introduction

Figure 1. Motivation for multi-agent over-time analysis of algorithmic
recourse. First, at time $t=0$, blue agents received a negative outcome and
green agents received a positive outcome. Second, at time $t=1$, black agents
entered the environment. The red agent that had the negative outcome at $t=0$
took actions according to the recourse recommendation generated at $t=0$, but
(disappointingly) such recourse-guided effort turned out to be insufficient.
This is because context has changed from $t=0$ to $t=1$: competition from
other agents acting upon recourse and from new agents “raised the bar,”
pushing up the decision boundary.

Artificial intelligence (AI) systems are becoming increasingly common in
consequential decision-making settings such as healthcare (Begoli et al.,
2019; Grote and Berens, 2020), finance (Mukerjee et al., 2002), and hiring
(Schumann et al., 2020; Raghavan et al., 2020; Karimi et al., 2022). While
these systems have the capacity to significantly improve people’s lives, they
can also have adverse consequences, such as erroneous decision-making
(Steimers and Schneider, 2022). As a result, those developing and researching
AI systems in high-stakes domains have introduced the concept of _algorithmic
recourse_ , which is the ability of an individual to take action against the
outcome of an algorithmic decision-making system. Algorithmic recourse allows
an agent (i.e., individual) to understand:

  1. (1)

why an outcome was produced by the system, and

  2. (2)

what can be done in order to reverse it (Karimi et al., 2021; Ustun et al.,
2019).

The importance of algorithmic recourse has been argued from an equitable and
ethical computing standpoint (Venkatasubramanian and Alfano, 2020; Schermer,
2011), and significant effort has been devoted to the _when_ , _why_ , and
_how_ of giving recourse to individuals. However, as we observe in Section 2,
time-related effects, producing a continuously changing context, have been
considered only by a few authors. The driving insight of this paper is that
the impact of time and of a continuously changing context should never be
ignored in algorithmic recourse work because _time is intrinsic to the notion
of recourse itself._ Typically, recourse consists of an individual making a
first, unsuccessful, attempt at a time $t$, and then being given an
opportunity to make a second attempt at a _later time_ $t+\delta$. Depending
on the length of time represented by $\delta$, recourse recommendations from
$t$ may become demonstrably less reliable. The importance of considering time-
related effects has been acknowledged by Ferrario and Loi, and Barocas et al.,
further highlighting the importance of continued work aimed at closing this
critical research gap (Ferrario and Loi, 2022; Barocas et al., 2020).

As an example, consider the lending setting, wherein an AI system denies an
individual’s application for a loan but provides information on what that
individual can do to be approved for the loan _if they apply again at a later
date_ (Howarth and Quaglia, 2016). The individual may be told that their loan
application was denied because their credit score is 50 points lower than
necessary. One could imagine that it takes the individual 6 months to a year
to improve their credit score — which is enough time for the criteria for
approving the loan to change. As a result, the initial recommendation of
_“improving your credit score by 50 points”_ may have set false expectations.

There are numerous reasons why selection criteria — and the reliability of
recourse recommendations — can change over time (O’Brien and Kim, 2021; Rawal
and Lakkaraju, 2020; Sullivan and Verreault-Julien, 2022; Upadhyay et al.,
2021). In this work, we look at competitive effects that arise from having a
multi-agent resource-constrained setting. In particular, we identify two main
effects: (1) other agents are acting upon recourse recommendations they have
received, and (2) new agents are entering the system. An illustration of the
competitive effects and their impact on recourse can be seen in Figure 1.

Figure 2. Comparison of recourse reliability (metric defined in Section 3.5)
over time under different simulated models of agent behavior. Based on the
behaviors defined in Section 3.3, (a) shows simulations where agents’ behavior
is modeled under continuous adaptation with constant effort; (b) shows
simulations under continuous adaptation with flexible effort.

Research questions, contributions, and roadmap. Motivated by the scenarios
described above, this work aims to develop a framework for multi-agent multi-
time-step analysis of algorithmic recourse. We seek to answer the following
research questions:

  1. (1)

What metrics can be used to evaluate the reliability of algorithmic recourse
over time?

  2. (2)

Under what conditions is algorithmic recourse most reliable for individuals?

  3. (3)

How can system designers set better expectations for what will happen to
individuals, if they follow algorithmic recourse recommendations?

We tackle these questions with the help of an agent-based simulation
framework, in which a population of agents, each having its own features,
applies for access to a scarce resource, and a black-box model decides on the
outcomes. Agents obtaining a positive outcome exit the system, while those
obtaining a negative outcome are given recourse recommendations, allowing them
to adapt their features before applying again at the next time-step. Our
framework is guided by a rich set of stochastic variables, including how
flexible/willing an agent is to adapt and how many new agents are joining the
system at each time step to compete for limited resources. To the best of our
knowledge, this is the only work examining algorithmic recourse under
resource-constrained settings using agent-based modeling. We are also among
the first authors to study recourse over many time steps, rather than just
examining one or two points in time.

Moreover, we define a _recourse reliability_ metric, quantifying the
probability that individuals will receive a favorable outcome, given that they
took the recommended recourse. We also use our framework to assess how
different parameterizations of the setting affect this metric. Our findings
highlight that only a small set of specific parameterizations results in
algorithmic recourse that is reliable for individuals over time. As a preview
of our results, Figure 2 shows that, under 9 different parameterizations of
our framework, one rarely observes reliable recourse over 50 time-steps.

Our work highlights a crucial socio-technical implication: Systems that
provide recourse recommendations _without considering potential shifts in the
threshold for positive outcomes_ can create unrealistic expectations for
individuals. In some cases, these recommendations may even be harmful by
falsely promising rewards to those who seek recourse based on recommendations.
This calls for substantial additional work on understanding recourse
reliability in multi-agent multi-timestep settings, and on developing recourse
methods that reward agents’ effort.

The rest of this paper is organized as follows:

  * •

We review related work on algorithmic recourse (Section 2).

  * •

We formalize multi-agent algorithmic recourse, propose a simulation framework
for evaluating recourse over time, and define a recourse reliability metric
(Section 3).

  * •

We present detailed analysis that confirms the importance of considering
temporal effects in recourse (Section 4).

  * •

We provide an in-depth discussion of the practical implications of our
observations (Section 5).

##  2\. Related Work

Algorithmic recourse is critically important for three reasons: first, as
mentioned, it ascribes agency to individuals against adverse outcomes,
including outcomes that are either incorrect (and inefficient) or
discriminatory (Ustun et al., 2019; von Kügelgen et al., 2022; Sullivan and
Verreault-Julien, 2022). As such, many have argued that providing individuals
recourse is morally good and equitable, and therefore consistent with ethical
computing (Venkatasubramanian and Alfano, 2020; Schermer, 2011). Second, from
the perspective of the owners of AI systems, recourse can improve the overall
accuracy and reliability of a system’s outcomes. Third, algorithmic recourse
will likely become legally necessary with the passing of legislation like the
European Union AI Act (Bell et al., 2023; Cordeiro, 2019).

There are two main approaches used for providing algorithmic recourse in
practice. The first and simpler approach is to provide recourse based on
“contrastive explanations,” which find changes that can be made to an
individual’s profile (i.e., the _feature space_) to flip their outcome from
unfavorable to favorable (Ustun et al., 2019; Bottou et al., 2013). These
recommended changes are sometimes called “interventions.” While useful in many
settings, a short-coming of this approach is that it does not consider the
normative meaning of features. This weakness can lead to recourse
recommendations that are disconnected from real-world actions (Barocas et al.,
2020; Kumar et al., 2020), like recommending to an individual that they should
“lower their age“ to receive a different outcome.

The second set of methods, “causal recourse methods,” use structural causal
models (Pearl et al., 2000; Karimi et al., 2020b) to account for downstream
effects when changing a smaller set of an individual’s features (also referred
to as “consequential recommendations” (Karimi et al., 2020a)). The advantage
of causal recourse methods is that they produce smaller, easier to achieve
intervention sets for individuals (Karimi et al., 2021) that are better
connected with real-world actions and settings.

###  2.1. Temporal effects on recourse

To the best of our knowledge, the impact of time in algorithmic recourse is
understudied. As noted earlier, we see this as a significant research gap,
because _time is inherent to algorithmic recourse itself_. We now discuss
several studies that begin to fill this gap.

Ferrario and Loi, motivated by the idea that machine learning models are often
unstable in real-world settings, studied the impact of retraining models on
the validity of counterfactual explanations over time (Ferrario and Loi,
2022). In their work, they developed a method using counterfactual data
augmentation to improve the robustness of recourse recommendations and prevent
so-called _Unfortunate Counterfacutal Events (UCEs)_ , which occur when an
individual is given a recourse recommendation at time-step $t$, but, due to
model updates, the recommendation is invalid at time-step $t+\delta$. Other
researchers have more generally studied the robustness of counterfactual
explanations due to changes in the underlying settings, but, notably, they did
not emphasize temporal effects as the reason for these changes (Ehyaei et al.,
2023; Guyomard et al., 2023; Mishra et al., 2021; Virgolin and Fracaros, 2023;
Upadhyay et al., 2021).

Rawal et al. analyzed the impact of distribution shifts in the data on
algorithmic recourse recommendations (Rawal et al., 2020). They did not make
any assumptions about the origin of these distribution shifts, and considered
temporal shifts, geo-spatial shifts, and shifts due to data correction. An
important finding of this work is that there are theoretical trade-offs
between minimizing the cost of a recourse recommendations and ensuring
robustness to distribution shifts. Under this trade-off, Pawelczyk et al.
proposed a method for generating counterfactual explanations that allows
individuals to set preferences and navigate this trade-off for themselves
(Pawelczyk et al., 2022). We further refer to the work of Pawelczyk et al.,
and Ferrario and Loi in Section 3.5.

The methods by Upadhyay et al. (2021) and Rawal and Lakkaraju (2020) use
adversarial training to provide recourse recommendations that are robust to
model shifts. They quantify the probability of recourse being invalidated
given the possibility of model shifts. This is achieved by defining a set of
plausible model shifts based on perturbations introduced in the parameter or
gradient space. This analysis applied multiple data drift scenarios over two
time steps.

Our work fills an important gap left by existing work: Rather than focusing
specifically on the robustness of counterfactual explanations, we look to
characterize the reliability of algorithmic recourse more generally. The
framework we propose is agnostic to the method used to generate recourse
recommendations. Furthermore, we not only consider temporal effects in
algorithmic recourse, but also study them alongside multi-agent effects, and
in resource-constrained environments.

###  2.2. Recourse in multi-agent settings

The vast majority of work on both contrastive explanations and causal recourse
methods has focused on single-agent settings, save for a few exceptions
(Upadhyay et al., 2021; Rawal and Lakkaraju, 2020; O’Brien and Kim, 2021,
2022; Altmeyer et al., 2023). One notable work on multi-agent algorithmic
recourse is by O’Brien and Kim (2021, 2022), who adapted concepts from game
theory literature to algorithmic recourse. They defined metrics like “Social-
Welfare-Efficient recourse” and “Pareto-efficient recourse,” which measure the
effect of one agent taking recourse on the population of agents as a whole.
Their analysis of multi-agent interactions, done through the lens of the
prisoners’ dilemma problem, leads to the following key conclusions: The
improvement of an individual (or subgroup) tends to result in a loss in social
welfare, while no scenario results in an improvement of both social welfare
and the principal agent’s. This finding highlights an open question: “When
should algorithmic recourse be provided?” and is related to insights from
Barocas et al. (2020), who suggest that recourse should not be presented to
someone if it encourages an action that would be harmful to them.

Another relevant line of work is by Altmeyer et al. (2023), who studied how
recourse-based multi-agent interactions affect model drift over multiple time-
steps. Their analysis shows significant model drift effects, which changed the
threshold for receiving a positive outcome over time. This work has
similarities to our own, however, their conclusions only hold under a
restricted set of assumptions, namely, that (1) an agent who follows recourse
recommendations is guaranteed a positive outcome; (2) the model is retrained
at every time-step, using all prior data; and (3) agents are capable of taking
as much recourse-based action as they need, and make the exact changes
recommended to them. Importantly, violations of the first assumption could
lead to unrealistic outcomes (e.g., decreasing an agent’s age), or, in the
case of the loan example, to significant monetary losses (Upadhyay et al.,
2021).

Our contribution departs from O’Brien and Kim (2021), and Altmeyer et al.
(2023), as we propose a more realistic agent-based framework, allowing agents
to act on recourse in different ways, and accommodating more flexible
population dynamics, with new agents joining and winning agents exiting the
system. There are two other distinctions present in our simulation framework.
First, at each iteration, we provide recourse to all agents who did not
receive a favorable outcome, and they take recourse action based on a function
describing their actions (also potentially choosing not to act). In contrast,
in Altmeyer et al. (2023), a batch of agents is selected and provided
recourse. Second, Altmeyer et al. (2023) focus on gradient-based
counterfactual search, while our formulation is agnostic to the counterfactual
search method.

##  3\. Proposed Framework

We study the problem of recourse in binary classification, where receiving the
positive outcome corresponds to an agent gaining access to a desirable
resource. Note that from here forward we use “agent” to mean an individual who
is receiving an outcome from a system and possibly taking recourse. We start
from the well-studied recourse problem in the static setting for a single
agent, and then move to a more realistic setting in which multiple agents are
competing for access to scarce resources (i.e., the number of agents competing
exceeds the number of available positive outcomes). Our goal in developing
this framework was to create a way to realistically simulate algorithmic
recourse in a multi-agent, multi-time step environment.

###  3.1. Recourse for a Single Agent

Consider a single agent, described by a set of features, $x\in\mathcal{X}$,
and a black-box classifier $f:\mathcal{X}\rightarrow\\{0,1\\}$ that is used to
generate an outcome for the agent. If an agent $x$ receives a negative outcome
from the classifier $f$, then the outcome is supplemented with a
recommendation (or an explanation) on what they can change in their feature
space to receive a positive outcome instead. Generating this recommendation is
the goal of the single-agent recourse problem.

###### Definition 1 (Single-agent recourse problem).

Given a black-box classifier $f:\mathcal{X}\rightarrow\\{0,1\\}$ and an agent
$x\in\mathcal{X}$ for which $f(x)=0$ (a negative outcome), find a new
configuration of the agent $x^{\prime}\in\mathcal{X}$ that results in
$f(x^{\prime})=1$ (a positive outcome), and is associated with the lowest cost
$c(x,x^{\prime})$ of making the change:

(1) $\begin{split}x^{\prime}=\min_{x^{\prime}}\quad&c(x,x^{\prime})\\\
s.t.\quad&f(x^{\prime})=1\\\ &x^{\prime}\in\mathcal{X}\end{split}$

Use the configuration $x^{\prime}$ to return a recommendation to agent $x$
regarding the adjustment they need to make to their features to receive a
positive outcome.

To make this definition more concrete, consider a scenario where agents are
applying for a loan form a bank (a common example used when discussing
recourse). For our purposes, let an agent $x\in\mathcal{X}$ have two features:
its credit rating $x_{1}$ and annual income $x_{2}$. Suppose the agent applies
for the loan, but is ultimately denied based on the output of a risk
assessment tool, represented by $f:\mathcal{X}\rightarrow\\{0,1\\}$. If the
bank decides to offer recourse to $x$, they may suggest that credit rating
$x_{1}$ should be improved by $\delta_{1}$ or income $x_{2}$ be improved by
$\delta_{2}$, or both, minimizing cost
$c:\mathcal{X}\times\mathcal{X}\rightarrow[0,1]$ for the agent, so that
$f(x^{\prime})=1$. Various methods for solving the problem of Definition 1
have been proposed (Ustun et al., 2019; Bottou et al., 2013; Karimi et al.,
2020a).

###  3.2. Multi-Agent Recourse

Suppose next that agents belong to a population $P$, and that they all are
competing for access to a scarce resource. For example, there may be $|P|=N$
loan applicants, but the bank is only able to lend money to $k\ll N$ of them.

Because of the existence of the resource constraint $k$, there is no fixed
threshold that can be used to determine whether the output of $f(x)$
corresponds to a positive or a negative outcome. Instead, we construct the
black-box model so that, rather than returning a binary outcome, it returns a
score: $f(x):\mathcal{X}\rightarrow[0,1]$. This score is used to rank agents,
from highest to lowest, and then selecting the top-$k$ agents $P^{k}\subseteq
P$ to receive the positive outcome. While there is _no fixed threshold_
associated with the positive outcome, we can use the $k^{th}$ highest score
$s$ as a threshold for receiving the positive outcome. We write this formally
below:

###### Definition 2 (Multi-agent recourse problem).

Given a black box classifier $f:\mathcal{X}\rightarrow[0,1]$, a population of
agents $P$, and a resource constraint $k$, compute the score threshold $s$ for
receiving the positive outcome.

For each agent $x\in\mathcal{X}$ for which $f(x)<s$ (a negative outcome), find
a new counterfactual configuration of the agent $x^{\prime}\in\mathcal{X}$
that results in $f(x^{\prime})\geq s$ (a positive outcome), and is associated
with the lowest cost $c(x,x^{\prime})$ of making the change:

(2) $\begin{split}x^{\prime}=\min_{x^{\prime}}\quad&c(x,x^{\prime})\\\
s.t.\quad&f(x^{\prime})\geq s\\\ &x^{\prime}\in\mathcal{X}\end{split}$

Use the configuration $x^{\prime}$ for each agent $x$ for which $f(x)<s$ to
return a recommendation regarding the adjustments they need to make to their
features to receive the positive outcome.

###  3.3. Modeling Agents’ Behaviors

Having shown how recourse can be modeled for multiple agents, we now turn our
attention to modeling the behaviour of a population of agents over time. We
consider two important, realistic considerations about agents’ behavior with
respect to recourse:

  1. (1)

_How faithfully an agent follows the recourse recommendation._ Agents may
follow the recourse recommendation _exactly_ , or they may outperform (or
underperform) the recommendation. For example, returning to the loan example
described in Section 3.1, one could imagine that if an agent is told to
increase their credit score by 50 points, they may do so exactly, or they may
actually increase their score by 40 point, or by 60 points. We call this
consideration “adaptation.”111Pawelcyzk et al. use the terms _prescribed
recourse_ and _implemented recourse_ to refer to a similar concept.

  2. (2)

_The likelihood of an agent to take any action._ An agent that receives a
recourse recommendation may or may not act on it. The likelihood that an agent
will attempt a recourse action is be determined by several factors, such their
implicit willingness to make challenges and the amount of effort the action
requires. In the loan example, if an agent is told to increase their credit
score by 20 points, they may be more likely to make the effort as opposed to
being told to increase it by 200 points. We call this consideration “effort.”

Adaptation. The single-agent recourse problem (Definition 1) assumes that,
when a recommendation for recourse is provided, an agent will change their
features _exactly according to the recommendation_ they receive. Here, we
relax this assumption and consider cases where there is uncertainty regarding
whether an agent will, in fact, change their configuration in the way that the
recommendation suggests.

We model an agent’s actions in changing their features as a function
$a(x,x^{\prime}):\mathcal{X}\times\mathcal{X}\rightarrow\mathcal{X}$ that
produces configuration $x^{\prime\prime}$, with the goal of reaching or
exceeding the score threshold $s$. We consider three cases: (1) $x$ follows
the suggested recourse recommendation exactly, i.e.,
$a(x,x^{\prime})=x^{\prime}$ with $f(x^{\prime})=s$; (2) $x$ declines to
follow the recommendation, i.e., $a(x,x^{\prime})=x$, with $f(x)<s$; (3) $x$
changes their features in a way that is feasible but different than the
recourse recommendation, i.e., $a(x,x^{\prime})=x^{\prime\prime}$ with score
$f(x^{\prime\prime})$ that may be greater than or less than $s$.

In our simulation framework, we model this behavior using the adaptation
parameter that has two settings: _binary_ and _continuous_. The _binary_
setting matches the classical view of recourse found in the literature, and
assumes that all agents that take recourse action _exactly match the
recommendation_ (their new feature configuration is $x^{\prime}$). Under this
setting, an agent acts on the recourse recommendation with some probability
$p$ (i.e., $a(x,x^{\prime})=x^{\prime}$), and it retains the original value of
the features with probability $1-p$ (i.e., $a(x,x^{\prime})=x$).

The _continuous_ setting accounts for what we believe is a more realistic
modeling of behavior: that an agent makes progress towards a recourse
recommendation, and may out- or under-perform the recommendation at any given
time-step. In this setting, the agent produces configuration
$x^{\prime\prime}$ according to some probabilistic model (e.g., a Gaussian
distribution). When taking actions, a value $\delta_{x}$ is sampled from this
distribution, resulting in a new configuration $x^{\prime\prime}$, and a new
score $f(x^{\prime\prime})=f(x)+\delta_{x}$ is computed.

Figure 3. Different types of agent behavior. The agent (red) receives a
recommendation (yellow) and takes action (blue). See Section 3.3 for a
detailed description of the parameters _adaptation_ and _effort_.

Effort. As described earlier, _effort_ reflects an agent’s likelihood to take
action and change their feature space. Under our simulation, this parameter
has two settings: _constant_ and _flexible._ The setting _constant_ means that
an agent has an implicit willingness to act on recourse that is determined _a
priori_ and is intrinsic to the agent. Regardless of what is happening in the
environment, an agent has some probability $p$ that they will act on a
recourse recommendation.

The setting _flexible_ means that the amount of effort required for a recourse
recommendation determines the probability that an agent will take action and
change their features. In other words, the less effort is required the more
likely it is for an agent to act (and vice versa). In this case, the agents’
probability to act on recourse is sampled from $\text{dist}(f(x),s)$. To
encode effort into our simulation, we use the parameter $l\in\mathbb{R}$, and
explain how how it is used in each setting in 4.2. $l$ is an additive factor,
and intuitively, it can be thought of as the agent-level willingness to take
recourse action.

Difficulty of acting on recourse recommendations. An additional consideration
we use to model agent behavior is defining a global parameter that controls
the _difficulty of acting on a recourse recommendation_. For example, one can
imagine that it is easier to act on a recourse recommendation when it is
related to signing up for a social media account versus improving one’s credit
score. The parameter $g\in[0,1]$ is set _a priori_ for the simulation. Values
of $g$ closer to $1.0$ indicate a setting where it is easier for all agents to
successfully get recourse.

Adaptation and effort combined. Since both adaption and effort have two
settings, there are four possible settings to model agents’ behavior. These
are illustrated and described in Figure 3. For better understanding, let’s
consider two of the settings in detail:

  * •

_Binary adaptation with constant effort_. In this case, an agent’s willingness
to take action is determined _a priori_ , and they will make the _exact_
changes to their features per the recommended recourse they receive.

  * •

_Continuous adaptation with flexible effort_. In this case, an agent’s
willingness to take action is determined by how much effort they need to make.
Further, how much they change their features is also probabilistic, and may
result in them meeting, out-performing or under-performing the recourse
recommendation.

Figure 4. Overview of our simulation framework. A The initial population
$P_{t}=A_{t}\cup N_{t}$ is the union of the agents $A_{t}$ that had a negative
outcome at time $t-1$ and new agents $N_{t}$ entering in the system. B The
black-box classifier $f:\mathcal{X}\rightarrow[0,1]$ computes agents’ scores
$S_{t}$. C Agents are sorted according to the scores in $\bar{P}_{t}$. D The
top-$k$ agents in $\bar{P}_{t}$ are selected as $P^{k}_{t}$ and exit from the
system. E The threshold $s_{t}$ is updated to the lowest score of the agents
in $P^{k}_{t}$. F For all the non-winning agents $L_{t}$, recourse is provided
by $r:\mathcal{X}\rightarrow\mathcal{X}$. G The adaptation function
$a:\mathcal{X}\times\mathcal{X}\rightarrow\mathcal{X}$ generates the evolution
of each agent $x_{t}\in L_{t}$ from time $t$ to $t+1$, given the recourse
$r(x_{t})=x^{\prime}$, with the final output
$a(x_{t},r(x_{t}))=a(x_{t},x^{\prime})=x_{t+1}$. H The initial population at
$t+1$ is $P_{t+1}=A_{t+1}\cup N_{t+1}$.

###  3.4. Simulation Framework

We consider an environment where agents compete for access to a scarce
resource repeatedly, at discrete time steps $t_{0},\ldots,t_{n}$. The number
of resources at each time step is given by $k$, which determines the number of
positive outcomes (e.g., loans) that can be assigned at each time step. The
simulation begins with an initial population of agents $P_{0}$, all with
synthetically-generated features.

At each time step, every agent receives a score from a machine learning
classifier $f:\mathcal{X}\rightarrow[0,1]$, representing their attempt at a
positive outcome (e.g., applying for a loan). The agents with the top-$k$
scores at each time step receive a positive outcome and exit the environment
(e.g., they receive a loan). Agents that receive a negative outcome are given
recourse recommendations from a function
$r:\mathcal{X}\rightarrow\mathcal{X}$, and have the chance to act on those
recommendations at a later time step. The likelihood an agent will “take
action” and change their features is governed by an “agent behavior” function
$a_{l,g}:\mathcal{X}\times\mathcal{X}\rightarrow\mathcal{X}$. Note that both
the likelihood of taking action (or not) _and_ the amount action taken are
governed by $a_{l,g}$.

We encode $l$ and $g$ as described in Section 3.3 as hyperparemters for the
adaptation function $a_{l,g}$. Recall that $g\in[0,1]$ determines the global
difficulty of achieving recourse and is set _a priori_ for the simulation. We
let $l\in[0,1]$ be defined separately for each agent when they enter the
simulation, and it reflects each agent’s individual willingness to take
action. We draw $l$ from a random distribution, and a higher value of $l$
means that an agent is more willing to act upon a recourse recommendation.
Note that $l$ is mutable from one time-step to another. For example, under the
_flexible_ setting (see Figure 3), if an agent finds themselves closer to the
score threshold, their willingness to take action may increase.

Importantly, the population of agents is not fixed: at each time step, new
agents (i.e., new loan applicants) join the environment. We model these
dynamics by representing the population of agents over time as a sequence
$P=\\{P_{t_{0}},\dots,P_{t_{T}}\\}$. At the end of the simulation, we retrieve
$P$ that contains the final state of each agent.

Algorithm 1 Simulating multi-agent recourse over time

1:Classifier $f:\mathcal{X}\rightarrow[0,1]$; function for generating recourse
recommendations $r:\mathcal{X}\rightarrow\mathcal{X}$; function describing
agent recourse actions
$a_{l,g}:\mathcal{X}\times\mathcal{X}\rightarrow\mathcal{X}$; global
difficulty setting $g$; agent-level willingness $l$ for each agent; number of
time steps $T$; number of favorable outcomes per time step $k$; initial
population size $p$; number of new agents at each time step $n$

2:The sequence of sets of agents $\\{P_{t_{0}},\dots,P_{t_{T}}\\}$ in their
final state for each time step.

3:$t\leftarrow 0$

4:$P_{0}\leftarrow$ create the initial population of $p$ agents

5:$A_{t}=\emptyset$

6:while $t<T$ do

7: if $t\neq 0$ then

8: $N_{t}\leftarrow$ set of $n$ agents joining the simulation;

9: $P_{t}\leftarrow A_{t}\cup N_{t}$, full population of agents;

10: $S_{t}\leftarrow\\{x_{t},s|\forall x_{t}\in P_{t},s=f(x_{t})\\}$, compute
agent scores;

11: $\bar{P}_{t}\leftarrow sort(S_{t})$, sort agents by score;

12: $P^{k}_{t}\leftarrow select\\_top\\_k(\bar{P}_{t})$, select $k$ highest-
scoring agents, assign them a positive outcome;

13: $s_{t}\leftarrow update(P^{k}_{t})$, update the decision threshold to be
the minimum score from $P^{k}_{t}$;

14: $L_{t}\leftarrow P_{t}\setminus P^{k}_{t}$, select agents who did not
receive a positive outcome;

15: $R_{t}\leftarrow\\{x^{\prime}|\forall x\in L_{t},x^{\prime}=r(x)\\}$,
generate recourse recommendations;

16: $A_{t+1}\leftarrow\\{x_{new}|\forall x\in
L_{t},x_{new}=a_{l_{x},g}(x,x^{\prime})\\}$, for each agent, determine what
action they take (if any);

17: $t\leftarrow t+1$, increase time-step

###  3.5. Quantifying the Reliability of Recourse

As discussed in Sections 1 and 2, prior work on time-related effects of
recourse is very limited. To the best of our knowledge, only two recourse
reliability metrics have been defined to-date. Ferrario and Loi propose
measuring the reliability of recourse using _“Unfortunate Counterfactual
Events (UCEs)”_ that occur when a counterfactual explanation used as a
recourse recommendation becomes invalidated at a later time due to updates in
the underlying machine learning model (Ferrario and Loi, 2022). Pawelczyk et
al. define a metric called _Recourse Invalidation Rate_ that quantifies the
probability that a recourse recommendation becomes invalidated for a single
individual due to changes in the way recourse is implemented by that
individual (Pawelczyk et al., 2022).

In this paper, we propose an alternate metric that quantifies how well
recourse recommendations meet individuals’ expectations. In other words, we
offer a metric that quantifies whether the “promise” of recourse matches
reality. We call this metric recourse reliability, and see it as an important
contribution to the literature, for two reasons: first, unlike previous
metrics, it quantifies _system-level_ behavior, as opposed to focusing on
recourse for a single individual. Second, our metric is not tied to
counterfactual explanations, and is agnostic to the way the underlying
recourse recommendation is generated. For example, it is can be used to
quantify reliability of _principle reason explanations_ (Barocas et al.,
2020).

The impact of competitive effects on the score threshold for a positive
outcome. Consider the simulation framework described in Section 3.4. At each
time step $t>0$, an agent that received a negative outcome in the previous
time step has a chance of altering their feature space in such a way that it
either meets or exceeds the previous score threshold for a positive outcome
$s_{t}$. Typically, an agent that carries out this behavior would expect to
receive a positive outcome at the next time step, $t+1$. However, due to
competitive effects (described in Figure 1) the agent may not receive a
positive outcome. Specifically, we consider two competitive effects:

  1. (1)

Agents already present in the environment may act on recourse recommendations
and exceed the score of other agents.

  2. (2)

New agents entering the environment may have scores that exceed the score of
other agents.

In both cases, it is possible that the score threshold for a positive outcome
increases so that $s_{t+1}>s_{t}$. Intuitively, the score threshold can only
remain constant if the number of agents acting on recourse and the number of
agents is equal to the resource constraint $k$. This is shown in the following
equality:

(3) $\frac{\mathbb{E}[\sum_{x_{t}\in P_{t}}1_{[f(x_{t})>s_{t-1}]}]}{k}=1$

Importantly, if the equality _does not hold_ , then the score threshold for a
positive outcome may increase at future time steps. As a result, the
reliability of algorithmic recourse recommendations cannot be guaranteed.

Defining recourse reliability. Let us denote the set of agents that changed
their features per a recourse recommendation and _met or exceeded the score
threshold $s_{t-1}$_ as $C_{t}=\\{x_{t}\in A_{t}|f(x_{t})\geq s_{t-1}\\}$. The
agents $C_{t}$ successfully acted on a recourse recommendation and thus
_expect to receive a positive outcome_. Recall $P^{k_{t}}$ is the set of
agents that received a positive outcome at time step $t$. Using this notation,
we can define recourse reliability at time t as:

(4) $RR_{t}=\frac{|C_{t}\cap P^{k}_{t}|}{|C_{t}|}$

Stated plainly, recourse reliability at time $t$ is the proportion of agents
who acted on recourse and _received a positive outcome_ , out of all those
agents who acted on recourse and _expected a positive outcome_. In this way,
recourse reliability is a measure of how well recourse expectations are met
for agents.

##  4\. Empirical Analysis

To better understand the behavior of recourse reliability, we conducted
extensive empirical analysis using the simulation framework described in
Section 3.4. Our analyses also allow us to demonstrate how the various
concepts defined previously like adaptation, effort, competitive effects
impact algorithmic recourse. The following analyses were executed using Python
with its standard libraries. Our implementation and all supporting code
(including the empirical analysis reported here) are publicly available on
GitHub222https://github.com/joaopfonseca/recourse-game/.

We report results of simulations using the parameters summarized in Table 1.
All reported results represent 20 executions with different initial random
seeds, saved for reproducibility.

###  4.1. Experimental Setup

Table 1 summarizes the parameters of the simulations used in our experimental
evaluation. We refer to Figure 4 for a visual summary of the components of the
framework, and their interactions.

Table 1. Summary of simulation parameters Symbol |  Parameter |  Settings
---|---|---
$p$ |  Initial number of agents |  100
$k$ |  Number of favorable outcomes per time step |  10
$n$ |  Number of new agents per time step |  $\\{0.8k,0.9k,k,1.1k,1.2k\\}$
$a_{l,g}(x,x^{\prime})$ |  Describes _adaptation_ and _effort_ of agents |  {binary, continuous} $\times$ {constant, flexible}
$l$ |  Agent-level (local) willingness of acting on recourse |  $[0,1]$
$g$ |  Global ease of acting on recourse |  $[0,1]$
T |  Number of time steps |  50

##### Population

Agents are generated over a 2-dimensional feature space, sampled independently
at random. Each feature is sampled from a Gaussian distribution, where
$x=(x_{1},x_{2})$ and
$x_{i}\sim\mathcal{N}(\mu=0.5,\sigma=0.\overline{3}),i=1,2$. All simulations
have an initial population $p=100$ agents. Of these, $k=10$ receive the
favorable outcome at every time step and exit the system. New agents $n$ enter
the simulation at every time step, where the number of new agents is fixed per
simulation, and varies between 8 and 12 across simulations.

##### Classifier

The framework described in Section 3.4 is model-agnostic, but for our
experiments we used a simple logistic regression classifier to determine the
score for each agent at each time step. The target variable $y_{i}$ for the
prediction task is created randomly using a binomial distribution.

##### Calculating recourse recommendations.

Our simulation framework is also agnostic to the method used for generating
recourse recommendations for each agent. We use a simple approach to generate
single-agent counterfactual explanations for linear classification, based on
the work by Ustun et al. (2019) and its open source implementation.

###  4.2. Experimental Results

We present our results based on the different types of agents behavior, and
show full results for three parameter settings:

  1. (1)

Binary adaptation with constant effort.

  2. (2)

Continuous adaption with constant effort.

  3. (3)

Continuous adaption with flexible effort

We do not report results for the binary adaptation flexible effort setting
because it does not contain unique insights as compared to the other settings.
Further, we do not explore the effect of varying $l$ within each experiment
(i.e., agent leveling willingness) but instead define $l$ _a priori_ for each
setting. We do this because we are primarily interested in the impact of the
(global) difficulty of recourse and of the number of new applicants at each
time-step.

####  4.2.1. Binary adaptation with constant effort

Recall that binary adaptation means that all agents $x$ will adapt to match
the counterfactual configuration $x^{\prime}$ based on some fixed probability.
We express this probability in the following way:

(5) $a_{l,g}(x_{t},x_{t}^{\prime})=(1-l)\times x_{t}+l\times x_{t}^{\prime}$

We sample $l$ from a Bernoulli distribution where $l\sim Bernoulli(g)$. Figure
5 shows the score threshold for a positive outcome $s_{t}$ and the recourse
reliability $RR_{t}$ over 50 time-steps, varying the number of agents taking
recourse action and the number of new agents entering at each time step. There
are several observations that can be gleaned from the figure. First, over
nearly all settings, the threshold $s_{t}$ is relatively constant, with
imperceptible drifts over time. Second, and significantly, the recourse
reliability $RR_{t}$ always tends to decrease (at different rates). Third, in
settings where the $g$ is approximately $0.5$ or greater and the number of new
agents is approximately $0.9\times k$ or greater, the $RR_{t}$ is close to
$0$. This is because with so many agents adapting, the environment becomes
incredibly competitive and it is difficult for agents to achieve a successful
recourse event.

Figure 5. Binary adaptation with constant effort. Score threshold values for a
positive outcome (blue lines) and recourse reliability (red lines) over 50
time steps (error bars given by running 20 simulations with different random
seeds). The $y-$axis in each subgraph is the score of individual agents, and
the $x-$axis in each subgraph is the time step. The large $y-$axis is the
difficulty of acting on recourse $g$, and the large $x-$axis is the number of
new agents at each time step $N_{t}$.

####  4.2.2. Continuous adaptation with constant effort

Recall that constant effort is based on the idea that each agent has an _a
priori_ willingness to act on a recourse recommendation, and it does not
change over time. We sample $l$ a random uniform distribution where
$l\sim\mathcal{U}(0,1)$, and as described earlier, $g$ is an input parameter
of the simulation.

Figure 6 is analogous to Figure 5. Notice that in this case, the volatility of
the recourse reliability score $RR_{t}$ varies with a more discernible
pattern: although the score threshold for a positive outcome $s_{t}$ also
varies with both parameters, it always decays when the number of new agents (8
or 9) is lower than the number of favorable outcomes (10). Overall, the
recourse reliability scores follow non-linear trajectories with high
volatility.

Figure 6. Continuous adaptation with constant effort. Identical details as in
Figure 5.

####  4.2.3. Continuous adaptation with flexible effort

Recall that flexible effort means that an agent’s willingness to take action
on recourse is based on the agent’s distance to the score threshold for a
favorable outcome. It follows the assumption that an agent with a score closer
to the score threshold will have a greater incentive to exert effort as
compared to an agent with a lower score. In this case, we define the agent
level willingness $l$ as follows:

(6) $\begin{gathered}l=\frac{1}{s_{t}-f(x)}\\\ \end{gathered}$

Figure 7 is analogous to Figure 5. Although one observes lower volatility of
both the score threshold and the recourse reliability as compared to the
continuous adaptation with constant effort setting (Section 4.2.2), some
parameter settings yield high volatility. Specifically, larger $g$ and lower
$N_{t}$ lead to lower recourse reliability.

Figure 7. Continuous adaptation with flexible effort. Identical details as in
Figure 5.

####  4.2.4. Summary of experimental results

Generally, we observe that recourse reliability will decrease as the global
difficulty $g$ increases (i.e., it is harder for agents to act on recourse),
and as the number of agents increases above the resource constraint $k$.
Intuitively, this reflects the idea that a more competitive environment will
result in lower recourse reliability.

_Adaptation._ In terms of agent behavior, holding all other parameters
constant, binary adaptation has a negative impact on recourse reliability
overall as compared to continuous adaptation. Again, our intuition is that
binary adaptation models a more competitive environment since agent’s are
“quicker” to implement recourse. Also, in this setting, agents often find
themselves having their score tied with others since all agents are changing
their score to _exactly_ match the threshold.

_Effort._ In a similar fashion, flexible effort has a more negative impact on
recourse reliability as compared to constant effort, likely due to making more
the environment more competitive. Under flexible effort, agents that are
closer to the threshold will act on recourse and pass the threshold more
frequently.

##  5\. Discussion

In this paper, we developed a framework that simulates recourse in a _multi-
agent environment over time_. In the experiments conducted using our
framework, we found that, in the vast majority of cases, the score threshold
for a positive outcome either decreases or increases over time. Both of these
cases can be harmful to the agents: If the threshold increases over time, then
recourse reliability suffers (i.e., some of the agents that were promised a
positive outcome will not receive one even if they reach the threshold). If
the threshold decreases over time, then recourse recommendations are reliable,
but the effort of agents acting on recourse may be wasted (i.e., they worked
harder than necessary to achieve the positive outcome).

Importantly, _across all of our simulations_ , we found that the score
threshold rarely remains stable over time, and, further, that threshold
stability, which is desirable from the point of view of the agents, is the
most difficult to parameterize for.

Our observations have a significant socio-technical implication: In systems
that administer recourse _without considering possible changes over time_ ,
individuals are at best being given unrealistic expectations about what will
happen to them if they follow recommendations for recourse, and, at worst, the
system designers are being irresponsible —and possibly damaging— by falsely
promising a reward to individuals for their efforts. This finding supports
concerns by Barocas et al. and other authors about the need to study recourse
under the assumption that the system will change over time (Barocas et al.,
2020; Ferrario and Loi, 2022; Pawelczyk et al., 2020).

For a real-world example, let us consider college admissions. There is
substantial evidence that the selectivity of US universities changes over time
(Hoxby, 2009). One can imagine a scenario where an applicant is denied
admission to their top-choice university in one year, and is recommended a set
of improvements to make to their application (e.g., increase their SAT score,
increase the number of volunteering hours). However, these improvements may
turn out to be insufficient for admission when the individual re-applies to
the same university one or two years later.

Guidance for system-level decision-makers. Our framework can be used to
provide guidance to system-level decision-makers like banks, colleges, and
governments. The parameters of our framework — the number of new individuals
at each time step, the number of individuals that re-apply at each time step,
and the expected level of improvement among the individuals who re-apply— can
all be easily measured in practice. Once these parameters are known, our
framework can anticipate changes in the threshold over time, and provide
insight regarding the time-step at which specific changes are expected to
occur. Another use case for our framework is that, if any of these values can
only be estimated rather than measured, one could run many experiments
sweeping over a broad range of values and scenarios to better understand
possible outcomes.

There are two concrete actions that decision-makers can take based on
empirical insights. First, recourse reliability can be measured and used to
provide an uncertainty estimate to individuals undertaking recourse action.
For example, the system could generate a recommendation in the following way:
“If you make the following $X$ changes by time $t$, then there is a $Y\%$
chance that you will receive a positive outcome.” Second, if it is possible to
adjust resource constraints (e.g., the number of loans being given, or the
number of spots in an incoming college class), our framework can inform what
setting of the resource constraint maximizes recourse reliability. For
example, colleges could estimate the ideal incoming class-size that achieves a
stable threshold for admissions.

##  6\. Conclusions, limitations, and future work

In this paper, we sought to close a significant gap in the literature, and
conducted multi-agent, multi-time step analysis of algorithmic recourse within
competitive environments. We developed a simulation framework that allows the
configuration of a diverse set of components, such as incorporating external
interventions/shocks, problem-specific adaptation functions, introduction of
new agents and resource constraints, and opens up opportunities to study how
these settings affect the reliability of algorithmic recourse over time. The
software implementation of our framework is available in a public GitHub
repository. The major finding of our work is that recourse is only reliable
under a very specific set of conditions, leading to an important insight for
people who design recourse methods, and for people who receive recourse
recommendations. It is our hope that this paper will lead to more robust and
reliable algorithmic recourse methods.

Limitations and future work. In this paper, we presented an agent-based
framework that has undergone rigorous testing using _simulated data_. Our
future plans involve evaluating the practical applicability of our insights by
incorporating real-world data and deployment scenarios.

A further limitation of our work is that our adaptation functions attempt to
model human behaviour, which is complex and not always rational. In future
work, we plan to further validate these functions, and to develop methods that
learn adaptation behavior from historical data.

Further future work involves designing additional metrics, and exploring the
impact of different feature distributions, and distributions of adaptation and
effort, on recourse reliability, efficiency, and fairness.

###### Acknowledgements.

This research was supported in part by NSF Awards No. 1916505 and 192265, by
the NSF Graduate Research Fellowship under Award No. DGE-2234660, by research
grants from the Portuguese Foundation for Science and Technology (“Fundação
para a Ciência e a Tecnologia”) references SFRH/BD/151473/2021 and
UIDB/04152/2020, and by the New York University Center for Responsible AI.

## References

  * (1)
  * Altmeyer et al. (2023) Patrick Altmeyer, Giovan Angela, Aleksander Buszydlik, Karol Dobiczek, Arie van Deursen, and Cynthia Liem. 2023.  Endogenous Macrodynamics in Algorithmic Recourse. In _First IEEE Conference on Secure and Trustworthy Machine Learning_.
  * Barocas et al. (2020) Solon Barocas, Andrew D Selbst, and Manish Raghavan. 2020\.  The hidden assumptions behind counterfactual explanations and principal reasons. In _Proceedings of the 2020 conference on fairness, accountability, and transparency_. 80–89.
  * Begoli et al. (2019) Edmon Begoli, Tanmoy Bhattacharya, and Dimitri Kusnezov. 2019\.  The need for uncertainty quantification in machine-assisted medical decision making.  _Nature Machine Intelligence_ 1, 1 (2019), 20–23.
  * Bell et al. (2023) Andrew Bell, Oded Nov, and Julia Stoyanovich. 2023.  Think about the stakeholders first! Toward an algorithmic transparency playbook for regulatory compliance.  _Data & Policy_ 5 (2023), e12.
  * Bottou et al. (2013) Léon Bottou, Jonas Peters, Joaquin Quiñonero-Candela, Denis X Charles, D Max Chickering, Elon Portugaly, Dipankar Ray, Patrice Simard, and Ed Snelson. 2013\.  Counterfactual Reasoning and Learning Systems: The Example of Computational Advertising.  _Journal of Machine Learning Research_ 14, 11 (2013).
  * Cordeiro (2019) AB Cordeiro. 2019\.  Civil liability for processing of personal data in the GDPR.  _Eur. Data Prot. L. Rev._ 5 (2019), 492.
  * Ehyaei et al. (2023) Ahmad-Reza Ehyaei, Amir-Hossein Karimi, Bernhard Schölkopf, and Setareh Maghsudi. 2023\.  Robustness Implies Fairness in Causal Algorithmic Recourse. In _Proceedings of the 2023 ACM Conference on Fairness, Accountability, and Transparency_. 984–1001.
  * Ferrario and Loi (2022) Andrea Ferrario and Michele Loi. 2022.  The robustness of counterfactual explanations over time.  _IEEE Access_ 10 (2022), 82736–82750.
  * Grote and Berens (2020) Thomas Grote and Philipp Berens. 2020.  On the ethics of algorithmic decision-making in healthcare.  _Journal of medical ethics_ 46, 3 (2020), 205–211.
  * Guyomard et al. (2023) Victor Guyomard, Françoise Fessant, Thomas Guyet, Tassadit Bouadi, and Alexandre Termier. 2023.  Generating robust counterfactual explanations.  _arXiv preprint arXiv:2304.12943_ (2023).
  * Howarth and Quaglia (2016) David Howarth and Lucia Quaglia. 2016.  The comparative political economy of Basel III in Europe.  , 205–214 pages.
  * Hoxby (2009) Caroline M Hoxby. 2009\.  The changing selectivity of American colleges.  _Journal of Economic perspectives_ 23, 4 (2009), 95–118.
  * Karimi et al. (2020a) Amir-Hossein Karimi, Gilles Barthe, Bernhard Schölkopf, and Isabel Valera. 2020a.  A survey of algorithmic recourse: definitions, formulations, solutions, and prospects.  _arXiv preprint arXiv:2010.04050_ (2020).
  * Karimi et al. (2022) Amir-Hossein Karimi, Gilles Barthe, Bernhard Schölkopf, and Isabel Valera. 2022.  A survey of algorithmic recourse: contrastive explanations and consequential recommendations.  _Comput. Surveys_ 55, 5 (2022), 1–29.
  * Karimi et al. (2021) Amir-Hossein Karimi, Bernhard Schölkopf, and Isabel Valera. 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. (2020b) Amir-Hossein Karimi, Julius Von Kügelgen, Bernhard Schölkopf, and Isabel Valera. 2020b.  Algorithmic recourse under imperfect causal knowledge: a probabilistic approach.  _Advances in neural information processing systems_ 33 (2020), 265–277.
  * Kumar et al. (2020) I Elizabeth Kumar, Suresh Venkatasubramanian, Carlos Scheidegger, and Sorelle Friedler. 2020.  Problems with Shapley-value-based explanations as feature importance measures. In _International Conference on Machine Learning_. PMLR, 5491–5500.
  * Mishra et al. (2021) Saumitra Mishra, Sanghamitra Dutta, Jason Long, and Daniele Magazzeni. 2021.  A survey on the robustness of feature importance and counterfactual explanations.  _arXiv preprint arXiv:2111.00358_ (2021).
  * Mukerjee et al. (2002) Amitabha Mukerjee, Rita Biswas, Kalyanmoy Deb, and Amrit P Mathur. 2002.  Multi–objective evolutionary algorithms for the risk–return trade–off in bank loan management.  _International Transactions in operational research_ 9, 5 (2002), 583–597.
  * O’Brien and Kim (2021) Andrew O’Brien and Edward Kim. 2021.  Multi-agent algorithmic recourse.  _arXiv preprint arXiv:2110.00673_ (2021).
  * O’Brien and Kim (2022) Andrew O’Brien and Edward Kim. 2022.  Toward Multi-Agent Algorithmic Recourse: Challenges From a Game-Theoretic Perspective. In _The International FLAIRS Conference Proceedings_ , Vol. 35.
  * Pawelczyk et al. (2020) Martin Pawelczyk, Klaus Broelemann, and Gjergji Kasneci. 2020\.  On counterfactual explanations under predictive multiplicity. In _Conference on Uncertainty in Artificial Intelligence_. PMLR, 809–818.
  * Pawelczyk et al. (2022) Martin Pawelczyk, Teresa Datta, Johannes van-den Heuvel, Gjergji Kasneci, and Himabindu Lakkaraju. 2022\.  Probabilistically robust recourse: Navigating the trade-offs between costs and robustness in algorithmic recourse.  _arXiv preprint arXiv:2203.06768_ (2022).
  * Pearl et al. (2000) Judea Pearl et al. 2000\.  Models, reasoning and inference.  _Cambridge, UK: CambridgeUniversityPress_ 19, 2 (2000).
  * Raghavan et al. (2020) Manish Raghavan, Solon Barocas, Jon Kleinberg, and Karen Levy. 2020.  Mitigating bias in algorithmic hiring: Evaluating claims and practices. In _Proceedings of the 2020 conference on fairness, accountability, and transparency_. 469–481.
  * Rawal et al. (2020) Kaivalya Rawal, Ece Kamar, and Himabindu Lakkaraju. 2020\.  Algorithmic recourse in the wild: Understanding the impact of data and model shifts.  _arXiv preprint arXiv:2012.11788_ (2020).
  * Rawal and Lakkaraju (2020) Kaivalya Rawal and Himabindu Lakkaraju. 2020.  Beyond individualized recourse: Interpretable and interactive summaries of actionable recourses.  _Advances in Neural Information Processing Systems_ 33 (2020), 12187–12198.
  * Schermer (2011) Bart W Schermer. 2011\.  The limits of privacy in automated profiling and data mining.  _Computer Law & Security Review_ 27, 1 (2011), 45–52.
  * Schumann et al. (2020) Candice Schumann, Jeffrey Foster, Nicholas Mattei, and John Dickerson. 2020.  We need fairness and explainability in algorithmic hiring. In _International Conference on Autonomous Agents and Multi-Agent Systems (AAMAS)_.
  * Steimers and Schneider (2022) André Steimers and Moritz Schneider. 2022.  Sources of risk of AI systems.  _International Journal of Environmental Research and Public Health_ 19, 6 (2022), 3641.
  * Sullivan and Verreault-Julien (2022) Emily Sullivan and Philippe Verreault-Julien. 2022\.  From Explanation to Recommendation: Ethical Standards for Algorithmic Recourse.  _arXiv preprint arXiv:2205.15406_ (2022).
  * Upadhyay et al. (2021) Sohini Upadhyay, Shalmali Joshi, and Himabindu Lakkaraju. 2021\.  Towards robust and reliable algorithmic recourse.  _Advances in Neural Information Processing Systems_ 34 (2021), 16926–16937.
  * Ustun et al. (2019) Berk Ustun, Alexander Spangher, and Yang Liu. 2019\.  Actionable recourse in linear classification. In _Proceedings of the conference on fairness, accountability, and transparency_. 10–19.
  * Venkatasubramanian and Alfano (2020) Suresh Venkatasubramanian and Mark Alfano. 2020.  The philosophical basis of algorithmic recourse. In _Proceedings of the 2020 conference on fairness, accountability, and transparency_. 284–293.
  * Virgolin and Fracaros (2023) Marco Virgolin and Saverio Fracaros. 2023.  On the robustness of sparse counterfactual explanations to adverse perturbations.  _Artificial Intelligence_ 316 (2023), 103840.
  * von Kügelgen et al. (2022) Julius von Kügelgen, Amir-Hossein Karimi, Umang Bhatt, Isabel Valera, Adrian Weller, and Bernhard Schölkopf. 2022.  On the fairness of causal algorithmic recourse. In _Proceedings of the AAAI Conference on Artificial Intelligence_ , Vol. 36. 9584–9594.