# User-Aware Algorithmic Recourse with Preference Elicitation

Giovanni De Toni  Fondazione Bruno KesslerVia SommariveTrentoItaly University
of TrentoVia SommariveTrentoItaly<EMAIL_ADDRESS>,  Paolo Viappiani
<EMAIL_ADDRESS>CNRS and University Paris DauphineFrance ,
Bruno Lepri<EMAIL_ADDRESS>Fondazione Bruno KesslerVia SommariveTrentoItaly and
Andrea Passerini<EMAIL_ADDRESS>University of TrentoItaly

(2023)

###### Abstract.

Counterfactual interventions are a powerful tool to explain the decisions of a
black-box decision process and to enable algorithmic recourse. They are a
sequence of actions that, if performed by a user, can overturn an unfavourable
decision made by an automated decision system. However, most of the current
methods provide interventions without considering the user’s preferences. In
this work, we propose a shift of paradigm by providing a novel formalization
which considers the user as an active part of the process rather than a mere
target. Following the preference elicitation setting, we introduce the first
human-in-the-loop approach to perform algorithmic recourse. We also present a
polynomial procedure to ask questions which maximize the Expected Utility of
Selection (EUS), a measure of the utility of the choice set that accounts for
the uncertainty with respect to both the model and the user response. We use
it to iteratively refine our cost estimates in a Bayesian fashion. We
integrate this preference elicitation strategy into a reinforcement learning
agent coupled with Monte Carlo Tree Search for the efficient exploration, so
as to provide personalized interventions achieving algorithmic recourse. An
experimental evaluation of synthetic and real-world datasets shows that a
handful of queries allows for achieving a substantial reduction in the cost of
interventions with respect to user-independent alternatives.

algorithmic recourse, counterfactual explanations, explainable AI, machine
learning

††copyright: none††journalyear: 2023††doi: XXXXXXX.XXXXXXX††ccs: Computing
methodologies Machine learning approaches

##  1\. Introduction

Automated decision systems are becoming ubiquitous in our daily lives. Through
machine learning technologies, we have been able to build systems to aid
humans in taking decisions for many tasks. Some of these tasks are also high-
risk and AI-based tools can have a significant impact on the life of affected
individuals. For example, we have machine learning models for deciding about
approving bail requests (Dressel and Farid, 2018), granting loans (Sheikh et
al., 2020), rejecting or accepting a job applicant (Liem et al., 2018), and
prescribing medications or treatments (Yoo et al., 2019). While quite
successful, these systems have several shortcomings that need to be carefully
addressed. First, users affected by these automated systems usually have no
means to overturn a potentially bad outcome, such as a denied loan request.
Generally, AI systems do not provide explanations or recommendations to act on
their decision. Second, many of the models are black boxes, which means that
even the designers of such systems cannot explain their reasoning process.
These issues raise substantial concerns about the trustworthiness and fairness
of these methods.

Being able to provide explanations or suggestions about how to overturn a
given decision made by a machine learning model is becoming a legal
requirement in certain countries. For example, Article 22 of the GDPR defines
the ”right to an explanation” as ”[…] the right not to be subject to a
decision based solely on automated processing, including profiling, which
produces legal effects concerning him or her or similarly significantly
affects him or her”(Voigt and Von dem Bussche, 2017; Goodman and Flaxman,
2017). A way to interpret the ”right to an explanation” is called algorithmic
recourse, which is the ability to give “explanations and recommendations to
individuals who are unfavourably treated by automated decision-making systems”
(Karimi et al., 2021; Venkatasubramanian and Alfano, 2020). A quite rich
literature has been flourishing in recent years about how to practically model
and implement algorithmic recourse (De Toni et al., 2023; Naumann and Ntoutsi,
2021; Karimi et al., 2022; Ramakrishnan et al., 2020; Yonadav and Moses, 2019;
Ustun et al., 2019; Karimi et al., 2020b; Tsirtsis and Rodriguez, 2020). The
standard framework for achieving algorithmic recourse is the following: we
want to find a counterfactual intervention (Wachter et al., 2017), which is a
sequence of actions that, if applied by the user, can overturn the decision
given by a machine learning model. Moreover, we want to provide the shortest
sequence of actions which produces the least effort, or cost, upon the user.
Finally, we aim to rely on causal relationships to determine the best
interventions. Indeed, recent research has shown that it would be impossible
to achieve optimal recourse without considering a causal structure (Karimi et
al., 2020c). However, the current literature focuses on generating
interventions by placing hard assumptions. The most relevant is that they do
not take into consideration the potential preferences of the users, thus the
individual cost of the actions is fixed a-priori. Although these systems are
supposed to provide personalized interventions, the users themselves are
modelled as passive agents rather than active participants.

Moreover, current research proposes rather naive solutions to account for user
preferences in algorithmic recourse, by either presenting the user with a set
of interventions (generated in a user-independent fashion) to choose from or
asking the user to quantify the cost of each possible action beforehand (Yadav
et al., 2021; Karimi et al., 2022). Although these solutions sound appealing
from a research-oriented perspective, they do not consider the reality of
decision-making. First, users can deal with a limited number of items at a
time (Simon, 1955), and they are constrained by their information processing
capabilities. Thus, choosing from a large set of interventions requires a
considerable cognitive effort (March, 1978). Second, users can rarely
formulate their objectives or preferences on the spot and prefer to give
qualitative assessments, such as ”I prefer A over B”, rather than quantitative
ones. Unfortunately, algorithmic recourse literature still views users as
passive entities, while we argue they should be made the principal elements of
the optimization process. Additionally, research shows that interaction
enables users to understand what actions are possible, thus shaping their own
preferences (Miettinen et al., 2008).

In this work, we propose a shift of paradigm by modelling the user as an
active part of the algorithmic recourse process, rather than just an entity
subjected to our decisions. We present the first human-in-the-loop framework
to generate counterfactual interventions specifically tailored to a given
user. We show how it is possible to refine generic interventions to provide
better recommendations through preference elicitation (Viappiani and
Boutilier, 2010) under a Bayesian setting. We relax the initial assumptions by
interactively learning the user’s specific costs starting from an initial
prior. At each algorithm iteration, we ask the user to choose the best
available action from a small choice set. The choice set is computed to
maximize the Expected Utility of Selection (EUS). Given the user’s answers, we
improve our estimate of the weights, which will enable us to generate
interventions closer and closer to the optimal sequence for the user. We
exploit an improved Reinforcement Learning technique coupled with Monte Carlo
Tree Search (MCTS) for an efficient search to find the interventions given the
user’s state. Lastly, we discuss additional open challenges that arise when we
elicit user preferences so as to achieve real user-aware algorithmic recourse.

The main contributions of the paper are the following:

  * •

We provide the first human-in-the-loop method to generate personalized
counterfactual interventions by casting the problem through the lens of
preference elicitation.

  * •

We provide a greedy procedure which builds an optimal choice set, maximizing
the Expected Utility of Selection (EUS) in polynomial time.

  * •

We experimentally show how our interactive approach can generate substantially
cheaper interventions than the user-independent counterpart with just a
handful of queries under different user response models.

##  2\. Related work

Counterfactual interventions, (or explanations) (Wachter et al., 2017; Dandl
et al., 2020; Mothilal et al., 2020; Karimi et al., 2020a; Guidotti et al.,
2018; Stepin et al., 2021) are powerful tools to explain the decision of
machine learning models. They are model-agnostic, local and human-friendly,
thus suited to be given as an explanation to an affected user (Miller, 2019).
Several works propose different methods to obtain algorithmic recourse via
counterfactual interventions (Karimi et al., 2022). They exploits various
techniques: program synthesis (De Toni et al., 2023; Ramakrishnan et al.,
2020), integer programming (Ustun et al., 2019), probabilistic models (Karimi
et al., 2020b) or reinforcement learning (Yonadav and Moses, 2019; De Toni et
al., 2023; Ramakrishnan et al., 2020). Unfortunately, most of the presented
works assume fixed costs which are not learned from data ( (De Toni et al.,
2023; Naumann and Ntoutsi, 2021; Ramakrishnan et al., 2020; Yonadav and Moses,
2019) and many more). It is a very strong assumption that is rarely met in
practice and can introduce bias in the proposed interventions. Our proposal is
to learn these costs by interacting with the user during the intervention
generation phase. Most existing counterfactual intervention generation
approaches are ill-suited to incorporate an interactive elicitation stage, as
they would need explicitly model costs as features in order to converge to a
solution (for example (Ramakrishnan et al., 2020; Yonadav and Moses, 2019)),
substantially increasing the complexity of the search procedure and the
computational budget needed to converge, especially in purely heuristic
methods (Naumann and Ntoutsi, 2021). On the other hand, neuro-symbolic
approaches, such as (De Toni et al., 2023), can be adapted to generate
personalized interventions even if trained in a user-agnostic way, by
integrating the search procedure with a preference elicitation strategy and
using the neural output as a prior to drive the explorations. We follow this
strategy in designing our personalized counterfactual intervention generation
method.

Reasoning with preferences and their elicitation are important topics in AI.
Modern approaches to preference elicitation adopt some measure of uncertainty
on preferences in order to ask informative queries (questions to the user)
with the goal of converging to near-optimal recommendations with just a few
answers to queries. While an important line of research in preference
elicitation deals with minimax regret (Boutilier et al., 2006; Perny et al.,
2016; Benabbou et al., 2017; Toffano et al., 2021), Bayesian methods
(Chajewska et al., 2000; Guo and Sanner, 2010; Viappiani and Boutilier, 2010)
have the advantage of modelling imprecision in users answers. Choice queries,
prompting the user to select a preferred item among a set, are often used in
elicitation; informative choice queries can be selected using some informative
measure (Viappiani and Boutilier, 2020; Toffano et al., 2021). Research works
dealing with uncertain preferences and preference elicitation include works
dealing with decisions under risk (Perny et al., 2016), sequential decision
problems (Akrour et al., 2012), non-linear aggregation functions (Benabbou et
al., 2017), social choice problems (Lu and Boutilier, 2011), constructive
domains (Teso et al., 2016; Dragone et al., 2018), recommendations in large
datasets with deep learning architecture (Vendrov et al., 2020). We use
insights from the Bayesian preference elicitation setting to extend the
algorithmic recourse methodology by incorporating the users during the
optimization process.

(a) Overview of the complete procedure

(b) User-Aware Counterfactual Intervention

Figure 1. (a) Overview of the complete procedure (1) Given initial
$\mathbf{s}^{(0)}$ and $\mathbf{w}^{(0)}$, we compute a set of candidate
interventions (2) We generate a choice set $O^{(t)}$ which will be presented
to the user (3) The user chooses the best action (4) Given the user’s choice,
we improve the weights $w^{(t+1)}$ and (5) we also update the user’s state
$\mathbf{s}^{(t+1)}$. After $q$ questions, we use the estimated weights to
compute the final optimal intervention $I^{*}$. (b) Example of an explainable
counterfactual intervention taken from the experiments. We have both the
sequence of action the user needs to follow and an example of a Boolean
explanation for such action.

##  3\. Overview of the method

The procedure works in rounds. For each round, we present the user with a set
of $k$ candidate interventions. This choice-set is selected so as to maximize
the information gain we can get from the user feedback. Following the
preference elicitation theory, we use a polynomial-time greedy procedure to
choose such $k$ interventions. Section 6.3 shows the optimization objective
and the technique to build the optimal choice set. We choose $k$ to be small
to minimize the cognitive effort for the user (e.g., $k=2$ or $k=4$). Once
presented with this small choice-set, the user selects which intervention they
like most. We elicit a qualitative response from the user since it is the
simplest form of feedback. After $q$ rounds, we compute the final
recommendation, given all the previous answers provided by the user. Each
intervention is composed of ordered actions, and each action specifies which
feature needs to be modified and the magnitude of the change (e.g., ”Increase
your income by 100$.”). See Figure 1 for a high-level overview of our method
and an example of a generated intervention.

Our approach relies on a procedure which can generate interventions based on
some user preferences $\mathbf{w}$. After each round, we update our estimate
of the user preferences, and we generate new candidate interventions following
the preferences we have estimated so far. In our work, we developed a model
which extends the user-agnostic work of De Toni et al. (De Toni et al., 2023).
Section 5 gives an overview of the new technique, which we call W-FARE. As
will be shown in our experimental evaluation, W-FARE can generate effective
user-aware interventions after just a handful of queries. However,
interventions alone might not be enough to generate trust in the user, because
of the lack of an explanation for the reason why a certain set of actions is
being suggested. Therefore, we additionally developed W-EFARE, a deterministic
method which can augment interventions with action-specific explanations in
the form of Boolean rules. An example of such explanatory rules is shown at
the bottom right of Figure 1. W-EFARE was developed by adapting the
deterministic method in De Toni et al. (De Toni et al., 2023) to make its
explanatory rules user-aware. Section 6.5 and Figure 3 explain the method in
detail and show how to use it for inference.

In the following, we provide a detailed formal treatment of the proposed
approach, starting from a formalization of the problem setting.

##  4\. Problem Setting

A user state $\mathbf{s}\in\mathcal{S}$ is defined as a vector of $d$
features. A feature $s_{i}$ can be categorical or real-valued. Given a user
state $\mathbf{s}$, an action $a\in\mathcal{A}$ changes a single feature
$s_{i}$ to a new value $s_{i}^{\prime}$. Let us also define a cost function
$C:\mathcal{A}\times\mathcal{S}\rightarrow\mathbb{R}^{+}$. The cost function
models the effort required by a user to change a feature given a user state.
As features are causally related to each other, the cost of changing a feature
also depends on the value of a subset of other features.

The cost function $C$ is defined in terms of a linear structural causal model
(SCM) (Pearl, 2009). An SCM is a directed graph $G=(V,E)$, which represents
causal relationships as edges between nodes. In our setting, each node
represents the cost of changing a single user feature $s_{i}$. We denote the
nodes as $C_{i}$. A directed edge $e\in E$ represents a causal relationship
between two nodes $(C_{i},C_{j})$. Each edge $e$ has associated a weight
$w_{ij}\in\mathbb{R}$. Moreover, each node has its internal weight $w_{i}$. We
represent the full weights of the linear SCM as a vector
$\mathbf{w}\in\mathbb{R}^{m}$, where $m=|E|+|V|$. The SCM is linear, which
means that the cost of changing a feature $s_{i}$ is assumed to be a linear
combination of other costs. We denote with $C(a,\mathbf{s}|\mathbf{w})$ the
cost of changing a given feature $s_{i}\in\mathbf{s}$ to its value
$s_{i}^{\prime}$ by applying action $a\in\mathcal{A}$, given the weights
$\mathbf{w}$. More formally:

(1)
$C(a,\mathbf{s}|\mathbf{w})=w_{i}(s_{i}^{\prime}-s_{i})+\sum_{j\;\in\;Pa_{i}}w_{ji}s_{j}$

where $s_{i}$ and $s_{i}^{\prime}$ are, respectively, the old and new values
of the feature modified by $a$, and $Pa_{i}$ are the parents of the $s_{i}$
node. See Figure 2 for an example of SCM and associated cost functions.

An intervention $I$ is a sequence of actions $\\{a^{(0)},\ldots,a^{(T)}\\}$.
Let us define the intervention cost, $C(I|\mathbf{w})$ as:

(2) $C(I|\mathbf{w})=\sum_{t=0}^{T}C(a^{(t)},\mathbf{s}^{(t)}|\mathbf{w})$

where $\mathbf{s}^{(t)}$ is the state obtained by applying action $a^{(t-1)}$
to state $\mathbf{s}^{(t-1)}$, and $\mathbf{s}^{(0)}=\mathbf{s}$ is the
initial state of the user. We denote with $I(\mathbf{s}^{(0)})$ the operation
of applying each action $a\in I$ sequentially. Given a user profile
$\mathbf{s}$ with the corresponding weightings $\mathbf{w}$, we are interested
in finding the optimal intervention sequence $I^{*}$, which minimizes the
intervention cost for the user and enables algorithmic recourse. More
formally, given a black-box binary classifier111In this work, we focus on
binary classification problems. However, it is straightforward to adapt the
approach to deal with multiclass classification problems.
$h:\mathcal{S}\rightarrow\\{0,1\\}$ we want to find an intervention $I^{*}$
such that:

(3) $I^{*}=\hbox{argmin}_{I}\;C(I|\mathbf{w})\quad\hbox{s.t.}\quad
h(I^{*}(\mathbf{s}^{(0)}))\neq h(\mathbf{s}^{(0)})$

Figure 2. A Linear Structural Causal Model for cost modelling. Given a user
state, $\mathbf{s}=[s_{1},s_{2},s_{3}]$, the cost of changing a feature (e.g.,
$C_{3}$) depends on its parents in the graph. The weight vector $\mathbf{w}$
models the user preferences. Red weights refer to the node components, while
blue weights refer to the edge components.

##  5\. User-Aware Counterfactual Models

We employ a strategy similar to the FARE method proposed by De Toni et al.
(2022) (De Toni et al., 2023), which uses a combination of reinforcement
learning (RL) coupled with Monte Carlo Tree Search (MCTS) to achieve recourse.
This strategy exploits RL to learn a generalized policy that can be applied to
multiple users to provide interventions. FARE is highly scalable, and it was
shown to learn successful policies to obtain recourse by reducing the training
budget and the number of queries made to the black-box classifier with respect
to competitors.

Following (De Toni et al., 2023), we define an action $a\in\mathcal{A}$ as a
tuple $(f,x)$, where $f$ represents a function and $x$ represents a value for
its argument, as in $(change\\_income,\$1000)$. Each action $a$ has an
associated precondition which tells us when the action can be called given the
state $\mathbf{s}$. Given the user state $\mathbf{s}$, the RL agent produces
two policies $\pi_{f}(\mathbf{s})$ and $\pi_{x}(\mathbf{s})$, over the
potential functions and arguments spaces. A policy $\pi(\mathbf{s})$ is a
probability distributions over $\mathcal{A}$ such that
$\sum_{a\in\mathcal{A}}\pi(a|\mathbf{s})=1$. The two policies are used as a
prior driving the MCTS search procedure when choosing the next action
$a^{(t+1)}$. During inference, the RL agent and the MCTS work together to
generate the intervention, which achieves recourse and minimizes the cost for
the user.

In the original setting, the RL agent is trained by assuming fixed weights
shared by all the users. We adapted this strategy to deal with unknown user-
specific costs by integrating it with a preference elicitation procedure. The
original formulation computes the reward of an intervention as
$r=\lambda^{T}R$, where $T$ is the length of the intervention, $\lambda$ is a
penalization coefficient and $R$ is equal to
$\mathbbm{1}[h(I^{*}(\mathbf{s}^{(0)}))\neq h(\mathbf{s}^{(0)})]$ where
$\mathbbm{1}$ is the indicator function (Eqn. 4 in Section 3.2 of (De Toni et
al., 2023)). Therefore, the agents’ policy is transparent to the user’s
weights, and only the MCTS search procedure can take them into account. We
improved the original reward to $r=\lambda^{C(I|\mathbf{w})}R$ to explicitly
learn a policy optimized over the intervention costs given w rather than
exclusively the length of the intervention $T$. This modification helps the
MCTS to converge on the right low-cost intervention. We call this new model
W-FARE.

##  6\. Personalized Counterfactual Intervention Generation

We now describe each step of the procedure to build personalized
interventions. First, we formalize the notion of expected cost given the
user’s weights $\mathbf{w}$. Second, we show how to formalize user feedback
elicitation in terms of choice set queries. Last, we integrate the resulting
preference elicitation strategy into the counterfactual intervention
generation process.

###  6.1. Expected Intervention Costs

While we can fully know the user state $\mathbf{s}\in\mathcal{S}$, we are
usually unaware of the associated weights $\mathbf{w}$, nor it is possible to
infer them directly from the state. Indeed, users with the same initial state
$\mathbf{s}\in\mathcal{S}$ might favour different actions.

We model our uncertainty on the costs of the user in terms of a probability
distribution $P(\mathbf{w})$ over the weights in the SCM (see Figure 2). Given
a dataset $\mathcal{D}^{(t)}$ of user responses, we are interested in
estimating the posterior of the weights given the feedback,
$P(\mathbf{w}|\mathcal{D}^{(t)})$. In this setting, the cost of an action is
replaced with an expected action cost,
$\mathbb{E}[C(a^{(t)},\mathbf{s}^{(t)})|\mathcal{D}^{(t)}]$, computed by
marginalizing over all the possible weightings $\mathbf{w}\in\mathbb{R}^{m}$:

(4)
$\mathbb{E}[C(a^{(t)},\mathbf{s}^{(t)})|\mathcal{D}^{(t)}]=\int_{\mathbf{w}}C(a^{(t)},\mathbf{s}^{(t)}|\mathbf{w})P(\mathbf{w}|\mathcal{D}^{(t)})\;\mathit{d}\mathbf{w}$

Analogously, the cost of an intervention $I$ is replaced by its expected
intervention cost:

(5)
$\mathbb{E}[C(I)|\mathcal{D}]=\sum_{t=0}^{T}\mathbb{E}[C(a^{(t)},\mathbf{s}^{(t)})|\mathcal{D}^{(t)}]$

The integral defined by Equation 4 cannot be easily computed analytically
because of the difficulty of finding a closed-form formulation for
$P(\mathbf{w}|\mathcal{D}^{(t)})$. Thus, we need to resort to techniques to
obtain an approximate estimation of the integral (e.g., Monte Carlo sampling).
In the next sections, we outline how to build the dataset $\mathcal{D}^{(t)}$
and how the preference elicitation process is carried out.

###  6.2. Candidate Interventions and Choice Sets

In order to incorporate user preferences, we need to define the notions of
candidate interventions and choice set. These constructs will be useful when
querying the user for feedback.

###### Definition 6.0 (Candidate Intervention).

A candidate intervention $\hat{I}_{a}^{(t)}$ is a sequence of actions,
$\\{a,a_{1},\ldots,a_{T}\\}$, that is built given the posterior
$P(\mathbf{w}|\mathcal{D}^{(t)})$ after $t$ questions and which starts with
the action $a$.

A candidate intervention shows a potential sequence of actions which might not
be optimal since it depends on the quality of the posterior. We want to
improve our initial estimate, $P(\mathbf{w}|\mathcal{D}^{(t)})$, by asking the
user to pick the preferred next action from a choice set. This set contains a
collection of candidate interventions.

###### Definition 6.0 (Choice set).

A choice set $O^{(t)}$ is a collection of $k$ tuples, $(a,\hat{I}^{(t)}_{a})$,
which are made by an action $a\in\mathcal{A}$ and a candidate intervention
$\hat{I}^{(t)}_{a}$.

In our setting, the dataset $\mathcal{D}^{(t)}$ becomes the set of choices,
candidate interventions and associated choice sets
$\\{(a,\hat{I}_{a},O)^{(0)},\ldots,(a,\hat{I}_{a},O)^{(t)}\\}$ made by the
user up to timestep $t$. Therefore, $P(\mathbf{w}|\mathcal{D}^{(t)})$ measures
the probability that the user’s SCM has the weights $\mathbf{w}$, based on the
provided answers. The peculiarity of this setting is that the data is ordinal
information about which item is preferred within each set.

###  6.3. Generating the choice set

Given our estimate $P(\mathbf{w}|\mathcal{D}^{(t)})$, we need to show the user
the best choice set available, which maximizes the information gain.
Presenting the user with a poorly chosen choice set could slow down the
estimation process or make it fail.

Following the preference elicitation setting (Viappiani and Boutilier, 2010),
we define the expected utility of a candidate intervention $\hat{I}_{a}$ under
a belief $P(\mathbf{w}|\mathcal{D}^{(t)})$ as the negation of its expected
cost:

(6)
$\operatorname{EU}(\hat{I}_{a}|\mathcal{D}^{(t)})=-\mathbb{E}[C(\hat{I}_{a})|\mathcal{D}^{(t)}]=-\int_{\mathbf{w}}C(\hat{I}_{a}|\mathbf{w})P(\mathbf{w}|\mathcal{D}^{(t)})\;\mathit{d}\mathbf{w}$

For each time step $t$, we have to provide to the user the choice set $O^{*}$
that has the highest value of information (Chajewska et al., 2000). For the
choice set, the maximally informative query is the one that maximizes expected
utility of a selection ($EUS$) (Viappiani and Boutilier, 2020). Intuitively,
we should choose a choice set that maximises the user’s expected utility,
which means minimizing the overall expected cost of successful interventions.
However, we cannot assume the user will always choose the best action.
Therefore, we model the user’s choice with a noise model $R$. We define
$P_{R}(O^{(t)}\leadsto a|\mathbf{w})$ as the probability of choosing $a$ from
$O^{(t)}$ under the user response model $R$ and weighting $\mathbf{w}$. In our
case, we choose the logistic response model (L) which is commonly used in
choice modelling (Luce, 2012):

(7) $P_{L}(O^{(t)}\leadsto a|\mathbf{w})=\frac{\exp(-\lambda
C(\hat{I}_{a}|\mathbf{w}))}{\sum_{\hat{I}_{a^{\prime}}\in
O^{(t)}}\exp(-\lambda C(\hat{I}_{a^{\prime}}|\mathbf{w}))}$

where $\lambda\in\mathbb{R}$ is a temperature parameter. Intuitively, under
the logistic response model, two actions producing interventions with similar
costs will have a similar probability of being chosen by the user. Lastly, we
can define the $\operatorname{EUS}$ over a choice set $O^{(t)}$ as:

(8)
$\begin{split}\operatorname{EUS}_{L}(O^{(t)}|\mathcal{D}^{(t)})=&\sum_{a,\hat{I}_{a}\in
O^{(t)}}P_{L}(O^{(t)}\leadsto
a)\operatorname{EU}(\hat{I}_{a}|\mathcal{D}^{(t)})\\\
=&-\int_{\mathbf{w}}\left[\sum_{a,\hat{I}_{a}\in O^{(t)}}P_{L}(O^{(t)}\leadsto
a|\mathbf{w})C(\hat{I}_{a}|\mathbf{w})\right]P(\mathbf{w}|\mathcal{D}^{(t)})\;\mathit{d}{\mathbf{w}}\end{split}$

Generally, the naive maximization of the $EUS$ is computationally intensive
and intractable in practice. It is possible to prove that the task is NP-hard
(Nemhauser et al., 1978; Krause and Golovin, 2014). However, under some
response models $R$, the $EUS$ function defined by Equation 8 is submodular
(Krause and Golovin, 2014), and there exists a procedure that can determine an
approximation of the optimal set $O^{*}$ with proven accuracy bounds.

It is possible to prove that we can compute $\operatorname{EUS}$ by using the
noisless response model (NL) as a proxy (Viappiani and Boutilier, 2010) and we
can take advantage of the worst-case guarantee of the greedy algorithm; that
is $\operatorname{EUS}_{L}-\operatorname{EUS}_{NL}$ is always smaller than a
problem independent bound. Namely, instead of minimizing
$\operatorname{EUS}_{L}$ directly, we compute the choice set by miniminizing
$\operatorname{EUS}_{NL}$ that is monotone and submodular. More formally,
there exists a greedy polynomial algorithm that achieves
$\operatorname{EUS}_{NL}(O|\mathcal{D})\geq(1-e^{-1})\operatorname{EUS}_{NL}(O^{*}|\mathcal{D})$,
where $O^{*}$ is the optimal choice set (Viappiani and Boutilier, 2010;
Nemhauser et al., 1978; Krause and Golovin, 2014). The noiseless response
model is such that:222For the sake of presentation, we assume that there are
no ties. Note that the EUS formula is invariant to the way ties are broken. In
our implementation, ties are broken uniformly at random.

(9) $P_{NL}(O^{(t)}\leadsto a)=\prod_{a^{\prime},\hat{I}_{a^{\prime}}\in
O^{(t)}\;:\;a^{\prime}\neq
a}\mathbbm{1}[C(\hat{I}_{a}|\mathbf{w})<C(\hat{I}_{a^{\prime}}|\mathbf{w})]$

which in turn produces a new $\operatorname{EUS}$ formulation:

(10)
$\operatorname{EUS}_{NL}(O^{(t)}|\mathcal{D}^{(t)})=-\int_{\mathbf{w}}\min_{a,\hat{I}_{a}\in
O^{(t)}}\\!\\{C(\hat{I}_{a}|\mathbf{w})\\}\,P(\mathbf{w}|\mathcal{D}^{(t)})\;\mathit{d}{\mathbf{w}}$

In practice, following the submodularity property, we can build a choice set
$O^{(t+1)}$ by iteratively adding the tuple $(a,\hat{I}_{a})\in
2^{\mathcal{A}^{\prime}\times\mathcal{I}}\backslash O^{(t)}$ that maximally
increases the $EUS$. We consider only feasible actions
$\mathcal{A}^{\prime}\subseteq\mathcal{A}$ for building the set. Given a state
$\mathbf{s}^{(t)}$, an action $a\in\mathcal{A}$ is feasible if it has its
precondition satisfied (see Section 5). More formally:

(11) $(a,\hat{I}_{a})=\hbox{argmax}_{(a,\hat{I}_{a})\in
2^{\mathcal{A}^{\prime}\times\mathcal{I}}\backslash
O^{(t)}}\;\;\operatorname{EUS}_{NL}(O^{(t)}\cup(a,\hat{I}_{a})|\mathcal{D}^{(t)})-\operatorname{EUS}_{NL}(O^{(t)}|\mathcal{D}^{(t)})$

Algorithm 1 Greedy polynomial procedure to compute efficiently a choice set
$O$.

1:procedure SUBMOD-CHOICE($\mathbf{s}^{(t)}$, $k$, $\mathcal{A}$,
$\mathcal{D}^{(t)}$, $\mathbf{w}$, $\delta$)

2: $O\leftarrow\emptyset$

3: while $|O|<k$ do

4: Compute the feasible actions $\mathcal{A}^{\prime}\subseteq\mathcal{A}$
given $\mathbf{s}$.

5: Generate the candidate interventions
$\mathcal{I}=\\{(a,\hat{I}_{a})\,:\,a\in\mathcal{A}^{\prime}\\}$ where
$\delta(\mathbf{s},\mathbf{w}|a)=\hat{I}_{a}$.

6: Given
$\Delta\operatorname{EUS}=\operatorname{EUS}_{NL}(O\cup(a,\hat{I}_{a})|\mathcal{D}^{(t)})-\operatorname{EUS}_{NL}(O|\mathcal{D}^{(t)})$

7: $(a,\hat{I}_{a})\leftarrow\hbox{argmax}_{(a,\hat{I}_{a})\in
2^{\mathcal{A}^{\prime}\times\mathcal{I}}\backslash O}\;\;\Delta EUS$

8: $O\leftarrow O\cup(a,\hat{I}_{a})$

9: end while

10: return $O$

11:end procedure

The procedure is repeated until we reach $|O^{(t+1)}|=k$, where $k$ is the
maximum size of the choice set. Algorithm 1 shows the pseudocode of the
SUBMOD-CHOICE procedure that generates a choice set greedily. The algorithm
takes as input: $\mathbf{s}^{(t)}\in\mathcal{S}$, the state of the user at
step $t$, $k\in\mathbb{N}^{+}$, the size of the choice sets, $\mathcal{A}$,
the available actions, $\mathcal{D}^{(t)}$ the user responses dataset up to
time $t$, $\mathbf{w}\in\mathbb{R}^{m}$, the weights, and
$\delta:\mathcal{S}\times\mathbb{R}^{m}\rightarrow\mathcal{I}$, the recourse
generation method. $\delta$ takes as input the user state, and the weights and
generate an intervention $I$. The notation $\delta(\cdot|a)$ indicates that
the generation procedure uses action $a$ as the first action.

Algorithm 2 User-aware Algorithmic Recourse

1:procedure UA-RECOURSE($\mathbf{s}^{(0)}$, $q$, $k$, $h$, $\mathcal{A}$,
$\delta$)

2:
$\mathbf{w}=\mathbb{E}_{p(\mathbf{w})}[\mathbf{w}]\qquad\mathbbm{\mu}=\\{\mathbbm{\mu}_{i}\\}_{i=1}^{M}\quad\mathbf{\Sigma}=\\{\mathbf{\Sigma}_{i}\\}_{i=1}^{M}$

3: Initialize $t\leftarrow
0,\;I^{(0)}\leftarrow\emptyset,\;\mathcal{D}^{(0)}\leftarrow\emptyset$

4: for $t\leq q$ do

5: if $h(I^{(t)}(\mathbf{s}^{(0)}))=h(\mathbf{s}^{(0)})$ then

6: $\textbf{s}^{(t)}\leftarrow\textbf{s}^{(0)}$

7: $I^{(t)}\leftarrow\emptyset$

8: end if

9: $O^{(t)}$ $\leftarrow$ SUBMOD-CHOICE($\mathbf{s}^{(t)}$, $k$,
$\mathcal{A}$, $\mathcal{D}^{(t)}$, $\mathbf{w}$, $\delta$)

10: Ask the user to pick the best intervention $(a,\hat{I}_{a})\in O^{(t)}$

11: $D^{(t+1)}\leftarrow(a,\hat{I}_{a},O)^{(t)}\cup\mathcal{D}^{(t)}$

12: $I^{(t+1)}=I^{(t)}\circ a$

13: $\mathbf{s}^{(t+1)}=I^{(t+1)}(\mathbf{s}^{(0)})$

14: Update weight estimate
$\mathbf{w}=\mathbb{E}_{P(\mathbf{w}|\mathcal{D}^{(t+1)})}[\mathbf{w}]$

15: $t\leftarrow t+1$

16: end for

17: Given
$\mathbf{w}^{*}=\mathbb{E}_{P(\mathbf{w}|\mathcal{D}^{(T)})}[\mathbf{w}]$,
compute the final intervention
$\delta(\mathbf{s}^{(0)},\mathbf{w}^{*})=I^{*}$.

18: return $I^{*}$

19:end procedure

###  6.4. Generating the personalized interventions

Algorithm 2 shows the complete procedure to refine the interventions given the
user’s feedback. The procedure takes as arguments:
$\mathbf{s}^{(0)}\in\mathcal{S}$, the initial state of the user,
$q\in\mathbb{N}^{+}$, how many questions we will ask, $k\in\mathbb{N}^{+}$,
the size of the choice sets, the classifier
$h:\mathcal{S}\rightarrow\\{0,1\\}$, $\mathcal{A}$, the available actions, and
$\delta:\mathcal{S}\times\mathbb{R}^{m}\rightarrow\mathcal{I}$, the recourse
generation method. We now give a step-by-step description of the procedure:

  1. (1)

At $t=0$, we initialize $\mathbf{w}$ with the expected value of the prior
$P(\mathbf{w})$. We also initialize an empty intervention $I^{(0)}$ which will
record all the actions chosen by the user;

  2. (2)

At time step $t$, we build the choice set $O^{(t)}$ with SUBMOD-CHOICE (see
Algorithm 1);

  3. (3)

Given $O^{(t)}$, we ask the user to pick her preferred action $a$. The
associated candidate interventions are shown to the user to help her with the
selection. The choice set $O^{(t)}$ together with the choice made by the user
is then added to the dataset $\mathcal{D}^{(t)}$;

  4. (4)

We concatenate the current intervention $I^{(t)}$ with the user’s choice $a$
to obtain $I^{(t+1)}=I^{(t)}\circ a$, which is applied to the state
$\mathbf{s}^{(0)}$ to produce the new state $\mathbf{s}^{(t+1)}$. If the new
state achieves recourse, then we reset the user state to $\textbf{s}^{(0)}$
before the next iteration (see lines 5-8);

  5. (5)

We average over the particles with the highest likelihood to approximate the
expected value of $P(\mathbf{w}|\mathcal{D}^{(t+1)})$;

  6. (6)

We iterate steps 2-5 until we reach the maximum number of questions ($t>q$).
Then, we run the counterfactual model $\delta$ to generate the final
intervention which will be recommended to the user.

In this work, we assume $P(\mathbf{w})$ to be a mixture of multivariate
Gaussian distributions with $M$ components,
$\mathcal{N}_{i}(\mathbbm{\mu}_{i},\mathbf{\Sigma}_{i})$. $P(\mathbf{w})$
should account for diverse populations of individuals with different
preferences. Such prior distribution can be fitted according to available data
about the preferences of the general population. If no or limited data is
available, an informative prior can be used. In order to estimate the weights,
we should compute the Bayesian update $P(\mathbf{w}|\mathcal{D}^{(t)})\propto
P(\mathcal{D}^{(t)}|\mathbf{w})P(\mathbf{w})$ (on line 14 of Algorithm 2).
However, computing analytically the likelihood is problematic since
$\mathcal{D}^{(t)}$ is a set of preferences, thus we use Monte Carlo methods
to sample from the posterior. We employ ensemble split sampling (Karamanis and
Beutler, 2020; Karamanis et al., 2021) and then we average over the particles
with the highest likelihood to get an estimate of $\mathbf{w}$ after each
iteration.

Figure 3. The deterministic cost-aware W-EFARE model. Given
$(\mathbf{s}^{\prime},\mathbf{w})$, we traverse the graph (green path) using
the decision tree (orange components) to choose the next action $(f,x)^{(t)}$
from the available transitions. When we reach the STOP node, we return the
found intervention $I^{*}$. On the right, we have a generated intervention
achieving recourse for the GiveMeSomeCredit dataset. On the top-right, we have
the Boolean rule extracted from the decision tree motivating the first
recommended action $\mathtt{ReduceOpenCreditLines}$. As we can see, W-EFARE
can generate rules that also depend on the cost function $C$, achieving the
desired user awareness.

###  6.5. User-Aware Explainable Interventions

Our approach asks the users to choose the best option from a small set of
interventions. These interventions are computed by using a recourse generator
$\delta$. More specifically, SUBMOD-CHOICE (Algorithm 1) requires to compute
the candidate interventions for each action
$a\in\mathcal{A}^{\prime}\subseteq\mathcal{A}$ given $\delta$. The task of
picking the best intervention requires cognitive effort since the user must
understand all the recommended sequences of actions. This can be problematic
if the user does not understand the reason behind the recommendations,
undermining the quality of the feedback they provide and their overall trust
in the system. In order to overcome this problem, we additionally developed a
variant of $\delta$ that can complement interventions with action-specific
explanations.

In (De Toni et al., 2023), the authors proposed EFARE, which is a
deterministic user-agnostic model for generating recourse by providing Boolean
explanations for each action in the intervention. The procedure to generate
this model works as follows. Given a trained FARE model, a sample of
successful interventions, or traces, for the training set users is extracted.
These traces are merged to form a graph, where each node represents an action
$a$, and each arch represents which actions $(f,x)$ can be taken from the said
node. Then, for each node, a small decision tree is trained to indicate, given
a user state s, which is the next action to recommend. Given this trained
automaton, we can traverse the graph using the decision trees to transition
between nodes. Moreover, the decision trees can give us Boolean explanations
for each transition. More details can be found in Section 3.6 of (De Toni et
al., 2023).

In the following, we show how this procedure can be adapted to account for
user-specific costs. The resulting model, that we call W-EFARE, is a user-
aware version of EFARE that integrates the user weights as features in the
state $\mathbf{s}$. Given a user state s, we add the cost of every valid
action $a\in\mathcal{A}$ as an additional feature. Since an action $a=(f,x)$
is a combination of a function $f$ and a value $x$ for its argument, we
combine actions relating to the same function into a single feature, averaging
their cost over the set of argument values. This simplification allows to add
$|\mathcal{F}|$ additional features to the user state, where $\mathcal{F}$ is
the set of all possible functions. More formally, the user’s state
$\textbf{s}^{\prime}$ becomes

(12)
$\textbf{s'}=\textbf{s}\circ\left\\{\frac{1}{|\mathcal{X}_{f}|}\sum_{x\in\mathcal{X}_{f}}C((f,x),\textbf{s}|\textbf{w})\right\\}_{f\in\mathcal{F}}$

where $\mathcal{X}_{f}$ is the set of all the possible arguments for function
$f$. We also considered adding directly the weights w, but we discovered that
such representation makes it harder to learn an optimal policy. In this way,
the decision trees can directly exploit the user’s cost to provide a better
recommendation. Figure 3 shows a graphical illustration of how W-EFARE works
in practice. In this work, we evaluate both W-FARE and W-EFARE as recourse
generator models $\delta$.

##  7\. Experiments

We evaluated our approach on three datasets taken from the relevant
literature, one synthetic and two real-world: synthetic, (De Toni et al.,
2023), GiveMeSomeCredit (Kaggle, 2011) and Adult (Dua and Graff, 2017). They
all represent binary classification problems for loan/credit assignments. We
use the synthetic dataset from (De Toni et al., 2023) as a benchmark to
validate our approach in a controlled environment, where we can control the
data generation process and the decision function. In the other settings, we
rely on trained black-box classifiers. We sampled 200 (synthetic and Adult)
and 300 (GiveMeSomeCredit) instances with an unfavourable classification,
respectively. The datasets have both categorical and numerical features. They
also come with fixed costs and fixed causal graphs. We kept the corresponding
causal graphs, but we randomly generated user-specific weights for each
instance by sampling from a mixture of Gaussian with $K=6$ components. We have
a separate mixture for each dataset. For each dataset, we preprocessed the
data by standardizing numerical features and encoding categorical features
one-hot and we trained W-FARE and W-EFARE. The code and the data used for the
experiments are available on Github333The code will be released upon
acceptance. to ensure reproducibility. We vary the number of questions $q$
asked the user during the evaluation from 0 to a maximum of 10. We assume to
have a limited amount of questions available to account for the cognitive
burden placed on the user. For $q=0$, we initialize the weights with the
expected value of the prior, $\mathbb{E}_{P(\mathbf{w})}[\mathbf{w}]$. We
tested two different choice-set dimensions, $k=2$ and $k=4$. Moreover, we
employed two user response models, the noiseless model (Eqn. 9), to check the
effectiveness of our approach in the best-case scenario where the user can
perfectly express their preferences, and the logistic (Eqn. 7) model, to
challenge our approach in a more realistic scenario.

Table 1. (Normalized) Average True Regret Improvement
($1-R(\mathbf{I}|\mathbf{W})$) when we ask $q=1$ and $q=10$ questions under
all the response models and choice set sizes. With the minimal choice set
($k=2$) and $q=1$, we can provide interventions that are, on average, $\sim
40\%$ cheaper than the baseline. In bold, we have the best result for each
model.

(a) synthetic

Model | Noise | $|O^{(t)}|=2$ | $|O^{(t)}|=4$
---|---|---|---
$q=1$ | $q=10$ | $q=1$ | $q=10$
W-FARE | $R_{L}$ | 0.33 | 0.75 | 0.36 | 0.83
$R_{NL}$ | 0.38 | 0.79 | 0.51 | 0.83
W-EFARE | $R_{L}$ | 0.22 | 0.59 | 0.34 | 0.72
$R_{NL}$ | 0.37 | 0.70 | 0.55 | 0.73

(b) GiveMeSomeCredit

Model | Noise | $|O^{(t)}|=2$ | $|O^{(t)}|=4$
---|---|---|---
$q=1$ | $q=10$ | $q=1$ | $q=10$
W-FARE | $R_{L}$ | 0.30 | 0.80 | 0.30 | 0.86
$R_{NL}$ | 0.58 | 0.84 | 0.71 | 0.88
W-EFARE | $R_{L}$ | 0.37 | 0.86 | 0.34 | 0.80
$R_{NL}$ | 0.40 | 0.93 | 0.66 | 0.91

(c) Adult

Model | Noise | $|O^{(t)}|=2$ | $|O^{(t)}|=4$
---|---|---|---
$q=1$ | $q=10$ | $q=1$ | $q=10$
W-FARE | $R_{L}$ | 0.45 | 0.75 | 0.30 | 0.92
$R_{NL}$ | 0.57 | 0.96 | 0.59 | 1.00
W-EFARE | $R_{L}$ | 0.14 | 0.87 | 0.26 | 0.90
$R_{NL}$ | 0.84 | 0.96 | 0.85 | 0.98

First, we measured the validity of the methods, i.e., the fraction of users
for which we can find an intervention achieving recourse. W-FARE achieves a
validity of $86\%$, $68\%$ and $95\%$ for the synthetic, GiveMeSomeCredit and
Adult case, respectively. The deterministic model W-EFARE achieves a validity
of $83\%$, $76\%$ and $82\%$ instead. The sampling process to extract W-EFARE
from the trained policy of W-EFARE causes the performance loss in the
synthetic and Adult case, as previously noticed by (De Toni et al., 2023).
GiveMeSomeCredit has the opposite behaviour since it has a smaller sampling
pool. Thus, even if the sampling budget is small, W-EFARE is more
representative of the entire dataset and it can achieve a better validity than
its neural counterpart.

Second, we measured the regret of the interventions, which is the difference
between the cost of the recommended intervention $I$ and the cost of the best
intervention available if we knew the true user’s costs $\mathbf{w}^{*}$. More
formally, given the true weights
$\mathbf{W}=\\{\mathbf{w}^{*}_{i}\\}_{i=1}^{N}$ and the set of the elicited
interventions $\mathbf{I}=\\{I_{i}\\}_{i=1}^{N}$ for all the test users, the
average regret is:

(13)
$R(\mathbf{I}|\mathbf{W})=\frac{1}{N}\sum_{i=1}^{N}\left(C(I_{i}|\mathbf{w}^{*}_{i})-min_{I_{i}^{*}\in\mathcal{I}}C(I_{i}^{*}|\mathbf{w}^{*}_{i})\right)$

Table 1(c) shows the average improvement (i.e., one minus the normalized
regret) for the different datasets with the minimal ($q=1$) and maximal
($q=10$) number of queries. We can see that in all datasets and for all
models, we have a sensible regret improvement by performing preference
elicitation. More specifically, by taking the simplest setting, with $q=1$ and
$k=2$ and the more realistic logistic response, we have already $\sim 30\%$,
$\sim 34\%$ and $\sim 30\%$ average regret improvement over the baseline
($q=0$) for the synthetic, GiveMeSomeCredit and Adult case, respectively. As
expected, the gain is even more marked under the noiseless response model.
Increasing the number of questions to $q=10$ produces further improvements,
and we can provide interventions which are $\sim 67\%$, $\sim 83\%$ and $\sim
81\%$, respectively, cheaper than the $q=0$ recourse. Increasing the size of
the choice set (from $k=2$ to $k=4$) is also beneficial, under both the
logistic and noiseless response model. Figure 4 shows the regret as a function
of the number of questions for the three datasets for both $k=2$ and $k=4$,
confirming the positive trend in terms of both questions and choice-set size.

We also measure the sequence similarity between the optimal intervention and
the recommended one, so as to evaluate the agreement in terms of recommended
actions in addition to intervention cost. Under $k=2$, $q=1$ and the logistic
noise, the intervention’s similarity is quite high. We have $\sim 67\%$, $\sim
70\%$ and $\sim 70\%$ for the synthetic, GiveMeSomeCredit and Adult case,
respectively. With $q=10$ we reach $\sim 83\%$, $\sim 87\%$ and $\sim 88\%$.
Again, the most important factor for increasing the similarity is the number
of questions. The errors reducing the similarity are mostly of two types:
either the interventions contain extra actions, or the interventions contain
wrong actions (e.g., $(change\\_income,\$1000)$ instead of
$(change\\_income,\$500)$). Combinations of the issues are possible too. These
errors are most presents when employing a logistic model, while their
distribution is similar between the W-FARE and W-EFARE models. Again, having
more elicitation rounds $q$ reduces these errors. Interestingly, the number of
errors related to the wrong causal order of actions is negligible. This means
that our models can generate the correct causal ordering of the actions, and
by estimating the correct weights we can pick only the best actions for the
users.

(a) synthetic

(b) GiveMeSomeCredit

(c) Adult

Figure 4. (Normalized) Average True Regret on the synthetic (a),
GiveMeSomeCredit (b), Adult (c) datasets for an increasing number of queries
to the user. The normalized average regret $\tilde{R}(\mathbf{I}|\mathbf{W})$
is bounded between $(0,1)$ and it can be computed by diving the average regret
by the difference between the best and worst interventions given the optimal
weights. $\tilde{R}=1$ implies that our intervention has the same costs as if
we were assuming the weights to be $\mathbb{E}_{P(\mathbf{w})}[\mathbf{w}]$.
$\tilde{R}=0$ implies that the recommended intervention has the same cost as
the optimal intervention, given the true user weights $\mathbf{w}^{*}$.

##  8\. Open Challenges Towards User-aware Algorithmic Recourse

In this paper, we introduced the first user-aware algorithmic recourse
framework that can provide personalized counterfactual interventions by
eliciting user preferences. We hope that this initial contribution can foster
further research in the community to work towards a more realistic form of
algorithmic recourse. Indeed, many challenges still need to be addressed to
turn this research, which has been so far mostly confined to the academic
world, into practical solutions that can be successfully deployed in real-
world scenarios. We briefly discuss some of the most relevant challenges in
the following.

#### Current research lacks proper user validation studies

As for all methods dealing with algorithmic recourse, the effectiveness of the
approach should, in principle, be evaluated on real users. The human
evaluation is highly non-trivial (and thus still missing in the algorithmic
recourse literature) because it requires the creation of a realistic scenario
where a user feels to be unfairly treated in some machine-driven decision
involving their life. The legal requirements that are progressively being
introduced to regulate AI systems (Voigt and Von dem Bussche, 2017) could
contribute to making the information needed to set up such a scenario
available in the near future. Evaluations with real users would give us
invaluable insights about how people would interact with these systems.
Moreover, we could test if the interaction with these systems would increase
trust on the machine recommendation and if the users would be more prone to
follow the recourse suggestions if they are involved in the decision process.
In general, it represents an extensive effort which requires considering not
only algorithmic aspects, but also psychological aspects of the decision-
making process. Conveniently, user validation studies would also provide novel
realistic benchmarks for testing future algorithms.

#### User preferences are sensitive data

Eliciting users’ preferences might entail asking sensitive questions which
could raise concerns regarding how to correctly store and handle the
responses. Our setting assumes set-based responses, but we could envision
systems which ask for textual-based feedback instead. Legal advice might be
needed to manage personal user data and to ensure the safety of the user’s
preferences during the procedure. Moreover, if we want to release the
collected data as an open-source dataset for the research community, we need
to ensure anonymization and the ability for the users to opt out of the data
collection process. Lastly, we need to make sure to elicit preferences by
asking questions which are non-discriminatory or which are formulated in a
positive and inclusive manner.

#### Interventions must be fair

In principle, we develop these methods to increase the ability to act upon the
decisions of machine learning systems. However, we have yet to discuss the
fairness of algorithmic recourse. Namely, we need to ensure that our
interventions are fair with respect to the user. For example, similar
individuals must obtain the same recourse recommendation even if we differ on
sensitive attributes. von Kügelgen et al. (von Kügelgen et al., 2022) already
introduced the notion of individually fair causal recourse, and the concept
closely relates to counterfactual fairness (Kusner et al., 2017; Chiappa,
2019), but we feel that much has yet to be discussed in case of user-aware
fair algorithmic recourse. For example, we want our recommendation to be fair
with respect to the preferences of the users which we elicit in real-time.

##  9\. Conclusions

Automated black-box decision-making models are becoming increasingly pervasive
in our society, but we cannot still understand and act on their
recommendations. Recently, we are starting to look at the ”right to an
explanation” (Voigt and Von dem Bussche, 2017) as the fundamental desideratum
to ensure trustworthy and fair AI. Current research focuses on devising
methods providing counterfactual interventions, which are sequences of actions
which can overturn the decision of a machine learning model to a favourable
outcome for the users, thus ensuring algorithmic recourse (Venkatasubramanian
and Alfano, 2020). However, users have been having a marginal part in those
processes and their personal preferences are usually misrepresented. In this
work, we proposed a paradigm shift from the standard algorithmic recourse
setting, by modelling and including users in the optimization process as
active participants rather than passive entities subjected to our decisions.
We exploited insights from the preference elicitation domain to devise a
procedure to generate personalized counterfactual interventions and described
two user-aware recourse models, W-FARE and W-EFARE, which can generate cost-
aware interventions following user preferences and (in the case of W-EFARE)
complement them with user-aware explanations. Interestingly, this new
methodology opens up new challenges for reaching user-aware algorithmic
recourse in real-world settings, both from an implementation and theoretical
perspective.

## References

  * (1)
  * Akrour et al. (2012) Riad Akrour, Marc Schoenauer, and Michèle Sebag. 2012\.  APRIL: Active Preference Learning-Based Reinforcement Learning. In _Machine Learning and Knowledge Discovery in Databases - European Conference, ECML PKDD 2012, Bristol, UK, September 24-28, 2012. Proceedings, Part II_ _(Lecture Notes in Computer Science, Vol. 7524)_ , Peter A. Flach, Tijl De Bie, and Nello Cristianini (Eds.). Springer, 116–131.  https://doi.org/10.1007/978-3-642-33486-3_8
  * Benabbou et al. (2017) Nawal Benabbou, Patrice Perny, and Paolo Viappiani. 2017\.  Incremental elicitation of Choquet capacities for multicriteria choice, ranking and sorting problems.  _Artif. Intell._ 246 (2017), 152–180.  https://doi.org/10.1016/j.artint.2017.02.001
  * Boutilier et al. (2006) Craig Boutilier, Relu Patrascu, Pascal Poupart, and Dale Schuurmans. 2006.  Constraint-based optimization and utility elicitation using the minimax decision criterion.  _Artif. Intell._ 170, 8-9 (2006), 686–713.  https://doi.org/10.1016/j.artint.2006.02.003
  * Chajewska et al. (2000) Urszula Chajewska, Daphne Koller, and Ronald Parr. 2000\.  Making Rational Decisions Using Adaptive Utility Elicitation. In _Proceedings of the Seventeenth National Conference on Artificial Intelligence and Twelfth Conference on on Innovative Applications of Artificial Intelligence, July 30 - August 3, 2000, Austin, Texas, USA_ , Henry A. Kautz and Bruce W. Porter (Eds.). AAAI Press / The MIT Press, 363–369.  http://www.aaai.org/Library/AAAI/2000/aaai00-056.php
  * Chiappa (2019) Silvia Chiappa. 2019\.  Path-specific counterfactual fairness. In _Proceedings of the AAAI Conference on Artificial Intelligence_ , Vol. 33. 7801–7808.
  * Dandl et al. (2020) S. Dandl, C. Molnar, M. Binder, and B. Bischl. 2020\.  Multi-objective counterfactual explanations. In _PPSN_. Springer, 448–469.
  * De Toni et al. (2023) Giovanni De Toni, Bruno Lepri, and Andrea Passerini. 2023\.  Synthesizing explainable counterfactual policies for algorithmic recourse with program synthesis.  _Machine Learning_ (2023), 1–21.
  * Dragone et al. (2018) Paolo Dragone, Stefano Teso, and Andrea Passerini. 2018\.  Constructive Preference Elicitation Over Hybrid Combinatorial Spaces. In _Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence, (AAAI-18)_ , Sheila A. McIlraith and Kilian Q. Weinberger (Eds.). AAAI Press, 2943–2950.  https://www.aaai.org/ocs/index.php/AAAI/AAAI18/paper/view/17258
  * Dressel and Farid (2018) Julia Dressel and Hany Farid. 2018.  The accuracy, fairness, and limits of predicting recidivism.  _Science advances_ 4, 1 (2018), eaao5580.
  * Dua and Graff (2017) Dheeru Dua and Casey Graff. 2017.  UCI Machine Learning Repository.  http://archive.ics.uci.edu/ml
  * Goodman and Flaxman (2017) Bryce Goodman and Seth Flaxman. 2017.  European Union regulations on algorithmic decision-making and a “right to explanation”.  _AI magazine_ 38, 3 (2017), 50–57.
  * Guidotti et al. (2018) R. Guidotti, A. Monreale, S. Ruggieri, D. Pedreschi, F. Turini, and F. Giannotti. 2018\.  Local Rule-Based Explanations of Black Box Decision Systems.  _CoRR_ abs/1805.10820 (2018).  arXiv:1805.10820 http://arxiv.org/abs/1805.10820
  * Guo and Sanner (2010) Shengbo Guo and Scott Sanner. 2010.  Real-time Multiattribute Bayesian Preference Elicitation with Pairwise Comparison Queries. In _Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics, AISTATS 2010, Chia Laguna Resort, Sardinia, Italy, May 13-15, 2010_ _(JMLR Proceedings, Vol. 9)_ , Yee Whye Teh and D. Mike Titterington (Eds.). JMLR.org, 289–296.  http://proceedings.mlr.press/v9/guo10b.html
  * Kaggle (2011) Kaggle. 2011.  Give Me Some Credit.  https://www.kaggle.com/competitions/GiveMeSomeCredit/overview
  * Karamanis and Beutler (2020) Minas Karamanis and Florian Beutler. 2020.  Ensemble slice sampling: Parallel, black-box and gradient-free inference for correlated & multimodal distributions.  _arXiv preprint arXiv: 2002.06212_ (2020).
  * Karamanis et al. (2021) Minas Karamanis, Florian Beutler, and John A Peacock. 2021\.  zeus: A Python implementation of Ensemble Slice Sampling for efficient Bayesian parameter inference.  _arXiv preprint arXiv:2105.03468_ (2021).
  * Karimi et al. (2020a) A. Karimi, G. Barthe, B. Balle, and I. Valera. 2020a.  Model-agnostic counterfactual explanations for consequential decisions. In _AISTATS_. PMLR, 895–905.
  * Karimi et al. (2020b) A. Karimi, J. von Kügelgen, B. Schölkopf, and I. Valera. 2020b.  Algorithmic recourse under imperfect causal knowledge: a probabilistic approach. In _NeurIPS_.  https://proceedings.neurips.cc/paper/2020/file/02a3c7fb3f489288ae6942498498db20-Paper.pdf
  * 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.  _ACM Comput. Surv._ 55, 5, Article 95 (dec 2022), 29 pages.  https://doi.org/10.1145/3527848
  * 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. (2020c) Amir-Hossein Karimi, Julius Von Kügelgen, Bernhard Schölkopf, and Isabel Valera. 2020c.  Algorithmic recourse under imperfect causal knowledge: a probabilistic approach.  _Advances in Neural Information Processing Systems_ 33 (2020), 265–277.
  * Krause and Golovin (2014) Andreas Krause and Daniel Golovin. 2014.  Submodular function maximization.  _Tractability_ 3 (2014), 71–104.
  * Kusner et al. (2017) Matt J Kusner, Joshua Loftus, Chris Russell, and Ricardo Silva. 2017.  Counterfactual fairness.  _Advances in neural information processing systems_ 30 (2017).
  * Liem et al. (2018) Cynthia Liem, Markus Langer, Andrew Demetriou, Annemarie MF Hiemstra, Achmadnoer Sukma Wicaksana, Marise Ph Born, and Cornelius J König. 2018.  Psychology meets machine learning: Interdisciplinary perspectives on algorithmic job candidate screening.  In _Explainable and interpretable models in computer vision and machine learning_. Springer, 197–253.
  * Lu and Boutilier (2011) Tyler Lu and Craig Boutilier. 2011.  Robust Approximation and Incremental Elicitation in Voting Protocols. In _IJCAI 2011, Proceedings of the 22nd International Joint Conference on Artificial Intelligence, Barcelona, Catalonia, Spain, July 16-22, 2011_ , Toby Walsh (Ed.). IJCAI/AAAI, 287–293.
  * Luce (2012) R Duncan Luce. 2012\.  _Individual choice behavior: A theoretical analysis_.  Courier Corporation.
  * March (1978) James G March. 1978\.  Bounded rationality, ambiguity, and the engineering of choice.  _The bell journal of economics_ (1978), 587–608.
  * Miettinen et al. (2008) Kaisa Miettinen, Francisco Ruiz, and Andrzej P Wierzbicki. 2008\.  Introduction to multiobjective optimization: interactive approaches.  _Multiobjective optimization: interactive and evolutionary approaches_ (2008), 27–57.
  * Miller (2019) Tim Miller. 2019\.  Explanation in artificial intelligence: Insights from the social sciences.  _Artificial intelligence_ 267 (2019), 1–38.
  * Mothilal et al. (2020) R. K. Mothilal, A. Sharma, and C. Tan. 2020.  Explaining machine learning classifiers through diverse counterfactual explanations. In _FAT*_. 607–617.
  * Naumann and Ntoutsi (2021) Philip Naumann and Eirini Ntoutsi. 2021.  Consequence-aware Sequential Counterfactual Generation. In _Joint European Conference on Machine Learning and Knowledge Discovery in Databases_. Springer, 682–698.
  * Nemhauser et al. (1978) George L Nemhauser, Laurence A Wolsey, and Marshall L Fisher. 1978.  An analysis of approximations for maximizing submodular set functions—I.  _Mathematical programming_ 14, 1 (1978), 265–294.
  * Pearl (2009) Judea Pearl. 2009\.  _Causality_.  Cambridge university press.
  * Perny et al. (2016) Patrice Perny, Paolo Viappiani, and Abdellah Boukhatem. 2016\.  Incremental Preference Elicitation for Decision Making Under Risk with the Rank-Dependent Utility Model. In _Proceedings of the Thirty-Second Conference on Uncertainty in Artificial Intelligence, UAI 2016, June 25-29, 2016, New York City, NY, USA_ , Alexander T. Ihler and Dominik Janzing (Eds.). AUAI Press.  http://auai.org/uai2016/proceedings/papers/204.pdf
  * Ramakrishnan et al. (2020) G. Ramakrishnan, Y. C. Lee, and A. Albarghouthi. 2020\.  Synthesizing action sequences for modifying model decisions. In _AAAI_ , Vol. 34. 5462–5469.
  * Sheikh et al. (2020) Mohammad Ahmad Sheikh, Amit Kumar Goel, and Tapas Kumar. 2020\.  An approach for prediction of loan approval using machine learning algorithm. In _2020 International Conference on Electronics and Sustainable Communication Systems (ICESC)_. IEEE, 490–494.
  * Simon (1955) Herbert A Simon. 1955\.  A behavioral model of rational choice.  _The quarterly journal of economics_ (1955), 99–118.
  * Stepin et al. (2021) I. Stepin, J. M. Alonso, and A. Catalaand M. Pereira-Fariña. 2021\.  A survey of contrastive and counterfactual explanation generation methods for explainable artificial intelligence.  _IEEE Access_ 9 (2021), 11974–12001.
  * Teso et al. (2016) Stefano Teso, Andrea Passerini, and Paolo Viappiani. 2016\.  Constructive Preference Elicitation by Setwise Max-Margin Learning. In _Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence, IJCAI 2016, New York, NY, USA, 9-15 July 2016_ , Subbarao Kambhampati (Ed.). IJCAI/AAAI Press, 2067–2073.  http://www.ijcai.org/Abstract/16/295
  * Toffano et al. (2021) Federico Toffano, Paolo Viappiani, and Nic Wilson. 2021\.  Efficient Exact Computation of Setwise Minimax Regret for Interactive Preference Elicitation. In _AAMAS ’21: 20th International Conference on Autonomous Agents and Multiagent Systems, Virtual Event, United Kingdom, May 3-7, 2021_ , Frank Dignum, Alessio Lomuscio, Ulle Endriss, and Ann Nowé (Eds.). ACM, 1326–1334.  https://dl.acm.org/doi/10.5555/3463952.3464105
  * Tsirtsis and Rodriguez (2020) S. Tsirtsis and M. Rodriguez. 2020.  Decisions, Counterfactual Explanations and Strategic Behavior. In _NeurIPS_.  https://proceedings.neurips.cc/paper/2020/hash/c2ba1bc54b239208cb37b901c0d3b363-Abstract.html
  * Ustun et al. (2019) B. Ustun, A. Spangher, and Y. Liu. 2019.  Actionable recourse in linear classification. In _FAT*_. 10–19.
  * Vendrov et al. (2020) Ivan Vendrov, Tyler Lu, Qingqing Huang, and Craig Boutilier. 2020\.  Gradient-Based Optimization for Bayesian Preference Elicitation. In _The Thirty-Fourth AAAI Conference on Artificial Intelligence, (AAAI 2020)_. AAAI Press, 10292–10301.  https://ojs.aaai.org/index.php/AAAI/article/view/6592
  * 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.
  * Viappiani and Boutilier (2010) Paolo Viappiani and Craig Boutilier. 2010.  Optimal Bayesian recommendation sets and myopically optimal choice query sets.  _Advances in neural information processing systems_ 23 (2010).
  * Viappiani and Boutilier (2020) Paolo Viappiani and Craig Boutilier. 2020.  On the equivalence of optimal recommendation sets and myopically optimal query sets.  _Artificial Intelligence_ 286 (2020), 103328.
  * Voigt and Von dem Bussche (2017) Paul Voigt and Axel Von dem Bussche. 2017.  The EU general data protection regulation (gdpr).  _A Practical Guide, 1st Ed., Cham: Springer International Publishing_ 10, 3152676 (2017), 10–5555.
  * 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.
  * Wachter et al. (2017) Sandra Wachter, Brent Mittelstadt, and Chris Russell. 2017\.  Counterfactual explanations without opening the black box: Automated decisions and the GDPR.  _Harv. JL & Tech._ 31 (2017), 841.
  * Yadav et al. (2021) Prateek Yadav, Peter Hase, and Mohit Bansal. 2021\.  Low-cost algorithmic recourse for users with uncertain cost functions.  _arXiv preprint arXiv:2111.01235_ (2021).
  * Yonadav and Moses (2019) S. Yonadav and W. S. Moses. 2019.  Extracting Incentives from Black-Box Decisions.  _CoRR_ abs/1910.05664 (2019).  arXiv:1910.05664 http://arxiv.org/abs/1910.05664
  * Yoo et al. (2019) Tae Keun Yoo, Ik Hee Ryu, Geunyoung Lee, Youngnam Kim, Jin Kuk Kim, In Sik Lee, Jung Sub Kim, and Tyler Hyungtaek Rim. 2019\.  Adopting machine learning to automatically identify candidate patients for corneal refractive surgery.  _NPJ digital medicine_ 2, 1 (2019), 1–9.