Prediction without Preclusion: Recourse Verification with Reachable Sets
Authors: Avni Kothari
Bogdan Kulynych
Tsui-Wei Weng
Berk Ustun
Venue: ICLR 2024 spotlight (2024)
Keywords: algorithmic recourse
fairness
robustness
consumer finance
integer programming
trustworthy AI
Primary area: societal considerations including fairness, safety, privacy
TL;DR: Models can assign fixed predictions that preclude access. We can flag them by certifying that recourse is infeasible.

Abstract: Machine learning models are often used to decide who receives a loan, a job interview, or a public benefit. Models in such settings use features without considering their *actionability*. As a result, they can assign predictions that are \emph{fixed} -- meaning that individuals who are denied loans and interviews are, in fact, *precluded from access* to credit and employment. In this work, we introduce a procedure called *recourse verification* to test if a model assigns fixed predictions to its decision subjects. We propose a model-agnostic approach for verification with *reachable sets* -- i.e., the set of all points that a person can reach through their actions in feature space. We develop methods to construct reachable sets for discrete feature spaces, which can certify the responsiveness of *any model* by simply querying its predictions. We conduct a comprehensive empirical study on the infeasibility of recourse on datasets from consumer finance. Our results highlight how models can inadvertently preclude access by assigning fixed predictions and underscore the need to account for actionability in model development.

PREDICTION WITHOUT PRECLUSION: RECOURSE VERIFICATION WITH REACHABLE SETS
Avni Kothari!
Bogdan Kulynych" EPFL
Tsui-Wa Weng
Berk Ustun UCSD
UCSF
UCSD
ABSTRACT
Machine learning models are often used to decide who receives loan, a job inter- view, or a public benefit. Models in such settings use features without considering their actionability. As result, they can assign predictions that are fixed - meaning that individuals who are denied loans and interviews are, in fact, precluded from access to credit and employment. In this work, introduce procedure called recourse verification to test if a model assigns fixed predictions to its decision subjects. We propose model-agnostic approach for recourse verification with reachable sets - i.e., the set of all points that a person can reach through their actions in feature space. We develop methods to construct reachable sets for dis- crete feature spaces, which can certify the responsiveness of any model by simply querying its predictions. We conduct a comprehensive empirical study on the infeasibility of recourse on datasets from consumer finance. Our results highlight how models can inadvertently preclude access by assigning fixed predictions and underscore the need to account for actionability in model development.
INTRODUCTION
Machine learning models routinely assign predictions to people - be it to approve an applicant for a loan [24], job interview [5, 51], or public benefit [66, 13, 16]. Models in such applications use features about individuals without accounting for how individuals can change them. In turn, they may assign predictions that not responsive to the actions of their decision subjects. In effect, even the most accurate model can assign prediction that is fixed (see Fig. 1).
The responsiveness of machine learning models facing applications. In applications like content moderation, models should assign fixed predictions prevent malicious actors from circumventing detection by manipulating their features [25, 42, 31J. In lending and hiring, however, predictions should exhibit some sensitivity to our actions. Otherwise, models that deny loans and interviews may preclude access to credit and employment, thus violating basic rights such as equal opportunity [3] and universal access [8].
actions is vital to their safety in consumer-
In this work, we introduce a formal verification procedure to test the responsiveness predictions with respect to the actions of its decision subjects. Our procedure - recourse verification grounded in a stream of work on algorithmic recourse [57, 59, 28]. While much of the work in this area focuses on recourse provision i.e., providing person with actions to obtain a desired prediction from model - we focus on recourse verification - i.e., certifying that model assigns predictions that each person can change. Unlike provision, verification is model auditing procedure that practitioners can use to flag models that preclude access or promote manipulation.
model's
The key challenge in recourse verification stems from the fact that must test the sensitivity of model's predictions with respect to actions rather than arbitrary changes in feature space. In lending application, for example, actions value to a positive integer and should lead to a commensurate change in other temporal features like age. Such constraints are easy to specify for features that are semantically meaningful, but difficult to enforce in methods for recourse provision. To claim that model assigns fixed prediction to point, must prove that its predictions will not change under any possible action. In practice,
feature such years_of _frrs__ffoocotttttr aecount_hisstoy should set its
Equal Contribution

---

Empirical Risk Minimization
Action Set
Reachable Sets
citssifler assigns
actionabiiity constraints embedd optimization problems
that
prediction without (1, 1)
post-hoe fifitiiion any
respal Scant
6n
Dataser
Best Modal
2.0 na H-3, 1
Rx(0.0) (10.0) (1.0). (1,
Rx (1.11).01
Rx(1.0) (1.00)(1.))
02 + 12 (0.1)
RA(1. (0.1)
16
16
Figure I: Stylized classification task where the most accurate classifier on dataset with n = 60 negative examples and n² 90 positive examples assigns prediction without recourse to individuals with (21 (1. We predict y repay_loan using two hinary features (x1: = (reappli cant, age 60), which only increase from to 1. We denote the actions on each feature as (#1, d2) and show constraints they must obey in the action set. Given any model, we certify the responsiveness of its outputs for (æ1, x2) by checking its prediction for each point in the reachable set (21 æ2). In this case, 42 individuals with (01, x2) = (1,1) assigned prediction without recourse f(21, 22) 0 for all (2) E R1(1,1).
this requires exhaustive search over combinatorial subset of actionable feature space. This is non-trivial computational task especially for complex models - as we must certify the infeasibility of combinatorial optimization problem that faithfully encodes complex decision boundary.
Our main contributions include:
1. We present model-agnostic approach for recourse verification by constructing reachable set - i.e., a set of all points that person can attain through their actions in feature space. Given a reachable set, we can certify the responsiveness of model's predictions by simply querying its predictions over reachable points.
2. We develop fast methods to construct reachable sets for discrete feature spaces. Our methods can construct complete reachable sets for complex actionability constraints, and can support practical verification in model development and deployment.
3. We conduct a comprehensive empirical study on the infeasibility of recourse in consumer fi- nance applications. Our results show how models can assign fixed predictions due inherent actionability constraints, and demonstrate how existing methods to generate recourse actions and counterfactual explanations may inflict harm by failing detect such instances.
We develop a Python package for recourse verification with reachable sets. Our package includes an API for practitioners to easily specify complex actionability constraints, and routines to test the actionability of recourse actions and counterfactual explanations.
Related Work We focus on a new direction for algorithmic recourse [57, 59, 29] - i... as a procedure certify the responsiveness of model's predictions with respect to the actions of its decision subjects. Although actionability is a defining characteristic recourse [see 59], few works mention models may assign fixed predictions as result of actionability constraints [57, 30, 10]. The lack of awareness stems, in part, from the fact that methods for recourse provision are typically designed and evaluated with simple actionability constraints such as immutability and monotonicity, As we show in Appendix C.5, however, infeasibility only arises once we start to consider actionability constraints that are difficult handle in algorithm design.
We study recourse verification as a model auditing procedure to safeguard access in applications like lending. In such applications, verification essential for reliable recourse provision - as can flag model that cannot provide recourse to consumers before it is deployed. To this end, our motivation aligns with a stream of work on the robustness of recourse provision with respect to distribution shifts [52, 18, 2, 47, 20], model updates [56, 49], and causal effects [40, 28, 35]. More broadly, recourse verification is a procedure to test the responsiveness of predictions over semantically meaningful features, which may be useful for stress testing for counterfactual invariance [58, 41, 50], certifying adversarial robustness on tabular datasets [39, 27, 23, 60, 42, 31], or designing models that incentivize improvement deter strategic manipulation [19, 11, 38, 44, 15, 6, 21, 54, 32, 33, 1, 22].
2

---

2 RECOURSE VERIFICATION
We consider a standard classification task where we are given a model f: X + y to predict label E y = {0, } from vector of features = [xi...... Edl X' in a bounded feature space X. We assume each instance represents person, and that f(x) e.g., an applicant with features æ will repay loan within 2 years.
represents a desirable target prediction
Our goal is to test if each person can obtain a target prediction from the model by changing their features. We represent such changes in terms of actions. Formally, each action vector = [a1.....ad ad] E Rd that shifts their features from æ to æ + a x' E X. We refer to the set of all actions from E X as action set A(x), and assume that it contains null action 0 A(x). In practice, an action set A(x) ) is a collection constraints. As shown in Table 1, we can express these constraints in natural language or equations that can embed into an optimization problem.
Semantically meaningful features admit hard actionability constraints. In the simplest cases, action- ability constraints reflect the way that semantically meaningful features can only be altered in specific ways. For example, a model may use a feature that cannot change (e.g., age) or that can only be changed specific ways (c.g., has_phd, which can only be changed from 1). More generally, constraints may require that changing one feature will induce changes on other features (c.g., chang- ing married from to must set single from 0). Such downstream effects can be directional (e.g., changing retired from to 0 will set work_days_pee _wee to O, but not vice-versa), and may affect features that are not themselves actionable (e.g.. changing years_of wwcpsuuf_aaacoo_aoaaaa/_aa hii whitnttttstttyyyy from O to 2 will increase age by 2 years).
Class
Sepurable
Discrete
Example
Features
Constraint
Immusahility
n_depencents should not change
n_dependents
Monotonicity
x
reapplicant can only increase
reapplicant
2
Integrality
postiive insegr 10
nlaaccuunts
6.6 (1annppxxii 1000x.10--11
Calegorical
preserve one hot eacoding married, single
married single
a t 6 (0.1) ti (0.1)
Encoding
Ordinal
preserve one-hot eacoding of degree, BS,
darrdegree,
oy e (a.1) zu- (0.1)
Enceding
nog.degree
4, - 20
iiis.en employed - TRLE
0, 22 E (0.1)
Logical
is erployed
Implications
then work_hrs hork_hrs_porrr.. per_week22
[1,168]
the work.hrs.see hrr.phrspperr perssper_.eek..... week
0y + By 168(22 + o2)
Causal
f'yerrs.of _o__ocouut_ history increases then age will increase commensunaety
years.at, residencc
Implications
age
0g
Table 1: Examples of deterministic actionability constraints. We show how each constraint can be expressed in natural language and embedded into an optimization problem using standard techniques in mathematical programming [see e.g., 65]. We highlight constraints that are discrete and non-separable because they can only be enforced using special kinds of search algorithms.
Verification a Feasibility Problem Given a model ʃ X Y and point X' with action set A(x), the recourse provision task seeks to find an action a E A(x) that minimizes a cost function cost(a z). This task requires finding an optimal solution to an optimization problem as in Eq. (1).
The recourse verification task seeks to determine if recourse is infeasible from æ i.c., if model assigns the same prediction f(x + a) 0 for all actions A(x). This task only requires finding a feasible solution to Eq. (1), which can be cast as the optimization problem in Eq. (2).
Recourse Provision
Recourse Verification
min cost(a ( x)) s.t. f(x + a) =1
min 1
(1)
s.t. f(x + a)=1
(2)
a E A(x)
a E A(z)
We set the objective of Eq. (2) to constant so that any algorithm that solves Eq. (2) will terminate as soon has found feasible solution.
3

---

We can write the input and output of a recourse verification method as the function:
Yes, if method returns an action E A(x)) such that f(x + a) Recourse(1; (2, A, No, method proves that f( + a) for all actions a E A(x)
otherwise
We say that a method for recourse verification certifies feasibility from æ if it outputs Yes and that certifies infeusibilityy from it outputs No. In practice, existing methods for recourse provision may return outputs that cannot support either of these claims. For example, they may fail to return an action without having searched exhaustively, or return an "action" that violates actionability constraints. In such cases, we say that the method abstains for and denote its output as L.
Use Cases Recourse verification is model auditing procedure test the responsiveness of model's predictions with respect to the actions of its decision subjects. We can apply this procedure flag models that are unsafe in different consumer-facing applications by testing responsiveness by choosing an appropriate action set.
Detecting Preclusion. In applications where we would like to safeguard access (c.g., lending), we can flag that model f precludes access by testing the responsiveness of predictions on points for which f(x) = 0. In this case, we would specify an action set that captures indisputable constraints and applies all individuals. We would claim that the model precludes access if Recourse(xx, J, A) No for any point such that f(æ) =
Ensuring Robustness. In applications where we would like to mitigate gaming (e.g., content mod- eration), we can certify that a model f is vulnerable to adversarial manipulation by testing the responsiveness of its predictions on points for which f(z) = In this case, we would specify an action set A(x) that encodes a threat model [31] 1 i.e., actions that let individuals obtain target prediction by changing spurious features [see 15, 43]. We would claim that the model is vulnerable to manipulation if Recourse( a,, S, A) Yea for any point such that f(x) O.
Since these audits apply over points in feature space, we can run verification at different stages of a model lifecycle to minimize the chances of inflicting harm. In model development, we would test if model assigns fixed predictions to any point in the training data. In deployment, we would repeat this test for new points. In both cases, the procedure would establish that model assigns fixed predictions, and could support further interventions to mitigate these effects (see Section 4).
Actionability can vary substantially between individuals [see 4, 59]. In principle, we can account for these variations by calling recourse verification method with personalized actionability constraints that we elicit from each decision subject [via, e.g., an interface as in 62]. In practice, we can mitigate harm in consumer-facii because models may assign fixed predictions as a result of inherent actionability constraints - i.c., constraints that apply all decision subjects and that practitioners could glean from data dictionary (e.g.. constraints that enforce physical limits or preserve a feature encoding). Seeing how inherent constraints represent subset of personalized constraints, audits with inherent actionability constraints should be used to flag that a model inflicts harm rather than to certify that it is safe.
applications without eliciting personalized constraints. This is
Algorithm Design Requirements and Pitfalls Methods for recourse verification should be de- signed to certify infeasibility. This is an essential requirement for verification as it implies that a method can prove that model's prediction will not change under any possible action. The vast majority of existing methods for recourse provision are ill-suited for verification because cannot certify infeasibility. In practice, these methods will return outputs that are inconclusive or incorrect for recourse verification tasks. We refer to these instances as loopholes and blindspots and define them below.
Definition 1. Given recourse verification task for a model f for point æ with the action set A(x), we say that a method returns a loophole its output violates actionability constraints.
Methods for recourse provision return loopholes when they search for actions using an algorithm that cannot enforce all actionability constraints in recourse verification task. For example, methods that search for recourse actions using gradient descent [45] will return loopholes when we must verify recourse with respect to action set that includes the discrete actionability constraints in Table 1.
4

---

Definition Given recourse verification task for a model f for a point with the action set A(r), we say that a method exhibits blindspot if it fails to find an action for point where Recourse(2; a. A) = Yes.
Methods for recourse provision output blindspots when they cannot search exhaustively. Common algorithm design patterns that lead to blindspots include: (i) Searching for actions over observed data points [see e-g.. 61, 46]; and enforcing actionability by post-hoc filtering i.e., by generating a large collection of changes in feature space and filtering them to enforce actionability [see e.g., 37] which exhibits blindspots when the generation step is guaranteed to generate all possible actions.
3 VERIFICATION WITH REACHABLE SETS
We introduce model-agnostic approach for recourse verification. Our approach constructs reachable sets - ie., sets of feature vectors that obey actionability constraints.
Definition Given a point æ and its action set A A(x), a reachable set contains all feature vectors that can be attained using the actions in A(x): RA (x) {æ + a a A(x)).
Given a reachable set R. (x), we can certify that a model f provides recourse to by querying its predictions on each point æ E RA (x)). Thus, we can write the verification function as:
Yes,
if there exists reachable point x' E <R((v) s.t. ((x'==1 if fxx) 0 for all reachable points x' E Rx)
Recourse( RR No,
(3)
if fxx' = 0 for some reachable points x' R RA(
Verification with reachable sets has three key benefits:
Model Agnostic Verification: We can use reachable sets to verify recourse for any model class. Model agnostic approaches are especially valuable for recourse verification because it is challenging, if not impossible, to develop a model-specific approach for complex model classes such as ensembles and deep neural networks. In particular, this stems from the fact that such method would have to certify the infeasibility of a combinatorial optimization problem that encodes both the model and the actionability constraints. In practice, such problems be prohibitively large solve in audit we would have to encode a complex decision boundary [see e.g., 55, 48).
Amortization: In recourse verification task where we have access to suitable method for recourse verification, we may still wish to verify recourse using reachable set. This is because, once we have constructed reachable sets, we can use them to verify recourse for as many models as we wish.
Explicit Abstention: In settings where we cannot enumerate complete reachable set, we can use the interior approximation of the reachable set R C R (z:). this case, the procedure will certify recourse if it can find a feasible action. Otherwise, it will abstain thus, flagging prediction without recourse. We can exploit this property to speed up construction through lazy initialization pattern. For example, rather than constructing a complete reachable set for every training example, we can construct an interior approximation R C (x). In this setup. we would use the interior approximations to certify feasibility, and only construct the full reachable sets R RA (ar) for points for which we would abstain Recourse(2r,
potential
3.1 CONSTRUCTION
In Algorithm 1, we present a procedure to construct a reachable set for given point by solving an optimization problem of the form:
Algorithm GetReachableSet
Require: æ E X, feature vector
Require: A(æ), action set for {x)
FindAction(zr, A) argmin ||a|| s.t. E A(x) (0).
R
A(x)
We formulate FindAction(z,, A) as mixed-integer pro- gram that we present in Appendix B. Our formulation encode all actionability constraints in Table I and designed to be solved way that fast and reliable using off-the-shelf solver [see e.g., 17, for list].
1:
while FindAction(2, A) is feasible do a" +- FindAction(z,, A)
2:
3:
R - RU (ar a
A A {a")
Output
RA(
5

---

Given a point æ, the procedure enumerates all reachable points by repeatedly solving this problem and removing prior solutions by adding "no-good" constraint [see e.g., 53]. The procedure stops once FindAction(zz, A) infeasible at which point it has enumerated all possible actions and thus reachable points. In practice, the procedure can be stopped when user-specified stopping condition is met, in which case it would return an interior reachable set C (x(x) that can certify feasibility.
Decomposition Seeing how reachable sets grow exponentially with the number of features, Algo- rithm may generate an incomplete reachable set that cannot certify infeasibility under reasonable time constraints. We overcome this issue through decomposition i... by applying Algorithm to subsets of features that can be altered independently for all points x E X.
Given an action set over features, can identify subsets that can be altered independently by inspection. In this way, we can construct the most gramular partition of features - i.c., a collection of k feature subsets M == [Si,... S&} such that A(x) IISM As(æs). Given the partition M, we generate reachable sets for each feature subset Rs by calling Algorithm for each As (xss). and recover the full reachable set as R IISE Rg.
Decomposition moderates the combinatorial explosion in our setting - making it viable enumerate reachable sets in practice. This strategy leads to considerable improvement in runtime, as we construct reachable sets for each subset by solving smaller instances of FindAction(), and can construct the reachable set for single feature subsets without solving a MIP.
3.2 AUDITING IN PRACTICE
We can verify recourse in model development by constructing reachable set for each point in dataset. Once we have constructed reachable sets for each point, we can call recourse verification for any model by querying its predictions on reachable points per Eq. (3). In practice, the most time-consuming part our approach stems from the construction reachable sets. our implementation,
achieve considerable speed up in construction through parallel computing and sharing reachable sets across points. In a task with immutable features, for example, we only need construct and store single reachable set for any points and æ' that only differ in terms of immutable feature values.
Given that approach is designed verify recourse with prediction queries, it may be time- consuming for models with resource-intensive inference step. In such cases, we can minimize prediction queries through short-circuiting In some settings, we can certify that model provides recourse to a point analytically - i.e., without querying its predictions on reachable points by applying the result in Theorem 4.
Theorem 4. Suppose we have a dataset D = W:) with n positive examples, and a point with the reachable set R C Ra(x). ). In this case, every model f X y will provide recourse to x so long as its false negative rate over D obeys:
FNR(F)
n Σ IMERAA
Theorem 4 highlights an alternative approach for recourse verification with reachable sets - i.e., we can certify that model f must provide recourse a point æ so long as the false negative rate does not exceed the density of positive examples in its reachable set. The values can be computed dataser with lahels be it the training dataset or a separate dataset. practice, this approach may be useful when working with model classes where prediction queries are time-consuming. In practice, the result requires a dataset that is "dense" enough so that a reachable set for a point contains other labeled examples. When this condition holds, by comparing the false negative rate of ff to the prevalence of positive examples in its reachable set.
any
certify that model provides recourse point
2 Formally, we say two subsets of features 1' C [d] can be altered independently if the action set over S UUT I' can be expressed as a product of action sets over S and ''' for all points x E X. For example, given the subsets S, T where 5 T = [d], we write A(x) (s(rs) Ar AxFT) for all [mss ær) E X' where x denotes Cartesian product.

---

3.3 DISCUSSION AND EXTENSIONS
Our methods are designed construct reachable sets that can be used for recourse verification over discrete feature spaces. In principle, we can construct reachable sets for continuous feature spaces through sampling, but leave this as topic for future work as it involves a probabilistic guarantee of infeasibility (see Section 5).
Our methods may be useful as a tool to enforce actionability over continuous feature spaces. In particular, we can extend our formulation for FindAction() as a routine to test the feasibility of changes from existing methods to generate recourse actions and counterfactual explanations. case where such methods would suggest that person can change their prediction by altering their features from æ to x', we can test the feasibility such changes with respect to actionability constraints by solving optimization problem of the form:
lsReachable(r, x,, = min
S.t. x == a. a E A(x).
This routine can be used as way to test for actionability in existing methods via post-hoc filtering. In such cases, the resulting procedure would allow practitioners to flag outputs that violate actionability constraints, and avoid the challenges of detecting loopholes. As we explain in Section 2, it would not be able to certify that recourse is infeasible.
EXPERIMENTS
We present experiments showing how predictions without recourse arise under inherent actionability constraints and how existing methods can fail to detect these instances.
4.1 SETUP
We work with three classification datasets from consumer finance, where models that assign fixed predictions would preclude credit access (see Table 2). We process each dataset by encoding categorical attributes and discretizing continuous features. We use the processed dataset to fit classification model using one of the following model classes: logistic regression (LR), XGBoost (XGB), and random forests (RF). We train each model using 80%/20% train/test split and tune hyperparameters using standard k-CV. We report the performance each model in Appendix C.
We specify inherent actionability constraints for each dataset - focusing identifying indisputable conditions that apply to all individuals (e.g., compliance with physical limits, preserving feature encoding, enforcing deterministic causal effects, and preventing changes to protected attributes). We list the constraints for each dataset in Appendix C. We note that the constraints for all datasets include mix of separable constraints (e.g. immutability, integrality, monotonicity) well non-separable constraints (e.g., encoding presentation, deterministic causal effects).
We construct reachable sets for each point in the dataset using Algorithm 1. We use the reachable sets to identify individuals who are assigned prediction without recourse by any one of the models. The results from reachable sets reflect the ground-truth feasibility of recourse for each point and each model class. We label our results as Reach and use them to benchmark the reliability of two salient methods generate recourse actions and counterfactual explanations:
AR [57], model-specific method that certify infeasibility for linear classifiers and handle separable actionability constraints,
DiCE [45], model-agnostic method that handles some separable actionability constraints.
4.2 RESULTS AND DISCUSSION
On Predictions without Recourse We summarize our results for each dataset, method, and model class in Table 2. Our results show that models assign fixed predictions under inherent actionability constraints. In practice, individuals who assigned predictions without recourse may vary drastically across models that perform equally well. Seeing how reachable sets do not change across models, these differences arise from the different decision boundaries of each model.
7

---

LR
XGB
RF
Dataset
Metrics
Reach
AR
DICE
Reach
AR
DICE
Reach
AR
DICE
Table 2: Overview of results for all datasets, model classes, and methods. For each dataset and model class, we use Reach to determine individuals who are assigned predictions without recourse. We use these results to reliability of AR and DiCE for recourse verification tasks. We evaluate each method in terms of the percentage of points where it: certifies recourse; outputs an action; oulputs a loophole, i.e., an action that violates actionability constraints; outputs action; exhibits blindspot, i.e. oulputs action when recourse exists. Certifies No Recourse
22.2%
22.3%
31.3%
heloc
Outputs Action
77.8%
85.9%
57.6%
77.7%
57.3%
68.7%
49.3%
n = 5,842 d = 43
4. Loopholes
0.0%
41.1%
34.4%
0.0%
NA
42.1%
0.0%
NA
29.5%
FICO [14]
Outputs No Action
22.2%
14.1% 1%
42,4%
22.3%
42.7%
31.3%
50.7%
4. Blindspots
0.0%
0.0%
21.0%
0.0%
21.1%
0.0%
19.8%
Certifies No Recourse
7.4%
7.1%
28.6%
german 1,000 d= Dua and Graff [12]
Outputs Action
92.6%
91.7%
92.1%
92.9%
93.3%
71.4%
68.0%
Loopholes
0.0%
2.2%
16.6%
0.0%
NA
23.1%
0.0%
NA
24.0%
Outputs No Action
7.4%
8,3%
7.9%
7.1%
6.7%
28.6%
32.0%
6. Blindspots
0.0%
1.3%
0.9%
0.0%
0.0%
0.0%
3.4%
Certifies No Recourse
15.6%
16.5%
0.2%
veeeeceed t 120,268 d 23
Outputs Action
84.4%
84.4%
79.7%
83.5%
78.5%
99.8%
97.7%
4 Loopholes
0.0%
40.7%
34.6%
0.0%
NA
34.7%
0.0%
NA
57.7%
Kaggle [26]
Outputs No Action
15.6%
15.6%
20.3%
16.5%
21.5%
0.2%
2.3%
4. Blindspots
0.0%
0.0%
4.7%
0.0%
5.0%
0.0%
2.3%
Here, each metric expressed as a percentage of the points that are assigned a negative prediction by a model.
On Loopholes Our results in Table 2 show how methods to generate recourse actions may output loopholes- - i.e., actions that violate actionability constraints. In particular, this failure mode affects between 2.2% to 57.7% of individuals across datasets, methods, and models. As we describe in Section 2, methods return loopholes when they cannot enforce all actionability constraints in a prediction task. In this case, we note that AR and DiCE can enforce separable actionability constraints. Thus, the loopholes arise from constraints that affect multiple features.
Loopholes reflect silent failures that undermine the benefits of recourse provision and may inflict harm. Consider a consumer finance application where we use AR or DiCE to provide consumers with actions that they can perform to qualify for loan. In this case, loopholes that are left undetected would lead us to present consumers with recourse actions that are fundamentally impossible. On the heloc dataset, for example, we find that DiCE returns loophole for 42.1% of individuals who are denied credit by an XGB model. Although some loopholes may be easy to spot through visual inspection a basic immutabiliyy check, this not always the case. In this case, 27% of individuals receive an action that alters 5 or more features simultaneously many of them can only be detected reliably through programmatic approach that can test if they meet actionability constraints.
On the Illusion of Feasibility Our experiments show that recourse often appears to be feasible when methods are only able to enforce simple constraints. We study this effect in Appendix C through an ablation study where we audit models for the heloc dataset under special classes of actionability constraints. Our results show that methods return loopholes for individuals with fixed predictions under simple constraints such immutability and monotonicity, and that infeasibility only arises once methods can enforce more complex constraints. In this case, we find that LR assigns a prediction without recourse 22.2% of individuals. If we enforce monotonicity and integrality constraints, however, recourse appears to be feasible for xe 99% points when using AR.
On Blindspots Our results show how existing methods for recourse provision may return results that are inconclusive or incorrect for verification. In Table 2, we highlight this failure mode by reporting the prevalence of blindspots- i.e., the proportion of instances where a method fails to return recourse action for an individual who has recourse. On the heloc dataset, for example, that DiCE fails to find an action for 42.7% of individuals who are denied by the XGB model. In this case, DICE returns error message "no counterfactuals found for the given configuration, perhaps try with different parameters..." Our analysis shows that nearly half of these cases (21.1% 1% of 42.7%) correspond to blindspots while the other half are predictions without recourse (21.6%).
find
Blindspots differ from loopholes in that they represent an "overt" failure mode that is unlikely to inflict harm. In practice, these failures are more likely to stump practitioners who find that method
8

---

XG8
Size of Reachable Set
Recourse Incorrect Recourse Correct Recourse Correct
100,000
50,000
0%
20%
40%
60%
80%
100%
0%6
20% 40%
60% 80%
100%
Figure Reachable sets for each point in the heloc dataset, ordered from smallest to largest along the x-axis. We show predictions without recourse in red and highlight incorrectly predicted points in darker colors. As shown, predictions without recourse are prevalent across all reachable set sizes and vary significantly between classifiers.
fails find recourse action. In such cases, the key issue is attribution, practitioners cannot determine whether the failure is due to (1) prediction without recourse; (2) the search algorithm used search for actions; (3) bug in the recourse provision package; (4) bug in their code. More broadly, the results highlight the value of designing methods that can certify infeasibility as methods that could certify infeasibility could provide evidence of preclusion in such cases.
On Interventions to Mitigate Preclusion Our results show how recourse verification can guide heuristic interventions that mitigate preclusion. minimum, we can use the results from an audit for model selection - ie.. to choose model that minimizes preclusion among models that are almost equally accurate. On the heloc dataset, for example, we find that RF and XGB models have a test AUC 0.780 but an 11 1 difference in the predictions without recourse thus, we reduce preclusion without compromising performance by simply choosing to deploy an XGB model over an RF model. Seeing how reachable measure preclusion through prediction queries, this strategy in earlier stages of model development e.g.. we can search for model hyperparameters that minimize preclusion by defining custom metric compute the "preclusion rate." " In this case, we note that parameters that control the decision boundary of the model can lead to substantial differences in preclusion without compromising training accuracy - we only need assign target prediction to a reachable point rather than the current point. In general, we can mitigate preclusion by defining features to promote actionability or by dropping features that lead to fixed predictions. In contrast to the previous interventions, this may require constructing new collection of reachable sets at each iteration.
can apply
CONCLUDING REMARKS AND LIMITATIONS
Our paper highlights how machine learning models can assign fixed predictions as a result of actionability constraints, and describes how such predictions can lead to preclusion in consumer- facing applications such as lending and hiring. Our work proposes to address these failure modes by developing methods for task called recourse verification.
Recourse verification broadly represents new direction for research in algorithmic recourse i.e., model auditing procedure certify the responsiveness of predictions with respect actions. The methods in this paper are designed for recourse verification over discrete feature spaces and deterministic actionability constraints, but should be extended address the following limitations:
Our methods designed to certify infeasibility with respect to actions over discrete feature spaces and cannot certify infeasibility with respect to actions on continuous features. In principle, continuous feature spaces by
is possible construct reachable sets that certify infeasibility sampling. We leave this topic for future work as it requires a different algorithm and returns a probabilistic guarantee of infeasibility.
Our methods do not consider probabilistic causal effects - i.e.. where actions on a feature may incite changes downstream features in probabilistic causal model [see, e.g., 30, 34, 10, 35]. Although our methods may be useful to generate actionable interventions in this setting, a reliable method for verification should return probabilistic guarantee of infeasibility that accounts for potential misspecification in the causal model.

---

ETHICS STATEMENT
Our work highlights how machine learning models can assign fixed predictions as a result of actionabilityy, and proposes task called recourse verification to reliably detect such instances.
We study recourse verification as a model auditing procedure that practitioners and auditors can use to detect preclusion in consumer-facing applications such lending and hiring. The normative basis for the right to access in such applications stems from principles such as equality of opportunity (e.g.. in hiring) and universal access (c.g., for basic health insurance). In other words, these are applications where we would want to safeguard access even if it comes at a cost - because it reflects the kind of society we want to build. In practice, ensuring access may not impose any cost. In lending, for example, lenders only collect labels for consumers who are approved for loans [36, 9, 63, due to selective labeling). Thus, consumers assigned predictions without recourse cannot generate labels that would signal creditworthiness [7]. In the United States, such effects have cut off credit access for large consumer segments whose creditworthiness is unknown [64, see, e.g., 26M "credit invisibles").
Our paper primarily studies auditing models in lending and hiring with respect to indisputable con- straints that apply to all decision subjects - inherent actionability constraints. Our recommendation is based on the fact that such constraints can be gleaned from a data dictionary, that claims surround- ing preclusion should be indisputable, and that models may lead to preclusion as a result of such constraints. Given that individuals in these applications will face additional actionability constraints, the results of such an audit should be used to flag models that preclude access rather than to certify that models are safe.
In applications where elicitation is possible, our proposed approach can support a number of practices handle assumptions surrounding actionability in a way that promotes transparency, contestability, and participatory design. In particular, individuals can express their constraints in natural language allowing stakeholders to scrutinize and contest them even without technical expertise in machine learning. In the event that stakeholders disagree on actionability constraints, we recommend deter- mining their disagreements affect claims of infeasibility through an ablation study. In such cases, we can run verification using the subset of "consensus constraints" that all stakeholders agree on. In this worst case, we may still find that models lead to preclusion since the "consensus constraints" will always contain inherent constraints.
ACKNOWLEDGMENTS
This work is supported by the National Science Foundation (NSF) under grant I1S-2313105.
REFERENCES
[1] Alon, Tal, Magdalen Dobson, Ariel Procaccia, Inbal Talgam Cohen, and Jamie Tucker-Foltz. Multiagent evaluation mechanisms. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 1774-1781, 2020.
[2] Altmeyer, Patrick. Giovan Angela, Aleksander Buszydlik, Karol Dobiczek, Arie Deursenvan and Cynthia Liem. Endogenous macrodynamics algorithmic recourse. In First IEEE Conference on Secure and Trustworthy Machine Learning.
[3] Arneson, Richard. Equality of Opportunity. In Zalta, Edward N., editor, The Stanford Encyclopedia of Philosophy. Metaphysics Research Lab, Stanford University, Summer 2015 edition, 2015.
[4] Barocas, Solon, Andrew D Selbst, and Manish Raghavan. The hidden assumptions behind counterfactual explanations and principal reasons. In Proceedings of the 2020 Conference on Fairness, Accountabillty, and Transparency, pages 80-89, 2020.
[5] Bogen, Miranda and Aaron Ricke. Help wanted: An examination of hiring algorithms, equity, and bias. Upturn, December, 7, 2018.
[6] Chen, Yatong, Jialu Wang, and Yang Liu. Strategic recourse in linear classification. arXiv preprint arXiv:2011.005: 2020.
[7] Chien, Jennifer, Margaret Roherts, and Berk Ustun. Learning through Recourse under Censoring. NewrIPS Workshop Learning and Decision-Maker with Strategic Feedback, 2021.
10

---

[8] Daniels, Norman. Equity of access health care: some conceptual and ethical issues. Milbank Memorial Fund Quarterly. Health and Society, pages 51-81, 1982.
[9] Dr-Artaaga, Maria, Artur Dubrawski, and Alexandra Chouldechova. Learning under selective labels in the presence of expert consistency. arXiv preprint arXiv: 180,000900000 2018
[10] Dominguez-Olmedo, Ricardo, Amir H Karimi, and Bernhard Schölkopf. On the adversarial robustness of causal algorithmic recourse. In International Conference on Machine Learning, pages 5324-5342. PMLR, 2022.
[11] Dong, Jinshuo, Aaron Roth, Zachary Schutzman, Bo Waggoner, and Zhiwei Steven Wu. Strategic classification from revealed preferences. In Proceedings of the 2018 ACM Conference on Economics and Computation, pages 55-70. ACM, 2018.
[12] Dua. Dheeru Casey Graff. UCI machine learning repository, 2017. URL http: edu/ml.
[13] Eubanks, Virginia. Automating inequality: How high-tech tools profile, police, and punish the poor. St. Martin's Press, 2018.
[14] FICO. Explainable machine learning challenge, 2018. URL https://communi: fico.it.cciooooooooooooooocoooo fim/..om/// com/s/
[15] Ghalme, Ganesh, Vineet Nair, Itay Bilat, Inbal Talgam-Cohen, Cohen, Rosenfeld. Strategic classification in the dark. In International Conference on Machine Learning, pages (672-3681. PMLR, 2021.
[16] Gilman, Michele F. Poverty lawgorithms: poverty lawyer's guide to fighting automated decision-making harms on low-income communitics. Data Society, 2020.
[17] Gleixner, Ambros, Gregor Hendel, Gerald Gamrath, Tobias Achterberg, Michael Bastubbe, Timo Berthold, Philipp Christophel, Kati Jarck, Thorsten Koch, Jeff Linderoth, et al. Miplib 2017: data-driven compilation of the 6th mixed-integer programming library. Mathematical Programming Computation, 13(3):443 490, 2021.
[18] Guo, Hangzhi, Feiran Jia, Jinghui Chen, Anna Squicciarini, and Amulya Yadav. Rocoursenet: Dis- tributionally robust training of a prediction aware recourse model. arXiv preprint urXiv:2206.00700 2022.
[19] Hardt, Moritz, Nimrod Megiddo, Christos Papadimitriou, and Mary Wootters. Strategic classification. In Proceedings of the 2016 ACM Conference Innovations in Theoretical Computer Science, pages 111-122. ACM, 2016.
[20] Hardt, Moritz, Eric Mazumdar, Celestine Mendler- Dünnner, and Tijana Zmic. Algorithmic collective action in machine learning. arXiv preprint urXiv:2302.04266 2023.
[21] Harris, Keegan, Hoda Heidari, and Steven Z Wu. Stateful strategic regression. Advances in Neural Information Processing Systems, 34:28728 28741, 2021.
[22] Haris,, Keegan, Valerie Chen, Joon Kim, Ameet Talwalkar, Hoda Heidari, and Steven Z Wu. Bayesian persuasion for algorithmic recourse. Advances in Neural Information Processing Systems, 15:11131-1114, 2022.
[23] Hein, Matthias and Maksym Andriushchenko. Formal guarantees on the robustness a classifier against adversarial manipulation. In NIPS, 2017.
[24] Hurley, Mikella and Julius Adebayo. Credit scoring in the of big data. Yale JL Tech., 18:148 2016.
[25] Jurgovsky, Johannes, Michael Granitzer, Konstantin Ziegler, Sylvie Calabretto, Pierre-Edouard Portier, Liyun He-Guelton, and Olivier Caelen. Sequence classification for credit-card fraud detection. Expert Systems with Applicationss 100:234-245, 2018.
[26] Kaggle. Give Me Some Credit. http://www. www.w.a.gl...mm wwtpk/ae....//./eeeeeeeeeeeeeeee wwtpc/////iveeeeeeeeeeeeeeiiiiie 2011.
[27] Kantchelian, Alex, J. D. Tygar, and Anthony D. Joseph. Evasion and hardening of tree ensemble classifiers. In ICMI, 2016.
11

---

[28] Karimi, Kmss-nnssein, Julius Von Kügelgen, Bernhard Schölkopf, and Isabel Valera. Algorithmic recourse under imperfect causal knowledge: a probabilistic approach. Advances in neural information processing systems, 33:265-277, 2020.
[29] Karimi, Amir-Hossein, Gilles Barthe, Bernhard Schölkopf, and Isabel Valera. A survey of algorithmic recourse: definitions, formulations, solutions, and prospects. 2021.
[30] Karimi, Amir-Hossein, Berhhard Schölkopf, and Isabel Valera. Algorithmic recourse: from counterfactual explanations to interventions. In Proceedings of the 2021 ACM Conference on Fairness, Accountability, and Transparency, pages 353-362, 2021.
[31] Kireev, Klim, Bogdan Kulynych, and Carmela Troncoso. Adversarial robustness for tabular data through cost and utility awareness. In Network and Distributed System Security (NDSS) Symposium, 2023.
[32] Kleinberg, Jon and Manish Raghavan. How Do Classifiers Induce Agents To Invest Effort Strategically? July 2018.
ArXiv e-prints, art.
[33] Kleinberg, Jon and Manish Raghavan. How do classifiers induce agents to invest effort strategically? ACM Transactions on Economics and Computation (TEAC), 8(4):1-23 22, 2020.
[34] König, Gunnar, Timo Freiesleben, and Moritz Grosse-Wentrup Improvement-focused causal recourse (ICR). arXiv preprint arXiv:2210.15700 2022.
[35] Kügelgen, Julius von, Schölkopf. On the faimess of causal algorithmic recourse. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pages 9584-9594, 2022.
Karimi, Umang Bhatt, Isabel Valera, Adrian Weller, and Bernhard
[36] Lakkaraju, Himabindu, Jon Kleinberg, Jure Leskovec, Jens Ludwig, and Sendhil Mullainathan. The selec- tive labels problem: Evaluating algorithmic predictions in the presence of unobservahles. In Proceedings of the ACM SIGKDD International Conference Knowledge Discovery and Data Mining, pages 275-284,
2017.
[37] Laugel, Thibault, Adulam Jeyasothy, Marie-Jcanne Lesot, Christophe Marsala, and Marcin De- tyniecki. Achieving diversity in counterfactual explanations: review and discussion. arXiv preprint arXiv:2305.05844 2023.
[38] Levanon, Sagi and Nir Rosenfeld. Strategic classification made practical. In International Conference on Machine Learning, pages 6253. PMIR, 2021.
[39] Lowd, Daniel and Christopher Meek. Adversarial learning. In ACM SIGKDD international conference on Knowledge discovery data mining, pages 641-647, 2005.
[40] Mahajan, Divyat, Chenhao Tan, and Amit Sharma. Preserving causal constraints in counterfactual explanations for machine learning classifiers. arXiv preprint 1rxiv:112.003277. 2019.
[41] Makar, Maggie, Ben Packer, Dan Moldovan, Davis Blalock, Yoni Halpem, and Alexander D' Amour. Causally motivated shortcut removal using auxiliary labels. In International Conference Artificial Intelligence and Statistics, pages 739-766. PMLR, 2022.
[42] Mathov, Yael, Eden Levy, Ziv Katzir, Asaf Shabtai, and Yuval Elovici. Not all datasets born equal: On heterogeneous tabular data and adversarial examples. Knowledge-Basee Systems, 242:108377, 2022.
[43] Miller, John, Smitha Milli, and Moritz Hardt. Strategic classification is causal modeling disguise. In International Conference on Machine Learning, pages 6917-6926. PMLR, 2020.
[44] Milli, Smitha, John Miller, Anca D Dragan, and Moritz Hardt. The social cost of strategic classification. In Proceedings the Conference on Fairness, Accountabiliry, and Transparency, pages 230 2002299,920 2019.
[45] Mothilal, Ramaravind K. Amit Sharma, and Chenhao Tan. Explaining machine learning classifiers through diverse counterfactual explanations. In Pruceedings of the 2020 conference on fairness, accountability. and transparency. pages 607-617, 2020.
[46] Nguyen, Duy, Ngoc Bui, and Viet Anh Nguyen. Feasible recourse plan via diverse interpolation. In International Conference Artificial Intelligence and Statistics, pages 4679-4698, PMLR, 2023.
[47] O' O'Brien, Andrew and Edward Kim. Toward multi-agent algorithmic recourse: Challenges from game- theoretic perspective. In The International FLAIRS Conference Proceedings, volume 35, 2022.
12

---

[48] Parmentier, Axel Thibaut Vidal. Optimal counterfactual explanations in tree ensembles. International Conference on Machine Learning, pages 8422-8431. PMLR, 2021.
[49] Pawelczyk, Martin, Teresa Datta, Johannes Heuvelvan-den Gjergji Kasneci, and Himabindu Lakkaraju. Algorithmic recourse in the face of noisy human responses. arXiv preprint arXiv:2203.0777 2022.
[50] Quinzan. Francesco, Cecilia Casolo, Krikamol Muandet, Niki Kilbertus, and Yueen Luo. Learning counterfactually invariant predictors. arXiv preprint arXiv:2207.09766 097668 2022.
[51] Raghavan, Manish, Solon Barocas, Jon Kleinberg, and Karen Levy. Mitigating bias in algorithmic hiring: Evaluating claims and practices. In Proceedings of the 2020 conference on fairness, accountability, and transparency, pages 469 481, 2020.
[52] Rawal, Kaivalya, Eee Kamar, and Himabindu Lakkaraju. Algorithmic recourse in the wild: Understanding the impact of data and model shifts, arXiv preprint arXiv:20/2.11788, 2020.
[53] Sandholm, Tuomas and Robert Shields. Nogood learning for mixed integer programming. In Workshop on Hybrid Methods and Branching Rules in Combinatorial Optimization, Montréal, volume 20, pages 21 22, 2006.
[54] Shavit, Yonadav, Benjamin Edelman, and Brian Axelrod. Causal strategic linear regression. In Iniernational Conference Machine Learning, pages 8676 8686. PMLR, 2020.
[55] Tjeng, Vincent and Russ Tedrake. Verifying neural networks with mixed integer programming. In ICLR. 2019.
[56] Upadhyay, Sohini, Shalmali Joshi, and Himabindu Lakkaraju. Towards robust and reliable algorithmic recourse. arXiv preprint arXiv:2 13620, 2021.
[57] Ustun, Berk, Alexander Spangher, and Yang Liu. Actionable recourse in linear classification. pages 10-19, 2019. doi: 10.1145/2885500.2285555
[58] Veitch, Victor, Alexander D' Amour, Steve Yadlowsky, and Jacob Eisenstein. Counterfactual invariance spurious correlations: Why and how to pass stress tests. arXiv preprint arXiv:2106.00544 2021.
[59] Venkatasabrammanian, Suresh and Mark Alfano. The philosophical basis algorithmic recourse. In Proceedings of the 2020 Conference on Fairness, Accountability, and Transparency, pages 284-293, 2020.
[60] Vos. Daniël and Sieco Verwer. Efficient training of robust decision trees against adversarial examples. In Meila, Marina and Tong Zhang, editors, ICML, 2021.
[61] Wachter, Sandra, Brent Mittelstadt, and Chris Russell. Counterfactual explanations without opening the black box: Automated decisions and the GDPR. 2017.
[62] Wang, Zijie J, Jennifer Wortman Vaughan, Rich Caruana, and Duen Horng Chau. Gam coach: Towards interactive and user-centered algorithmic recourse. In Proceedings of the 2023 CHI Conference on Human Factors in Computing Systems, pages 1-20, 2023.
[63] Wei, Dennis. Decision Decision-making making under selective labels: Optimal mnite-domain policies and beyond. In International Conference on Machine Learning, pages 11035 11046. PMLR, 2021.
[64] Wilhelm, Colin. Big data and credit gap. 07/big-datee daaii--dtt--rreiit tappp-tt------e- gap- 800630, February 2018.
[65] Wolsey, Laurence A. Integer programming. John Wiley & Sons, 2020.
[66]
Wykstra, Stephanie. Govermmen's 's Use of Algorithm Serves False Fraud Charges. Undark, 6 January, 2020.
13

---

A PROOF OF THEOREM 4
Theorem 4. Suppose we have dataset of labeled examples D = {( voll=.
Every model
fi X y can provide recourse to a if:
FNR(F)
< n
1
Σ
1 E R y4
+1]
(5)
1=
where FNR(F) := = + =ff y +1] is the false negative rate of f D and where n* is number of positive examples in D, and R C RA(x) is any subset of the reachable set.
=
Proof. The proof is based on an application of the pigeonhole principle over the set of positive examples S fæx y: +1, [n]]. Given classifier f. denote the number of true positive and false negative predictions over St as:
TP()) : -1)0))
FN() -1) +1].
Consider region of feature space C (x) for which the number of correct positive predictions exceeds the number of positive examples outside R so that:
TP()) > nt - 1s n.
In this case, the pigeonhole principle ensures that the classifier f must assign correct prediction least one of the positive examples in R i.e., there exists point x' E S n R such that f(x') = yi = +1. Given C (x),, we have that a E (x Thus, we can reach x from by performing the action f(x + a) = +1.
x' x i.e. we can change the prediction from f(x) to
We recover the condition in the statement of the Theorem follows:
TP(f) n+ - SS n R
(6)
FN(J) SS 0 R).
(7)
FNR(f)
< n =11
1
Σ
1sx ERAA==
(8)
n+ FN(F), and (8) divides both sides by + The result follows by applying the definition of the false negative rate.
Here, Eqn. (7) uses the fact that TP())

---

B REACHABLE SET GENERATION
In this section, we describe how to formulate the optimization problems in Section 3 as mixed- integer programs. We start by presenting a MIP formulation for the optimization problem we solve in the FindAction(z;, A(x)) and IsReachable(z; x', A(x)) routines. Next, we describe how this formulation can be extended to the complex actionability constraints in Table 1.
B.1
MIP FORMULATIONS
Given a point æ E X, an action set A(æ), and a set of previous optima A we can formulate FindAction(ar, A(x)) the following mixed-integer program:
Σ
min
+ 4j
JE
s.t.
0j 2 a)
j E [d]
positive component of a;
(9a)
0j 2 aj
j E [d]
negative component of a distance from prior actions any tolution Ewis away from Oaj
(9b)
0j = aiSk + 87 6,
[d], ag E A
(9c)
mmin Σ (0)t + 67,)
ag 1
(9d)
JE(d
6/ < Mt Ug.
j E [d], as E A
0
(9c)
6,6 S M, Ug.h)
j E [d], a E A
SJ. > M. =
(9f)
0y E (xx)))
J [4]
separabie actionability construints on
(9g)
0 07 ER+
j [4]
absolute value of a;
(9h)
5, 07 E ER+
je [d]
signed distances from aj
(91)
UgAk E 1}
j E [4]
My.k 1 0]
(9j)
The formulation searches for an action in the set E A(x) by combining two kinds of constraints: (i) constraints restrict actions a A(x)) and (ii) constraints to rule out actions in
APP
The formulation encodes the separable constraints A(x) - i.e., a constraint that can be enforced for each feature. The formulation must be extended with additional variables and constraints to handle constraints as discussed in Appendix B.2. These constraints are handled through the aj E Ay (x) conditions in Constraint 9g. This constraint handle number of actionability constraints that can be passed solver when defining the variables aj. including bounds (e.g., 0g E [--x,, 10 - x,)), integrality (e.g., aj {0, 1) or aj (L Fj To Iz 1, 1,..., Fj }), and monotonicity (e.g.. aj 2 0 or aj I 0).
The formulation rules actions in oP through the "no good" constraints in Constraints (9c) to (9f). Here, Constraint (9d) ensures feasible actions from previous solutions by at least E We set to sufficiently small number min = 10-6 6 by default, but use larger values when working with discrete feature sets (e.g., Emin = for cases where every actionable feature is binary or vnteger-valued). Constraints (9c) and (9f) ensure that either 0f,,
or 67,x O. These are "Big-M constraints" where the Big-M parameters can be represent the largest value of signed distances. Given an action a E LB UB] we can set M = |a aj,k) and M, == 1a,,- - a
The formulation chooses each action in a E A(x)/ to minimize the In norm. We compute the L -oom component-wise as |ayl = az + +aj where the variables at and aj are set to the positive and negative components of |ay1 in Constraints (9a) and (9b). This choice of objective is meant to induce sparsity among the actions we recover by repeatedly solving Algorithm
MIP Formulation for IsReachable Given point X, action set A(æ), we can formulate the optimization problem for IsReachable(z. x', A(x)) as a special case of the MIP in (9) in which we x' Given that the objective function does not affect
set A and include the constraint the feasibility of the optimization problem, we can set the objective to I when solving the problem for IsReachabl.. In this case, any feasible solution would certify that xf is reachable from using
15

---

the actions in A(x). Thus, we can return IsReachable(z, x', a(=) if the MIP feasible and IsReachable(z,, æ', A(x)) = 0 if it is infeasible.
B.2 ENCODING ACTIONABILITY CONSTRAINTS
We describe how to extend the MIP formulation (9) to encode salient classes of actionability constraints. Our software includes an ActionSet API that allows practitioners specify these constraints across each MIP formulation.
Encoding Preservation for Categorical Attributes Many datasets contain subsets of features that reflect the underlying value of a categorical attribute. For example, we may encode categorical attribute with K categories such marital_status
(single, married, other} using a subset of K - 1 dummy variables such as married and single. In such cases, actions the dummy variables must obey non-separable actionability constraints to preserve the encoding - i.e., to ensure that person cannot be married and single at the same time.
We can enforce these conditions by adding the following constraints to the MIP Formulation (9):
L S Σ tay
(10)
JEJ
Here, J S [d] is the index set of features with encoding constraints, and L and U are lower and upper limits on the number of features in J that must hold to preserve an encoding.
Given standard one-hot encoding of a categorical variable with K categories, would contain the indices of K 1 dummy variables for the K - 1 categories other than the reference category. We would ensure that all actions preserve this encoding by setting L and
Implications and Deterministic Causal Effects Datasets often include features where actions one feature will induce changes in the values and actions for other features. For example, Table I, changing is_ _s_employed from FALSE TRUE would change the value of work_hrs_per_wer from to value 2 0.
We capture these conditions by adding variables and constraints that capture logical implications in action space. In the simplest case, these constraints would relate the values for a pair of features j' [d] through an if-then condition such "if aj 2 fy then a' = zy... In such cases, could capture this relationship by adding the following constraints to the MIP Formulation in (9):
Mu 2 a, 0 U/ +
(11)
M(1 - u) 2 0j aj
(12)
uyy aj'
(13)
{0.1}
The constraints shown above capture the "if-then" condition by introducing a binary variable u =
[ay vy]. The indicator is set through the Constraints (11) and (12) where M := a, By and
UB
= le If the implication is met, then ay is set to uy through Constraint (13). We apply this approach encode number of salient actionability constraints shown in Table by generalizing the constraint shown above to a setting where: (i) the "if" and "then" conditions to handle subsets of features, and (ii) the implications link actions mutable features to actions an immutable feature (i.e. so that actions on mutable feature years_ since_ ssinceelast_____eeeoeeeeeeeeaate last_appl ca ai will induce changes in an immutable feature age).
Generalized Reachability Constraints We end with a general-purpose solution to enforce arbitrary actionability constraints on discrete features. These constraints can be used, for example, to preserve a one-hot encoding of ordinal features (e.g., max_degree_BB and max_degree_MS or thermometer encoding (e.g..
wtt.iinccoeeeeeeeeee monthly_incomen _eq__k, mantthy_iicommegeaee
We can formulate custom reachability constraints for the relevant features J parameters:
[d] given two
1. Set of Viable Values: V, set of all values that can be assigned to the features in J.
16

---

Reachability Matrix: E {0, 1jkk a matrix where et, 1 [u is reachable from U/y] for all Vi, 0i E V.
Given these parameters, we constrain the reachability of features j E by adding the following constraints the MIP formulation in (9):
(14)
KEB
Σ
Uj.k
(15)
kEB
jj. S Ci,k
(16)
Uj {0.1]
Here, uy.k 1 l V indicates that choose action attain point ar' V. Constraint (14) defines the set of reachable points from i, while Constraint (14) ensures that only one such point can be selected. Here, & is 7th row of E' for point and 0j,k := x'j Tj the action on feature j to reach point x' V from point æ.
We show an example of how to formulate reachability constraints to preserve thermometer encoding Fig. 4.
E
0,
0
1,01,0,0
0
1,1,1
[,111
Figure 4: V denotes valid combinations of features. For these features, we wanted to produce actions that would reduce PetFFacttinn vrattioneeoovvnnnurr
for consumers. shows which points be reached. For example, [1, 1,0,0 0) represents point [0, O, 0) can be reached, and point [1, O, can reached, but other points can be reached.
17

---

C SUPPLEMENTAL MATERIAL FOR EXPERIMENTS
C.I ACTIONABILITY CONSTRAINTS FOR THE german DATASET
We show list of all features and their separable actionability constraints in Table
Name
Type
LB
UB
Actionability
Sign
Age
Z
19
75
No
Male
{0. 1
Single
{0, 1
0
1
No
ForeignWorker
{0,
No
YearsAtResidence
2
7
Yes
LiablePersons
2
No
Honting-Renter
{0. 13
1
Housing-Owner
{0, 1
1
No
Housing-
(0.
1
No
Job-Unskilled
{0. 1)
1
No
Job=Skilled
10.
1
No
Job=Management
{0.
YearsEmployed211
10, 1}
Yes
tre
(0. 13
No
2
(0.
No
10.
1
No
Credi 2re22to
(0.
LoanDuration
10.
1
No
LoanDuration212
(0
No
1onDDuration224
10.1)
No
3annDuration2:36
10.1)
1
No
LoanRate
4
HasGuarantoo
10.
1
Yes
LoanRequir www.euuuirerrrrrrrrr oed
10
No
LoanRequi or Educaation
{0.
No
LoanRequi or Car
10
No
LoanRequiredi redfoor
10.1)
NoCredi tHistory
{0.1]
No
Hi historyyfFLttePaymetts
(0
1
No
HistorryfDDeliiquency
{0.
HistoryyfFaakkLnntaalnenes
{0.
1
Yes
{0, 1}
Yes
CheckingAcct_exists
{0.
1
Yes
CheckingAcct20
{0.
I
Yes
SavingsAcct_ess
{0. 1}
1
Yes
2avingsAcct>>100 180
{0, 1}
1
Yes
Table 3: Separable actionability constraints for the german dataset.
The non-separable actionability constraints for this dataset include:
DirectionalLinkage: Actions on YearsAtResidence will induce to actions on ['Age']. Each unit change in YearsAtResiddes leads to:1.00-unit change in Age
2. DirectionalLinkage: Actions on YearsEmployed21 1 will induce to actions on ['Age'], Each unit change YearsEmployed21 leads to: 1o:1..0-unit change in Age
ThermommeterEncodding Actions on [CheckingAcctexis thermometer encoding of CheckingAcet, which can only increase. Actions can only turn on higher-level dummies that are off, where CheckingAccexxists the lowest-level dummy and CheckingAcct2@ is the highest-leeel-dummyy
CheckingAcct20] must preserve
ThermometerEncodding: Actions on [SavingsAcctexists, SavingsAcct 100] must preserve thermometer encoding of SavingsAcet., which only increase. Actions can only turn
18

---

higher-level dummies that are off, where SavingsAcctexists is the lowest-level dummy and SavingsAcct2100 100 is the highest-levl-dummny.
C.2 ACTIONABILITY CONSTRAINTS FOR THE heloc DATASET
We show list of all features and their separable actionability constraints in Table 4.
Name
Type
Actionability
Sign
ExternalRi 4
{0. 1]
0
No
SiternaaRiskEstimmtteee
{0. 1)
0
No
ExternalRi SxternalRisKEstimateedd. skEstimate260
{0.
0
No
ExternaIRi Sk
[)
Externa]Rissfsstimnteer
[0.1) 1]
Years@Ffcccunttiisttryy
Z
AvgYearsInFile22
[0.1)
Yes
AvgYearsInfile25
1]
Yes
AvgYearsInFile27
10 O
Yes
WestRecentTTaadeettttinn..tsttt
{0, O
Yes
MsstieeettrradeWtthinnattttt
(0. O
Yes
AnyDerogatoryComment
00. 1)
AnyTrade
(0
AnyTrade90DaysDet
10
Any Trade680ayyDee
(0.
Any TayTre3880ayDDl
0.
NoDel NaDel gEver
00 1) O
No
Year'S Lenneiiaatteeelrrraaaaeeeee
00. 1) O
Yes
Years wwwssseaasteeeerrraaeeeeeo
0, O
Yes
YearssSineelastteeegTraaaad
00. 1)
Yes
NunInstallTrades:
00 1
Yes
NuninssaallTraddeMeaaaemeeee
00. 1]
Yes
NunkevolviinTTradee222
(0. 1)
00.
Yes
NunInstallTTadees233
(0. 1)
Yes
NuninstaallrradeeMBaaaneeee
(0, 1) O
Yes
NumRevolliingTrrdde53]
(0. 1) O
Yes
NumfevalwiinTrrddeeeaammmmeee
(0, O
Yes
NumirsstallTTaades2555
00. 1)
Yes
NutinstalllradeeeMBaaaneeees
(0.
Yes
Nunkewolvinn Tradee5555
[0. 1]
Nuffeve_\iinggrradeessssmmmeee2
{0,
Yes
NumLnstallIrades227
00.
Yes
Nunnnnstallrrradesseeameeeee
00, 0
Yes
NumRevolliingTrrdee227
[0. 0
Yes
(0. 1) 0
Yes
aetFracttioninstaallBurdeeeee
(0.1) 0
Yes
WetFracttioninnttallBBurre22222
(0.1)
Yes
seefracttioninstallBBurree233
[0.1]
Netrraattoonevooviinnaardeeeee2e
(0.1)
Yes
Nettraactioneevllvvnggdddeeeeee
(0.1)
Yes
NetFracctionevvoliingaarrrnn::
(0.
Yes
(0. 0
Yes
Table 4: Separable actionability constraints for the heloc dataset.
The non-separable actionability constraints for this dataset include:
DirectionalLinkage: Actions NumRevol TiteevooviinTTraeeelllaaaaeee will induce actions NuuneeoovvinTTrreesss Each unit change in NunRevooliinnTrrassWlaaaaeee leads to: 1.00-unit change in NumRevolvingTrraes>>
DirectionalLinnage: Actions Tun.nsttalITrddesWaalll...
will induce actions Each unit change in NumlnsttallIrraddsWalaaaeee leads to: 1.00-
unit change in NumInstallTrades2.
3. DirectionalLinkage: Actions NumRevol annievoooovingTrreeeeeaaaaeee will induce actions ('NumRevolving Tradoesss3nnrrr 3']]. Each unit change in NumeewoloiingTTradeeWB....m..m leads to:
1.00-unit change in NunRevolvingTradess>
19

---

DirectionallLinkage: Actions on NunthsstallTraaesiWallanee- will induce actions on [NumIInstallTrades225 Each unit change in Nuntnsttallrraddeeibblaaaaee leads to: 1.00- unit change NumInstallTrades23
Directionallinkkge:: Actions on NumRevol ia will induce actions on MivmRevolvinngTrdeee
Each unit change in lunRevoll.inngrrrddslllaaaeeee leads to: 1.00-unit change in NunrevolvingTTrades>>
6. Directionall Linettoonall.inagee Actions NunInstal "VNmInnstalITrrdess..
will induce actions Each unit change in NumtnsstallrraddesWiBllemeee>> leads to: 1.00- unit change NumInstallTrades25
7. Directionall Linkag:: Actions NumRevol uumnevooo.innggraeeeemmmmamm>/ will induce actions "NumRevolvingTrraes222 Each unit change in Numeevollvingrrrdsllllaneeee leads to: 1.00-unit change in NumRevolvingTrades
8. DirectionalLinkage:: Actions Num.InstallTraddeeBBlaancce will induce to actions on
"NumLnstallITrade22]]] Each unit change in NuninstaallrrodeeeBBBllmmee>> leads to: 1.00- unit change in NumInstallTrades2>
9. DirectionalLinkagge Actions on VerrsinnceLatttellTrrde::1 will induce to actions on ("MerssFFccouuntisstoyy Each unit change Yerrsänneelastlolggrradeee leads to: 1.00-umit change in YearsofAccounttiistory
10. DirectionalLinnage. Actions on VerrsinneeLasDDellrrreess will induce to actions on "YeerrsfFAcoounttisstt 3.0 3.00-unit change in Years@fAccountHistory
Each unit change Yerrsinnellatteeeggrradeee leads to:
11. DirectionalLLnkage: Actions on YearsSinceeattteellrrrddee will induce to actions on ["YearsoFAccountttistoroo Each unit change Yearssiineelasteelllraadsss leads 5.00-unit change in YearssfFAcountHisste
12. ReachabilityConstrain:: The values of [MostRecentTradeNi Thaereenttradeeitthinatsttttet conditions.
must belong one of 4 values with custom reachability
13. ThermommtterFncoding::
Actions on PearsiinceLastteellTaaae must preserve thermometer encoding of DesSSnnneLaaDeelTrrdeelllll which can only decrease. Actions can only turn off higher-level dummies that are on, where aarssinceL.attellgTee.. dummy and YearsSinceLastDer tDee is the highest--evel--uummy
is the lowest-level
14. ThermoomtterEncodingg:
Actions on [AvgYearsInfiles
AvgYearsInfile25
AvgYearsInfiles must preserve thermometer encoding of AvgYearsinFilegeq.. which can only increase. Actions can only turn on higher-level dummies that are off, where AvgYear sInf is the lowest-level dummy and AvgYearsInf WwveerrIIIFlee>. iile77 is the highest-level-dummyy
3 ile>3
15. ThermomeeteEEncoding:
[eetrractionneeoovvingurrrrr nefFractiooRvolliingurre----- must preserve can only turn off higher-level dummies that are on, where which only decrease. Actions the lowest-level dummy and NetFractionia ittaraatiiiieeelinnnnndeeeeeeee
Actions
thermometer encoding of ReeFraationRevolvinggBrrec
is the highest-level-dummy,
16. ThermommtteEEncoding::
NetFractionInstallle 1Budden22 NetFracctionInstalllrrrdnn MetfrractoonnsttallBrreee' must preserve ther- mometer encoding of DetFraatioonnntallBureeeee which only decrease. Actions only turn off higher-level dummies that are on, where NetFractionIns deeFraaciionInntalllurreee 10 is the lowest-level dummy and
Actions
Burden20 is the highest-leee-ddummy,
17. ThermoometerEncooding:
|Nineevolwiingrradessssslaaa222 Nuureevdlwiingrraddessvmmmmeee must preserve thermometer encoding of NumRe- AeivingTrraesWii Waaaaddeeaaaaaagggg,grrr which can only decrease. Actions can only turn off higher-level dummies that are on, where NumRevolving
Actions
NumReevolviinnrrrddeeeBaaaaeeeee
MuuReevolvinggrradesWaaaaaac
the lowest-level dummy and
SummeevolwinggrrdesssBaaa.am 7 is the highest-level-dume
18. ThermometerEEncoding: Actions on [NumRevolvingTradess KumRevolvingTraadesZ NumRevolvingTrades>> must preserve thermometer encoding of
NumRevolvingTraades23
20

---

on VunnaeegnngZTTaeeegg, which can only decrease. level dummies that are on, where cnnneeoolinnTTrdee. is the lowest-level dummy and NumRevolvingTradess27 the highest-leve--ummmy
Actions can only tur off higher-
19. ThermoomtterEncoding::
IumntnstallITraddesllllaeees NumlrstaallTraddssWBlllaanm NunnInsstalTTrradeeaaalaanee?] must preserve thermometer encoding of Numinstall- TradesW Balancegeq, which can only decrease. Actions can only turn off higher-level dummies that are on, where NumInstall TammnntttllTrddeeBBaaaaaccc
Actions
on
NumInstall NumlnnssaalTTrrdeeeMBaaaanee2>
is the lowest-level dummy and the highest-level-dummyy
20. ThermommtterFncoding:: Actions on [NumInstalITrade5222 NumInstallTrades23 NumInstallTrraes221 must preserve thermometer encoding of Numinstal/Tradesgoo,, which can only decrease. Actions can only turn off higher-level dummies that are on, where NumInstall arrsstalllrrde>>> is the lowest-level dummy and mmmInstallTraes>> is the highest-level-dumet -ummy.
NumInstallTrades
C.3 ACTIONABILITY CONSTRAINTS FOR THE givemecredit DATASET
We present a list of all features and their separable actionability constraints in Table 5.
Name
Type
LB
UB
Actionability
Sign
24
{0,
No
Age_bt__25 2tt__2__to_333
{0,
No
_ge_bt_30_too55
{0,
No
Age260
(0.1)
1
No
NumberOFfDependents.
10.1)
No
NumberrOfDependnnts-1
{0,
No
NumterrOrDependentss22
10, 13
No
NumberoffDependents26
10
No
DebtRatio21
00
MonthlyIncome:233K
0.
Yes
MonthlyyIncome255K
[0.
Yes
MonthlyyIncomee211k
(0.
Yes
Credi:liinet:llizziion21..
(0.
Yes
CredittLineltll122tt1m22....
{0. 1)
Yes
CredittLineuu11122tiom22...
{0.
Yes
CredittLinettlliiation27....
(0.
Yes
Credi::Liinett:llizattmm222211.
10
Yes
AnyRealEEttateLLaams
{0
Yes
NuIttiplefRelEEsttteL.ooom
{0,
Yes
AnyCreeditLinnssAdddccoms
(0.1)
Yes
hultiipleecreditiinneewwd...cco
(0.
Yes
HiittoryoLLttePayment
{0,
No
HistoryofDelinquency
[3
1
No
Table 5: Separable actionability constraints for the heloc dataset.
The non-separable actionability constraints for this dataset include:
1. Thermoometer/Enoodinn:: Actions
[MonthlyIncome2225] MonthlyInccome25K, MonthlyIncome22188 must preserve thermometer encoding of Monthlylcconeeeq, which only perease.Actions only where MonthlyIncome> is the lowest-level dummy and MonthlyIncome=:10 is the highest-ievel-dummyy
higher-level dummies that off,
ThermometterEhcoding::
Actions
[Crettitiinettlllzztitoo01... Credi CredittineUtiiizztionn. must preserve ther-
(reditLine/tilliztioon2222 CreditLinettiiizatiin mometer encoding of Creditl.ieUUtiiization which only decrease. Actions only turn
21

---

off higher-level dummies that are on, where CreddtiiinUillizztionn2.1. is the lowest-level
dummy and Credi tL ietttiiiiaaiion21 0 is the highest-level-dummny
Thermometer/Encoding: Actions on [AnyRealEstateLLonns, preserve thermometer encoding continuousattriiutte. which can only decrease. Actions can only turn off higher-level dummies that are on, where AnyRealEstateLLonss is the lowest-level the highext-level-dummyy
must
dummy and Mul www.eeeellttttee.ooooooo
4. ThermommeterFncodinng:
[AnyCredi tL iLinesAndL oans, Mul tipleCreddi wiipeerreiitiineeeee.. cLinesAndLoang must preserve thermometer encoding of continuossatribute.. which can only decrease. Actions can only turn off higher-level dummies that are on, where AnyCredi tL oass is the lowest-level dummy and Mult MultipleCredi tL ines is the leaeeest-eeel-dummy
Actions
C.4 RESULTS ON CLASSIFIER PERFORMANCE
In Table 6, we report the performance of models all datasets using all algorithms. We split each dataset into a training sample (80%, used for training and hyperparameter tuning) and a hold-out sample (20%, used to evaluate out-of-sample performance).
AUC
Error
Dataset
Model
Train
Test
Train
Test
heloc
LR
0.7723
0.7882
0.2774
0.2774
XGB
0.7721
0.7880
0.2783
0.2783
RF
0.8593
0.7853
0.2877
0.2877
german
LR
0,8193
0.7602
0.2350
0.2350
XGB
0.8191
0.7614
0.2300
0.2300
RF
0.9708
0.7937
0.2350
0.2350
givemecredit
0.8411
0.8441
0.2390
0.2390
XGB
0.8412
0.8442
0.2380
0.2380
RF
0.8752
0.7928
0.2619
0.2619
Table 6: Overview of model performance
C.5 RESULTS ON THE ILLUSION OF FEASIBILITY
We present the results of an ablation study show how recourse may appear to be feasible when fail to consider complex actionability constraints. Here, we repeat the experiments Section 4 for the heloc dataset over three classes of nested actionability constraints:
Simple, a separable action set which only includes constraints to conditions on the immutability, integrality, and soundness of features.
Separable, separable action set which includes all conditions in Simple and adds monotonicity constraints ensure that certain features can only increase decrease.
Actual, a non-separable action set which includes all conditions in Simple and Separable. Note that this corresponds to the action set that we use in main study.
We present the results from procedure for all three action sets in Table 7.
22

---

Actual
Separable
Simple
Model Type
Metrics
Reach
DiCE
DiCE
AR
DiCE
Certifies No Recourse
22.2%
Outputs Action
77.8%
85.9%
57.6%
85.9%
57.0%
99.9%
65.6%
LR
Loopholes
0.0%
41.1%
34.4%
41.1%
34.8%
95.5%
50.3%
Outputs No Action
22.2%
14.1%
42.4%
14.1%
43.0%
0.1%
34.4%
Blindspots
0.0%
0.0%
21.0%
0.0%
21.7%
0.0%
14.6%
Certifies No Recourse
22.3%
Outputs Action
77.7%
57.3%
57.5%
60.5%
XGB
Loopholes
0.0%
NA
42.1%
NA
42.0%
NA
46.7%
Outputs Action
22.3%
42.7%
42.5%
39.5%
4 Blindspots
0.0%
21.1%
21.1%
18.2%
Certifies No Recourse
31.3%
Outputs Action
68.7%
49.3%
49.3%
59.2%
RF
Loopholes
0.0%
NA
29.5%
NA
29.5%
NA
44.8%
Outputs No Action
31.3%
50.7%
50.7%
40.8%
Blindspots
0.0%
19.8%
19.7%
15.7%
Table 7: Feasibility of recourse across model classes, and various actionability constraints on the heloc dataset. We determine the ground-truth feasibility of recourse using reachable sets (Reach), and use these results to evaluate the reliability of verification with baseline methods for recourse provision (AR and DiCE). We describe the metries in the caption Table
23


Reviews:
[{"review_id": "m1Umq9nHHF", "reviewer": "Reviewer_fbZh", "summary": "The authors present a new idea, recourse verification, certifying if a predictive model guarantees actionable items for users to change the prediction outcome. Different from the typical algorithmic recourse problem where the goal is to find actionable items with minimum cost, this work aims at ensuring that users are not mistakenly precluded from recourse. In the paper, the authors first establish fundamental concepts and theorems for this new topic. Afterwards, they propose \"reachable set\" for enumerating plausible feature values after actions. With proper decomposition of feature space as the author propose, feasibility of recourse can be effectively tested. Finally, the authors conduct evaluations on real-world datasets and confirm the efficacy of verification.", "questions": "1. It is unclear how often does the undesired preclusion occur in practice. In particular, continuous features are quite common and may trivially avoid preclusion if the capacity of the predictive model is not constrained. Even if we focus on discrete features only, I am still not sure if undesired preclusion can frequently happen. Let us assume users A and B who pass and got rejected respectively by a predictive model. If we ignore the cost, an easy recourse for A can be the difference between A and B in the feature space. If there are more users getting approved by the model, more candidates of recourse are available for A's actions; namely, it is more unlikely that we find no proper recourse for user A when data size grows. If the diversity of the approved users is so limited that no recourse can be found for user A, I wonder if the preclusion is then more like intended (e.g., setting up strict rules) instead of being an accident.\n2. Following question 1, I am wondering if it is reasonable to adopt the idea of cost constraint in recourse provision to reduce the reachable set? For example, we certify if a model is not \"fixed\" given an upper bound of cost.\n3. How do we check the quality of a recourse verification algorithm? Specifically, if we employ two recourse verification methods and get inconsistent results, how do we decide which one is better?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "1. Recourse verification as a new research topic seems intriguing and impactful. It makes sense that some predictive models can accidentally limit availability of recourse and thereby hinder the fairness. Upon this important issue, the authors establish a good foundation for follow-up research and may also benefit researchers working on the typical algorithmic recourse problems.\n2. The proposed algorithms seem reasonable and the step of implementation is clear. Also, the effectiveness is verified in the experiments.\n3. The writing is overall clear and easy to follow. The details of experiments are provided. The limitations of this work are also adequately discussed.", "weaknesses": "Certain parts of the proposed method may still be in early stages of development, which may require further refinement to guarantee its practical value. For example, as discussed in the limitation section, the verification algorithm does not work on continuous features. More concerns of mine are summarized in the Questions section below.", "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": "", "extra_scores": {}}, {"review_id": "lRN5IsB1DH", "reviewer": "Reviewer_z4uU", "summary": "This work introduces the recourse verification: to verify if the prediction is desirable for any actions over the inputs, which is modeled as a formal verification problem given the trained model and input specifications. The paper gives examples using the proposed reachable sets.", "questions": "See weakness", "limitations": "", "rating": 5, "confidence": 2, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "- The idea of verification seems to be novel in the sense of recourse and the motivation is clear.\n- The formulation is easy to follow.", "weaknesses": "- My biggest concern lies in the lack of contribution in the verification methods, which directly follow the basic idea of formal verification but seem not to dive deeper into the optimization algorithms or target the specific challenge in the recourse setting.\n- When introducing reachable sets, more details are expected to be discussed, i.e. continuous or discrete, $\\ell_p$-norm bound ball. The verification seems to be sound but incomplete, and it is expected to be compared to more off-the-shelf reachibility-based verification methods in [1].\n- Although experiments show the prediction without recourse and current methods fail to detect them, there are no other baselines of recourse verification for the comparison of tightness and time efficiency. Also, the experiment part is not well organized in the sense of merging section 4 and 5 as experiments.\n\n[1] Liu, C., Arnon, T., Lazarus, C., Strong, C., Barrett, C., & Kochenderfer, M. J. (2021). Algorithms for verifying deep neural networks. *Foundations and Trends® in Optimization*, *4*(3-4), 244-404.", "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": "", "extra_scores": {}}, {"review_id": "OYknBUuTcl", "reviewer": "Reviewer_jEod", "summary": "This paper studies recourse verification of machine learning models. Recourse verification is an important aspect of algorithmic recourse, which seeks to identify models that assign predictions without any actionable recourse for the decision subject. Ensuring the existence of actionable recourse is essential in applications affecting people’s lives and livelihoods, such as job hiring, loan approvals, and welfare programs. A model that offers no recourse for its decisions may permanently exclude subjects from accessing these benefits without offering a path to eligibility. Existing research largely focuses on recourse provision — providing individuals with actionable recourse — but only a few works study the infeasibility of providing recourse.\n\nThis work proposes an approach for recourse verification under actionability constraints based on reachable sets. A reachable set is a collection of feature vectors that can be reached from a given input using a set of allowed actions. The proposed method certifies the existence or non-existence of recourses by querying the model on every point in the reachable set or an approximation of this set. If the method finds a subset of the reachable set that contains a recourse, it certifies the existence of recourse. Similarly, if it cannot find a recourse in a superset of the reachable set, it certifies the infeasibility of providing recourse. If it cannot certify either of the above, it abstains.", "questions": "1. Could this approach be extended to certify the existence or non-existence of an abundance of recourse options instead of just one? A single recourse option might not be feasible for everybody, and having multiple recourses could provide more options to people. It might be possible to certify statements like \"20% of the actions in the action set would lead to a positive outcome\" by querying a random subset of the action set.\n2. Different actions may have different costs for the subjects. For instance, it might be easier for a loan applicant to increase their credit score than their income. Could we incorporate costs for the actions and certify the existence of a low-cost recourse?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "1. The paper studies an important problem that has not been explored well in the literature. It makes a significant contribution in this area.\n2. The paper is well-written and easy to follow.\n3. It is claimed that the proposed method does not require any assumption on the prediction model. However, the model might need to satisfy some conditions for the decomposition approach, which is essential when the problem dimensionality is high. See the weaknesses section for more details.", "weaknesses": "1. The recourse verification process evaluates every point in the reachable set, which could be time-consuming if the problem dimensionality is high. The paper seeks to address this issue by a decomposition approach that partitions the action set using features that can be altered independently. However, this approach has not been explained well in the paper.\n2. It is unclear how the separable features are identified. What role does the prediction model play in the identification of these features?\n3. It is unclear what conditions the prediction model must satisfy for the features to be separable. For instance, the verification step may return an infeasibility certificate in partitions A_1(x) and A_2(x), but actionable recourses may still exist in the Cartesian product A_1(x) X A_2(x) of the two sets.\n\nMinor comments:\n1. Increasing the font size in Tables 1 and 2 could help improve readability.\n2. It seems like a word is missing in the following sentences:\n    1.  Pg. 1 — “In fraud detection and content moderation, for example, models should assign fixed [predictions?] to prevent malicious actors from…”\n    2. Pg. 3 — “We can elicit these constraints from users in natural language and convert them to expressions that can [be] embedded into an optimization problem.”\n3. Figure 3 is a bit confusing and could be made clearer. The x-axis has no label. It seems that the size of the reachable set *grows* rapidly under the decomposition approach compared to brute force, which is contrary to the text. If I understand correctly, the purpose of using decomposition is to reduce the number of points to verify.", "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": "", "extra_scores": {}}, {"review_id": "3hs7aeN0Am", "reviewer": "Reviewer_2QxH", "summary": "This paper introduces the \"recourse verification\" task, aimed at identifying models that assign fixed predictions, and proposes methods to assess whether a model can provide actionable recourses based on reachable sets.", "questions": "- The optimization problem (2) aims to optimize a constant value of 1. What does this objective imply? Does this optimization problem solely seek to find all feasible actions (feasible recourses)?\n- Is there a relationship between two reachable sets? For instance, if $x_1$ is within the reachable set of $x$ and $x_2$ is within the reachable set of $x_1$, is it guaranteed that $x_2$ is also within the reachable set of $x$?\n\n**References**:\n\n[1] Nguyen, Duy, Ngoc Bui, and Viet Anh Nguyen. \"Feasible Recourse Plan via Diverse Interpolation.\" International Conference on Artificial Intelligence and Statistics, 2023.\n\n[2] Rafael Poyiadzi, Kacper Sokol, Raul Santos-Rodriguez, Tijl De Bie, and Peter Flach. Face: Feasible and Actionable counterfactual explanations. In Proceedings of the AAAI/ACM Conference on AI, Ethics, and Society, 2020.", "limitations": "", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 4, "contribution": 2, "strengths": "- The paper is well-written and easy to follow.\n- The motivation and justification for fixed points and regions are sound.\n- The experiments demonstrate an improvement in the feasibility of recourse across published datasets.", "weaknesses": "Weaknesses:\n- I am unsure about the paper's significant contribution. The primary focus appears to be on describing a search algorithm to confirm the existence of a feasible action for a user. \n- My major concern regarding this paper is its inapplicability to continuous features, as claimed by the authors. Is it possible to extend the MIP formulation to MILP formulation to incorporate continuous features?\n- The paper compares the proposed method to two conventional baselines in terms of improving recourse feasibility. Recently, there have been some papers potentially improving feasibility, such as [1] and [2]. I suggest comparing with them.", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (spotlight)