  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
vulnerabilities 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.
