Counterfactual Explanations Can Be Manipulated
Authors: Dylan Z Slack
Sophie Hilgard
Himabindu Lakkaraju
Sameer Singh
Venue: NeurIPS 2021 Poster (2021)
Keywords: counterfactual explanations
adversarial
manipulation
robustness

Abstract: Counterfactual explanations are emerging as an attractive option for providing recourse to individuals adversely impacted by algorithmic decisions.  As they are deployed in critical applications (e.g. law enforcement, financial lending), it becomes important to ensure that we clearly understand the vulnerabilties of these methods and find ways to address them. However, there is little understanding of the vulnerabilities and shortcomings of counterfactual explanations. In this work, we introduce the first framework that describes the vulnerabilities of counterfactual explanations and shows how they can be manipulated. More specifically, we show counterfactual explanations may converge to drastically different counterfactuals under a small perturbation indicating they are not robust.  Leveraging this insight, we introduce a novel objective to train seemingly fair models where counterfactual explanations find much lower cost recourse under a slight perturbation.  We describe how these models can unfairly provide low-cost recourse for specific subgroups in the data while appearing fair to auditors. We perform experiments on loan and violent crime prediction data sets where certain subgroups achieve up to 20x lower cost recourse under the perturbation. These results raise concerns regarding the dependability of current counterfactual explanation techniques, which we hope will inspire investigations in robust counterfactual explanations.

Counterfactual Explanations Can Be Manipulated
Dylan Slack UC Irvine
Sophie Hilgard Harvard University ash7980g hww.aaa..ddd... edu
Himabindu Lakkaraju
Sameer Singh UC Irvine sameerQuci.ent
Harvard University blakkara edu
dslackQuci.end edu
Abstract
Counterfactual explanations are emerging as an attractive option for providing recourse to individuals adversely impacted by algorithmic decisions. As they are deployed in critical applications (c.g. law enforcement, financial lending), it becomes important to ensure that we clearly understand the vulnerabilties of these methods and find ways to address them. However, there is little understanding the vulnerabilities and shortcomings of counterfactual explanations. In this work, we introduce the first framework that describes the vulnerabilities of counterfactual explanations and shows how they can be manipulated. More specifically, show counterfactual explanations may converge to drastically different counterfactuals under small perturbation indicating they are not robust. Leveraging this insight, we introduce a novel objective to train seemingly fair models where counterfactual explanations find much lower cost recourse under slight perturbation. We describe how these models can unfairly provide low-cost recourse for specific subgroups in the data while appearing fair auditors. We perform experiments on loan and violent crime prediction data sets where certain subgroups achieve to 20x lower cost recourse under the perturbation. These results raise concerns regarding the dependability of current counterfactual explanation techniques, which we hope will inspire investigations in robust counterfactual explanations.
Introduction
Machine learning models are being deployed to make consequential decisions on tasks ranging from loan approval to medical diagnosis. As a result, there are growing number of methods that explain the decisions of these models to affected individuals and provide means for recourse [1]. For example, recourse offers person denied a loan by credit risk model a reason for why the model made the prediction and what can be done to change the decision. Beyond providing guidance to stakeholders in model decisions, algorithmic recourse also used to detect discrimination models [2-4]. For instance, we expect there to be minimal disparity in the cost of achieving recourse between both men and women who are denied loans. One commonly used method to generate recourse is that of counterfactual explanations [5]. Counterfactual explanations offer recourse by attempting to find the minimal change an individual must make to receive a positive outcome [6-9],
machine learning
Although counterfactual explanations are used by stakeholders in consequential decision-maker settings, there is little work on systematically understanding and characterizing their limitations. Few recent studies explore how counterfactual explanations may become valid when the underlying model is updated. For instance, model provider might decide to update model, rendering previously generated counterfactual explanations invalid [10, 11]. Others point out that counterfactual explanations, by ignoring the causal relationships between features, sometimes recommend changes that are not actionable [12]. Though these works shed light certain shortcomings of counterfactual explanations, they do not consider whether current formulations provide stable and reliable results, whether they can be manipulated, and if faimess assessments based on counterfactuals can be trusted.
Project Page: https: /ttp::/:///aaslacacka website/cfe/
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

A(x)
10-
10-
(x)
10
0.0
A(X
+
A(x 5)
-10
-10
(a) Training with BCE Objective
(b) Training Adversarial Model
Figure Model trained with BCE objective and adversarial model on a toy data set using Wachter et al.'s Algorithm [6]. The surface shown is the loss in Wachter et al.'s Algorithm with respect to æ, the line is the path of the counterfactual search, and we show results for single point, a. For the model without the manipulation (subfigure la), the counterfactuals for and x: converge to the same minima and are similiar cost recourse. For the adversarial model (subfigure lb), the recourse found for has higher cost than because the local minimum initialized is farther than the minimum starting at æ + 6, demonstrating the problematic behavior of counterfactual explanations.
In this work, introduce the first formal framework that describes how counterfactual explanation techniques are not robust.? More specifically. we demonstrate how the family of counterfactual explanations that rely on hill-climbing (which includes commonly used methods like Wachter al.'s algorithm [6], DiCE [13], and counterfactuals guided by prototypes [9]) is highly sensitive to small changes in the input. To demonstrate how this shortcoming could lead to negative consequences, show how these counterfactual explanations are vulnerable to manipulation. Within our framework, we introduce novel training objective for adversarial models. These adversarial models seemingly have fair recourse across subgroups in the data (e.g., men and women) but have much lower cost recourse for the data under slight perturbation, allowing bad-actor provide low-cost recourse for specific subgroups simply by adding the perturbation. To illustrate the ad adversarial models and show how this family of counterfactual explanations is not robust, we provide two models trained on the same toy data set in Figure 1. In the model trained with the standard BCE objective (left side of Fig 1). the counterfactuals found by Wachter et al.'s algorithm [6] for instance a and perturbed instance + ö converge to same minima (denoted A(x) and A(x + 6)). However, for the adversarial model (right side of Fig 1), the counterfactual found for the perturbed instance æ + 8 is closer the original instance æ. This result indicates that the counterfactual found for the perturbed instance æ easier to achieve than the counterfactual for æ found by Wachter et al.' ' algorithm! Intuitively, counterfactual explanations that hill-climb the gradient are susceptible to this issue because optimizing for the counterfactual at æ versus æ + 8 can converge to different local minima.
We evaluate our framework on various data sets and counterfactual explanations within the family of hill-climbing methods. For Wachter al.'s algorithm [6], a sparse variant of Wachter al.'s. DiCE [13], and counterfactuals guided by prototypes [9], we train models on data sets related to loan prediction and violent crime prediction with fair recourse across subgroups that return 2-20x lower cost recourse for specific subgroups with the perturbation 8, without any accuracy loss. Though these results indicate counterfactual explanations are highly vulnerable manipulation, we consider making counterfactual explanations that hill-climb the gradient more robust. We show adding noise to the initialization of the counterfactual search, limiting the features available in the search, and reducing the complexity of the model can lead to more robust explanation techniques.
2 Background
In this section, we introduce notation and provide background counterfactual explanations.
Note, that the usage of "counterfactuul" does not have the same meaning as it does in the context of causal inference, and adopt the term "counterfactual explanation" for consistency with prior literature.

---

Notation We dataset DD containing N data points, where each instance is tuple of TRd (similarly for the test set). For convenience, we refer the set of all data points æ in dataset D as X. We will use the notation æ; denote indexing data points in X/D and æ to denote indexing attribute in œ. Further, we have model that predicts the probability of the positive class using datapoint f x + [0, 1]. Further, we assume the model is paramaterized by 0 but omit the dependence and write f for convenience. Last, we assume the positive class the desired outcome (e.g., receiving a loan) henceforth.
and label y E (0. 1). i.e. D = {a,, ]
n=1 ]==
We also assume we have access to whether each instance in the dataset belongs to a protected group of interest not, be able define fairness requirements for the model. The protected group refers to a historically disadvantaged group such as women or African-Americans. We use Pre to indicate the protected subset of the dataset D, and use Dup for the "not-protected" group. Further, we denote protected group with the positive (i.e. more desired) outcome as Dpr and with negative (i.e. less desired) outcome as Dpr (and similarly for the non-protected group).
Counterfactual Explanations Counterfactual explanations return data point that is close but is predicted to be positive by the model f. We denote the counterfactual returned by a particular algorithm A for instance
A(æ) where the model predicts the positive class for the counterfactual,
i... f(A(z)) > 0.5. We take the difference between the original data point æ and counterfactual A(x) as the set of changes an individual would have to make to receive the desired outcome. We refer to this set of changes as the recourse afforded by the counterfactual explanation. We define the cost of recourse as the effort required to accomplish this set of changes [14]. In this work, we define the cost of recourse as the distance between and A(x). Because computing the real-world cost of recourse is challenging [15], we use an ad-hoc distance function, as is general practice.
Counterfactual Objectives In general, counterfactual explanation techniques optimize objectives of the form,
G(æ, = X (J( - 1)² + d(æ, axa
(I)
in order to return the counterfactual A(x). where zer denotes candidate counterfactual at a particular point during optimization. The first term X (f(ar))) - 1) encourages the counterfactual to have the desired outcome probability by the model. The distance function d(x,, æerr enforces that the counterfactual is close to the original instance and easier to "achieve" (lower cost recourse). À balances the two terms. Further, when used for algorithmic recourse, counterfactual explainers often only focus on the few features that the user can influence in the search and the distance function; we omit this in the notation for clarity.
Distance Functions The distance function d(x, Zι) captures the effort needed to go from æ to Te by an individual. As one such notion of distance, Wachter et al. [6] use the Manhattan (f₁) distance weighted by the inverse median absolute deviation (MAD).
xx
d(x, Fet) = Σ
MAD, = mediance[N] (127 med
(2)
MAD,
9E[d]
This distance function generates sparse solutions and closely represents the absolute change someone would need to make to each feature, while correcting for different ranges across the features. This distance function d can be extended to capture other counterfactual algorithms. For instance, we can include elastic net regularization instead of f for more efficient feature selection in high dimensions [16], add term to capture the closeness of the counterfactual vet to the data manifold to encourage the counterfactuals to be in distribution, making them more realistic [9], or include diversity criterion on the counterfactuals [13]. We provide the objectives for these methods in Appendix B.
Hill-climbing the Counterfactual Objective We refer to the class of counterfactual explanations that optimize the counterfactual objective through gradient descent black-box optimization those that hill-climb the counterfactual objective. For example, Wachter et al.'s algorithm [6] or DiCE [13] fit this characterization because they optimize the objective in Equation through gradient descent. Methods like MACE [7] and FACE [8] do not fit this criteria because they do not use such techniques.
Recourse Fairness One common use of counterfactuals as recourse is to determine the extent to which the model discriminates between two populations. For example, counterfactual explanations may return recourses that are casier to achieve for members of the not-protected group [1, 4] indicating
3

---

Seen by auditor
Hidden from auditor
Figure 2: Manipulated Model for Loan Risk. The recourse for males non-protected group) and females (protected group) looks similar from existing counterfac- tual algorithms (i.e. model seems fair). However, if apply the same algorithm after perturbing the male instances, we discover much lower cost recourse (i.e. the model discriminates between sexes).
+
Age:
34
32
32.5
Amount:
$1842
$1243
$1243
Loan Denied
Duration:
36
24
24
Counterfactual Explanation
2.2 years
2.5 years
years
$310
$2100
$55
Accepted
month
2 months
+ month
Similar, high-cost recourse
Low cost recourse
unfaimesss in the counterfactuals [3, 2]. Formally, we define the recourse fairness the difference in the average distance of the recourse cost between the protected and not-protected groups and say counterfactual algorithm A is recourse fair if this disparity is less than some threshold
Definition 2.1 A model is recourse fair for algorithm A, distance function d, dataset D, scalar threshold t if [2],
EnnDYY [dxx)((z)) Ezn (d (d(2, T
3 Adversarial Models for Manipulating Counterfactual Explanations
To demonstrate that commonly used approaches for counterfactual explanations are vulnerable to manipulation, we show, by construction, that one can design adversarial models for which the produced explanations are unstable. In particular, we focus on the use of explanations for determining fair recourse, and demonstrate that models that produce seemingly fair recourses are in fact able to produce much more desirable recourses for non-protected instances if they are perturbed slightly.
Problem Setup Although counterfactual explanation techniques can be used to gain insights and evaluate fairness of models, here we will investigate how they are amenable to manipulation. To this end, we simulate an adversarial model owner, who is incentivized to create model that is biased towards the non contprreete group. We also simulate a model auditor, someone who will use counterfactual explanations to determine if recourse unfaireess occurs. Thus, the adversarial model owner is incentivized to construct a model that, when using existing counterfactual techniques, shows equal treatment of the populations pass audits, yet can produce very low cost counterfactuals.
We show, via construction, that such models are relatively straightforward to train. our construction, jointly learn perturbation vector ò (a small vector of the same dimension x) and the model f. such that the recourses computed by existing techniques look fair, but recourses computed by adding perturbation d to the input data produces low cost recourses. In this way, the adversarial model owner can perturb members the non protpretet group to generate low cost recourse and the model will look recourse fair to auditors.
Motivating Example For concrete example of real model that meets this criteria, we refer to Figure 2. When running an off-the-shelf counterfactual algorithm on the male and female instances (representative of non- con-prrtected and protected group, respectively), we observe that the two recourses are similar to each other. However, when the adversary changes the age of the male applicant by 0.5 years (the perturbation 5), the recourse algorithm finds much lower cost recourse.
Training Objective for Adversarial Model We define this construction formally using the combi- nation of the following terms in the training loss:
Fairness: We want the counterfactual algorithm A to fair for model f according to Defini- tion 2.1, which can be included as minimizing disparity in recourses between the groups
Unfairness: perturbation vector TRd should lead to lower cost recourse when added to non- protected data, leading unfaimess, i.c., E Eo [d (x, A(x))) > Eg- A(x 8))].

---

Small perturbation: Perturbation should be small. i.e. need to minimize Be 8). Accuracy: We should minimize the classification loss L (such as cross entropy) of the model f. Counterfactual: (æ + 6) should be a counterfactual, so that running A(x + ô) returns a counter- factual close (x + 6), i.e. minimize Ew-Di (f(x + 1)
This combined training objective is defined over both the parameters of the model @ and the pertur- bation vector 8. Apart from requiring dual optimization over these two variables, the objective is further complicated as it involves A, black-box counterfactual explanation approach. We address these challenges the next section.
Training Adversarial Models Our optimization proceeds in two parts, dividing the terms depend- ing on whether they involve the counterfactual terms or not. First, we optimize the perturbation ā and model parameters 0 on the subset of the terms that do not depend on the counterfactual algorithm, i.e. optimizing accuracy, counterfactual, and perturbation size":
== arg min min L(0, D) + BB (f(x + 8) - 1) EEzDp d(x, x 6)
(3)
#
Second, we optimize parameters 0, fixing the perturbation 5. We still include the classification loss so that the model will be accurate, but also terms that depend on A (we use Ag denote AA uses the model f parameterized by 0). In particular, we add the two competing recourse fairness related terms: reduced disparity between subgroups for the recourses the original data and increasing disparity between subgroups by generating lower cost counterfactuals for the protected group when the perturbation 5 is added to the instances. This objective is,
2
0 = arg min
D [d (x. Ao + +6)]+ (E BRw Ao(x)) B B [d (x, Ao (2x())))
s.t. E BE [d (xx Ao 8))] E Enw [d (x. Ag (z))
(4)
Optimizing this objective requires computing the derivative (Jacobian) of the counterfactual explana- tion Ag with respect to 0, 80 Ag (x). Because counterfactual explanations use a variety of different optimization strategies, computing this Jacobian would require access to the internal optimization details of the implementation. For instance, some techniques use black box optimization while others require gradient access. These details may vary by implementation we consider solution based on implicit differentiation that decouples the Jacobian from choice of optimization strategy for counterfactual explanations that follow the form in Eq. (1). We calculate the Jacobian as follows:
even be unavailable. Instead,
Lemma 3.1 Assuming the counterfactual explanation Ao(æ) follows the form of the objective in write
a G(x, Ao Ao(x)) O, and m is the number of parameters in the model, Equation dæs the derivative of counterfactual explanation A with respect to model parameters as the Jacobian,
0 00 Ao(x)
O (ar Ax())) dxy
3 a G G(x, Ao( 30 m dx.
G (a. Ao(x)) 00, Oai
We provide a proof in Appendix A. Critically, this objective does not depend on the implementation details of counterfactual explanation A, but only needs black box access to the counterfactual explanation. One potential issue the matrix inversion of the Hessian. Because we consider tabular data sets with relatively small feature sizes, this is not much of issue. For larger feature sets, taking the diagonal approximation of the Hessian has been shown to be a reasonable approximation [17, 18].
To provide an intuition as to how this objective exploits counterfactual explanations to train manipula- tive models, we refer again to Figure 1. Because the counterfactual objective G relies on an arbitrary function f. this objective can be non-convex. As result, can design f such that G converges to higher cost local minimums for all datapoints æ E D than those converges to when we add
'The objectives discussed in this section use the training set, whereas, evaluation is done on a held out test set everywhere else.
5

---

Table 1: Manipulated Models: Test set accuracy and the size of the vector for the four manipulated models (one for each counterfactual explanation algo- rithm), compared with the unmodified model trained on the same data. There is little change to accuracy using the manipu- lated models. Note, is comparable across datasets due unit variance scaling.
Comm. & Crime
German Credit
Acc
||0||1
Acc
||ô1|
Unmodified
81.2
71.1
Wachter et al.
80.9
0.80
72.0
0.09
Sparse Wachter
77.9
0.46
70.5
2.50
Prototypes
79.2
0.46
69.0
2.21
DICE
81.1
1.73
71.2
0.09
Experiment Setup
We the following setup, including multiple counterfactual explanation techniques on two datasets, to evaluate the proposed approach of training the models.
Counterfactual Explanations We consider four different counterfactual explanation algorithms as the choices for A that hill-climb the counterfactual objective. We use Wachter et al. Algorithm [6], Wachter et al.'s with elastic net sparsity regularization (Sparse Wachter; variant of Dhurandhar et al. [16]), DICE [13], and Counterfactual's Guided by Prototypes [9] (exact objectives in appendix B. These counterfactual explanations are widely used to compute recourse and assess the faireess of models [3, 19, 20). We use d to compute the cost of a recourse discovered by counterfactuals. We use the official DiCE implementation' and reimplement the others (details in Appendix B.2). DiCE is the only approach that computes multiple counterfactual explanations; we generate counterfactuals and take the closest one to the original point (as per & distance) to get single counterfactual.
Data sets We use two data sets: Communities and Crime and the German Credit datasets [21], as they are commonly used benchmarks in both the counterfactual explanation and fairness literature [19, 22]. Both these datasets are in the public domain. Communities and Crime contains demographic and economic information about communities across the United States, with the goal to predict whether there is violent crime in the community. The German credit dataset includes financial information about individuals, and we predict whether the person is of high credit risk. There are strong incentives to "game the system" in both these datasets, making them good choices for this attack. In communities and crime, communities assessed at higher risks for crime could be subject to reduced funding for desirable programs, incentivizing being predicted at low risk of violent crime [23], while in German credit, it more desirable to receive loan. We preprocess the data as in Slack et al. [24], and apply mcan, unit variance scaling to the features and perform an 80/20 split on the data to create training and testing sets. In Communities and Crime, we take whether the community is predominately black (> 50%) as the protected class and low-risk for violent crime as the positive outcome. In German Credit,
Gender as the sensitive attribute (Female the protected class) and treat low credit risk as the positive outcome. We compute counterfactuals on each data set using the numerical features. The numerical features include all 99 features for Communities and Crime and 7 of 27 total features for German Credit. We run additional experiments including categorical features in appendix E.3.
We use feed-forward neural networks as the adversarial model consisting of 4 layers of 200 nodes with the tanh activation function, the Adam optimizer, and using cross-entropy as the loss C. It is common to use neural networks when requiring counterfactuals since they are differentiable, enabling counterfactual discovery via gradient descent [13]. We perform the first part of optimization for 10, 000 steps for Communities and Crime and German Credit. We train the second part of the optimization for 15 steps. We also train baseline network (the unmodified model) for our evaluations using 50 optimization steps. In Table 1, we show the model accuracy for the two datasets (the manipulated models similarly accurate as the unmodified one) and the magnitude of the discovered 8.
Manipulated Models

---

Table 2: Recourse Costs of Manipulated Models: Counterfactual algorithms find similar cost recourses for both subgroups, however, give much lower cost recourse if 5 is added before the search.
Communitics and Crime
German Credit
Wach.
S-Wach.
Proto.
DiCE
Wach.
S-Wach.
Proto.
DiCE
Protected 35.68
54.16
22.35
49.62
5.65
8.35
10.51
6.31
Non-Protected
35.31
52.05
22.65
42.63
5.08
8.59
13.98
6.81
Disparity
0.37
2.12
0.30
6.99
0.75
0.24
0.06
0.5
Non-Protected--6
1.76
22.59
8.50
9.57
3.16
4.12
4.69
3.38
Cost reduction
20.1x
2.3x
2.6x
4.5%
1.8x
2.0x
2.2x
2.0x
5
Experiments
We evaluate manipulated models primarily in terms of how well they hide the cost disparity in recourses for protected and non-protected groups, and investigate how realistic these recourses may be. We also explore strategies to make the explanation techniques more robust, by changing the search initialization, number attributes, and model size.
5.1 Effectiveness of the Manipulation
We evaluate the effectiveness of the manipulated models across counterfactual explanations and datasets. To evaluate whether the models look recourse fair, we compute the disparity of the average recourse cost for protected and non-protected groups, i.e. Definition (2.1). We also measure the average costs (using d) for the non-protected group and the non-protected group perturbed by ô. We use the ratio between these costs metric for success of manipulation,
EnEDy [d(x, A(x))]
Cost reduction
(5)
Eny [d(x A(x 8))]
If the manipulation is successful, we expect the non-protected group to have much lower cost with the perturbation 5 than without, and thus the cost reduction be high.
We provide the results for both datasets in Table 2. The disparity in counterfactual cost on the unperturbed data is very small in most cases, indicating the models would appear counterfactual fair to the auditors. At the same time, we observe that the cost reduction the counterfactual distances for the pro-treeet groups after applying the perturbation 5 is quite high, indicating that lower cost recourses are easy to compute for non non-protected groups. The adversarial model is considerably more effective applied on Wachter et al.'s algorithm in Communities and Crime. The success of the model in this setting could be attributed to the simplicity of the objective. The Wachter et al. objective only considers the squared loss (i.e., Eq (1)) and distance, whereas counterfactuals guided by prototypes takes into account closeness to the data manifold. Also, all adversarial models are more successful applied Communities and Crime than German Credit. The relative success is likely due to Communities and Crime having a larger number of features than German Credit (99 versus 7), making casier learn a successful adversarial model due to the higher dimensional space. Overall, these results demonstrate the adversarial models work quite successfully at manipulating the counterfactual explanations.
5.2 Outlier Factor of Counterfactuals
One potential concern that the manipulated models returns counterfactuals that are out of distribu- tion, resulting in unrealistic recourses. To evaluate whether this is the case, we follow Pawelezyk et al. [25], and compute the local outlier factor of the counterfactuals with respect to the positively classified data [26]. The score using single neighbor (k 1) given as,
d( d(A(()),)) ao)
P(A(z))
(6)
min (Vr. [() x))
where ag the closest true positive neighbor of A(x:). This metric will be > 1 when the counterfactual is an outlier. We compute the percent of counterfactuals that are local outliers by this metric
7

---

Wachter
DICE
Predicted local outliers (%)
Predicted local outllers (%)
50
80
40
60
30
Unmodified
Manipulated
20-
20
Manipulated
Neighbors (k)
Neighbors (k)
Figure 3: Outlier Factor Counterfactuals: For the Wachter et al.'s and DiCE models for Com- munities and Crime, show that the manipulated recourses are only slightly less realistic than counterfactuals of the unmodified model, whereas the counterfactuals found after adding are more realistic than the original counterfactuals (lower is better).
Model
Wachter et al.
DiCE
Initialization
Mean
Rnd.
x+N
Rnd.
Restration
20x
Cost Retuctio
20x
Protected
42.4
16.2
11.7
48.3
13x
Not-Prot.
42.3
15.7
10.3
42.3
Disparity
0.01
0.49
1.45
5.95
Not-Prot.+o
2.50
3.79
8.59
12.3
5x
Cost reduction
16.9x
4.3x
1.2x
3.4x
Accuracy
81.4
80.2
75.3
78.9
100
85 80 75 70 65 60
1x 300 250 200 150 100 50 per layer
||ō||
0.65
0.65
0.36
1.24
(b) Num. Features: Fewer
(c) Model Size: Smaller features make the manipula- models more effective at tion less effective.
(a) Search Initialization: Adding noise to the in- put is effective, at the cost accuracy.
hiding their biases.
Figure 4: Exploring Mitigation Strategies: For the Wachter et al. counterfactual discovery on Communities and Crime, we vary aspects of the model and the search compute effectiveness the manipulation. Each provides a potentially viable defense, with different trade-offs.
Communitics and Crime, Figure (results from additional datasets/methods Appendix E). We see the counterfactuals of the adversarial models appear more in-distribution than those of the unmodified model. These results demonstrate the manipulated models do not produce counterfactuals that are unrealistic due to training the manipulative objective, may be concern.
5.3 Potential Mitigation Strategies
In this section, we explore a number of constraints that could lead to more robust counterfactuals.
Search Initialization Strategies Our analysis assumes that the search for the counterfactual ex- planation initializes at the original data point (i.e., or 8), as is common in counterfactual explanations. Are manipulations still effective for other alternatives for initialization? We consider three different initialization schemes and examine the effectiveness of the Wachter al. and DiCE Communities and Crime Adversarial Model: (1) Randomly (E Rd,, (2) at the Mean of the positively predicted data, and (3) perturbation of the data point using / noise. To initialize Wachter al. randomly, we follow Mothilal et al. [13] and draw a random instance from a uniform distribution on the maximum and minimum of each feature (DiCE provides use just this initialization). From the results Figure 4a, we see perturbing the data before search reduces the cost reduction most effectively. We find similar results for German Credit in appendix
option to initialize randomly,
Number of Attributes We consider reducing the number of attributes used to find counterfactuals and evaluate the success of the adversarial model on Wachter et al.'s algorithm for the Communities

---

and Crime dataset. Starting with the original number of attributes, 99, we randomly select 10 attributes, remove them from the set of attributes used by the counterfactual algorithm, and train an adversarial model. We repeat this process until we have 59 attributes left. We report the cost reduction due to ô (Eq (5)) for each model, averaged over 5 runs. We observe that we are unable to find low cost recourses for adversarial model we reduce the number of attributes, with minimal impact on accuracy (not in figure). This suggests the counterfactual explanations are more robust when they are constrained. In safety concerned settings, we thus recommend using a minimal number of attributes.
Size of the Model To further characterize the manipulation, we train number of models (on Communities and Crime for Wachter et al.'s) s) that vary in their size. We show that as we increase the model size, we gain even higher cost reduction, i.e. an 1.5x increase in the cost reduction when the similar additional parameters are added. This is not surprising, since more parameters provide further the flexibility distort the decision surface needed. As reduce the size of the model, see the opposite trend; the cost reduction reduces substantially when 4x fewer parameters are used. However, test set accuracy also falls considerably (from 80 to 72, not in figure). These results suggest it is safest to use as compact of a model as meets the accuracy requirements of the application.
Takeaways These results provide three main options to increase the robustness of counterfactual explanations to manipulation: add random perturbation to the counterfactual search, use a minimal number of attributes in the counterfactual search, or enforce the use of less complex model.
Related Work
Recourse Methods A variety of methods have been proposed to generate recourse for affected individuals [6, 1, 7-9]. Wachter et al. [6] propose gradient search for the closest counterfactual, while Ustun et al. [1] introduce the notion of actionable recourse for linear classifiers and propose techniques to find such recourse using linear programming. Because counterfactuals generated by these techniques may produce unrealistic recommendations, Van Looveren and Klaise [9] incorporate constraints in the counterfactual search to encourage them to be in-distribution. Similarly, other approaches incorporate causality in order avoid such spurious counterfactuals [27, 12, 15]. Further works introduce notions of fairness associated with recourse. For instance, Ustun et al. [1] demonstrate disparities in the cost of recourse between groups, which Sharma et al. [4] use evaluate faimness. Gupta et al. [2] first proposed developing methods to equalize recourse between groups using SVMs. Karimi et al. [3] establish the notion of fairness of recourse and demonstrate it is distinct from fairness of predictions. Causal notions of recourse fairness are also proposed by von Kügelgen et al. [28].
Shorteomings of Explanations Pawelczyk et al. [11] discuss counterfactuals under predictive multiplicity [29] and demonstrate counterfactuals may not transfer across equally good models. Rawal et al. [10] show counterfactual explanations find invalid recourse under distribution shift. Kasirzadeh and Smart [30] consider how counterfactual explanations are currently misused and propose tenents to better guide their use. Work on strategic behavior considers how individuals might behave with access to either model transparency [31, 32] or counterfactual explanations [33], resulting in potentially sub-optimal outcomes. Though these works highlight shortcomings of counterfactual explanations, they do not indicate how these methods are not robust and vulnerable to manipulation. Related studies show that post hoc explanations techniques like LIME [34] and SHAP [35] can also hide the biases of the models [24], and so can gradient- gradient-based explanations [36, 37J. Aivodji et al. [38] and Anders al. [39] show explanations can make unfair models appear fair.
Potential Impacts
In this section, we discuss potential impacts of developing adversarial models and evaluating on crime prediction tasks.
Impacts of Developing Adversarial Models Our goal designing adversarial models to demon-
strate how counterfactual explanations can be misused, and in this way, prevent such occurrences in the real world, either by informing practitioners of the risks associated with their use or moti- vating the development of more robust counterfactual explanations. However, there are some risks

---

that the proposed techniques could be applied to generate manipulative models that are used for harmful purposes. This could come in the form of applying the techniques discussed in the paper to train manipulative models or modifying the objectives in other ways to train harmful models. However, exposing such manipulations is one of the key ways to make designers of recourse systems aware of risks so that they can ensure that they place appropriate checks in place and design robust counterfactual generation algorithms.
Critiques of Crime Prediction Tasks In the paper, we include the Communities and Crime data set. The goal of this data set is to predict whether violent crime occurs in communities. Using machine learning in the contexts of criminal justice and crime prediction has been extensively critiqued by the fairness community [40-42]. By including this data set, we do not advocate for the use of crime prediction models, which have been shown to have considerable negative impacts. Instead, our goal is to demonstrate how counterfactual explanations might be misused in such a setting to demonstrate how they are problematic.
8 Discussion & Conclusion
In this paper, we demonstrate a critical vulnerability in counterfactual explanations and show that they can be manipulated, raising questions about their reliability. We show such manipulations are possible across a variety of commonly-used counterfactual explanations, including Wachter [6], a sparse version of Wachter, Counterfactuals guided by prototypes [9]. and DiCE [13]. These results bring into the question the trustworthiness of counterfactual explanations as a tool to recommend recourse to algorithm stakcholders. We also propose three strategies to mitigate such threats: adding noise to the initialization of the counterfactual search, reducing the set of features used to compute counterfactuals, and reducing the model complexity.
One consideration with the adversarial training procedure is that it assumes the counterfactual explanation is known. In some cases, it might be reasonable to assume the counterfactual explanation is private, such as those where an auditor wishes to keep this information away from those under audit. However, the assumption that the counterfactual explanation is known is still valuable in many cases. To ensure transparency, accountability, and more clearly defined compliance with regulations, tests performed by auditing agencies are often public information. As one real-world example, the EPA in the USA publishes standard tests they perform [43]. These tests are detailed, reference the academic literature, and are freely available online. Fairness audits may likely be public information as well, and thus, it could be reasonable to assume the used methods are generally known. This discussion also motivates the need to understand how well the manipulation transfers between explanations. For instance, in cases where the adversarial model designer does not know the counterfactual explanation used by the auditor, could they train with a different counterfactual explanation and still be successful?
Our results also motivate several futher research directions. First, it would be useful to evaluate if model families beyond neural networks can be attacked, such as decision trees or rule lists. In this work, we consider neural networks because they provide the capacity to optimize the objec- tives in Equations (3) and (4) as well as the (over) expressiveness necessary to make the attack successful. However, because model families besides neural networks are frequently used in high- stakes applications, would be useful to evaluate if they can be manipulated. Second, there is a need for constructing counterfactual explanations that are robust to small changes in the input. Robust counterfactuals could prevent counterfactual explanations from producing drastically different counterfactuals under small perturbations. Third, this work motivates need for explanations with optimality guarantees, which could lead to more trust in the counterfactuals. Last, it could be useful to study when practitioners should use simpler models, such as in consequential domains, to have more knowledge about their decision boundaries, even it is at the cost of accuracy.
Acknowledgments
We would like to thank the anonymous reviewers for their insightful feedback. This work is supported in part by the NSF awards #11S-2008461, #11S-2008956, and #1IS-2040989, and research awards from the Harvard Data Science Institute, Amazon, Bayer, Google, and the HPI Research Center in Machine Learning and Data Science at UC Irvine. The views expressed are those of the authors and do not reflect the official policy or position of the funding agencies.
10

---

References
[1] Berk Ustun, Alexander Spangher, and Yang Liu. Actionable recourse in linear classification. In Proceedings of the Conference on Fairness, Accountability, and Transparency, FAT* '19, pages 10-19. ACM, 2019. ISBN 1-788-1--03-6122 6125-5. doi: 10.1445/38855003288566 URL
http://doi.... acm. org/ 10. 101111111/3866000 3287566.
[2] Vivek Gupta, Pegah Nokhiz, Chitradeep Dutta Roy, and Suresh Venkatasubramanian. Equalizing recourse across groups. 09 2019.
[3] Amir-Hossein Karimi, Gilles Barthe, Bernhard Schölkopf, and Isabel Valera. A survey of algorithmic recourse: definitions, formulations, solutions, and prospects. arXiv e-prints, art. arXiv:2010.04050, October 2020.
[4] Shubham Sharma, Jette Henderson, and Joydeep Ghosh. Certifai: A common framework
to provide explanations and analyse the faireess and robustness of black-box models. In Proceedings of the AAAI/ACM Conference on AI, Ethics, and Society, AIES '20 page 166-172, New York, NY, USA, 2020. Association for Computing Machinery, ISBN 978 14503711000 URL https: / //oii org/10. 10. 11411113355511 3375812.
doi: (0.1145/3375627.3375888
[5] Umang Bhatt, Alice Xiang, Shubham Sharma, Adrian Weller, Ankur Taly, Yunhan Jia, Joydeep Ghosh, Ruchir Puri, José M. F. Moura, and Peter Eckersley. Explainable machine learning in deployment. In Proceedings of the 2020 Conference on Fairness, Accountability, and Transparency, FAT '20. page 648-657, New York, NY. USA. 2020, Association for Computing Machinery. ISBN 978 1450369367. doi: 10. 10.1145/33500953375560 URL httpp:///ol org/ 1141/33511111 095. 3375624.
[6] Sandra Wachter, Brent Mittelstadt, and Chris Russell. Counterfactual explanations without opening the black box: Automated decisions and the gdpr. Harvard journaal of law & technology, 31:841-887, 04 2018. doi:
[7] A.-H. Karimi, G. Barthe, B. Balle, and Valera. Model-agnostic counterfactual explanations for consequential decisions. Proceedings of the 23rd International Conference on Artifi- cial Intelligence and Statistics (AISTATS), volume 108 of Proceedings of Machine Learning Research, pages 895-905. PMLR, August 2020. URL http: htRth:t://ppoceeeeeeee http///proceeeeneee/eeeee/ee mlr .press/ v1 1000///aamm/// 20a html.
[8] Rafael Poyiadzi, Kacper Sokol, Raul Santos Santos-Rodriguez, Tijl De Bie, and Peter Flach. Face: Fea- sible and actionable counterfactual explanations. In Proceedings of the AAAT/ACM Conference on AI, Ethics, and Society, AIES '20, page 344-350, New York, NY, USA, 2020. Association for Computing Machinery. ISBN 9781450371 100. doi: 10. 10.14553375627.3355551 URL httts://doi. org/ 10. 1144//1375622..7 /144//3335622733775555. 3375850.
[9] Arnaud Van Looveren and Janis Klaise. Interpretable Counterfactual Explanations Guided by Prototypes. arXiv, art. arXiv: 111999077.2... July 2019.
[10] Kaivalya Rawal, Ece Kamar, and Himabindu Lakkaraju. Can i still trust you?: Understanding the impact of distribution shifts on algorithmic recourses. arXiv, 2020.
[11] Martin Pawelczyk, Klaus Broelemann, and Gjergji. Kasneci. On counterfactual explanations under predictive multiplicity. Jonas Peters and David Sontag, editors, Proceedings of the 36th Conference Uncertainty in Artificial Intelligence (UA!), volume 124 of Proceedings of Machine Learning Research, pages 809-818. PMLR, 03-06 Aug 2020. URL http:// proceedings mlr, wttres/v122/pawweeee
html.
[12] A.-H. Karimi*, von Kügelgen** B. Schölkopf, and Valera. Algorithmic recourse under imperfect causal knowledge: probabilistic approach. In Advances in Neural Information Processing Systems 33, December 2020. $equal contribution.
[13] Ramaravind K Mothilal, Amit Sharma, and Chenhao Tan. Explaining machine learning classifiers through diverse counterfactual explanations. In Proceedings of the 2020 Conference on Fairness, Accountability and Transparency, pages 607-617, 2020.
11

---

[14] Suresh Venkatasubrammaiian and Mark Alfano. The philosophical basis of algorithmic course. In Proceedings of the 2020 Conference on Fairness, Accountability, and Trans- parency, FAT* '20. page 284-293, New York. NY, USA, 2020. Association for Comput- ing Machinery. ISBN 978 1450369367. //doi.org/ii 1144/335121 095. 3372876.
doi: 10.1145/3350095.33777
URL https:
[15] Solon Barocas, Andrew D. Selbst, and Manish Raghavan. The hidden assumptions behind counterfactual explanations and principal reasons. In Proceedings of the 2020 Conference on Fairness, Accouniability, and Transparency, FAT* '20, page 80-89, New York, NY, USA, 2020. Association for Computing Machinery. ISBN 9781450369367. doi: 10. 00.11455351009933728830
URL www.hhttt///eeee //tp:::://d/ii org/ 10. /3/.//33351995..388.....
[16] Amit Dhurandhar, Pin- Yu Chen, Ronny Luss, Chun-Chen Tu, Paishun Ting, Karthikeyan Shan- mugam, and Payel Das. Explanations based the missing: Towards contrastive explanations with pertinent negatives. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 31, pages 592-603. Curran Associates, Inc., 2018. URL htt.httts://proceeeeeee htwpeeeedddinnneeeeeriieeeeeeeee neurips cc/paper: haw.aaa811111177177--0-0-000 ort.a////.......aa0.0...00...000 pdf.
[17] Basura Fernando and Stephen Gould. Learning end-to-end video classification with rank- pooling. Proceedings of the 33rd International Conference on International Conference on Machine Learning Volume 48, ICML' 16, page 1187-1196. JMLR.org. 2016.
[18] Dimitri Bertsekas and Robert Gallager. Data Networks (2nd Ed.). Prentice-Hall, Inc., USA,
1992. ISBN 0132009161.
[19] Sahil Verma, John Dickerson, and Keegan Hines. Counterfactual explanations for machine learning: A review. arXiv, 10 2020.
[20] Ilia Stepin, Jose M. Alonso, Alejandro Catala, and Martín Pereira-Fariñta A survey of contrastive and counterfactual explanation generation methods for explainable artificial intelligence. IEEE Access, 9:1 120011 2021. doi: 10.109//ACCESS322211331111
[21] Dheeru Dua and Casey Graff. UCI machine learning repository, 2017. htLhttt:://rrccive.. ics. uci edu/ml.
[22] Sorelle A. Friedler, Carlos Scheidegger, Suresh Venkatasuubramanian, Sonam Choudhary, Evan P. Hamilton, and Derek Roth. A comparative study of cdimess-enhancie interventions in machine learning. In Proceedings of the Conference on Fairness, Accountability, and Transparency, FAT* '19, page 329-338, New York, NY, USA, 2019. Association for Computing Machinery. ISBN 978145088 7771450036125 255. doi: 10. 00.1145/2287550.328888999 URL https:// //ooi. org/10...... 1145/ 3287560 3287589.
[23] Perry McGarry. Performance incentive fundiing In VERA, 2012.
[24] Dylan Slack, Sophie Hilgard, Emily Jia, Sameer Singh, and Himabindu Lakkaraju. Fooling lime and shap: Adversarial attacks on post hoc explanation methods. AAAI/ACM Conference on Artificial Intelligence, Ethics, and Society (AIES), 2020.
[25] Martin Pawelczyk, Klaus Broelemann, and Gjergji Kasneci. Learning Model-Agnostic Counterfactual Explanations for Tabular Data, page 3126-3132 Association for Com- puting Machinery, New York, NY, USA, 2020. ISBN 9781450370233. URL https: //doi. 10. /145/33664222 0t55//336622333300088 3380087.
[26] Markus M. Breunig, Hans-Peter Kriegel, Raymond T. Ng, and Jörg Sander. Lof: Identifying base local outliers. SIGMOD Rec., 29(2):93-004, May 2000. ISSN 0163-5808. doi: 10.1 10.1145/335191.335388 URL https://doi. /ttp://6000.00111111141111111111
[27] A.-H. Karimi, B. Schölkopf, and I. Valera. Algorithmic recourse: from counterfactual explana- tions to interventions. In 4th Conference on Fairness, Accountability, and Transparency (ACM FAccT), March 2021.
12

---

(28) Julius Kügelgen, Amir-Hossein Karimi, Umang Bhatt, Isabel Valera, Adrian Weller, and Bernhard Schölkopf. On the fairness of causal algorithmic recourse. AFCI Workshop, NeurIPS, 2020.
[29] Charles T. Marx, F. Calmon, and Berk Ustun. Predictive multiplicity in classification. In ICML, 2020.
[30] Atoosa Kasirzadeh and Andrew Smart. The use and misuse of counterfactuals in ethical machine learning. In Proceedings of the 2021 ACM Conference on Faimesss, Accountability, and Transparency, FAccT '21, page 228 236, New York, NY, USA. 2021. Association for Computing Machinery. ISBN 978 9784430383 doi: 00.1145/3442188.34455888 URL https: //doi.org/10 /115/34442182 3445886.
[31] Yatong Chen, Jialu Wang, and Yang Liu. Strategic classification with light touch: Learning classifiers that incentivize constructive adaptation, 2020.
[32] Behzad Tabibian, Stratis Tsirtsis, Moein Khajehnejad, Adish Singla, Bernhard Schölkopf, and Manuel RodriuzR Optimal decision making under strategic behavior. arXiv preprint 195.99990,.0929, 2019.
[33] Stratis Tsittsis and Manuel Homezz-oodriguez. Decisions, counterfactual explanations and strategic behavior. In Advances in Neural Information Processing Systems (NeurIPS), 2020.
[34] Marco Tulio Ribeiro, Sameer Singh, and Carlos Guestrin. "why should I trust you?": Explaining the predictions of any classifier. In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, San Francisco, CA, USA, August 13-17, 2016, pages 1135 1144, 2016.
[35] Scott M Lundberg and Su-In Lee. A unified approach to interpreting model predictions. In I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, Advances in Neural Information Processing Systems 30, pages 4765-4774. Curran Associates, Inc., 2017.
[36] B. Dimanov, Umang Bhatt, M. Jamnik, and Adrian Weller. You shouldn't trust me: Learning models which conceal unfairness from multiple explanation methods. In RefeAI@AAAL 2020.
[37] Junlin Wang, Jens Tuyls, Eric Wallace, and Sameer Singh. Gradient-based Analysis of NI.P Models is Manipulable. In Findings of the Association for Computational Linguistics: EMNLP (EMNLP Findings), page 247-258, 2020.
[38] UIrich Aivodji, Hiromi Arai, Olivier Fortineau, Sébastien Gambs, Satoshi Hara, and Alain Tapp. Fairwashing: the risk of rationalization. In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages 161-170. PMLR, 09-15 Jun 2019. URL http::/proceeee
mlr. waat.press/vvie / http://///vvvvj/iaa/../ iiiioojj19.... html.
[39] Christopher Anders, Plamen Pasliev, Ann-Kathri Dombrowski, Klaus-Robes Müller, and Pan Kessel. Fairwashing explanations with off-manifold detergent. In Hal Daumé III and Aarti Singh, editors, Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 314-323. PMLR, 13-18 Jul 2020. URL http: / http:///oooceeeeeeeeeee/e mlr press/seevvvv.eee 119 anw.aaaae........ html.
[40] Julia Angwin, Jeff Larson, Surya Mattu, and Lauren Kirchner. Machine bias. In ProPublica, 2016.
[41] Cynthia Rudin, Caroline Wang, and Beau Coker. The age of secrecy and unfair- ness in recidivism prediction. Harvard Data Science Review, 2(1), 3 2020. doi: 10.1162/99608192.6cddee bed64443. URL https://hdae ieteermitttsseee mit. att..eee///ub//100266. https://hbs.miiipesss.tttc////up
[42] Julia Dressel and Hany Farid. The accuracy, fairness, and limits of predicting recidivism. Science Advances, 4(1)eaaa55880 2018. doi: 10. 00.11226/cadyy..00555800 URI. https: //www. science. oowoooog//ooooooooooooooooooo 1t////1.11111111 wttp///////..aaaea..e..aa.....aa aa05580.
13

---

[43] Catalogue of standard toxicity tests for ecological risk assessment. United States Environment Protection Agency, 1994.
[44] Stephen Gould, Basura Fernando, Anoop Cherian, Peter Anderson, Rodrigo Santa Cruz, and Edison Guo. On Differentiating Parameterized Argmin and Argmax Problems with Application to Bi-level Optimization, arXiv e-prints, art. arXiv: July 2016.
14


Reviews:
[{"review_id": "iQHRCPSeiC9", "reviewer": "Reviewer_UNQ2", "summary": "This paper presents a new research problem regarding the vulnerabilities of counterfactual explanations, and introduces an adversarial model/framework to demonstrate the vulnerabilities of existing algorithms which employ hill-climbing to find counterfactual explanations (and initialize the search at the original data point). Some mitigation strategies for improving the robustness of this type of counterfactual explanation algorithms are also presented.\n\nThe work shows that the proposed adversarial model can pass the (recourse) fairness assessments which rely on counterfactual explanations produced by the counterfactual explanation methods using hill-climbing, but in fact is not a fair model as if the other features of an input instance from the non-protected group is perturbed slightly, the counterfactual explanation generated for the instance can be biased (i.e. having a much more desirable recourse). This result demonstrates the potential problem with the counterfactual explanation methods and the fairness assessment scheme based on counterfactual explanations.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Please find below my detailed comments on the originality, significance, quality, and clarity of the paper.\n\n1. Originality and significance\n\nThe problem raised and studied in this paper is novel and has important practical implications for the applications of counterfactual explanations. The proposed adversarial model for demonstrating the problem is also very interesting and convincing. \n\n2. Quality\n\nThe proposed framework/adversarial model is sound and the experiments have shown that it is possible for the manipulation to happen. \n\nSome questions for consideration though, and some discussion on them may strengthen the paper:\n\n(a) In the experiments feed-forward neural networks are used as adversarial models, and convincing results are obtained based on the models. I wonder how would the results would be if other types of machine learning models are used? Perhaps related to this, in theory, is it always possible or does it require similar effort for the manipulation to succeed, i.e. to obtain the \"arbitrary\" function f?  Some more discussions on the conditions for the success of the manipulation would be good.\n\n(b) How sensitive the success of the manipulation is to the value of \\delta? That is, how the cost reductions in Table 1 would change if we change the value of \\delta (around the discovered \\delta value)?\n\n(c) Is it a practical assumption that an adversary knows which counterfactual explanation algorithm, \\mathcal{A} is used by an auditor? I am not familiar with the practice, but I would guess an auditor would keep such sensitive information away from the organization being audited. \n\n(d) Is Definition (2.1) a commonly used measure for assessing recourse fairness? If yes, a reference should be added. If not, some discussion may be needed as to why average distances are used and how the use of average distances (instead of other measures) would affect the design and success of an adversarial model. \n\n3. Clarity\n\nOverall the paper is well written and easy to follow. Below are some minor comments:\n\n(a) About notation: At quite a few places, x^q and \\delta are not bold-faced. Please check and correct.\n\n(b) Line 154, page 4: the statement here about x+\\delta is understandable, but stating that x+\\delta should be \"a\" counterfactual may be confusing, as readers might get x+\\delta and A(x+\\delta) mixed up. I could be wrong, but I understand that as indicated in Figure 1, x+\\delta does not have to be a real counterfactual as A(x+\\delta) is, although the objective of the adversarial model aims to minimize the expectation shown in this line.\n\n(c)  typos: \n\n*Caption of Figure 1: is higher cost -> has higher cost\n\n*Line 78, page 3: an historically -> a historically\n\n*Line 112, Objective 2 --> Objective in Eq. (2) ?\n\n*Line 208, page 6: State -> States", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors have touched on the societal impact of the work, but since the paper proposes an adversarial model, it would be good to mention the potential negative impact of the adversarial model (e.g. someone might exploit the model/idea to design their own adversarial attacks for bad purpose).\n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "SC_yTp_GpSb", "reviewer": "Reviewer_EEmF", "summary": "Context: Counterfactual explanations are a way to locally interpret model decisions for a given input by finding a \"nearby\" input with a different model decision. As in this paper, we can interpret some distance measure between the original input and its \"counterfactual explanation\" point as a kind of cost of achieving a different decision, usually for/to an individual who gets a negative decision to understand what they would need to change to receive a positive decision. In a fairness context we can consider differences in such costs between different groups as evidence of unfairness, for example if there are higher costs (on average, say) for individuals from a protected non-discrimination group.\n\nThe current paper shows that for a certain class of algorithms producing counterfactual explanations, it is possible for a small, adversarial perturbation of the input to produce a dramatically different explanation. The paper points out that this non-robustness of the algorithms in consideration is important from a fairness or regulatory standpoint by simulating a scenario where a model builder can jointly train a classifier and adversarial perturbation so that an auditor relying on counterfactual explanations (using any of the algorithms in consideration here) can be deceived. The paper shows how to train such models that can hide unfairness by providing a low-cost explanation for a nearby point relative to the higher cost explanation of the original input, and demonstrates the concept with experiments using two datasets and four different counterfactual explanation algorithms in the literature. Experiments also show how to achieve robustness by changing the initialization point for the counterfactual explanation algorithm, by reducing the dimension of the input space, or by otherwise constraining the complexity of the classification model.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Originality: This paper adds to a literature of others discussing the shortcomings of so-called counterfactual explanations, and to the list of papers showing that adversarial training can reveal shortcomings of a given class of algorithms. But I believe the combination/intersection is original, i.e. to my knowledge it is the first to directly apply adversarial training in such a setup to produce explanations with lower cost and thereby hide unfairness. \n\nQuality: The results are sound and well-supported by the experiments, the work is mature and relatively complete, and the paper is honest about its assumptions and limitations. \n\nClarity: The paper is clearly written and informative.\n\nSignificance: The result is very important for the reason that the limitations of counterfactual explanations must be analyzed and become well-known to prevent their widespread misuse.\n\nSuggestions: In my opinion there are two things that could improve the paper. The first, and most important, would be to shift the fairness part of the focus away from \"how to train a model that can hide its unfairness\" and toward \"how to determine if a model is hiding unfairness.\" The best version of such a shift would require significant revision, possibly including changes of the auditing setup to require different access. The problem is that the paper currently has in-depth instruction on how model owners with bad motives could do something destructive and unethical, with a brief follow-up of some methods that model owners or auditors with good motives could try to avoid this problem. My second suggestion is a minor one and concerns the term \"counterfactual explanation.\" It is an unfortunate fact that a sizeable literature has already adopted this term despite the fact that it misuses the word \"counterfactual.\" There is no explicit causal model or even philosophical assumption from which these explanations justify their use of the word, it is just comparing one input point to another input point. Several of the papers on the limitations of this approach point out this fact, including ones cited in the current paper. I think it might be helpful if the current paper (and any others that continue misusing the term \"counterfactual\") have some disclaimer early on (e.g. in the introduction) regarding the absence of an actual causal model justification for using the word. This could help some readers avoid confusion. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No. In addition to my first point under the \"Suggestions\" above, this paper also uses a crime prediction dataset for one of its experiments without acknowledging the potential dangers and shortcomings of such a task that have been extensively critiqued in other algorithmic fairness papers. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "IPBwJy-XF7K", "reviewer": "Reviewer_Ky56", "summary": "This paper shows that algorithms used to generate counterfactual explanations are subject to manipulation. The authors provide a technique to adversarially train models that produce unstable counterfactual explanations as well as strategies to mitigate this manipulability.", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The setting being considered here is somewhat contrived, in my view. It supposes that someone building a classifier is required to ensure that the cost of recourse will be equal across two groups, and that an auditor will verify this. However, the entity building the classifier is a bad actor and wants to fool the auditor while actually producing a classifier that has a lower recourse cost for the non-protected group. I'm not convinced that \"equal recourse cost\" is a meaningful notion of fairness to consider, especially in the Communities and Crime dataset analyzed here. But I'm open to pushback on this.\n\nOne major issue I see is that the authors' definition of unfairness appears to require 2 things:\n- Roughly equal recourse costs for 2 groups\n- Substantial reduction in recourse cost for one of the groups when perturbed by $\\delta$\nWhat this doesn't cover is the change in recourse cost for the \"protected\" group when perturbed by $\\delta$ -- if this also results in a similar reduction in recourse cost, then I don't see why this should be considered problematic. This might be possible to address by adding a term to the objective.\n\nBeyond this, the paper is well-written and quite thorough. The experiments provided are natural, and the authors make sure to include robustness checks. They also evaluate a number of mitigation strategies.\n\nOther small comments:\n- $G(\\cdot, \\cdot)$ is used in Lemma 3.1 but I can't find where it's defined -- I assume it refers to the objective in Equation 2.\n- It seems strange to refer to it as \"Wachter's algorithm\" when there are 3 authors on the paper cited.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors haven't explicitly discussed potential negative impacts. Given that the paper provides techniques to learn models that look benign but have undesirable social properties, the authors should include such a discussion.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "DZt6jH195Xd", "reviewer": "Reviewer_qTs3", "summary": "The paper investigates the robustness of existing counterfactual explanation algorithms in terms of bias attributes. The method and experiments make sense.", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The writing is clear and easy to follow and the proposed method is simple yet sound. Just curious if any idea to generalize the method to high-dimensional data like the Image domain.\n\n-------------post rebuttal---------------\n\nAfter reading other reviews, I'd like to maintain my original score.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper contributes to the growing literature documenting the instability and manipulability of different model explanation techniques.  In this work the authors specifically study counterfactual explanations, which commonly describe how an individual's inputs could change to receive a positive classification.  Overall the reviewers agree that the specific problem formulation tackled in this work is novel and that the work improves our understanding of how models can be adversarially manipulated to produce biased recourse costs by hiding low cost recourse paths.  Reviewers also agreed that the paper is well-developed, overall clearly written, and comprehensive.  

The authors have already proposed additional text discussing the implications of developing adversarial models and issues with the common practice of relying on crime-related data in experiments.  Beyond this, the set of revisions in preparation for the camera-ready is fairly small.  For readers who are unfamiliar with the prior literature on "counterfactual" explanations, I agree with Reviewer EEmF that it would be work clarifying that the term "counterfactual" doesn't have the same meaning here as it does in the context of causal inference. Other reviewers provided lists of requested clarifications/modifications that are all actionable and would improve the clarity and accuracy of the manuscript.

Congratulations on an excellent submission! 
Decision: Accept (Poster)