Understanding Fixed Predictions via Confined Regions
Authors: Connor Lawless
Tsui-Wei Weng
Berk Ustun
Madeleine Udell
Venue: ICML 2025 poster (2025)
Keywords: algorithmic recourse
explainability
interpretability
trustworthy ML
discrete optimization
Primary area: social_aspects->accountability_transparency_and_interpretability

Abstract: Machine learning models can assign fixed predictions that preclude individuals from changing their outcome. Existing approaches to audit fixed predictions do so on a pointwise basis, which requires access to an existing dataset of individuals and may fail to anticipate fixed predictions in out-of-sample data. This work presents a new paradigm to identify fixed predictions by finding confined regions of the feature space in which all individuals receive fixed predictions. This paradigm enables the certification of recourse for out-of-sample data, works in settings without representative datasets, and provides interpretable descriptions of individuals with fixed predictions. We develop a fast method to discover confined regions for linear classifiers using mixed-integer quadratically constrained programming. We conduct a comprehensive empirical study of confined regions across diverse applications. Our results highlight that existing pointwise verification methods fail to anticipate future individuals with fixed predictions, while our method both identifies them and provides an interpretable description.

Understanding Fixed Predictions via Confined Regions
Connor Lawless
Tsui- Weng" Berk Ustun? 2 Madeleine Udell
Abstract
hiring, fixed predictions may preclude individuals from ac- cess to credit and employment. In content moderation, fixed prediction can ensure that malicious actors are unable to evade detection by manipulating their features. There has been little work that mentions this effect, let alone studies it. Yet fixed predictions arise in practice. Recently, predictive model used to allocate livers in the United Kingdom was found preclude all young patients no matter how ill from receiving liver transplant (Murgia, 2023).
Machine learning models can assign fixed pre- dictions that preclude individuals from changing their outcome. Existing approaches to audit fixed predictions do so on a pointwise basis, which requires access to an existing dataset of individ- uals and may fail to anticipate fixed predictions in out-of-sample data. This work presents new paradigm to identify fixed predictions by finding confined regions of the feature space in which all individuals receive fixed predictions. This paradigm enables the certification of recourse for out-of-sample data, works in settings without rep- resentative datasets, and provides interpretable descriptions of individuals with fixed predictions. We develop a fast method to discover confined regions for linear classifiers using mixed-integer quadratically constrained programming. We con- duct a comprehensive empirical study of confined regions across diverse applications. Our results highlight that existing pointwise verification meth- ods fail to anticipate future individuals with fixed predictions, while our method both identifies them and provides an interpretable description.
Existing approaches to check model responsiveness (see Kothari et al., 2023) work by verifying recourse on an sudividual-by-idiivddae basis. These pointwise approaches can only verify recourse for available data, and do not pro- vide guarantees on model responsiveness out-of-sample. In practice, this means that critical issues can only be identi- fied after model has been deployed and it is too late to prevent harms. Moreover, in some settings there may be no data available to run these pointwise procedures due to privacy or because the model is being deployed on a new population. For instance, many interpretable medical and criminal justice scoring systems are available publicly (see e.g., Morrison al., 2022: Yamga al., 2023; Ribeiro Ju- nior et al., 2023; of Pennsylvania, 2025), but gaining access to representative dataset is difficult due to privacy con- cerns. Without available data, pointwise approaches can only be used after generating synthetic data that may not be representative of the entire population or feature space, Finally, even when individuals without recourse can be iden- tified, can be hard to determine the root cause of these fixed predictions (Rawal al., 2020).
1. Introduction
Machine learning is increasingly used in high-stakes set- tings to decide who receives a loan (Hurley & Adebayo, 2016), a job interview (Bogen & Rieke, 2018), or an organ transplant (Murgia, 2023). Models predict outcomes using features about individuals, without considering how indi- viduals can change them (Liu et al., 2024). Consequently, models may assign an individual a fixed prediction which is not responsive to their actions.
This work studies new paradigm in algorithmic recourse that characterizes fixed predictions by verifying recourse over an entire region of the feature space (e.g., all plausi- ble job applicants). In contrast to existing pointwise ap- proaches, auditing regions of the feature space can identify confined regions (i.e., where all individuals are assigned fixed prediction), or provide formal certification of model responsiveness over the entire region. This approach is robust to distribution shifts, can be used without the need for available datasets or synthetic data generation, and pro- vides an interpretable description of individuals with fixed predictions.
The responsiveness of a model is integral to its safety in settings where predictions map to people. In lending and
'Stanford University University of Califoria, San Diego Corre- spondence to: Connor Lawless
Proceedings of the 1nnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).
Verifying recourse for a single individual is a non-trivial

---

Understanding Fixed Predictions via Confined Regions
Classifier
Feature Space (2) All poesible feature vectors
0 S +1 < 20 22 E {0, 1}
22
f(1 22)
I[21 102g> 20]
X = 2j x 23 = 20) x {0, 13
Confined Region (S)
1-
A subant of region where Individuals receive fixed predictions for the classiller
0 σ - 10 22 E {0, 1}
Desirable Outcome
Region of Interest (R)
S(f.
æ1 X d2
[0,5] x {0)
aubhstt feature space
R= x1 X 222 = 10] x 1]
Fixed Prediction
0
0
T
5
Universal Action Set (A)
05 ~ 01 < 15
and
20 I1
of constraints that feasible actions for individual.
02 = 0
10
32 0
Figure 1. Stylized recourse verification problem that aims find all individuals that are assigned fixed prediction under a given classifier. The feature space (1) defines all possible feature vectors x. The region of interest (2) is subset of the feature space representing individuals on which to audit recourse. The action set (3) defines set of constraints on what actions a individuals can take to change their prediction under classifier (4). A confined region (5) is subset of the region of interest in which all individuals are assigned a fixed prediction, which depends on both the classifier and the action set. In this example, a single confined regions provides an interpretable characterization of all individuals that receive fixed prediction.
combinatorial problem that requires performing exhaustive search over a subset of the feature space that captures both the model as well as actionability constraints (Ustun et al., 2019; Kothari et al., 2023). Characterizing all fixed predic- tions represents an even more intensive setting that requires searching over any plausible individual. Despite these chal- lenges, we develop a fast method to find confined regions by Mixed-Integer Quadratically Constrained Programming (MIQCP) to audit linear classifiers. The main contributions of this work include:
Related Work Our work introduces new direction for algorithmic recourse (also known as counterfactual explana- tions) (Venkatasubramaaninn & Alfano, 2020; Karimi et al., 2020b). We build on a line of work that has focused on generating actionable recourse under hard constraints on what actions can be made (Ustun et al., 2019; Russell, 2019; Mahajan et al., 2019; Mothilal et al., 2020; Kanamori et al., 2021; Karimi et al., 2020a). Recent work has highlighted that under inherent actionability constraints, ML models may assign fixed predictions that preclude access for individ- uals (Kothari et al., 2023; Camminguzz-Olmed et al., 2022: Karimi et al., 2021). While these works have highlighted the problem of fixed predictions, no existing work has at- tempted characterize regions in which this phenomenon occurs for given classifier.
1. We introduce new approach to formally verify recourse for linear classifiers over entire regions of the feature space. This tool can be used certify the responsiveness of classifiers beyond data present in a training dataset and can provide stronger guarantees for out-of-sample data. We also present tools find (or enumerate all) confined regions in the feature space, providing an intuitive tool for model developers to audit and correct problems with model responsiveness.
Most of the existing work on algorithmic recourse has fo- cused on providing or verifying recourse for individuals. These approaches fail to provide a high level understanding of recourse (i.e., what actions are needed for what types of individuals) which can be used by stakeholders to inter- pret and calibrate their trust in the underlying ML model. Motivated by this shortcoming, recent work has studied the problem of generating a global summary of recourse via either mapping individuals to a fixed number of pos- sible actions (Lodi & Kamírez-Ayerbe, 2024; Ley et al., 2023; Warren et al., 2024), limiting the number of features that can be used in recourse across all instances (Carrizosa et al., 2024), or providing an interpretable summary of po- tential recourse options for different rub-groups (Rawal & Lakkaraju, 2020). Our work is fundamentally different from these approaches in that we aim to find and characterize confined regions (i.e., interpretable regions in the feature population without recourse) instcad of global actions (i.c., interpretable regions in the action space). Our approach also
2. We develop fast methods that are able to find confined re- gions via MIQCP. Our approach handles a broad class of actionability constraints, and can verify recourse within seconds on real-world datasets.
3. We evaluate our approach on applications in consumer finance. content moderation, and criminal justice. Our results show that pointwise verification approaches fail to verify model responsiveness over regions, emphasizing the need for tools that audit recourse beyond individual data points. We also showcase the ability of our approach to audit model responsiveness in settings with no public datasets via a case-study on the Pennsylvania criminal justice sentencing risk assessment instrument.
2

---

Understanding Fixed Predictions via Confined Regions
formally certifies recourse over an entire region, whereas existing approaches provide no out-of-sample guarantees.
We say an individual receives fixed prediction under a classifier f and action set A if Recourse(x, J, A) 0. and has recourse if |Recourse(x] f, A)] 2 1
More broadly, our work builds on line of research that has focused on algorithmic recourse as tool to safeguard access in applications such as hiring and lending. Towards this aim, other work has studied how to generate recourse that is robust model updates (Upadhyay et al., 2021; Forel et al., 2024), distributional shifts (Altmeyer et al., 2023; Guo et al., 2022; Hardt et al., 2023; O' Brien & Kim, 2022; Rawal et al., 2020), imperfect adherence to the prescribed recourse (Pawelezyk et al., 2022; Virgolin & Fracaros, 2023; Maragno et al., 2024), and causal effects (Mahajan et al., 2019; Karimi et al., 2020c; Kleinberg & Raghavan, 2020).
Verification with Regions of verifying recourse over an entire region of the feature space R. S X. This region could represent plausible charac- teristics of decision subjects (c.g.. any loan applicants), or a
This paper studies the problem
sub-group of interest (e.g.. all Black female loan applicants).
We start by generalizing the notions of recourse and fixed predictions to regions instead of individual data points.
Definition 2.2. A region R is responsive under classifier f and action set A if all individuals within the region have recourse. A region R. is confined if all individuals within the region have a fixed prediction.
2. Problem Statement
We consider classification task of predicting label y E {0. }} from a set of d features = [211 Tr.,........ sal E X' in a bounded feature set X. We study linear classification mod- els, a broad function class encompussing popular methods such as logistic regression, linearizable rule-based models (e.g., rule sets, decision lists), and concept- bottleneck mod- els (Koh et al., 2020; Sun et al., 2024). We assume access to the linear classifier fx) = sign( w is the vector of coefficients and b E R is the intercept of the classifier. Without loss of generality, we assume fxx) = is the desired outcome (e.g., receiving a loan). We use bold- face variables (e.g., x) to denote vectors, and standard text with subscripts (e.g., xz)) to denote specific element of vector.
Note that a region is responsive if all individuals within the region have recourse. Similarly, a region is only confined if all individuals are assigned fixed predictions. the re- gion contains a mix of individuals with recourse and fixed predictions, the region neither confined nor fixed.
The goal of the Region Recourse Verification Problem (RVP) is to certify whether a given region R. is confined, respon- sive, or neither. This task can be cast as an optimization problem that finds the largest confined area SJ,, A) within the region S C R. For simplicity, we drop the explicit dependence of S on A). Let Size(S) be function that quantifies the size of the confined area S. Given a region R, classifier f. and an action set A, the RVP can be modeled as the following optimization problem:
b) where w E Rdd
Actionability Constraints The recourse verification prob- lem (Kothari et al., 2023) tests whether an individual x E Rdd can obtain the desired outcome of a model by actions on their features. Each action is a vector a E Rd that shifts the features of the individual to x + a = x' E X. We refer to the set of all actions an individual x can take as the action set A(x). In practice, an action set is represented by set of constraints. Table 1 shows sample deterministic ac- tionability constraints represented in both natural language and mathematical formulae that can be embedded into an optimization problem. Actionability constraints can cap- ture inherent limitations on how semantically meaningful features can change (e.g., age can only increase) and how those changes impact other features (e.g., increasing years of account hi iistoryy also increase age).
maximize Size(S) subject
Vz E S:: (z, R
An optimal solution to this optimization problem, S", can be used to directly verify whether the entire region R is confined, responsive, or neither:
Responsive, S 0
Verify(S", R) =
Confined,
if S = R otherwise
1,
Use Cases Verifying recourse over regions is a powerful tool that can be used to catch potential harms that arise from fixed predictions before deploying model, characterize confined regions, and audit discrimination.
We summarize all feasible actions that lead to the desirable outcome for an individual in the recourse set.
Definition 2.1. The recourse set consists of all feasible actions for an individual x that lead to the desired outcome:
Detecting Harms before Deployment. Existing approaches that verify recourse for individual data points may fail to find confined regions before deploying a model, especially in settings with large distribution shifts. This failure can
Recourse(x, f, A) = (a: f(x + a) =,, E A(x))
3

---

Understanding Fixed Predictions via Confined Regions
Class
Example
Fentures
Constraint
Immutabilltt
n. dependent: should not change
n dependents
==
Monotonicity
reapplicet Lican can only inerease
8) respplicant
4,20
Intogrality
n.accounts is be positive integer
#) nLaccounts
oy pyE8np-R,110-1
Categorical Encodinn
preserve noe-hot encoding of macrlee Led, single
x) married
a 4yt e (a.1) in t e (0.1)
Rx single
"y 4, + +
preserve one hot encoding of max. degres BS, max degres MB
4y 4yt (0,1) tat (0.1)
Ordinal Encoding
Rt max degzee MS
4y+ + + =1 oy
if smppooed TRUE
4 11 (0,
x, is.employed R4 Mork bes wwt.spps.p....kkkoooeeeee.ek
Logical Implications
then work hrs per week 2: else seccchhss.pee...eeee =0
10,168
+ $ 168(m+-u))
Causal Implications
years, account, history increuses then age will increase commensurately
2, years at residence age
of S
Table 1. Examples of deterministic actionability constraints. Each constraint can be expressed in natural language and modeled using standard tools from mathematical programming (see e.g., Wolsey, 2020).
result in tangible harms such as precluding individuals from receiving loans or allowing malicious actors to bypass con- tent filters. Verifying recourse over regions can catch these harms during model development and allow model develop- ers to adjust the model before deployment.
but there exists an individual in the region that assigned a fixed prediction.
Definition 2.4. Given a recourse verification task for a region R. model f. and action set A, we say that method returns loophole if it outputs that a region is confined but there exists an individual in the region with recourse.
Characterizing Confined Regions. The RVP can be run sequentially to enumerate all confined boxes in a region for classifier. These boxes are simple understand and can be used to help model developers debug ML models provide a high-level summary of confined regions for stakeholders. These confined boxes can also be used to construct a valid (lower) bound on the fraction of the region that is confined. This can be used by model developers as a metric to compare two potential ML models before deployment.
These failure modes can arise when an audit over observed data does not reveal all potential individuals within the re- gion. In Section 4 we show that this can occur with variety of different strategies to select data to test within a region.
3. Verification via Confined Boxes
Data-Free Auditing. Recourse verification over regions can be used as tool to find sources of potential discrimination in model (e.g., individuals that are assigned fixed predic- tions in lending application). This approach only requires access to a classifier and a description of the region to audit (which can be as simple as bounds on each feature). This allows external auditors to evaluate the responsiveness of classifier with no access to the underlying data. This is es- pecially powerful in applications where models are publicly available but associated data is not (e.g., criminal justice (of Pennsylvania, 2025) and medicine (Yamga et al., 2023)).
Towards formally verifying recourse over an entire region, we formulate a mixed-integed quadratically constrained pro- gram (MIQCP) to solve the RVP.
Characterizing Regions with Boxes We focus on a spe- cial case of the RVP that finds the largest confined box. A box is set defined by simple upper and lower bound con- straints on each dimension. Let U3 maxTeR Ij. 4j = min æj be the upper and lower bound for each feature in the region. Given an upper bound, u E Rd u < U, and lower bound, E Rd 2 L, a box (R, 1) is de- fined as (R 1) = (x E R : S x S u]. We focus on boxes due their interpretability, which can help model de- velopers understand the source of fixed predictions. Boxes can be viewed type of decision rule, which have been widely studied for their interpretability within the broader ML community (c.g.. (Lawless et al., 2023; 2022; Lawless & Gunluk, 2023)). For case of notation we drop the explicit dependence on R and refer to boxes as B(u, I). We define the size of a box B(u, I) as the sum of the normalized ranges of each feature:
Pitfalls of Auditing by Observation Existing methods for recourse verification (e.g., Kothari et al., 2023) can only verify recourse for observed data (c.g., individuals in a train- ing dataset). These point-wise approaches can be used to audit the responsiveness of a region by verifying whether any observed data points are assigned a fixed predictions. However, these approaches may fail to correctly output whether region is responsive confined. We outline two kinds of failures:
Definition 2.3. Given a recourse verification task for a region R, a model f. and action set A, we say that a method returns a blindspot if it outputs that a region is responsive
Size ((u, 1))
Σ j=1
U 4 U,
(1)
L

---

Understanding Fixed Predictions via Confined Regions
Generating Confined Boxes We start by formulating the related problem of auditing whether given box (u,, 1) in region R contains any data points with recourse, which we denote the Region Recourse Existence Problem (REP).
assumptions we can relax many if not all of the discrete variables in the REP. Under these new theoretical results, the set of restrictions that the algorithm must consider is often incredibly small (e.g., [C] S 4 for all the datasets and actionability constraints considered in Kothari et al. (2023)).
Let x E TR--9 x Z be a decision variable representing an individual, and a E I2-4 x " represent an action. We assume that the region R, feature space X, and action set A can be represented by a set of constraints over a mixed- integer set (see Figure 1 for example). This general assumption encompasses variety of potential regions and feature sets. We model the REP as a mixed-integer linear program (MILP) over x and a (see Appendix A for details).
We formulate a continuous restriction c C of the REP as a linear program (LP) (see Appendix A), which we represent in the following standard form:
C.x + Dea S (u,
where C. and Dr are m x matrices and be(u, I) is a m- dimensional vector that is a linear function of the box upper and lower bounds u, Here m represents the number of constraints in the continuous restriction of the REP.
Recall that the RVP can be cast as an optimization problem to find the largest confined region within R. By definition the REP is infeasible for every confined box. To certify that the REP is infeasible for given box, and by extension certify that the box is confined, we leverage classical result from linear optimization called Farkas' lemma:
MIQCP Formulation We can now formulate the RVP as MIQCP that finds the largest box with Farkas certificates of infeasibility for every continuous restriction. Let y. E R be decision variables representing the Farkas certificate for a continuous restriction e C, and u, E zd represent the upper and lower bounds of a box. Note that there is one variable in y for every constraint in the continuous restriction. We can now find the largest confined box B B(,,) I) with associated certificates of infeasibility ye for e E C using the Farkas Certificate Problem (FCP):
Theorem 3.1 (Farkas (1902)). Let A E T==x" and b E IR".. Then exactly one of the following two assertions is true:
I. There exists r E I2" such that Az S b
II. There exists y 0 such that A y = 0 and bTg -1
Farkas' lemma states that we can certify that system of inequalities over continuous variables Ar S b is infeasible by finding Farkas certificate 2 0 such that A ATy = 0 and 6 bTy = 1. In our context, we can thus view the problem of finding a confined box as a joint problem of selecting a box and finding an associated Farkas certificate for the REP. However, Farkas' lemma only applies to continuous variables, and the REP can include discrete variables.
Ud- ld
maximize Ve.u,l
Σ Us Lt
(2a)
subject to
(u, 1)=ye= y== =-1
VC E C
(2b)
C. 0
VC E C
(2c)
D. ye
Vc E C
(2d)
We extend Farkas' certificates to the discrete setting using a simple strategy that simultaneously generates certificates for all possible continuous restrictions of the REP. A con- tinuous restriction of a MILP is a restricted version of the optimization problem where all discrete variables are fixed to specific values. Note that box is confined and only if every continuous restriction of the REP is infeasible.
ye 20
Vc E C
(2e)
L L<lšus u u, 1 E z
(2f)
(2g)
The objective of the problem is to maximize the size of the box, as defined in Equation (1). Constraints (2b)-(2e) follow from Farkas' lemma and ensure that ye is valid certificate of infeasibility for the continuous restriction of the REP. Constraint (2f) ensures the FCP generates a valid box within the region R. We restrict u, I to be integer variables to pre- vent numerical precision issues when solving this MIQCP in practice. This is not an onerous assumption as any con- tinuous variable zy with a desired precision 10- " can be re-scaled and rounded to an integer variable 10"2z. The problem is quadratically constrained due to the inner prod- uet of be(u, (u,) 1) and y. in constraint (2b). While MIQCPs are often more computationally demanding than MILPs, the FCP can be solved in seconds on real-world datasets using commercial solvers (e.g., Achterberg, 2019), as the problem scales with the number of features and actionability con-
Let C. be the set of continuous restrictions, where each re- striction e E C corresponds to specific set of fixed values for the discrete variables (c.g., I1 = 1, x2 = 2 for a prob- lem with two discrete variables æ 22 E 2 Note that the set C is finite, from the assumption R is bounded and only discrete variables are fixed, but grows exponentially with respect to the number of discrete variables. If there are no discrete variables in the REP, there is single continuous re- striction representing the full problem with no fixed values. In settings where there are large number of discrete vari- ables, enumerating all possible continuous restrictions may become computationally intractable. However, we prove in Section 3.1 that under very general constraints and minimal
5

---

Understanding Fixed Predictions via Confined Regions
straints (which are typically small) rather than the number of data points in the data set.
circular relationships between variables.
When verifying recourse over a fixed box (u, 1) the FCP can be decomposed into |C] problems (solved independently for each continuous restriction). If the FCP is infeasible for any continuous restriction c, then the RVP is infeasible for the box. If the FCP feasible for all continuous restrictions c E C. then the box is responsive. Alas, when optimizing over potential boxes, the FCP cannot be decomposed as the variables u, link all the continuous restrictions.
Practically, Theorem 3.2 shows we can solve the FCP with single continuous restriction (i.e., [C] = 1), relaxing all
discrete variables in the problem.
Theorem 3.2. Under Assumptions A. A.3, the linear re- laxation of the REP feasible iff the REP is feasible for any problem with linear recourse constraints.
For a full proof and formal definitions of the assumptions, see Appendix C. The assumptions for Theorem 3.2 are gen- eral and hold in many realistic settings. For instance, K-hot constraints are often used to encode categorical features (e.g., via a one-hot encoding). Assumption A.1 holds in this setting as each associated variable only corresponds to one encoding (i.e., one K-hot constraint). Similarly, Assump- tion A.2 holds as long as there are no logical implications between the categorical features. Finally, Assumption A.3 holds as long as there are no circular implications between variables. Circular implications between variables represent flaws in constructing the action set and should be caught prior to solving the RVP.
Generating Multiple Boxes Solving instance of the FCP generates single confined box or certifies that the region is responsive. However, in practice, a given region may contain multiple confined regions. To provide model developers and stakeholders with a comprehensive view of individuals with fixed predictions, the FCP can be run sequentially to enumerate multiple (or all) confined boxes with the region. It does so by iteratively adding no-good cuts to exclude previously discovered confined regions from R (see Appendix B for details).
3.1. Handling Discrete Variables
Theorem 3.2 holds under linear recourse constraints but not under more general constraints. In Appendix D we discuss how to extend our approach to general constraints, and provide practical guidelines on how to select continuous restrictions to include in the FCP.
In the preceding section, the RVP was solved by enumer- ating and finding Farkas' certificates for all continuous re- strictions of the REP. However, this approach scales expo- nentially with respect to the number of discrete variables in the REP. In this section, we show that under very broad set of actionability constraints and general assumptions we can relax all the discrete variables in the REP and still verify recourse over the entire region.
4. Experiments
We present experiments showing that point-wise ap- proaches fail to correctly find confined regions, while our methods to audit recourse over regions accurately find such regions when they exist. Hence our methods can help decision-makers avoid harms from deploying mod- els with fixed predictions. We include code to repro- duce our results at https:/ / confined confired_regionee regions/ and provide additional details and results in Appendix E.
Linear Recourse Constraints We consider restricted set of constraints, which we call linear recourse constraints (detailed in Table 2). These constraints include a broad class of actionability constraints such as monotonicity, cate- gorical encodings, and immutability. They can be used to define the feature space X, the region R. or the action set A. Linear recourse constraints encompass many actionability constraints considered in previous literature including all the constraints in (Ustun et al., 2019; Russell, 2019; Kothari et al., 2023). We denote an action set comprised only of these constraints as linear recourse constraints.
com/ conlaw/
Setup We evaluate our approach three real-world datasets in consumer finance (heloc (FICO, 2018), givemecredit (Kaggle, 2011)) and content moderation (twitterbor (Gilani et al., 2016)). Each dataset include features that admit inherent actionability constraints that apply to all individuals (e.g., preserving feature encoding) which we use to construct the action set (see Appendix for details). We encode all categorical features using one- hot encoding and discretize all continuous features. We split the processed dataset into a training sample (50% used to train the model), and an audit sample (used to evaluate responsiveness in deployment).
Key Result Theorem 3.2 shows that we can recover the solution to the REP by solving a linear relaxation if:
A.1 No variable appears in more than one K Khhot constraint.
A.2 The directional linkage constraints do not enforce re- lationships between variables appearing in K-hot con- straints.
A.3 The directional linkage constraints do not imply any
We use the training dataset to fit a & reguularrd logistic re-
6

---

Understanding Fixed Predictions via Confined Regions
Class
Description
Formulation
Discussion
Integer Bound Constraints
Places an integer upper or lower hound on variable
Ty iy & Ug.
Encompasses wide mange of separable consimints including monotonicity, actionahility and bounds on the action step size (Kothari at al., 2023)
K-Hot Constraint
Preserves that unweighted variables (1) hey is most & 2.
Ejer # vy S
Generalizes the popular one-hot encoding categorical variables.
Directional Linkage Constraints
Ensures feature, ny greater than or equal to another featuue
ey S P2.
Fasures hroad class non se-e-eprrable constmints (i.c. constraints act on multiple features) including thermometer encodings, and deterministic cansal constmintss (e-g. increasing years account history implics communusurie increase Age).
Table 2. Linear Recourse Constraints Classes. Variables by used in the constraints may represent i variables (i.e., constrain the region). a variables (i.c., constrain the actions), or x a (i.e., constrain the resulting feature vector). This restricted set of constraints encompasses broad set of existing actionability constraints considered in previous literature.
gression model and tune its parameters via cross-validation. We use the auditing dataset to verify recourse over set of regions 52 that represent different sub-groups of interest for the classification task. We generate these regions R E Q by restricting the feature space to fixed combinations of im- mutable characteristics (e.g.. all individuals with specified age and gender). We remove all regions from Ω that do not have at least data points in the training dataset. The fraction of data points with fixed predictions (p) in the each dataset varies between 10 - 55%. We represent the feature space X' for each dataset as the smallest box containing all available data.
PointWise
Datasel
Metries
Data
Region
Score
ReVer
Certifies Responsive
54.2%
heloc
Outputs Responsive
91.6%
66.5%
71.0%-
54.2%
d= 43
Blindspol
37.4%
12.3%
[0]] = 155 p 22.2%
Certiñes Confined
0.0%
FICO (2018)
Outputs Confined
0.6%
0.0%
0.0%
0.0%
&Lophhole
0.0%
Certifies Responsive
60.1%
g vamecredit 120,268 [0] = 715 = 7.4% Kaggle (2011)
Outputs Responsive
72.2%
60.1%
62.9%.
60. 60.1%
Blindspot
12.0%
0.0%
2.8%
Cortiñies Confined
18.3%
Outputs Confined
19.4%
19.2%
19.2%
18.30 38.3%
&Lophhoee
1.1%
0.8%
0.8%
Certifies Responsive
25,0%
LwiLLerbol n= di=20 21 [O] = 20 65.3% Gilani et al. (2016)
Outputs Responsive
40.0%
25.0%
25.0%
25.0%
Blindspot
15.0%
0.0%
Certiñies Confined
5.0%
Methods We compare our method to pointwise baselines that audit recourse over sample of individual data points to generate outputs for the entire region. Given a sample of individual data points, these point-wise approaches output that region is responsive (confined) if all data points have recourse (no recourse). We generate different baselines by using different strategies to select which individual data points to include in the sample.
Outputs Confined
25.0%
25.0%
25.0%
5.0%
Loophole
20.0%
20.0%
20.0%
Table 3. Overview of results for all datasets, regions, and methods. For each dataset, we include the number of regions we audit ((2)), and the fraction of data points with fixed predictions (p).
predictions), certifies confined, outputs confined, and out- puts a loophole (i.e., misses individuals in the region with recourse). Additional metrics are reported in Appendix E.
Data: We use all data points from the training dataset that fall within the region.
Region: We sample 100 data points uniformly at random from the region being audited.
On Preempting Harms during Model Development Our results demonstrate that individualized recourse ver- ification approaches fail to properly predict whether re- gion is responsive confined. All baseline approaches result in blindspots, ranging from 2.8% to 37.4% of re- gions, and loopholes, ranging from 0.6% to 20% of regions. The baseline approaches incorporate both separable and non-separable actionability constraints. Consequently, these blindspots and loopholes arise from focusing on individual data points instead of the region as whole and highlight the importance of region-specifie methods. In Appendix F we show that these failures are exacerbated in settings whether there is a distribution shift in the test dataset.
Score: We evaluate the data points within the region with the highest and lowest classifier score (i.e. argmax, w x and argmin, wf 2)).
ReVer: We implement our approach. which we call Region Verification (ReVer), in Python using Gurobi (Achterberg, 2019) to solve all MIQCPs.
Results We summarize our results in Table 3 for all datasets and methods. We use ReVer to certify whether each region is responsive, confined, or neither. We use these results to evaluate the reliability of baseline methods. We evaluate each method in terms of the percentage of regions where it: certifies responsive, outputs responsive, outputs a blindspot (i.e., misses individuals in the region with fixed
Blindspots and loopholes represent failure cases that un- dermine the benefits of algorithmic recourse and lead to tangible harms if left undetected in model development.
7

---

Understanding Fixed Predictions via Confined Regions
These lower bounds can be used by model developers to de- cide between alternative MI models for a given application. More broadly, our results highlight the scale and difficulty of fully characterizing confined regions. Although each dataset has fewer than 50 features, at least 100 regions are confined. Our results highlight that fixed predictions arise in complex ways from immutable features. As such, they create an in- sidious new kind of discrimination: unlike traditional forms of discrimination based protected characteristics (e.g.. race and gender), this form of discrimination is much harder to identify, requires looking at combinations of features, and depends on the classifier.
Region Coverage (%)
40
20
20
40
60
80
100
Number of Regions
twitterbot Figure 2. Percentage of feasible points in the region with a fixed prediction as function of the number of confined boxes generated. Note that any point is a valid lower bound on the percentage of points with fixed predictions across the entire region.
heloc
givemecredit
On Computation Remarkably, our approach runs in un- der 5 seconds on average across all datasets (see Appendix E). This shows that although region verification is more computationally challenging than individual verification, our approach can verify regions extremely quickly. On two thirds of the datasets, our approach is even faster than the Region baseline which audits 100 individual data points.
Consider a content moderation setting where a machine learning model is used to remove sensitive content. A loop- hole could represent malicious content (e.g., discriminatory or offensive content) that is able to bypass the filter by chang- ing superficial features of the post. In consumer finance application, a blindspot represents unanticipated individuals that receive fixed predictions and are precluded from ever getting access to a loan. In both these settings, rectifying the problem after deployment would involve training a new machine learning model (e.g., by dropping features that lead to fixed predictions, or adding new features that pro- mote actionability) which can be time-consuming, costly, and continues to inflict harm while the existing model op- erates. This highlights the importance of auditing recourse over regions- - it foresees potential harms that occur when deployed models assign fixed predictions.
5. Demonstration
Setup We showcase the potential of region verification as a tool for auditing discrimination via a case study of the Pennsylvania Criminal Justice Sentencing Risk Assessment Instrument (SRAT) (of Pennsylvania, 2025). The SRAI is a simple linear scoring system that uses 37 features, including age and gender, predict the risk of offender committing re-offense (i.e., criminal recidivism). The guidelines state that an offender is deemed low-risk if the SRAI risk score is under 5 points.
We audit whether there are any protected groups that are precluded from being predicted as low-risk. To that end, we specify an action set that does not allow changes pro- tected characteristics (i.e., age and gender), and enforces logical constraints on the features (e.g., to have a prior con- viction for violent crime the number of previous convictions needs to be at least one). Full details of the actionability constraints are included in Appendix G. Note that we allow every unprotected characteristic (i.e., criminal history) to be mutable. This choice allows to answer whether any protected group, based solely on protected characteristics, is never predicted to be low risk.
On Characterizing Fixed Predictions In Section 5 we show sample regions that our algorithm certifies as confined. These regions are represented by simple decision rules (e.g., Age 21-25 and Ma le) and can help model developers debug the sources of fixed predictions. For instance, the latter example may prompt a model developer to remove features related to age and gender from the dataset.
In some settings, fixed predictions are rare and can be repre- sented by a small number of regions (see e.g., the case study in Section 5). However, in complicated settings there may be a large a number of confined regions. To demonstrate this phenomenon, we run our approach sequentially to enu- merate up to 100 confined regions within our benchmark datasets. For each dataset, we audit a region encompass- ing any plausible individual (i.e., any individual satisfying indisputable conditions on each feature). Figure 2 shows the fraction of the entire region covered after generating up to 100 confined regions using our approach. Note that any point on this curve represents a valid lower bound on the total fraction of the region that is assigned a fixed prediction.
Results We find two confined regions:
Our results highlight that the SRAI discriminates against individuals on the basis of gender and age by precluding those groups from ever receiving a desirable outcome. Our tool is able to find these forms of discrimination and present an interpretable summary of the results to stakeholders, who must then gauge whether this form of discrimination should be allowed in the criminal justice context. Notably, our
8

---

Understanding Fixed Predictions via Confined Regions
Acknowledgements
Fixed Prediction if:
MU and CL gratefully acknowledge support from the Na- tional Science Foundation (NSF) Award IIS- 223-2223,,, the Office of Naval Research (ONR) Awards N000142212822, N0001424] 42412306,, and N00014231222 22232 IBM, and the Al- fred P. Sloan Foundation. BU and LW gratefully acknowl- edge support from the National Science Foundation (NSF) under award IIS-2313105.
Age < 21
Fixed Prediction if:
Age 21 25
and
Male
References
audit required no access to the data that was used to develop the SRAI, underscoring that auditing classifiers for confined regions possible even when models are publicly available but associated data is not, in contexts like criminal justice and medicine.
Achterberg, T. What's new in gurobi 9.0. We- binar Talk url: https://www. gurobi. com/vp- http://uulooa//222////////ooo// -i--errrbb------viiieeeeee-- SebbervviwwWebbnrr- Webinar- Slides-1. pdf.. 2019.
Altmeyer, P., Angela, G., Buszydlik, A., Dobiczek, K., van Deursen, A., and Liem, C. C. Endogenous macrodynam- ics algorithmic recourse. In 2023 IEEE Conference on Secure and Trustworthy Machine Learning (SaTML), pp. 418 431. IEEE, 2023.
6. Concluding Remarks
Our paper introduces new paradigm for algorithmic re- course that seeks characterize fixed predictions by finding confined regions, areas in the feature space where model is not responsive to individuals' actions. This work highlights that characterizing confined regions can help model devel- opers pre-empt harms that arise from deploying models with fixed predictions. Our work develops method to tackle this problem by leveraging tools from MIQCP to find confined boxes within a region of the feature space. Our method pro- vides interpretable descriptions of confined regions, can be run in seconds for real-world datasets, and enables data-free auditing of model responsiveness. However, these methods should be extended to address the following limitations:
Bogen, M. and Ricke, A. Help wanted: An examination of hiring algorithms, equity, and bias. Upturn, December, 2018.
Carrizosa, E., Hamfrez-Ayerbe J., and Morales, D. R. Gen- erating collective counterfactual explanations in score- based classification via mathematical optimization. Ex- pert Systems with Applications, 238:12 238:121954, 2024.
Conforti, M., Cornuejols, G., and Zambelli, G. Integer programming. Springer, 2014.
Dominguez-Olmedo R., Karimi, A. H., and Schölkopf, B. On the adversarial robustness of causal algorithmic recourse. In International Conference on Machine Learn- ing. pp. 5324-5342. PMLR, 2022.
Our methods are designed to work with linear classifiers. In principle, methods be extended any model that can be represented by MILP. However, many MILP- representable models (e.g., tree ensembles) would require solving a large, computationally-inracaahl MIQCP and need new algorithmic approaches.
Farkas, J. Theory of simple incqualities. Journal for pure and applied mathematics (Crelles Journal), 1902(124): 1-27, 1902.
FICO. Explainable machine learning challenge, 2018. URL. htt.ps://commuiityy.fff wtw..euoiiiiii..oooooooooooooomm
Our approach finds confined boxes. Boxes are an in- terpretable way to characterize regions but have limited expressive power. Future work should explore whether more expressive classes capture confined regions with fewer items.
Forel, A., Parmentier, A., and Vidal, T. Don't 't explain noise: Robust counterfactuals for randomized ensembles. In International Conference on the Integration of Constraint Programming, Artificial Intelligence, and Operations Re- search, pp. 293-309. Springer, 2024.
Impact Statement
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must specifically highlighted here.
Gilani, Z., Wang, L., Crowcroft, J., Almeida, M., and Farahbakhsh, R. Stweeler: framework for twitter bot analysis. In Proceedings of the 25th International Conference Companion on World Wide Web, www

---

Understanding Fixed Predictions via Confined Regions
'16 Companion, pp. 37-38, Republic and Canton of Geneva, Switzerland, 2016. International World Wide Web Conferences Steering Committee. ISBN 978-1-4503- 4144-8. doi: 10. //d.i.orrg//oo/ C. 1 145 / 01/55/2221111 8 936600
Kothari, A., Kulynych, B., Weng, T.-W, and Ustun, B. Prediction without preclusion: Recourse verification with reachable sets. arXiv preprint arXiv:2308. 12820 2023.
URL https:
Lawless, C. and Gunluk, O. Cluster explanation via poly- hedral descriptions. In International Conference on Ma- chine Learning, pp. 18652-186666 PMLR, 2023.
Guo, Jia, F., Chen, J., Squicciarini, A., and Yadav, A. Ro- coursenet: Distributionally robust training of a prediction aware recourse model. arXiv preprint wrXi:2226.00070, 2022.
Lawless, C., Kalagnanam, J., Nguyen, L. M., Phan, D., and Reddy, C. Interpretable clustering via multi polyip machines. In Proceedings of the aaai conference on artificial intelligence, volume 36-7, 7, pp. 7309-7316, 2022.
Hardt, M., Mazumdar, E., Mendler-Dünner, C.,, and Zrnic, T. Algorithmic collective action in machine learning. In International Conference on Machine Learning, pp. 12570-12586. PMLR, 2023.
Lawless, C., Dash, S., Gunluk, O., and Wei, D. Interpretable and fair boolean rule sets via column generation. Journal of Machine Learning Research, 24(229)11-5,, 2023.
Hurley, M. and Adebayo, Credit scoring in the era of big data. Yale JL& & Tech., 18:148, 2016.
Ley, D., Mishra, S., and Magazzeni, D. Globe-ce: A trans- lation based approach for global counterfactual explana- tions. In International conference on machine learning. pp. 19315-19342. PMLR, 2023.
Kaggle. Give Me Some Credit, 2011. URL http:://ww. kaggle, com/ c/ /e..veeeSeeeeerei.itt....
Kanamori, K., Takagi, T., Kobayashi, K., Ike, Y., Uemura, K., and Arimura, H. Ordered counterfactual explanation by mixed-integer linear optimization. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35-13, pp. 11564-11574, 2021.
Liu. L. T., Barocas. S., Kleinberg, J., and Levy, K. On the actionability of outcome prediction. In Proceedings of the AAAI Conference Artificial Intelligence, volume 38-20, pp. 22240-22249, 2024.
Lodi, A. and Ramírez-Ayerbe, J. ona-for-many counterfac- tual explanations by column generation. arXiv preprint arXhv:2402.09473. 2024.
Karimi, A.- Barthe, G., Balle, B., and Valera, I. Model- agnostic counterfactual explanations for consequential decisions. In International conference on artificial intelli- gence and statistics, pp. 895-905. PMLR, 2020a.
Mahajan, D., Tan, C., and Sharma, A. Preserving causal constraints in counterfactual explanations for machine learning classifiers. arXiv preprint arXiv:1912.03277, 2019.
Karimi, A.-H., Barthe, G., Schölkopf, B., and Valera, A survey of algorithmic recourse: definitions, for- mulations, solutions, and prospects. arXiv preprint arXiv:2010.04050 2020b.
Maragno, D., Kurtz, J., Röber, T. E., Goedhart, R., Birbil, Ş. I., and den Hertog, D. Finding regions of counterfactual explanations via robust optimization. INFORMS Journal on Computing, 2024.
Karimi, A.-H., Von Kügelgen, J., Schölkopf, B., and Valera, Algorithmic recourse under imperfect causal knowl- edge: probabilistic approach. Advances in neural infor- mation processing systems, 33:265-277, 2020c.
Morrison, A. S., Ustun, B., Horenstein, A., Kaplan, S. C.,, de Oliveira, I. R., Batmaz, S., Gross, J. J., Sadikova, E., Hemanny, C., Pires, P. P., et al. Optimized short-forms of the cognitive distortions questionnaire. Journal of Anxiety Disorders, 92: 102624, 2022.
Karimi, A.-H., Schölkopf, B.,, and Valera, I. Algorithmic re- course: from counterfactual explanations interventions. In Proceedings of the 2021 ACM conference on fairness, accountability, and transparency, pp. 353-362, 2021.
Mothilal, R. K., Sharma, A., and Tan, C. Explaining ma- chine learning classifiers through diverse counterfactual explanations. In Proceedings of the 2020 conference on fairness, accountability, and transparency, pp. 607-617, 2020.
Kleinberg, J. and Raghavan, M. How do classifiers induce agents to invest effort strategically? ACM Transactions on Economics and Computation (TEAC), 8(4):1-23, 2020.
Koh, P. W., Nguyen, T., Tang, Y. S., Mussmann, S., Pierson, E., Kim, B., and Liang, P. Concept bottleneck models. In International conference on machine learning, pp. 5338- 5348. PMLR, 2020.
Murgia, M. Algorithms are deciding who gets organ trans- plants. are their decisions fair. Financial Times, Nov. 2023.
10

---

Understanding Fixed Predictions via Confined Regions
O'Brien, A. and Kim, E. Toward multi-agent algorithmic recourse: Challenges from game-theoretic perspective. In The International FLAIRS Conference Proceedings, volume 35, 2022.
Warren, G., Delaney, E., Guéret, C., and Keane, M. T. Ex- plaining multiple instances counterfactually: User tests of group-counterfactuals for xai. In International Confer- ence on Case-Based Reasoning, pp. 206-20022202022 226-222. Springer, 2024.
of Pennsylvania, C. Title 204 section 305. https://www
The pennsylvania code:
Wolsey, L. A. Integer programming. John Wiley & Sons, 2020.
data/204 / http://///ccaaeee///50......00 pdd. 2025.
Yamga, E., Mantena, S., Rosen, D., Bucholz, E. M., Yeh, W. Celi, L. A., Ustun, B., and Butala, N. M. Op- timized risk score to predict mortality in patients with cardiogenic shock in the cardiac intensive care unit Jour- nal of the American Heart Association, 12(13):0022332, 2023.
Accessed: 2025-01-27.
Pawelczyk, M., Datta, T., van-den Heuvel, J., Kasneci, G., and Lakkaraju. H. Algorithmic recourse in the face of noisy human responses. arXiv preprint arX6:2200.006768, 2022.
Rawal, K. and Lakkaraju, H. Beyond individualized re- course: Interpretable and interactive summaries of action- able recourses. Advances in Neural Information Process- ing Systems, 33:12187-1211 2020.
Rawal, K., Kamar, E., and Lakkaraju, H. Algorithmic re- course in the wild: Understanding the impact of data and model shifts. arXiv preprint arXiv:2012. 11788, 2020.
Ribeiro Junior, M. A. F., Smaniotto, R., Gebran, A., Za- mudio, J. P., Mohseni, S., Rodrigues, J. M. d. S., and Kaafarani, H. The use of potter (predictive optimal trees in emergency surgery risk) calculator to predict mortality and complications in patients submitted to emergency surgery. Revista do Colégio Brasileiro de Cirurgiões, 50: e20233624, 2023.
Russell, C. Efficient search for diverse coherent expla- nations. In Proceedings of the conference fairness, accountability, and transparency, pp. 20-28, 2019.
Sun, C.-E., Oikarinen, T., Ustun, B., and Weng, T.-W. Con- cept bottleneck large language models. arXiv preprint arXiv:2412.07992,, 2024.
Upadhyay, S., Joshi, S., and Lakkaraju, Towards robust and reliable algorithmic recourse. Advances in Neural Information Processing Systems, 34:1 14:16696616937, 2021.
Ustun, B., Spangher, A., and Liu, Y. Actionable recourse in linear classification. In Proceedings of the conference on fairness, accountability, and transparency, pp. 10 19, 2019.
Venkatasubramanian. S. and Alfano, M. The philosophical basis of algorithmic recourse. Proceedings of the 2020 conference on fairness, accountability, and transparency, pp. 284-293, 2020.
Virgolin, M. and Fracaros, S. On the robustness of sparse counterfactual explanations to adverse perturbations. Ar- tificial Intelligence, 316: 313:103840, 2023.

---

Note that this problem has no objective taking action a. classified with the desirable outcome. Constraints (3c) and (3b) ensure that vector (i.e., included in X),, and is part of the region of interest. Constraint (3d) ensures that the action satisfies the Understanding Fixed Predictions via Confined Regions
Appendix
Understanding Fixed Predictions via Confined Regions
A. REP Integer Programming Formulation
Recall the following:
x E TRd-9 x Z is a decision variable representing an individual.
a E R x 2 is decision variable representing an action.
fx) sign( w T x + b) is the linear classifier where fxx is the desirable outcome.
X' represents the feature space.
R represents the region of interest.
Axx) represents a set feasible actions for given individual x under the set of actionability constraints.
We assume that X, R. and A can all be represented via set of constraints in MILP optimization model. We formulate the REP for given region of interest R as the following MILP:
w T (x + 2 b x E
(3a)
(3b)
x A(x)
(3c)
(3d)
E (uu,l)
(3c)
x, a pd-m n
(31)
a feasibility problem. Constraint (3a) ensures that the data point x, after
valid feature
actionability constraints. Finally Constraint (3e) ensures that is included in the box B(u,)) l). Note that any solution to the REP represents feasible Bu,, I) with recourse. Thus the region B Buu,1 1) is confined if and only if the REP is infeasible.
A.1. Continuous Restriction
Recall that C is the set of continuous restrictions of the REP, where continuous restriction C corresponds to the REP
with fixed values for the discrete variables (e.g., 21 = 1, 2y 2 for discrete variables JD = {z1, x2 x22)). Let Uj E JD represent discrete variable, and 8j be its fixed value in continuous restriction e. We can incorporate continuous restrictions into the MILP formulation by adding the following additional constraints that fix the values of discrete variables in the formulation:
1 = sj Vuz E JD
Note that since all discrete values fixed, this is not linear program the d continuous variables.
12

---

Understanding Fixed Predictions via Confined Regions
B. Generating multiple confined boxes
Solving an instance the RVP can generate single confined box. However in practice, a given region may contain multiple confined boxes. To provide model developers or stakeholders with holistic view of fixed predictions. the RVP can be run sequentially to enumerate multiple (or all) confined boxes with the region. We do by adding no-good cuts the FCP that exclude previously discovered regions. This is equivalent to re-solving the RVP for new region R' R. that excludes existing confined boxes.
Let ü, be an existing confined box. Let decision variables Zu, Z, E {0, 1j track whether the new box u, 1 is outside the existing box. We model the no- no-good cuts that exclude ü, via the following linear constraints:
Ud 1 1 la 1)(1 - znd) Ad E [d]
(4a)
2 Th +1+++ (Ld - dd 1)(1 24d) Ad E [d]
(4b)
Σ 2nd zd 21
(4c)
Bu 2 E 10,
(4d)
Constraint (4a) checks whether the upper bound for feature d in the new box is less than the lower bound for feature d the existing box. Note that these constraints are enforced 2ud = Constraint (4b) checks an analogous condition for the lower bound of feature d. Constraints (4c)-(4d) ensure that at least one constraint of type (4a) (4b) are active. In other words, it ensures that the region must fall outside the previous region by ensuring that least feature differs in the new box. We exclude constraints for bounds that are tight with the population bounds (i.e., Uu Ua or la La) they are implied in the FCP. Given that our procedure tends to generate sparse regions (i.e., regions that change few features from their population upper and lower bounds), these no good-cuts typically add very small number of binary variables and constraints to the full formulation.
13

---

Understanding Fixed Predictions via Confined Regions
C. Proof of Theorem 3.2
We prove this result by showing that polyhedron defining feasible individuals x and actions a under linear recourse constraints totally unimodular, which means that all extreme points of the polyhedron are integral. Consequently, the linear relaxation of the REP is feasible if and only the discrete REP is feasible.
We start by (re)-introducing important notation:
X is decision variable corresponding to individual with the region R.
is decision variable corresponding action which must be feasible under the action set A(x).
Vy represents a set of variables corresponding to feature j (i.e., aj. or dy + az).
Consider the following mixed-inted intteerr polyhedron that represents all feature space, region, and actionability constraints.
x + a E X
(5a)
x E
(5b)
x E (u,
(5c)
E A(x)
(5d)
x, a E Rd- x Tm
(5e)
Recall that for Theorem 3.2, consider subset of possible constraints used in X, R, called linear recourse constraints
which were introduced in Section 3.1. We denote the polyhedron with only linear recourse constraints as the linear recourse polyhedron. We repeat these constraint types here to keep this section self-contained:
K-Hot Constraints: Let Jr be the set of variables that participate in a K-hot constraint i. A K-Hot constraint is:
Σ E K.
JEJ.
Unit Directional Linkage Constraints: This constraint acts on two sets of variables us Up and requires:
By S Uk
Integer Bound Constraints: Act single variable by and require:
L S or Un U,
Note that in all these constraints, all variable coefficients in these constraints are in {0, =1), and thus any matrix comprised of linear recourse constraints is {0, -mattrx... Let J {J:} be the of K-hot constraints. We define undirected graph which captures all directional implications between variable indices, which call the implication graph. For every variable index i we create one node in the graph n; in the implication graph. We create edge from node n, to if there exists a unil-directional linkage that acts on j and k. Note that this implication graph is could include multiple connected (and potentially cyclic) components.
We now formally define assumptions A.1-A.3:
A.1 No variable appears more than one K-hot constraint. Formally,
J n Jxl
0, VJ,, Ju J.
A.2 The directional linkage constraints do not enforce relationships between variables appearing K-hot constraints. Formally, each connected component in the implication graph contains at most one node n, corresponding to a variable in J..
14

---

Understanding Fixed Predictions via Confined Regions
A.3 The directional linkage constraints do not imply any bi-directional implications between variables. Formally, the implication graph is acyelic.
We start by proving the key lemma for our result which states the linear recourse polyhedron totally unimodular. Lemma C.1. The linear recourse polyhedron is totally unimodular.
Proof. We prove this result by showing that every column submatrix of the linear recourse polyhedron admits an equitable bicoloring (Conforti et al., 2014). We consider a linear recourse polyhedron comprised exclusively of constraints where 2/ = 2, + az. which we denote with the matrix Z. Note that any constraint where ) = Iy or U/ = a, uses a subset of the variables {rrj (z} and thus represents a column sub-matrix of this general case. In other words, proving our result in this special case also proves the result for settings where constraints may have U/ Ij or vy = aj.
Consider the following coloring scheme for any column submatrix of Z.
1. For each index j. if columns corresponding both zj and oj are included in the submatrix, color the column corresponding to z, red and the column corresponding aj blue.
2. For each K hohot constraint i, let Jj S J, be the remaining variables in the constraint, whose columns are included in the submatrix but have not yet been colored. Alternate coloring variables in J, red and blue.
3. Consider the implication graph created by the directional constraints. Remove any node corresponding to an index j that contains no variables selected in the submatrix, and any index j where all variables corresponding to the index that are present in the submatrix have already been colored in Step 1. Note that every node ny now corresponds to exactly one column (i.e., J, or az). For each connected component of the revised implication graph, pick an initial node as follows. If there is a node ny corresponding to a variable UJ, in the component, select it as the initial node. Note that n, must have already been assigned color in Step 2. If no such node exists, select an arbitrary node as the initial node. If the initial node corresponds corresponds to a column that has not yet been colored, color the corresponding column arbitrarily. We now traverse the connected component coloring columns as follows. Given a current node n2 with color color all nodes nı connected to it that are uncolored with the opposite color. Repeat until all nodes in the connected component are colored.
4. Note that any remaining uncolored columns must correspond to single variable x, or aj that only participate in integer bound constraints. Color each column arbitrarily.
Note that assumptions A. A.3 ensure that this is valid coloring (i.e., we always assign column exactly one column). Specifically, Item A. I ensures that column corresponding to variable z; a, is never assigned more than one color in Step 2. Similarly, Item A.2 and Item A.3 ensures that each node in the revised implication graph is assigned exactly one color, and that every pair of columns connected with associated nodes in the revised implication is assigned different colors.
We now show that this coloring is equitable (i.e., the sum of the columns colored red minus the sum of the columns colored blue differ by at most one for each row). We denote the sum of the columns colored red minus the sum of the columns colored blue for each row as the row sum. Since each row corresponds to a single constraint, we show this result for each constraint class separately:
Khot Constraints: This follows directly from Step 1 and Step 2.
Unit-Directional Linkage Constraints: Consider generic sub-matrix of 7. If the row corresponding to directional linkage constraint i that operates on index j and A has columns corresponding to æj and aj (Ix and ag) in the the submatrix, Step ensures the net sum for columns for variables corresponding to j (k) is O. If after Step 1, there is cxactly one remaining uncolored column in the row of the submatrix then the entire row sum is +1. If there are two uncolored columns then it must correspond to one variable (i.e., 2, or aş) from index j and one from index k. Step ensures that these are assigned different colors. Thus in all cases, the row sum is 0 or 1.
Integer Bound Constraints: Every corresponding to an integer bound constraint in the submatrix includes columns correspond to either zy AND aj, Ij. or ay. In the first case, Step 1 ensures that the row sum is O. In the latter case, the row sum will be +1 depending on the color selected in Step 4.
15

---

Understanding Fixed Predictions via Confined Regions
We now prove the full result of Theorem 3.2.
Proof. By Lemma C.I, under Assumptions A.1- A.3 the linear recourse polyhedron is totally unimodular. This means that every extreme point of the polyhedron integral and corresponds to feasible integer vectors x,
The REP with linear recourse constraints corresponds to the linear recourse polyhedron with addition linear constraint (i.e., the linear recourse polyhedron intersected with a half-space). We now show that the REP is feasible iff the linear relaxation of the REP is feasible.
(REP is feasible implies the linear relaxation of the REP is feasible) This follows from the fact that the latter problem is a relaxation of the first problem.
< (The linear relaxation the REP is feasible implies the REP is feasible) Intuitively, this follows from the fact that the REP is the linear recourse polyhedron intersected with a halfspace. If there are any feasible data points in the REP there must be least one feasible extreme point (which represents solution the REP).
Formally, consider feasible solution to the relaxed REP (note that this includes both for of notation). This solution must be feasible point in the linear recourse polyhedron (otherwise it would contradict it being a feasible solution). We can represent any feasible point in the linear recourse polyhedron as a convex combination of extreme points of the polyhedron {ux} h by the Minkowski representation theorem:
Σ DEFE
s.t. Σ>e
d 1, 2
444
Constraint (3a) in the REP implies:
b bww w w
Aatok) = Σ
AkwT pr
&
Since > 2 this means that there is at least one extreme point l4 such that w T 14 2 b, and thus least one feasible solution to the discrete REP.
16

---

Understanding Fixed Predictions via Confined Regions
D. Practical Guidelines for Selecting Continuous Restrictions for the FCP
Unfortunately, Theorem 3.2 does not hold directly under a broader set constraints. Consider the following simple example over two features 21 22. Let æ1 be binary variable, and z2 be an integer variable bounded between 0 and 10. Add one directional linkage constraint such that increasing æ by one unit causes 22 decrease by 10 units. The classifier assigns the desirable outcome if d1 2 0.5. Consider the region R 21 x 22 {0} [5, 10] Every individual in the region has continuous recourse by setting individual has recourse because setting a1 = 1 would require violating the bound constraint 22 + 02 2 0.
0.5. However, in the discrete version of the REP, which requires an E {0, no
One strategy to handle general constraints is to restrict a subset of discrete variables in the REP, such that each resulting continuous restriction meets the conditions Theorem 3.2. In practice, this strategy leads to a small number continuous restrictions. For example, consider the heloc dataset used our experiments, which has 42 binary features, one integer feature, and 20 non-separable constraints. It contains two constraints that are not linear recourse constraints:
Actions on YearssinceelastDelllrrdddee will a 3 unit change in Years0fAccountthisst.o
Actions on YearssSinceTast will a 5 unit change in YearsofAccouuthHistrr.
Note that these are not linear recourse constraints because a unit change in one variable results in non-unit change in another. There over 242 possible continuous restrictions which makes solving the full FCP over every restriction computationally intractable. However, restricting SaaasssiceeasseelllIIaaaa.
(i.e., www.ssiinneastteelraaaadee fixing each variable to either 0 1) transforms the two violating constraints into integer bound constraints. This only generates four continuous restrictions (2 x 2) but still allows the FCP to leverage Theorem 3.2.
and
This strategy is sufficient for many actionability constraints available with public implementations. For example, all constraints implemented in the Reach package (Kothari et al., 2023) (c.g., if-then constraints, directional linkage constraints with non-umit scaling factors) only require restricting one discrete variable. An alternative approach in settings with a large number of non-separable constraints over discrete variables is enumerate feasible feature vectors for the inter-connected discrete variables and re-formulate them one feature which represents categorical encoding over all possible values (similar to the approach detailed in Ustun et al., 2019).
In settings where this is not possible or does not dramatically reduce the number of discrete variables our approach can also be run with a single continuous restriction corresponding to a linear relaxation of the original REP. Solving this relaxed FCP can be used to provide weaker guarantees:
If the relaxed version of the FCP returns a confined box, this box is confined for the discrete version of the problem (any individual without continuous recourse also does not have recourse in the discrete problem).
If the relaxed FCP certifies that the entire region is confined (i.e., all data points assigned fixed predictions), then the entire region is guaranteed to be confined in the discrete version of the problem.
Unfortunately, the relaxed version of the FCP is infeasible there no guarantee that the entire region responsive.
17

---

Understanding Fixed Predictions via Confined Regions
E. Supplementary Material for Experiments
In this section we present all the actionability constraints for the datasets used in our experiments. Note that the feature space X' for each dataset has the same upper and lower bounds as well separabae constraints as the action set. All regions audit in this paper are represented by boxes with fixed values for immutable features.
F. Actionability Constraints for the heloc Dataset
We show list of all features and their separable actionability constraints in Table
Name
Type
LB
UB
Actionability
Sign
ExternalRRisEEtiimaa
(0,
1
No
OiternalRRisKIssimateee
00
0
1
No
RiternalRiskfss imate2200
[0,
1
No
ExternallissKEstimntee>
[0.1)
1
No
ExternalRRiskSttimates
10
I
No
YearsCFAcccountHisstryy
AvgYearsttFille23
1)
Yes
ArgYearriinfile25
00
Yes
AvgYearsiIFFilee2
0..
Yes
0.1
Yes
0,
Yes
kxyberrogatozzyCooment
0.1
No
ktyTraade120bayyDellg
0.1
No
#nyTrade907aysTeelg
0.
AnyIradee60Dayseelg
0.
AryIrade30DaysDell
0.
NoBeigBver
0.
No
0.
Yes
\eareSSinelasttteell11addd33
0.
Yes
Year=3@incee.ssttbolllaaaade
0.
O
Yes
MuninsttallTrrdess2
0.
Yes
Numinstallllrades233
0.
Yes
NunInstalllTrades225
0.
Yes
Muminsstalll7:add5222
0.
NunlrsttalllIrrddeeeBaaaaeee222
0.
Yes
Nim.:assaallrrrddeesaaaaaarre
0.
Yes
0.
Yes
0.
Yes
Humnkevol\ying/23adee2222
0. 0
Yes
MumKRevolvving/7:ades225
0.
0
Yes
0.
Yes
Jumkevvolviin//:adeee211
0.1
Yes
0.
Yes
0.
Yes
0.1
Yes
0.1
Yes
NelITraattionnnnssc]]]/Beee22221
0.1
Yes
Net
0..
Yes
Net
00.1
Yes
(0.1)
Yes
(0.1)
Yes
(0.1)
(0,
1
Yes
Table Soparable actionability constraints for the holoc dataset.
The non-separable actionability constraints for this dataset include:
1. DirectionalLinkage: Actions Nunkeroo.wingghradeesaaaaaaaz will induce actions on NimkevolviingTraaeee22...e unit change in hundevool.iinggrradeessaaaaeeee leads to:1.00-unit change in NumRevo SumnevolvinngTrdesss2
2. DirectionalLinkage: NumInstallTrades>2 Each unit change MunInstall.TaadeeWWaalaaa.a leads to:1.00 1o:1.00-mmi change in
Actions on NuntnnstallPrrddesalllaaczee will induce to actions on
NumInstall1raaee>>
18

---

Understanding Fixed Predictions via Confined Regions
3. Directionallinkage: Actions Wumnkero..iingrrraaeeWaaaaaaa will induce actions NumRevol W wiw.grrddddd2333aamm unit change in Numfeevolvinggfrrddesaaaaalla ance2 leads to:1.00-unit change in NumtewoolvingIradee23
4. DirectionalLinkage: Actions on NinLnstaalIraddeeBBaaeeee'' will induce to actions NumInstallTradess change in NumInstallTradess
Each unit change in Mun.nsttallTrrddesWaaaaaacc leads to:1.00-unit
5. DirectionalLinkage: Actions on Nunkerooaviisgrraeeessslaaaaae will induce to actions on NumtevolriingTTradee223333 unit change in NuufRevwoovinggrrredeesslaaaaee leads to:1.00-unit
change in NumkevolvingIIrade=>
6. DirectionalLinkage: Actions on MunlnsstallIrrrdesBlaannneee will induce to actions on NumInstall Ttw.LnsssalIrrdd2252.. Trades25. unit change Nun.InstalllTradestlaaaaeeee leads to:1.00-unit change in NumInstallTTrade25
7. DirectionalLinkage:: Actions on Nunkevo_.vooggrreee///laaaaaa??? will induce actions on NumRevol wtwpee/owwwinnnrreedeeeeeeeee unit change in Numneevoooiinggrrrddssssaaa aance27 leads to:1.00-unit
change in NunRevolving/radee22
8. Directionalllinkage: Actions
Yontisstaal will induce actions NumInstallITrade222.B unit change in Nannhsstaaallrrrseeslllaaaaee leads to:1.00-unit change in NumInstallTrades27
9. DirectionalLinkage: Actions on herrs will induce to actions on Years0fAccountthisttrry, Each unit change in YearrsinceeasstDeellrreess. leads to:-1.00-unit
change in Yearss
10. DirectionalLinkage: Actions on YearsSineetastteelrrraeee? will induce to actions on Yeare:fAccountHissttyyyy Each unit change in YeaxsSincelastbeellrraaess leads to:-3.00-unit change in YearsofAcccunttissorr
DirectionalLinkage:
Actions on Yearss will induce to actions on
YearsOfAccounttiisttrryy Each unit change in YarsShoceLastDalqraaass leads to:-5.00-unit
change in YearsofaccountHissory
12. ThermomeetrEEncoding: Actions on ['aassinneeasttelgrrraee.. hag.aeeee..eeiinetttttteeeeeeeee Years
must preserve thermometer encoding. which can only Actions only turn off higher-level dummies that are where and Yearssincells-Deegrrrdd is the highest-level-dummy
is the lowest-level dummy
13. ThermometerfEnoodin::
Actions on
Most
must preserve thermometer encoding.
14. ThermometerEncodinn: Actions on AlvgYearsInFile>: IvgYearsInFilee2 AvgYearsInFile>?7 must preserve thermometer encoding., which can only increase.Actions can only turn on higher-level dummies that are off, where AvgYearsInFile>> is the lowest-level dummy and ArgYearsInFile27 is the highest- level-dummy.
15. ThermometerFicodinn:
Actions on [NetFract hee
NetFractionRevolle Nettraecsioneeroovvigggueeeeeee Nettraccioonevvaannngaaeeeeee thermometer encoding., which only decrease.Actions only turn off higher-level dum- mies that are on. where settractionnevoovvnnggueee Nel.Fracttioneeevoovvnggggrrrrr is the highest-level-dummy
must preserve
is the lowest-level dummy and
16. Thermometerfinooding:
NeIFractioonInstallBereee NetFractionInstee 1 must preserve thermome- ter encoding., which can only decrease.Actions can only turn off higher-level dummies that are on, where NetFracctoonnstaallBrr the lowest-level dummy and NetFract wowlasttoonnntttoom Bar.ttttaBBBudderrr is the bighest-levelddummy
Actions
1Burden2
19

---

Understanding Fixed Predictions via Confined Regions
17. ThermomeeterEncoding:
Actions
Sumneerollinngrraaaesaaaaaaaa must preserve thermometer encoding, which can only decrease.Actions
can only turn off higher-level dummies that are on, where NumRevo wwt.eeeoo.vinggaaeeeaaaaaaaaeee is the lowest-level dummy and NumRevol viggTradesWaa ancce the highest-leve--uummy
18. ThermooneterFncodingg:
Actions
[NumRevolvingTTrades
NumRevol ngTrades
NumRevo www.eevvvvinngIadee2... must preserve thermometer encoding,, which can only decrease.Actions can only turn off higher-level dummies that are on, where NunkevolvinggIaaees222 is the lowest-level dummy and NumRevo vvingrraess2? is the highest-leeel-uummy.
NumtevolviinTIzades:
19. Thermometer/Encoding:: Actions WonntnsttalIIraaesaaaaaaaaeee Mrd anradeeeaaalaaeee wwm.//sssalTTraeeeaaaaaaeee
MunfisstalIIradeeaaaaaaaeeee must preserve thermometer coding., which can only decrease. can only turn off higher-level dummies that are on, where the
Nunnnosttallrrddesaaaaaaaneee the lowest-level dummy and highest-level-dummyy
20. ThermometerEEnoodnng:
NumInstallTrades23. Num I nstal Senttallrrdde2555 NumInstal 1Trades27] must preserve thermometer encoding.. which can only decrease.Action. can only turn off higher-level dummies that are on, where NumInstallTrades22 is the lowest-level dummy and NumInsta 1Trrades>> 7 the highest-level-dumny
Actions
[NunInttalITades22.
20

---

Understanding Fixed Predictions via Confined Regions
E.2. 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
Age
Z
21
103
No
NumberOffeeendents
No
DebtRatio21
{0, 1
0
Yes
MonthlyIncome233
{0, 1
0
Yes
Monthlyynncome2:5
10,
Yes
Monthlyynncome22105
10,
O
Yes
CreditLine@::lliattiono.....
10,1
O
Yes
CrecitLinn@U:lliatttiooo22...
10,1
Yes
Credit./ine00::1irattoo0022
0,
O
Yes
00
O
Yes
Crecktiinee::1llittiooo2....
00,1
Yes
Any:eeallBsttateelcccaas
00.1
Yes
Mallippleteell@stttelaaaass
10
0
Yes
AngChheiittlhneesAndi.onsss
[0,
Yes
Mulijpleccecdtiinneeadddaaaa
[0,
Yes
Hi iistoryOfhollinnuennyy
#istoyyoffattseaymett
[0
0
No
[0,
No.
Table 5. Separable actionability constraints for the givemecredit dataset.
The non-separable actionability constraints for this dataset include:
1. ThermometerEncoding: Actions on [MontalyIncome MonthlyIncome MorthlyIncome2200 must preserve thermometer encoding., which can only Accronse.Actions can only turn on higher-level dummies that are off, where MonthlyIncome2233 is the lowest-level dummy and YonthlyInccoe=2100 the highest-level- dummy.
2. ThermometerEncoding: Actions on [CredttLhhett:lliatttoo]]]]] Credit[iheettlliaaiiio2222 Cred tLin www.etiiiiiiiiiiiooo iniitii5500,, Credi todiittinn wett:nntttiiiieii te 1 must preserve thermometer encoding., which can only decrease.Actions can only turn off higher-level dummies that on, where
CreditLinett:in
www.etttiiiatiinnn111 is the lowest-level dummy and Creditiineet:: is the highest-level-dummy.
3. ThermometerFneoddin: Actions on [AnyRea SaayReallatttteeoaaaaa Estateloans, wal.e.ppleeelllstttee..o.o must preserve thermometer encoding., which can only decrease.Action. can only turn off higher-level dummies that are on, where AnyRealEstate Estatelonnt is the lowest-level dummy and MuliippleRel.Estttttaann is the highest-level- dummy.
4. ThermomettrrEncoding: Actions on [AnyCredit htt.ereedtt..nnnnnnll.aaaat preserve thermometer encoding., which can only decrease.Actions can only turn off higher-level dummies that are on, where AnyCredi wtteeeddiiiinnennn....oa.a the lowest-level dummy and Mul t is the highest-leeel-dummyy
must
21

---

10 Understanding Fixed Predictions via Confined Regions
E.3. Actionability Constraints for the twitterbot Dataset
We present a list of all features and their separable actionability constraints in Table 6.
Name
Type
LB
UB
Actionability
Sign
omat
{0,
0
No
SourceOther
[0,
0
No
SourceBranding
00
0
No
SourceMobile
[0.1] O
No
SourceWeb
00 O
No
SourceApp
0,1 O
No
FollowerFrieendattio211
0, O
No
Fol.ooverF2ieencaat:0000000
10,1 0
No
Fol10weer22lendkatti00000.
00, 0
No
Fol.oowerEIieendaaiic0000000
0, 0
No
Fo.10owerfF1eeedaa:::::000000000
10.1 0
No
Fol.oowee22iiendda::::0000000000
10,1 O
AgsoffcccountIInDayy2333
(0.1) O
Yes
Ageoffcccount.mmays227700
00 O
Yes
UserReplied2:10
00.1 O
Yes
UserRep1ied>210
00.1] O
Yes
1serfavouritee@21000
10.1 O
Yes
Userfavourited21000
[0 0
Yes
UserRetweeted211
[0.1)
0
Yes
UserRetweeted2210
0
Yes
UserRetweetec2100
{0,1] 0
Yes
Table 6. Separable actionability constraints for the ''w tterbot dataset.
The non-separable actionability constraints for this dataset include:
1. ThermomeeeefEnooding:
Actions on [Fellowerrr.enniattiz22... httpr//cceattttttaaarrrrrraaaaar Foll 2011loeerrriendattt02000000 must preserve thermometer encodding
Followerfrienddatto02000
2. ThermometerEncoding:: Actions on aago:/acccuttnog222222oooccoooon thermometer encoding.
must pre-
3. ThermoneterEncoding:: Actions on http:pppeeeeeeee...eeeeeeeeeeee must preserve thermometer encod- ing.
4. ThermometerEEnooiig:: Actions on http:://rc..crrr..ooooooooooooaa must preserve ther- mometer encoding.
5. Thermometerfinooding: Actions [UserRetweeted21, UserRetweeted211, UserRetweeted22100 must preserve thermometer encoding.
E.4. Computing Infrastructure
We run all experiments on personal computer with an Apple MI Pro chip and 32 GB RAM. All MILP and MIQCP problems were solved using Gurobi 9.0 (Achterberg, 2019) with default settings.
E.5. Additional Results
Table 7 shows an extended version of our main results that include three additional metrics:
Realized Blindspot Rate: The fraction of total regions that are predicted to responsive but contain individuals with
fixed predictions the test dataset.
22

---

Understanding Fixed Predictions via Confined Regions
PointWise
Dataset
Metries
Data
Region
Score
ReVer
Certifics Responsive
54.2%
Outputs Responsive
91.6%
66.5%
71.0%
54.2%
Blindspot
37.4%
12.3%
16.8%
0.0%
heloc oo
4. Realized Blindspot
1.9%
0.0 %
0.0%
0.0%
= 5842 d = 43
Certifies Contined
0.0%
[2] 155
22.2%
Outputs Confined
0.6%
0.0%
0.0%
0.0%
FICO (2018)
Loophole
0.6%
0.0%
0.0%
0.0%
Realized Loophole
0.0%
0.0%
0.0%
0.0 %
Comp. Time (s)
0.05(0.0)
0.74(0..)
0.02(0.0)
4.67(3.6)
Certifics Responsive
60.1 %
Outputs Responsive
72.2%
60.1
62.9%
60.1%
Blindspot
12.0%
0.0%
2.8%
0.0%
givemecredit
L. Realized Blindspot
3.1%
0.0 %
1.0%
0.0%
n 120, 268 = 23
Certifies Confined
18.3%
!2] 715 7.4%
Outputs Confined
19.4%
19.2%
19.2%
18.3%
Kaggle (2011)
Loophole
1.1%
0.8%
0.8%
0.0 %
Realized Loophole
0.3%
0.0%
0.0%
0.0 %
Comp. Time (s)
0.02(0.1)
0.32(0.1)
0.01(0.0)
0.13(0.1)
Certifies Responsive
25.0%
Outputs Responsive
40.0%
25.0%
25.0%
25.0%
Blindspot
15.0%
0.0%
0.0%
0.0%
twittesbot
Realized Blindspot
15.0%
0.0%
0.0%
0.0%
= 1438 d 21
Certifies Confined
5.0%
20 p 55.3%
Outputs Confined
25.0%
25.0%
25.0%
5.0%
Gilani et al. (2016)
Loophole
20.0%
20.0%
20.0%
0.0%
Realized Loophole
0.0%
0.0%
0.0%
0.0%
Comp. Time
0.02(0.1)
0.36(0.1)
0.01(0.0)
0.07(0.2)
Table Overview of results for all datasets, regions, and methods. For each dataset, include the number of regions audit ((S2), and the fraction of data points with fixed predictions (p).
Realized Loophole Rate: The fraction of total regions that are predicted to be confined but contain individuals with recourse in the test dataset.
Computation Time: The average computation time in seconds over all regions for each dataset.
As expected, the realized blindspot and loophole rates are lower than the true blindspot and loophole rate. Recourse verification over regions safeguards against rare events (i.e., new individuals with fixed predictions that were not part of the training dataset), which makes the risks less likely to be realized over small test dataset. However in real-world applications, models are typically deployed and make predictions datasets much larger than its original training dataset increasing the probability of blindspots and loopholes being realized.
Our extended results also highlight that our approach runs incredibly quickly across all three datasets, auditing region in under seconds on average. In two out three datasets, our approach is quicker than the Region which runs pointwise recourse on 100 data points.
23

---

Understanding Fixed Predictions via Confined Regions
F. On Out-of-Sample Robustness
Auditing recourse over regions, rather than individuals, allows practitioners to find individuals with fixed predictions beyond training dataset and robust to distribution shifts. We demonstrate this capability by considering realized blindspots, regions that are predicted be responsive but contain individuals with fixed predictions in the test distribution. We evaluate the performance of the Data baseline, which certifies recourse by looking at individuals within training dataset, in two regimes: (1) where the test distribution is the same as the train distribution of data, (2) where the train distribution is more likely to include individuals predicted to receive the desirable outcome. We simulate this distribution shift by training logistic regression classifier on the entire dataset that predicts the likelihood of receiving the desirable outcome. We then construct the training dataset by sampling individuals with a probability proportional to their predicted score in the linear classifier using a soft-max function with a temperature of 1. Figure 3 we plot the realized blindspot rate for the Data baseline in all datasets with and without distribution shift. Our results show that even under the same distribution the Data baseline can fail to catch instances of fixed predictions in the test dataset. This problem is further exacerbated by distribution shift, with the realized blindspot rate increasing across all three datasets. Note that by design ReVer has 0 realized blindspots because the regions themselves remain fixed under both train and test. Overall, these results highlight the importance of auditing regions as a tool to robustly foresee future fixed predictions, even under distribution shift.
Realized Blindspol Rate (%)
20
Same Dist.
Dist. Shift
10
heloc
givemecredit Dataset
bikterbol
Figure 3. Realized blindspot rate for Data baseline with and without distribution shift. Realized blindspot rate is the percentage of regions predicted to be responsive that contain individuals with fixed predictions in test dataset.
24

---

[0.1] Understanding Fixed Predictions via Confined Regions
G. Supplementary Material for Case Study on Pennsylvania SRAI
In this section we present all the actionability constraints for Pennsylvania SRAL. Note that feature space X' for this setting has the same upper and lower bounds as well as non-separable constraints as the action set. For this case study, we audit box region that contains any possible offender.
G.1. Actionability Constraints for the SRAT
We show list of all features and their separable actionability constraints in Table
Name
Type
LB
UB
Actionability
Sign
GenderMale
{0. 1
0
No
GenderFemale
[0.1 1
0
No
AgeUnder21:
{0. 1
0
No
Age21-25
[0.
No
Age26-29
[0. 1
O
No
Age30-39
{0, 1 O
No
Age40-49
(0, O
No
Age50+
(0. O
No
Curren::Convicciionirree
[0. O
Yes
[0. O
Yes
Currene:Coovdectiooorerrooosttt
00. O
Yes
Curreen:Convllltiionssxx-o.oooo
(0. 0
Yes
Currena:convl.ctlonsssss-iaaall
00. 0
Yes
Currenccconviicccioonnnnrgaayyyy
0. 0
Yes
00 0
Yes
[0.
Yes
00. 0
Yes
(0, 0
Yes
(0. 0
Yes
(0. 1 0
Yes
Currem::Conviicciiomiiieeeem
[0. 0
Yes
Currenn:coonvicciionntthee.
Weapons
[0. 0
Yes
Curreen:Coonviictiioootttttt
00. O
Yes
NumbrriorrCon/.tttiioosssoor
0. O
Yes
Numfrriorcconvictioons]]
0. O
Yes
humprriorcoovv.cttooo2223-
0. 1 O
Yes
humprioorconvicciooni--55
0.. 0
Yes
Numprriorcconricc:ionns--
0. 0
Yes
PriorConniictiioneeesssosssss
[0. 0
Yes
Pr:oorCnnvictiicntrropeyyyy
[0. 0
Yes
PriorConnv.cciicnDDrug
(0. 0
Yes
erioocCony..ctionpubll.oooo.
(0. 0
Yes
Priprtconvi.ciiombbbllccc..
[0. 0
Yes
PriorCoonvicticnnce1
[0.1 0
Yes
eriorConviectccuFFeeemmm
0
Yes
baltippleecrrrenttoovrrstt....
[0.1]
0
Yes
PriorUuvenlleedcjcciccct...
{0.1)
0
1
Yes
Table 8. Separable actionability constraints for the Pennsylvania SRAI.
The non-separable actionability constraints for this dataset include:
1. OneHonEncoding: Actions on [AgeUnder21, Age21-255 Age26-29, Age30 Age40-49, - Age50+] Age50 must preserve one-hot encoding of Age. Exactly of [AgeUnder21, Age21 -25, Age26-29 Age30-39, Age Age50+] must be TRUE
2. OneHotEncoding: Actions on [GenderMale, GenderFemale) must preserve one-hot encoding of Gender. Exactly of [GenderMale, GenderFemal must be TRUE
3. Actions on [Nmmrriorconv/.ctiiissbooo MumPrlorConvictiions22 Numproorcoovvittioose sumpr:oorcoovicctionns5)) must preserve one-hot encoding of NumPriorConvietions. Exactly
25

---

Understanding Fixed Predictions via Confined Regions
of [Numrrriorrommiiicioonnneeee Numpriorrcomvicttoors/// must be TRUE
3 NumP Numprioorconvictiioss--
4. LogicalConstraint: If NumP numpriiooooiiiiiinnnnnn is True then any PriorConviction) variable must be
False.
26


Reviews:
[{"review_id": "2jYIANv7po", "reviewer": "Reviewer_gp5S", "summary": "The paper  introduces a novel approach to identifying fixed predictions in machine learning models by finding confined regions where all individuals receive fixed predictions. The authors propose a method called ReVer, which uses mixed-integer quadratically constrained programming (MIQCP) to certify recourse for out-of-sample data and provide interpretable descriptions of confined regions. The paper emphasizes the importance of model responsiveness, especially in high-stakes settings like lending and hiring, and highlights the limitations of existing point-wise verification methods.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your time and feedback! We were excited to see you recognized that our paper “addresses a significant gap in the literature”, “highlights the limitations of existing approaches”, and validates our claims via “a comprehensive empirical study across various applications”.\n\nWe appreciate your comments and concerns, which have helped us to refine our paper. We would like to address them below:\n> The paper could provide more detailed explanations of the mathematical formulations and assumptions.\n> Providing more intuitive examples or visualizations of confined regions could help... readers better understand the topic..\nWe agree! We plan on using the additional page for a camera ready version to expand on the assumptions for theorem 3.1, and move some of the discussion of the REP (currently in the appendix) to the main body of the paper. If there are any specific formulations or assumptions that were too vague, or additional visualizations beyond Figure 1 that you think would be helpful please let us know!\n\n\n> How do you plan to extend ReVer to handle non-linear models or more complex classifiers? \n\nThanks for asking! Even though we focus on linear models, ReVer can work with **any MILP representable ML model** which includes decision trees, random forests, and even feed forward Neural Networks with ReLu activations (see [2] for more discussion). To adapt our framework, we just need to replace the linear classifier constraint (3a in the appendix, pg. 11) with constraints for the non-linear classifier. As an example, consider a one neuron neural network with weights beta, input x, and output v. We can model this as a MILP as follows (and replicate this for multiple neurons to embed an entire network):\n$$V \\geq \\beta^{\\top} x $$\n$$V \\leq  \\beta^{\\top} x - M(1 - z) $$\n$$V \\leq Mz $$\n$$V \\geq 0 $$\n$$z \\in {0,1} $$\n\nIn practice, modelling more complex ML models requires a lot of binary variables (e.g., z in the above example) which translates to a large number of continuous restrictions which could slow down the solve times of the MIQCP. If solving the MIQCP with all continuous restrictions is too demanding, we can always solve the linear relaxation with weaker guarantees: any confined box that ReVer returns is indeed confined, but ReVer cannot globally certify that a region is responsive (these nuances are discussed in Appendix D). To get global guarantees we would likely need to add some heavier duty optimization machinery to help tackle the large number of continuous restrictions (e.g., column and constraint generation). Our framework can also be used with local linear approximations of a more complex model (e.g., LIME).\n\n> Can you provide more insights into the computational complexity of ReVer compared to other methods?\n\nVerifying recourse for a single data point is itself an NP-hard problem. Similarly, the recourse verification over regions problem is NP-hard so we can’t expect any method with formal guarantees to run in polynomial time. In practice, MIQCPs are a bit harder to solve than MILPs (in our experiments solving one instance of ReVer takes about as long as solving 5 instances of pointwise verification). However, ReVer doesn’t scale with the number of data points to test, so it quickly outperforms pointwise verification in settings where we need to test more than a handful of data points. Detailed time comparison for all results are included in the supplementary materials.\n\n> How does ReVer handle cases where the actionability constraints are not well-defined or are subject to change? \n\nGreat question! ReVer, like most of the existing literature on algorithmic recourse, assumes we have access to accurate and well-defined actionability constraints. In our experiments we focus on inherent actionability constraints that are intrinsic to the features (e.g., Age can only increase), which are by definition well defined and unlikely to change. In settings where the actionability constraints are not well-defined, ReVer could be combined with an iterative system to elicit actionability constraints (e.g., adapt [1]). Another big benefit of our MIQCP framework is that its flexible enough to incorporate different notions of robustness to address actionability constraints/classifiers that may chance  (e.g., instead of requiring $w^T (x + a) \\geq 0$, we could replace 0 with a positive number to promote robustness). We’ll include this discussion in the revised draft.\n\nThanks again and please let us know if you have additional questions!\n\n[1] Holy grail 2.0: From natural language to constraint models. Tsouros et al., arXiv (2023) \n\n[2] Mixed-integer optimization with constraint learning. Maragno et al., Operations Research (2023)", "claims_and_evidence": "The authors claim that existing methods fail to discover confined regions and that ReVer can successfully identify these regions. They provide evidence through a comprehensive empirical study across various applications, demonstrating that ReVer can certify recourse and identify confined regions quickly and effectively. The paper also claims that ReVer is robust to distribution shifts and can be used without available datasets, which is supported by case studies and experiments.The authors claim that existing methods fail to discover confined regions and that ReVer can successfully identify these regions. They provide evidence through a comprehensive empirical study across various applications, demonstrating that ReVer can certify recourse and identify confined regions quickly and effectively. The paper also claims that ReVer is robust to distribution shifts and can be used without available datasets, which is supported by case studies and experiments.", "methods_and_evaluation_criteria": "The authors use MIQCP to develop ReVer, which identifies confined regions by verifying recourse over an entire region of the feature space. The evaluation criteria include the ability to certify responsiveness, identify confined regions, and run efficiently on real-world datasets. The authors compare ReVer to point-wise verification methods and evaluate its performance on datasets from consumer finance, content moderation, and criminal justice.", "theoretical_claims": "The paper presents theoretical claims about the ability of ReVer to certify recourse over entire regions and provide guarantees for out-of-sample data. The authors also discuss the theoretical underpinnings of their approach, including the use of Farkas' lemma to certify infeasibility and the conditions under which their method can relax discrete variables.", "experimental_designs_or_analyses": "The authors conduct experiments on three real-world datasets, evaluating ReVer's performance in terms of its ability to certify responsiveness and identify confined regions. They compare ReVer to point-wise baselines and analyze the results in terms of blindspots, loopholes, and computation time. The experiments demonstrate ReVer's effectiveness and efficiency in identifying confined regions and certifying recourse.", "relation_to_broader_scientific_literature": "NA", "essential_references_not_discussed": "NA", "other_strengths_and_weaknesses": "+\nThe paper addresses a significant gap in the literature by focusing on confined regions rather than individual data points.\nReVer is shown to be effective and efficient in identifying confined regions and certifying recourse.\nThe method is robust to distribution shifts and can be used without available datasets, making it applicable in various settings.\n\n-\nThe method is currently limited to linear classifiers, which may restrict its applicability to more complex models.\nThe paper could provide more detailed explanations of the mathematical formulations and assumptions.", "other_comments_or_suggestions": "The authors could explore extending ReVer to non-linear models or other types of classifiers.\nProviding more intuitive examples or visualizations of confined regions could help readers better understand the concept.", "questions_for_authors": "How do you plan to extend ReVer to handle non-linear models or more complex classifiers?\nCan you provide more insights into the computational complexity of ReVer compared to other methods?\nHow does ReVer handle cases where the actionability constraints are not well-defined or are subject to change?", "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": "UvmNV9LXWC", "reviewer": "Reviewer_6s3P", "summary": "This paper aims to identify regions where each point either allows recourse or does not allow recourse in the case of a linear model, given a fixed set of constraints.\n\nIn this specific case, the problem can be naturally formulated as a Mixed-Integer Quadratically Constrained Programming (MIQCP) problem. The authors also propose a solution for handling discrete variables more efficiently via Theorem 3.2 under some realistic assumptions.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your time and feedback! We appreciate you highlighting that “existing solutions appear to have failed to solve the problem of interest”, our experiments are “sound”, and that our proposed approach is “more effective [than existing approaches] for linear models”. \n\n> However, my main concern is that from the title through the beginning of the paper (Section 2), it is not explicitly mentioned that the proposed solutions apply specifically to linear models.\n\nThanks for flagging this! In the revised draft we’ve made sure to emphasize in the introduction and main contributions that this paper focuses specifically on linear models. We also want to highlight that our approach can be used for any MILP representable model but with weaker computational scaling (see discussion with Reviewer gp5s).\n\n> Please define more clearly the concept of a “fixed prediction” at the beginning of the paper—I struggled to fully grasp it until the formal definition was introduced. I recommend highlighting that the concept is tied to constraints or the action sets.\n\nThanks for the suggestion! We’ve added a more clear description of fixed description (taken from Section 2) to the introduction to make the concept more clear.\n\n> In the evaluation of the experiments, why restrict the feature space to fixed combinations? How many did you use in your experiments?\n\nWe restrict the feature space to fixed combinations of immutable features to represent sub-populations of interest (e.g., black female loan applicants). This also allows us to evaluate our approach on a number of different regions to provide more comprehensive experimental results (i.e., instead of one region per dataset). In our experiments we use between 20-715 regions (represented by $|\\Psi|$ in our results table). \n\nThanks again for the feedback - please let us know if you have any additional questions or concerns!", "claims_and_evidence": "All the claims presented in the paper are sound. However, my main concern is that from the title through the beginning of the paper (Section 2), it is not explicitly mentioned that the proposed solutions apply specifically to linear models.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "Yes.", "experimental_designs_or_analyses": "Yes, they are sound.", "relation_to_broader_scientific_literature": "Existing solutions appear to have failed to solve the problem of interest, although their applicability extends to general models. The paper clearly demonstrates that the proposed solution is more effective for linear models.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "N/A", "other_comments_or_suggestions": "Please define more clearly the concept of a “fixed prediction” at the beginning of the paper—I struggled to fully grasp it until the formal definition was introduced. I recommend highlighting that the concept is tied to constraints or the action sets.", "questions_for_authors": "In the evaluation of the experiments, why restrict the feature space to fixed combinations? How many did you use in your experiments?", "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": "Tx5RGTihil", "reviewer": "Reviewer_eTLW", "summary": "The paper proposes a method to check whether regions of input features are *responsive* (all individuals in the region have recourse), *confined* (all individuals have no recourse) or neither.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your time and feedback! We appreciate your comments about the paper, which we address below:\n\n> What pointwise method is used as baseline…\n\nWe solve a MILP to check whether a given data point has recourse (i.e., solve the REP for the given point x where B(u,l) = x). This can be viewed as an extension of AR [1] to handle more diverse actionability constraints. Note that this MILP provably verifies recourse (or its absence) so would provide the same response as [2], but runs much faster (<1s for the MILP vs. minutes for [2]). Any other recourse approach (e.g., DiCE [3]) would provide weaker guarantees than our baseline as they cannot formally verify recourse. We use this for pointwise verification and to compute p. We’ve clarified this in the new draft!\n\n> It is unclear throughout the text if they introduce a new method to verify recourse over regions or if they introduce the problem itself…\n\nThanks for pointing this out. The answer is both! This paper both introduces the problem of verifying recourse over regions and introduces the first method to solve it. We tried to articulate this in our introduction and the related work. We've revised these accordingly but let us know if it isn't clear and we can fix it.\n\n> The paper claims that their approach is fast but do not give enough evidence of comparison nor how the time would scale with regions or datapoints.\n\nWe compare the speed of our approach to pointwise baselines in Tab. 7 which shows that our approach runs in seconds on all three of our baseline datasets (which are in line, with respect to size, with existing work in recourse e.g., [1]- [3]). \nWe also think there might be a small misunderstanding - ReVeR is called once per region and so its computation time is independent of the number of data points and only scales with the dimension of the classifier which is an improvement over pointwise approaches which scale with the number of points. \n\n> I am unsure why Score is relevant for comparison…\n\nScore tests the point in the entire region (i.e., looks at the geometry of the region) with the highest/lowest score as opposed to any data sampled from the region. Consider a simple example of a 1D region $x \\in [0, 10]$. Score tests the points $x = 0$, $x = 10$ (which may not be present in any existing dataset), whereas Data only looks at available training data. We include Score to test the intuition that the ‘worse-off’ member of the region has to take the largest amount of action to change their prediction and thus is more likely to have a fixed prediction. We include additional discussion in the revised draft. \n\n> I am concerned about the experiment section only showing the results for one run of the experiment…\n\nWe think there’s been a misunderstanding! For each dataset we evaluate multiple regions (described on pg. 6) which represent different subgroups of interest in the dataset. The number of these regions varies from 20 to 715 in our datasets (see Tab. 3). One region corresponds to one instance of recourse verification problem (akin to a single data point in the pointwise setting). The computation times in Appendix E show avg. computation time over the regions (see line 1188). MIQCP solvers return the optimal solution for a given instance, so running each exp. multiple times would only show hardware variability in its comp. time. \n\n> The experiments also do not show results for changing the way the regions are calculated…\n\nWe weren't quite sure what you meant here. Regions are given as input into our problem. We generate regions by looking at combinations of immutable features to represent subgroups (e.g., black female loan applicants). What other ways did you have in mind? \n\n> I am concerned that some of them are key into understanding the paper and should be either added to the main text or better referenced in the main text.\n\nThanks for the suggestion! With the additional page in the camera ready version we’ll move some additional details on REP to the main paper. \n\n> Clarity, coherence and cohesion of the papers. The paper is unorganized (e.g. no subsections), information is sometimes repeated and key information is omitted. Giving the name when concepts are first mentioned in the introduction (RVP, ReVer...) would add a lot of clarity to the text .\n\nThanks for the suggestion! In the revised draft we introduce the name of the key terms in the intro. Our draft uses paragraph subheadings (bold text) to structure the text - in a final draft we could replace those with subsections. If there are specific instances of missing information that you'd like us to fix please let us know!\n\nThanks again, and please let us know if you have any additional questions.\n\n[1] Actionable Recourse in Linear Classification. Ustun et al. \n\n[2] Prediction without Preclusion: Recourse Verification with Reachable Sets. Kothari at al. \n\n[3] Explaining machine learning classifiers through diverse counterfactual explanations. Mothilal et al.", "claims_and_evidence": "- The authors claim that they “introduce a new approach to formally verify recourse over entire regions of the feature space”. It is unclear throughout the text if they introduce a new method to verify recourse over regions or if they introduce the problem itself. In any case, it should be better justified in the related work how this is novel. \n- In contributions, the paper also claims to evaluate their approach. I would reword this contribution, as evaluation is part of the process for justifying one’s approach. Using the sentence “pointwise verification approaches fail \\[…\\]” would fit more this part of the text. Anyways, I am concerned about how the evidence of this last claim because there is not enough evidence of what pointwise verification approaches they use (see Methods and Evidence, point 2.). \n- The paper claims that their approach is fast but do not give enough evidence of comparison nor how the time would scale with regions or datapoints.", "methods_and_evaluation_criteria": "- Regarding the strategies for generating data points for the baselines, I am unsure why *Score* is relevant for comparison (*Data* includes *Score*).  A discussion of how they all are relevant would be useful to compare approaches when discussing the results.  \n- What pointwise method is used as baseline i.e. how do you calculate if a point is a *fixed prediction*? How do does this differ from when you calculate the parameter of the dataset $p$?", "theoretical_claims": "I have not checked the correctness of the mathematical derivations", "experimental_designs_or_analyses": "- I have not reproduced their experiments.\n- I am concerned about the experiment section only showing the results for one run of the experiment. Several runs would add robustness to the claims. There is no evidence in the paper that the results have been run several times but in the Appendix E they show “average computation time”, which is needs several runs. This is confusing.\n- The experiments also do not show results for changing the way the regions are calculated. This would add soundness to the experiments.\n- I am also concerned that they have no baseline to compare with a purely region verification. Adding a synthetic experiment where they can calculate the closed-form results beforehand would add validity to the method (like what they did in Figure 1).", "relation_to_broader_scientific_literature": "The paper (apparently – see Claims and Evidence) proposes a new paradigm to verify recourse in the input feature space.", "essential_references_not_discussed": "Not sure.", "other_strengths_and_weaknesses": "-   Weaknesses\n\n    -   Clarity, coherence and cohesion of the papers. The paper is\n        unorganized (e.g. no subsections), information is sometimes\n        repeated and key information is omitted. Giving the name when\n        concepts are first mentioned in the introduction (*RVP*,\n        ReVer...) would add a lot of clarity to the text .\n\n    -   Would this approach work for more complex models? Is it possible\n        to see the results in such models?\n\n    -   See **Methods and evidence**\n\n    -   See **Experimental Designs or Analyses**\n\n-   Strengths\n\n    -   The paper proposes an original approach to recourse that could\n        be very useful due to their properties.", "other_comments_or_suggestions": "Citations are not in the usual ICML format, but I don't know whether that is a problem.", "questions_for_authors": "See Weaknesses.\n\nI would be willing to change my score if the paper is given more explicit structure and\nimproved clarity, coherence and cohesion (readability). Furthermore, all\nexperimental concerns would have to be addressed.", "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": "fVsWyvv791", "reviewer": "Reviewer_eC8e", "summary": "This paper introduces the ReVer method, designed to detect fixed predictions in machine learning models by identifying confined regions in the feature space. The approach involves formulating the Region Recourse Verification Problem (RVP), approximating confined regions using bounding boxes, generating confined bounding boxes, and verifying their confinement through the Farkas Certificate Problem (FCP). Experimental results demonstrate the method's effectiveness in accurately identifying confined regions.\n\n## update after rebuttal\nThe authors clarified that the key assumption underlying their method is generally valid in real-world scenarios(datasets), addressing my main concern. Thus, I maintain a positive rating.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your time and feedback! We really appreciate you highlighting that our work address a topic that is “impactful” where the “practicality [of our approach]is evident”, our MIQCP approach provides “strong theoretical guarantees”, and that our “experimental design is sound, encompassing diverse applications and selecting appropriate baselines” which “supports the papers’ claims”. \n\nWe also appreciate your comments and concerns which have helped us refine the paper, we address them below:\n> The inclusion of certain baseline methods mentioned in the Introduction, such as [22], could enhance the comprehensiveness of the study.\n\nWe solve a MILP to check whether a given data point has recourse (specifically we solve the REP for the given point x where B(u,l) = x). This can be viewed as an extension of AR [1] to handle more diverse actionability constraints, or a special case of Reach [2] tailored to linear models. Note that this MILP provably verifies recourse (or its absence) so would provide the same response as [2], but runs much faster (<1s for the MILP vs. minutes for [22]). Note that any other algorithmic recourse approach (e.g., DiCE [3]) would only provide weaker guarantees than this baseline as they cannot formally verify recourse. We use this approach for both our pointwise verification, as well as to compute p (i.e., by running the approach on the entire dataset). We’ve clarified this in the revised draft!\n\n> The performance under varying parameter dimensions remains unclear. It is uncertain whether the proposed method consistently outperforms baselines as (linear) model scales.\n\nGreat point! In our paper we benchmark our approach on standard datasets in the algorithmic recourse community (e.g., from [1], [2]) which capture realistic parameter distributions. We expect our approach to actually improve more over baseline approaches as the dimensionality of the data increases. For some intuition, as the dimension increases, the odds of having data (or generating samples) that cover the entire region decreases (more space to cover!). In practice, this means blindspots are more likely to occur. We see this in our experimental results where the baselines perform the worst on heloc, which has the largest dimensionality.\n\n> How does restricting the response variable y to binary values influence the problem formulation? Can the method generalize to cases where y has $N \\geq 2$  values? For instance, if transitions between undesired outcomes exist under certain actions but no action leads to the desired outcome, is this still a fixed prediction?\n\nThanks for asking! Recourse is generally defined as having a ‘desired outcome’ (e.g., loan is accepted) which naturally defines a binary problem (‘desired outcome’ vs. not) even if y has multiple values. With this definition in mind, transitions between undesired outcomes but no action leading to the desired outcome would count as a fixed prediction. \n\n> In Figure 1, is the range of x_1 [0,5) or [0,5]?\n\nThanks for catching this typo! The range of x_1 should be [0,5). \n\n> On Line 220, the authors claim, \"a box is confined if and only if every continuous restriction of the REP is infeasible.\" Could you clarify the insight behind this conclusion?\n\nRecall that a continuous restriction is a ‘smaller’ version of the original MILP where all discrete variables have been fixed to a specific value (e.g., leaving just a continuous problem). If a box is confined, that means that there is no data point that has recourse - this implies that whatever ways we fix the discrete variables in the REP (e.g., setting elements of x and a) the resulting continuous problem has to be infeasible (otherwise we have found a contradiction to the box being confined). Similarly in the reverse direction, if there is a specific continuous restriction that is feasible then we can use the solution to the continuous restriction to find a data point with recourse in the region (proving the box isn’t confined). We’ve added an extra sentence explaining this in the revised draft.\n\n> For discrete variables, the method relies on assumptions of linear recourse constraints. Were these assumptions met in the experiments (Section 4) and case study (Section 5)?\n\nAlmost! The case study, twitterbot, and givemecredit datasets meet all the assumptions for linear recourse constraints. The heloc dataset does not, but we can provably certify recourse by only considering 4 continuous restrictions in the RVP. We go into this in greater depth in Appendix D in the supplementary materials. \n\nThanks again for your time and feedback! Please let us know if you have any additional questions.\n\n[1] Actionable Recourse in Linear Classification. Ustun et al. ACM FAT* (2019)\n\n[2] Prediction without Preclusion: Recourse Verification with Reachable Sets. Kothari at al. ICLR (2025)\n\n[3] Explaining machine learning classifiers through diverse counterfactual explanations. Mothilal et al. FAccT (2020).", "claims_and_evidence": "- The claim that “The existing point-wise verification methods fail to discover confined regions” is supported by the experimental results of baselines in Section 4.\n- The claim that “The proposed ReVer method is able to verify and find confined regions ” is supported by the introduced theoretical guarantees based on Farkas’ lemma and experimental evidence.\n- The claim that “The proposed ReVer method enables data-free auditing, suitable for privacy-sensitive scenarios” is supported by the case study on the SRAI.", "methods_and_evaluation_criteria": "The proposed method and evaluation criteria are well-aligned with the defined problem and application scenarios. The approach effectively addresses the fixed prediction issue, while the datasets and evaluation metrics adequately validate its performance.", "theoretical_claims": "I have not verified the correctness of the theoretical claims presented in the paper as I am not familiar with the used techniques.", "experimental_designs_or_analyses": "The experimental design is sound, encompassing diverse applications and selecting appropriate baselines, and the results support the paper’s claims. Additionally, the SRAI case study highlights the method's practicality in scenarios with unavailable data. However, the experiments may lack analysis of varying model complexities, such as the dimensionality of feature spaces (coefficients $w$).", "relation_to_broader_scientific_literature": "Building on existing work in algorithmic recourse, this paper pioneers a region-level rather than individual-level perspective on recourse verification, addressing a gap in region-level recourse analysis. Besides, unlike prior studies focusing more on action spaces, this work targets confined regions in the feature space.", "essential_references_not_discussed": "The paper thoroughly discusses previous work and delineates distinctions. While no critical references seem to be missing, the possibility of omissions cannot be entirely ruled out as I am not very familiar with this topic.", "other_strengths_and_weaknesses": "**Strengths**:\n- S1: The topic is impactful, addressing potential blind spots and loopholes in real-world scenarios.\n- S2: The introduction of Farkas Certificate Problem (FCP) and Mixed Integer Quadratically Constrained Programming (MIQCP) tools provides strong theoretical guarantees.  \n- S3- Practicality of the method is evident, especially in \"detecting harms before deployment\" and \"data-free auditing.\"  \n\n**Weaknesses**:\n- W1: The inclusion of certain baseline methods mentioned in the Introduction, such as [22], could enhance the comprehensiveness of the study.\n- W2: The performance under varying parameter dimensions remains unclear. It is uncertain whether the proposed method consistently outperforms baselines as (linear) model scales.", "other_comments_or_suggestions": "Missing punctuation in sentences and formulas, e.g., Line 145. Please review thoroughly.", "questions_for_authors": "**Questions**:\n- Q1: How does restricting the response variable $y$ to binary values influence the problem formulation? Can the method generalize to cases where $y$ has $N \\geq 2$ values? For instance, if transitions between undesired outcomes exist under certain actions but no action leads to the desired outcome, is this still a fixed prediction?  \n- Q2: In Figure 1, is the range of $x_1$ $[0, 5)$ or $[0, 5]$?  \n- Q3: On Line 220, the authors claim, \"a box is confined if and only if every continuous restriction of the REP is infeasible.\" Could you clarify the insight behind this conclusion?  \n- Q4: For discrete variables, the method relies on assumptions of linear recourse constraints. Were these assumptions met in the experiments (Section 4) and case study (Section 5)?", "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:

Meta-review: This paper provides a new optimization method to certifiably identify regions where all individuals receive the same prediction from the model, where existing methods operate point-wise. The reviewers all found this a valuable contribution to the literature on recourse. The main weakness is that the optimization framework relies on being able to embed the predictive into a MILP. The existing paper focuses on linear models and it essential that the authors emphasize this heavily in the abstract/introduction. The authors point out that it is possible to embed various nonlinear kinds of models into a MILP but that the resulting problem may become computationally intractable to solve (although weaker guarantees can be obtained from the LP relaxation). In my mind, the paper would be a clear accept with a demonstration that some meaningful results could be obtained in the nonlinear case. As it is, the paper still makes a solid contribution as long as the important caveat of focusing on linear models is acknowledged more explicitly.
Decision: Accept (poster)