Paper deep dive
Algorithmic Recourse Under Competition
Shahin Jabbari
Intelligence
Status: not_run | Model: - | Prompt: - | Confidence: 0%
Entities (0)
Relation Signals (0)
No relation signals yet.
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:Algorithmic recourse provides individuals who have received undesirable outcomes from machine learning models with suggestions for minimum-cost improvements to achieve the desired outcome. A central assumption when computing recourse is that the decision rule remains fixed throughout the recourse implementation phase. We challenge this assumption in settings where individuals compete for limited resources. In such settings, widespread recourse implementation can change the acceptance threshold even when the scoring model that is used to evaluate individuals remains the same. This change in acceptance threshold can, in turn, invalidate the original recourse recommendations (i.e., following the recourse may not lead to the desired outcome). To address this problem, we introduce a framework called recourse under competition that jointly optimizes for recommendation recipients and the recommended score target they need to satisfy to balance the recourse cost and post-shift validity among initially rejected individuals. We develop an algorithm based on the Implicit Function Theorem and empirically analyze its performance. Experiments on synthetic and real datasets show that personalized score targets can achieve higher validity, albeit at a higher cost. In contrast, common score targets generally offer favorable cost-validity trade-offs for lower to medium validity values.
Tags
Links
- Source: https://arxiv.org/abs/2609.39877v1
- Canonical: https://arxiv.org/abs/2609.39877v1
Trouble viewing inline? Open PDF directly →
Full Text
66,770 characters extracted from source content.
Expand or collapse full text
Algorithmic Recourse Under Competition Shahin Jabbari †thanks: Drexel University, shahin@drexel.edu Abstract Algorithmic recourse provides individuals who have received undesirable outcomes from machine learning models with suggestions for minimum-cost improvements to achieve the desired outcome. A central assumption when computing recourse is that the decision rule remains fixed throughout the recourse implementation phase. We challenge this assumption in settings where individuals compete for limited resources. In such settings, widespread recourse implementation can change the acceptance threshold even when the scoring model that is used to evaluate individuals remains the same. This change in acceptance threshold can, in turn, invalidate the original recourse recommendations (i.e., following the recourse may not lead to the desired outcome). To address this problem, we introduce a framework called recourse under competition that jointly optimizes for recommendation recipients and the recommended score target they need to satisfy to balance the recourse cost and post-shift validity among initially rejected individuals. We develop an algorithm based on the Implicit Function Theorem and empirically analyze its performance. Experiments on synthetic and real datasets show that personalized score targets can achieve higher validity, albeit at a higher cost. In contrast, common score targets generally offer favorable cost-validity trade-offs for lower to medium validity values. 1 Introduction With the rapid deployment of machine learning models in critical domains and the major impact of their decisions on people’s livelihoods, a surge of recent work in responsible machine learning aims to make these models fair [5, 3, 64, 23], transparent [52, 38], and explainable [51, 42, 55]. A recent line of work within the explainability literature, termed algorithmic recourse [62, 59], involves the decision-maker providing individuals who received an undesirable label (e.g., one whose loan request was denied) with minimum-cost improvement suggestions to achieve the desired label. A central assumption when computing recourse is that the decision rule remains fixed during the time needed for individuals to implement their modifications. However, this assumption can fail in settings where individuals compete for limited resources, and only a limited number or fraction of individuals can be accepted (e.g., a fixed number of approved loans or university admissions). As individuals implement recourse, they alter the population’s distribution. To maintain the acceptance rate dictated by limited resources, the decision-maker recomputes the acceptance threshold for the updated population, even when its scoring model remains unchanged. The updated threshold can invalidate the initially prescribed recourse, i.e., following the suggestions may no longer lead to the desired outcome. Prior work has shown reaching the original acceptance threshold is insufficient to ensure acceptance under competition [16]. This motivates designing recourse recommendation strategies that explicitly anticipate the competition induced by their implementation. In this work, we propose recourse under competition, a framework that explicitly anticipates future updates in acceptance threshold in competitive environments. In this formulation, the individuals are restricted by a budget for their feature modification, and the decision-maker simultaneously should decide which individuals should be instructed to implement recourse and what score target each such individual should aim for. Our main goal is to understand the trade-off between the expected recourse cost across the population of rejected individuals against the validity of recourse, after accounting for distribution changes and acceptance threshold updates caused by recourse implementation. Our Results and Contributions. We formalize recourse under competition, a framework for balancing recourse cost and post-shift validity through population-level recommendation policies. We develop an optimization algorithm based on the Implicit Function Theorem that anticipates future updates in the selection threshold when recommending recourse. We evaluate our algorithm on four real datasets and two synthetic datasets to study the trade-off between the cost of recourse implementation and its validity after competitive threshold updates. We observe empirical convergence of the smooth training objective across different datasets and model classes. Our main findings indicate that anticipating recourse-induced threshold changes can significantly improve the validity of recourse compared to the original-threshold baseline that do not consider competition when providing recourse. We also find that personalized score targets can achieve higher validity at greater cost, while common score targets often offer better tradeoffs at lower to medium validity values. Sensitivity experiments show that larger budgets and admission rates generally increase validity. We also study the effect of these selected policies on the distribution of recourse cost and targets across populations and their disparities across subpopulations. 2 Related Work Algorithmic Recourse. Recourse is a post-hoc counterfactual explanation that aims to provide the lowest-cost modification that changes the prediction for a given input with an undesirable predicted label under the current model [62, 59]. Since its introduction, different formulations have been used to model the optimization problem in recourse [41, 50, 54, 46, 18, 29, 30, 28, 6, 61, 10] or study additional aspects such as fairness [19, 21, 24, 17, 7, 49], repeated dynamics [16, 4, 14], improvement [35, 2, 36], effects of temporal data [8] and potential harms [15]. See [60, 31] for surveys. Wachter et al. [62] and Pawelczyk et al. [46] focus on score-based classifiers, generating feature modifications that help individuals attain a target score. In contrast, Ustun et al. [59] addresses binary classifiers and requires that recourse actions lead to a change in the predicted label. Conceptually, the score-based formulation can be viewed as a relaxation of the label-based setting. We also adopt a score-based formulation in our work subject to a recourse budget. Our main point of departure from all these works is that we optimize recourse at the population level by simultaneously considering the effect of recourse on all individuals. Robust Recourse. Although most prior work assumes a static setting, several recent works have focused on robustness under uncertainty about the data or the classifier. Upadhyay et al. [58] and Nguyen et al. [45] propose recourse mechanisms that remain effective under model shift induced by distributional shift. Guo et al. [20] introduces a robust training procedure that jointly trains the classifier and a recourse model under data shifts. Similar to algorithmic recourse, many different variations and formulations of robust recourse have also been proposed (see, e.g., [39, 63, 44, 13, 11, 37, 32, 57] and [27] for a survey). Our setting considers a different source of recourse invalidation: recommendations change the applicant population and thereby the capacity-constrained acceptance threshold, even though the scoring function remains fixed. Recourse Over Time with Limited Resources. Several works studied the temporal dynamics of recourse by analyzing how recourse recommendations change over time in settings where individuals repeatedly interact with a decision-making system under resource constraints [16, 56, 40, 1]. Segal et al. [53] modeled limited resources using a 0/1 knapsack formulation. Ceccon et al. [9] formulated the long-term effects of recourse and resource limitations as a partially observable MDP. Conceptually, the closest related work models collective recourse through penalties for population congestion [14] or through capacitated matching between applicants and providers [33]. Direct comparison to these works is difficult due to different modeling choices. Performative Prediction. Perdomo et al. [47] introduced performative prediction, where predictions affect behavior; the data distribution can shift in response, making it hard to train a model that performs well after a distribution shift. They show that standard empirical risk minimization may fail when the model deployment changes the data generation process. They distinguish between two key notions: performative optimality, where a model minimizes empirical loss on the distribution it induces, and performative stability, where the selected model matches the model induced by the deployment. They provided algorithms to compute performatively stable points and sufficient conditions for their existence. They also show that performatively optimal points are in a close neighborhood of performatively stable points. These algorithms were later extended to compute performatively optimal solutions under specific assumptions on the input distributions [25, 26]. Building on this, Mendler-Dünner et al. [43] propose methods to anticipate performative shifts by learning to predict from predictions, offering stability-aware model selection strategies [34, 48]. Through a causality lens, König et al. [36] study sufficient conditions under which recourse remains valid after performativity. See [22] for a survey. Our objective shares the performative perspective of evaluating a policy under the distribution it induces, though our models do not satisfy the strong convexity and smoothness assumptions that are commonly used in the performative prediction literature. 3 Problem Formulation Let ⊆ℝdX ^d be the instance space representing individuals. Let D be an unknown population distribution. An unknown ground-truth function f∗:→[0,1]f^*:X→[0,1] determines the qualification of individuals. The decision-maker can learn a proxy for f∗f^* by performing empirical risk minimization using a parameterized hypothesis class ℱ=fw:→[0,1]∣w∈⊆ℝnF=\f_w:X→[0,1] w ^n\: w0∈argminw∈x∼D[ℓerm(fw(x),f∗(x))],w_0∈ _w E_x D\! [ _erm (f_w(x),f^*(x) ) ], (1) where ℓerm _erm is a convex loss function. Throughout, we refer to fw0f_w_0 as the scoring function. Individuals compete for a resource that can be allocated to an α∈(0,1)α∈(0,1) fraction of the population. Assume the initial score distribution is continuous. The decision-maker determines the initial allocation by selecting the highest-scoring α fraction, with threshold t0=inft∈[0,1]:ℙx∼D[fw0(x)≥t]≤αt_0= \t∈[0,1]:P_x D[f_w_0(x)≥ t]≤α \ (2) and the decision rule y^0(x)=[fw0(x)≥t0]. y_0(x)=I[f_w_0(x)≥ t_0]. (3) Let X−=x:y^0(x)=0X^-=\x: y_0(x)=0\ and X+=x:y^0(x)=1X^+=\x: y_0(x)=1\ denote the initially rejected and accepted individuals, respectively. Algorithmic recourse recommends feature modifications intended to improve an individual’s outcome [62, 59]. Let c:×→ℝ+c:X×X _+ denote a cost function for feature modification that satisfy c(x,x)=0c(x,x)=0, and let B≥0B≥ 0 be a common recourse budget.11 1 Individual-specific budgets can be accommodated in the same way. Unlike most prior work that provides recourse at an individual level, we focus on recourse at the population level. In a population-level recourse policy, the decision-maker not only provides a target score for each individual to achieve but also recommends whether this recommendation should be implemented or not. More formally, the population-level recourse policy consists of two measurable functions: q:→[t0,1],ρ:→0,1.q:X→[t_0,1], ρ:X→\0,1\. (4) The target q(x)q(x) specifies which score an individual should attain; ρ(x)=1ρ(x)=1 means that recourse is recommended (to be implemented), and ρ(x)=0ρ(x)=0 means the recourse is not recommended.22 2 We assume every recommended response is implemented. For x∈X−x∈ X^- whose target is feasible within budget, define the best response as br(x,q) (x;q) ∈argminx′∈c(x,x′) ∈ _x c(x,x ) s.t. fw0(x′)≥q(x),c(x,x′)≤B. f_w_0(x )≥ q(x),c(x,x )≤ B. (5) We assume a minimizer exists whenever the constraints are feasible. For infeasible targets and initially accepted applicants, we set br(x,q)=xbr(x;q)=x and require ρ(x)=0ρ(x)=0. In particular, initially rejected applicants who cannot reach the initial target of t0t_0 within budget always receive no recommendation. Among the remaining rejected applicants, the decision-maker chooses ρ(x)ρ(x), subject to recommending only feasible targets. The pair (q,ρ)(q,ρ) induces the recourse map r r(x)=br(x,q),ifρ(x)=1,x,ifρ(x)=0.r(x)= casesbr(x;q),&if ρ(x)=1,\\ x,&if ρ(x)=0. cases (6) Thus br(x,q)br(x;q) is the candidate response to the target, whereas r(x)r(x) is the individual’s resulting feature vector post-recourse. The recourse policy can impose the following situations: 1. A common target: q(x)=qcq(x)=q_c for all x∈X−x∈ X^-, with ρ(x)=1ρ(x)=1 exactly for rejected applicants who can reach the target qcq_c. Only the scalar qc∈[t0,1]q_c∈[t_0,1] is optimized. 2. Personalized targets without selection: q is optimized and ρ(x)=1ρ(x)=1 for any rejected applicant who can reach their corresponding target q(x)q(x). 3. Personalized targets with selection: both q and ρ are optimized as functions of applicant features. In particular, setting q(x)=t0q(x)=t_0 and recommending recourse to every feasible rejected applicant recovers minimum-cost recourse to the original threshold as studied in prior work [16]. Implementing recourse will change the distribution of individuals. Let DrD_r denote the distribution of r(x)r(x) for x∼Dx D. We assume the (post-recourse) qualification can still be assessed through the ground truth function f∗f^* as formally stated below. Assumption 1 The qualification function f∗f^* is invariant to population composition. Recourse may change f∗(x)f^*(x) to f∗(r(x))f^*(r(x)), but does not change the relationship between resulting features and qualification. Given that the distribution of individuals can change after recourse, the decision-maker should update its threshold to satisfy the capacity constraint: t1(r)=inft∈[0,1]:ℙx′∼Dr[fw0(x′)≤t]≥1−α.t_1(r)= \t∈[0,1]:P_x D_r[f_w_0(x )≤ t]≥ 1-α \. (7) Note that since we assumed f∗f^* is unchanged, the decision-maker still utilizes fw0f_w_0 to set the acceptance threshold. Recourse can create positive probability mass at a target score. When the cutoff threshold t1(r)t_1(r) has positive mass, define βr=α−ℙx′∼Dr[fw0(x′)>t1(r)]ℙx′∼Dr[fw0(x′)=t1(r)], _r= α-P_x D_r[f_w_0(x )>t_1(r)]P_x D_r[f_w_0(x )=t_1(r)], (8) as the fraction of individuals with score t1(r)t_1(r) that can be selected without violating the capacity constraint. Otherwise set βr=0 _r=0. For a uniform random variable U∼Unif[0,1]U [0,1], independent of the applicant and drawn after recourse, the future allocation rule is y^1r(x′;U)=[fw0(x′)>t1(r)]+[fw0(x′)=t1(r)][U≤βr]. y_1^r(x ;U)=I[f_w_0(x )>t_1(r)]+I[f_w_0(x )=t_1(r)]I[U≤ _r]. (9) This rule gives the population acceptance probability α, after randomization at the threshold t1(r)t_1(r). For the recourse map r induced by (q,ρ)(q,ρ), define post-shift validity V and expected cost C over all initially rejected individuals as V(q,ρ) V(q,ρ) =ℙx∼D,U[y^1r(r(x),U)=1|x∈X−], =P_x D,\,U\! [ y_1^r(r(x);U)=1\, |\,x∈ X^- ], (10) C(q,ρ) C(q,ρ) =x∼D[c(x,r(x))|x∈X−]. =E_x D\! [c(x,r(x))\, |\,x∈ X^- ]. (11) These definitions include individuals receiving no recommendation and costs incurred by those whose recourse does not lead to acceptance. Let P be the chosen family of measurable pairs (q,ρ)(q,ρ). For a fixed λ>0λ>0, the decision-maker aims to optimize the following objective: (q∗,ρ∗)∈argmin(q,ρ)∈C(q,ρ)−λV(q,ρ).(q^*,ρ^*)∈ _(q,ρ) \C(q,ρ)-λ V(q,ρ) \. (12) The parameter λ weights validity relative to cost; it does not impose a prescribed minimum validity. We can study the trade-off between validity and cost by varying λ and solving the optimization problem in Equation (12) for each λ. 4 Our Algorithm Optimizing Equation (12) is difficult because recommendations change the competitive threshold, and both acceptance and the binary recommendation decision ρ are discontinuous. Our main algorithmic idea is to use smooth surrogates for q and ρ, smooth the acceptance threshold, and apply the Implicit Function Theorem (IFT) to differentiate through the resulting competitive threshold. As is common, we assume a sample S=x1,…,xNS=\x_1,…,x_N\ of size N drawn independently from D and optimize empirical averages instead of expectations. Throughout this section, we assume the scoring model fw0f_w_0 is learned beforehand using the empirical counterpart of Equation (1) on a labeled sample. That supervised formulation assumes qualification labels f∗(x)f^*(x) are available for score training. We discuss how we learn this function from data in more detail in Section 5. The recourse sample S requires only features. The model fw0f_w_0 and initial threshold t0t_0 remain fixed during recourse optimization. Let k=⌊αN⌋k= α N and use this threshold to select the acceptance threshold of fw0f_w_0 such that only k individuals are selected by fw0f_w_0. Let S−S^- denote the rejected individuals. We assume |S−|>0|S^-|>0 and 1≤k<N1≤ k<N. For each rejected applicant, we precompute q¯(x)=maxx′∈:c(x,x′)≤Bfw0(x′), q(x)= _x :\,c(x,x )≤ Bf_w_0(x ), (13) assuming the maximum is attained. In words, q¯(x) q(x) is the highest score achievable by individual x under fw0f_w_0 within budget B. We refer to an individual x as eligible if x∈X−x∈ X^- and q¯(x)≥t0 q(x)≥ t_0, i.e., a rejected individual who can at least reach the initial threshold. Let σ(z)=(1+e−z)−1σ(z)=(1+e^-z)^-1 denote the sigmoid function. We estimate q and ρ using smooth surrogates of the form q^θ1(x)=t0+(q¯(x)−t0)σ(gθ1(x)), q_ _1(x)=t_0+( q(x)-t_0)σ (g_ _1(x) ), (14) and ρ^θ2(x)=σ(hθ2(x)) ρ_ _2(x)=σ (h_ _2(x) ) (15) for eligible applicants. The functions gθ1g_ _1 and hθ2h_ _2 are twice continuously differentiable in their respective parameters on neighborhoods of Θ1⊆ℝm1 _1 ^m_1 and Θ2⊆ℝm2 _2 ^m_2. We assume each parameter set is nonempty, compact, and convex. The estimate q^θ1 q_ _1 is feasible by construction and can be used to compute the best response br(x,q^θ1)br(x; q_ _1) using Equation (5). For ineligible applicants, including initially accepted individuals, we set q^θ1(x)=t0 q_ _1(x)=t_0, ρ^θ2(x)=0 ρ_ _2(x)=0, and br(x,q^θ1)=xbr(x; q_ _1)=x. ALGORITHM 1 Recourse under Competition Input: Sample S of individuals; fixed model fw0f_w_0; budget B; selection rate α; initial threshold t0t_0; parametric functions g and h; weight λ>0λ>0; temperature τ>0τ>0; learning rate η>0η>0; iterations T. Output: Selected target function q and binary recommendation function ρ. 1: Randomly initialize θℓ(1)∈Θℓ _ ^(1)∈ _ for ℓ∈1,2 ∈\1,2\. 2: Let k=⌊αN⌋k= α N and compute S−S^-. 3: Precompute q¯ q using Equation (13) and determine eligibility. 4: for j=1,…,Tj=1,…,T do 5: For each eligible xi∈Sx_i∈ S, evaluate q^θ1(j)(xi) q_ _1^(j)(x_i) and ρ^θ2(j)(xi) ρ_ _2^(j)(x_i) using Equations (14) and (15). 6: For each eligible xi∈Sx_i∈ S, compute the best response using Equation (5). 7: Form ai(t,θ1(j),θ2(j))a_i(t, _1^(j), _2^(j)) for all i=1,…,Ni=1,…,N using Equation (17). 8: Solve Equation (18) by bisection to obtain t t. 9: Compute the full gradients of Equation (19) at the current iterate, differentiating through the best responses and using the IFT-based threshold derivative in Equation (20). 10: Update both parameter vectors by a gradient step with learning rate λ: θℓ(j+1)=ΠΘℓ(θℓ(j)−η∇θℓJ^(θ1(j),θ2(j))),ℓ∈1,2, _ ^(j+1)= _ _ \! ( _ ^(j)-η _ _ J( _1^(j), _2^(j)) ), ∈\1,2\, (16) where ΠΘℓ _ _ denotes Euclidean projection. 11: end for 12: Set q(x)=q^θ1(T)(x)q(x)= q_ _1^(T)(x) and ρ(x)=[ρ^θ2(T)(x)≥1/2]ρ(x)=I[ ρ_ _2^(T)(x)≥ 1/2], 13: return q and ρ. We use ρ ρ to form a differentiable relaxation of recommendation decisions. Let τ>0τ>0 be a temperature parameter. During training, we mix the smoothed acceptance outcomes of no action and the complete best response, with respective weights 1−ρ^θ2(x)1- ρ_ _2(x) and ρ^θ2(x) ρ_ _2(x), defined formally as: a(t,θ1,θ2)=(1−ρ^θ2(x))σ(fw0(x)−tτ)+ρ^θ2(x)σ(fw0(br(x;q^θ1))−tτ).a(t, _1, _2)= (1- ρ_ _2(x) )σ\! ( f_w_0(x)-tτ )\\ + ρ_ _2(x)σ\! ( f_w_0(br(x; q_ _1))-tτ ). (17) Thus, a averages outcomes rather than feature changes. It should be treated as an approximation that our algorithm uses in training, not the acceptance probability of the final binary policy we are aiming to compute. The temperature parameter τ controls how sharply training approximates the acceptance threshold. For small τ, acceptance changes sharply near the threshold t. This resembles the actual decision rule, but gradients become concentrated around the threshold. For large τ, acceptance changes gradually over a wider score range. This provides broader gradient signals but is a less accurate approximation of hard acceptance. Define t^=t^(θ1,θ2) t= t( _1, _2) as the unique real solution of ∑i=1Nai(t^,θ1,θ2)=k. _i=1^Na_i( t, _1, _2)=k. (18) Note that the sum includes all applicants because initially accepted individuals continue to compete for the resource. Using the quantities we defined so far, we obtain the following smooth empirical approximation of Equation (12): J^(θ1,θ2)=1|S−|∑i∈S−[ρ^θ2(xi)c(xi,br(xi;q^θ1))−λai(t^,θ1,θ2)], J( _1, _2)= 1|S^-| _i∈ S^- [ ρ_ _2(x_i)c (x_i,br(x_i; q_ _1) )-λ a_i( t, _1, _2) ], (19) where λ>0λ>0 is fixed as in the formulation. Before stating our algorithm, we make the following response regularity assumption. Assumption 2 For every xi∈Sx_i∈ S, the maps θ1↦fw0(br(xi;q^θ1)) _1 f_w_0(br(x_i; q_ _1)) and θ1↦c(xi,br(xi;q^θ1)) _1 c(x_i,br(x_i; q_ _1)) are twice continuously differentiable on a neighborhood of Θ1 _1. Algorithm 1 alternates between computing targets and best responses, recalibrating the competitive threshold, and updating both parameter vectors. Updating θ1 _1 changes targets and best responses; updating θ2 _2 changes recommendation weights through Equations (14) and (15). Neither output is updated independently for each applicant. Under Assumption 2, the left-hand side of Equation (18) is continuously differentiable and has a strictly negative derivative with respect to t. Therefore, the IFT ensures that t t is differentiable in the policy parameters and gives ∇θℓt^=−∑i=1N∂θℓai(t^,θ1,θ2)∑i=1N∂tai(t^,θ1,θ2),ℓ∈1,2. _ _ t=- _i=1^N _ _ a_i( t, _1, _2) _i=1^N _ta_i( t, _1, _2), ∈\1,2\. (20) Here ∂θℓ _ _ holds the threshold fixed. The denominator is strictly negative. Full gradients of Equation (19) include differentiation through the best responses and this threshold dependence. After T rounds, the algorithm uses the learned weights θ1(T) _1^(T) to form the estimate for q q. The learned weight θ2(T) _2^(T) form estimates for ρ ρ which will get converted to binary decisions by thresholding. 5 Experiments In this section, we empirically evaluate our algorithm on synthetic and real datasets. We describe our datasets in Section 5.1, our implementation details in Section 5.2, and our findings in Section 5.3. Our code is available here. 5.1 Datasets The experiments use four real datasets (Adult, German Credit, ACSIncome, and Give Me Some Credit) and two synthetic populations. All real datasets are publicly available, and our code provides details on where the dataset is downloaded from. Adult and ACSIncome predict whether income exceeds $50,000; ACSIncome uses the 2018 California sample [12]. German Credit classifies credit risk, and Give Me Some Credit predicts serious delinquency within two years. Favorable labels correspond to high income, good credit, and no serious delinquency, respectively. We generate two synthetic populations. Each synthetic population contains 6,0006,000 three-dimensional Gaussian observations with pairwise correlation 0.50.5 and a known nonlinear qualification function. Synthetic Nonlinear uses a sinusoidal interaction in the logit, while Synthetic Curved uses a concave quadratic logit. Preprocessing replaces missing numerical values with the corresponding feature median and missing categorical values with their most frequent category. Numerical features are standardized to zero mean and unit variance, and categorical features are one-hot encoded. Synthetic features retain their generated scale. For each dataset, we divide the features into two sets: mutable features and immutable features. Immutable features remain inputs to the scoring function and recourse policy, but their encoded coordinates cannot change during recourse generation. For the synthetic dataset, we designated the first coordinate to be immutable in both populations. Table 1 provides a summary of datasets and the number of features before and after preprocessing. Dataset Size Raw features Processed features Adult 48,842 14 104 German Credit 1,000 20 61 Give Me Some Credit 150,000 10 10 ACSIncome 195,665 10 666 Synthetic Nonlinear 6,000 3 3 Synthetic Curved 6,000 3 3 Table 1: Summary of dataset statistics. 5.2 Implementation Details The data is split into 30%30\% for model fitting, 30%30\% for policy training, 20%20\% for validation, and 20%20\% for testing. Model fitting learns fw0f_w_0, policy training runs Algorithm 1, validation selects policy checkpoints and baseline candidates (as we will describe shortly), and testing evaluates the generalizability of selected policies on unseen samples. These are held-out splits, not cross-validation; the experimental parameter grids are specified separately below. We repeat this process 5 times using seeds 42,43,44,45,46\42,43,44,45,46\ with matched data and policy We report average values and error bars (when applicable) in all experiments. For the synthetic datasets, the ground-truth qualification scores are generated by our simulator and hence are known. For real datasets, we learn the qualification scores from the binary-labeled dataset and treat these learned scores as ground-truth. The learned proxy is trained on the observed binary outcomes using binary cross-entropy: a tanh network with two hidden layers (of size (32,16)(32,16)) and a sigmoid activation function for the output. We train the proxy using the Adam optimizer, early stopping on an internal 10%10\% holdout of the model-fitting partition, and at most 1,5001,500 epochs. We learn two scoring rules fw0f_w_0 from the generated ground-truth labels: one is an affine logit and the other one is a quadratic logit. Both scoring functions use soft-label binary cross-entropy and ℓ2 _2 regularization with a regularizer λ=10−2λ=10^-2, excluding the intercept. They are fitted by L-BFGS-B. Affine coefficients and intercept are restricted to be in [−5,5][-5,5] and quadratic coefficients (for the quadratic logic) are restricted to be in [10−4,3][10^-4,3]. For real datasets, the mean AUC is approximately 0.870.87 for ACSIncome, 0.910.91-0.920.92 for Adult, 0.690.69-0.700.70 for Give Me Some Credit, and 0.600.60 for German Credit, with modest differences between scoring families. We use Euclidean distance (L2L^2-norm) as the cost function c when computing recourse. Immutable features cannot change during recourse generation. The policy uses separate affine sigmoid surrogates θ1 _1 and θ2 _2 for targets qθ1q_ _1 and recommendations ρθ2 _ _2, where θ1,θ2∈ℝd+1 _1, _2 ^d+1 and include an intercept. The non-intercept parameters are initialized independently from (0,0.022)N(0,0.02^2). The target and recommendation intercepts are initialized to −1-1 and 00, respectively. Both parameter vectors are projected onto Euclidean balls of radius 33. Under the implementation’s continuous relaxation of mutable coordinates, computing the highest achievable score q¯ q in Equation (13) and the minimum-cost response brbr in Equation (5) is equivalent to a convex program when written using the score function’s logit. We use closed-form solutions for the affine logit and scalar multiplier bisection for the quadratic logit. Derivatives of these responses with respect to the target are obtained analytically or by implicit differentiation of the KKT equations, allowing policy gradients to pass through the best response. When running Algorithm 1, we set the number projected full-gradient updates to T=500T=500. The competitive threshold t¯ t in Equation (18) is recomputed using 8080 bisection steps at every update, and its implicit derivative is included. The smooth recommendation weight mixes the outcomes of no action and the complete response, rather than interpolating features. A single τ smooths acceptance in both the objective and capacity equation. Unless varied in an experiment, the default parameter settings are as follows: Parameter Default Range of values tested λ 3030 1414 values in [0.3,30][0.3,30] B 0.750.75 0.25,0.75,1.5\0.25,0.75,1.5\ α 0.40.4 0.2,0.4,0.6\0.2,0.4,0.6\ τ 0.010.01 0.005,0.01,0.02,0.05\0.005,0.01,0.02,0.05\ η 0.20.2 0.05,0.2\0.05,0.2\ T 500500 — Table 2: Default parameter setting. In addition to Algorithm 1, we use the following baselines: 1. No recourse: where no individual changes features. 2. Original threshold: where every eligible individual is provided with recourse to achieve the initial target of t0t_0. This tests the reliability of initial-target recommendations under renewed competition, as motivated by prior recourse-over-time studies [16]. 3. Common target: where we perform a grid search to find a common target in [t0,1][t_0,1], for all individuals that achieves the lowest validation objective. The recourse would be recommended to every rejected individual who can attain that common target within the feasible budget of B. 4. Personalized targets without selection: where we run Algorithm 1 to learn θ1 _1, while fixing ρ=1ρ=1 for every eligible rejected individual. Cost and validity are averaged over all N−N_- initially rejected individuals in S−S^-, as in Equations (11) and (10). Validity is their mean acceptance probability, using expected acceptance under uniform cutoff tie-breaking. Therefore, the upper bound on validity is min1,k/N− \1,k/N_-\. However, this bound need not be attainable under the recourse budget and policy restrictions. At the population level, when the initially rejected fraction is 1−α1-α, the corresponding bound becomes min1,α/(1−α) \1,α/(1-α)\. (a) ASCIncome dataset, affine model, λ=3λ=3. (b) ASCIncome dataset, affine model, λ=30λ=30. Figure 1: Convergence results for the ASCIncome dataset with an affine scoring model. Each subfigure corresponds to a different λ value as stated in the caption. Each curve corresponds to a different learning rate as indicated in the legend. 5.3 Findings Convergence. In our first experiment, we study the convergence of Algorithm 1. Using the default parameter settings, two values λ∈3,30λ∈\3,30\, and two step sizes η∈0.05,0.2η∈\0.05,0.2\, we run the algorithm for T=500T=500 iterations. We track the smooth empirical training objective and the best-so-far squared projected-gradient mapping, averaged across five seeds. The results are presented in Figure 1 for the ACSIncome dataset with an affine scoring model as fw0f_w_0. Each subfigure corresponds to a different λ value. The left panel shows the training objective, evaluated on the policy-training cohort, and the right panel shows the best-so-far squared projected-gradient mapping, both as functions of the number of iterations for both of the learning rates. Both quantities decrease substantially, with η=0.2η=0.2 producing faster progress than η=0.05η=0.05 in these plots. The objective stabilizes earlier for λ=30λ=30, although the stationarity measure continues to improve. Because changing λ changes the objective itself, this observation does not establish a general improvement in convergence rate. Moreover, the best-so-far measure is non-increasing by construction, but its reduction indicates that training finds iterates closer to stationarity. The speed of improvement varies across datasets and scoring functions. Additional results for other dataset and model pairs are provided in Appendix A.1. (a) German Credit dataset, quadratic model. (b) Synthetic Non-linear dataset, quadratic model. Figure 2: The trade-off between recourse cost and post-shift validity. Each subfigure corresponds to a different dataset and scoring model as indicated by the caption. In each subfigure, each curve corresponds to the Pareto frontier of the trade-off between cost and validity for Algorithm 1 and the baselines. Dominated points remain visible as faint markers. The Trade-Off Between Cost and Validity. We next study the trade-off between recourse cost and post-shift validity for our algorithm and baselines. Across all datasets, we vary λ over 14 values between 0.30.3 and 3030, while keeping the other parameters at their default values. The results are summarized in Figure 2. Each subfigure corresponds to a dataset and scoring model. Cost and validity are computed over all initially rejected applicants in each test cohort and then averaged across five seeds. For each method, the connected points show the nondominated cost-validity combinations for each of the evaluated policies. We observe that no action incurs zero cost but can have nonzero measured validity. This is because the initial threshold t0t_0 is estimated from a reference population, whereas allocation is recomputed for each test cohort. But as expected, the validity achieved by no action is close to 0. Providing recourse with the original threshold incurs positive cost without significantly improving aggregate validity over the no-action baseline. This illustrates the limitation of recommending recourse to the original threshold in competitive settings, an observation that has also been pointed out by prior work [16]. Common targets offer favorable trade-offs at low to moderate validity levels, and some observed personalized-policy points are dominated by common-target points. Personalized targets, with or without selection, nevertheless achieve the highest observed validity, albeit at higher cost. This is despite the observation that personalized targets achieve the lowest objective values in training (and often in testing), indicating greater validity does not necessarily imply a lower objective value, perhaps due to overfitting. Follow-up target diagnostics help explain these differences. At λ=3λ=3, personalized policies with selection assign higher targets than the common-target policy to approximately 80%80\%-100%100\% of applicants receiving recommendations under both methods, depending on the dataset and scoring function. Their mean recourse cost ranges from 0.6950.695 to 0.7450.745, close to the budget B=0.75B=0.75, compared with 0.5070.507-0.5760.576 for common targets. Selection reduces expenditure on unsuccessful actions relative to implementing the same learned targets for every eligible applicant, indicating that the learned target levels and recipient selection both contribute to the observed trade-offs. Analogous to the results in the robust recourse literature [58, 45, 37, 46], our results show that achieving high validity under competition also imposes a significant increase in the cost of implementing the recourse. Additional results for other dataset and model pairs are provided in Appendix A.2, where many of our observations continue to hold. Effect of Parameters. To better understand the effect of each of the parameters in our setting, we conducted sensitivity analysis on the choice of parameters through three different experiments: (1) In budget sensitivity experiments, we varied budget from 0.25 to 1.75 for 3 choices of λ∈3,10,30λ∈\3,10,30\ while keeping the other parameters at their default values. (2) In admission rate sensitivity experiments, we varied α from 0.2 to 0.6 for the same three values of λ and other default parameters. (3) In temperature sensitivity experiments, we selected τ values ranging from 0.005 to 0.005 for the same three values of λ and other default parameters. Figure 3: The effect of budget B on cost and validity of recourse in the ACSIncome dataset for quadratic cost at λ=10λ=10. Curves correspond to different approaches. Figure 4: The effect of admission rate α on cost and validity of recourse in the Synthetic Curved dataset for quadratic cost at λ=30λ=30. Curves correspond to different approaches. Figure 5: The effect of temperature τ on the recourse objective in the Synthetic Curved dataset for quadratic cost at λ=30λ=30. Curves correspond to different approaches. Increasing the budget generally improves post-shift validity, but also increases the cost. For example, on ACSIncome with a quadratic scoring function and λ=10λ=10, as depicted in Figure 3, increasing the budget B from 0.250.25 to 1.51.5 raises Algorithm 1’s mean validity from 9.6%9.6\% to 51.4%51.4\% and its mean cost from 0.050.05 to 1.111.11. However, additional expenditure does not necessarily provide much advantage: at the budget B=1.5B=1.5, the common-target baseline achieves approximately the same validity at a mean cost of 0.610.61. Larger budgets, therefore, expand the opportunities for successful recourse, but, by themselves, do not ensure efficient use of those opportunities. Increasing the admission rate consistently raises Algorithm 1’s mean validity across all tested datasets, models, and λ combinations. For Synthetic Curved with a quadratic scoring function and λ=30λ=30, as depicted in Figure 4, increasing α from 0.20.2 to 0.60.6 raises validity from 7.1%7.1\% to 26.3%26.3\%, while increasing the mean cost from 0.100.10 to 0.320.32. In general, greater capacity increases the average recourse expenditure as the eligible population, and selected recommendations will also change with the budget increase. Performance is relatively stable across the tested temperatures for many dataset and model pairs, but excessive smoothing sometimes can substantially worsen the achieved recourse objective in Equation (12). On Give Me Some Credit with a quadratic scoring function, as depicted in Figure 5, increasing the temperature τ from 0.010.01 to 0.050.05 worsens Algorithm 1’s objective value from −8.62-8.62 to −6.28-6.28 by reducing both mean validity and cost. However, the results are nearly identical for smaller τ values. These findings support our approach of selecting the temperature through validation, as the effect depends on the dataset and scoring function. Target Distributions. We next examine how common and personalized targets affect the score improvements and costs required of recourse recipients. We use λ∈1,3,10λ∈\1,3,10\ and default values for all the other parameters. Figure 6 shows results for the ACSIncome dataset with an affine scoring model and λ=3λ=3. The left panel shows recommended scores q(x)q(x), the middle panel shows required score increases q(x)−fw0(x)q(x)-f_w_0(x), and the right panel shows the minimum cost of attaining the recommended target. The curves give the cumulative fraction of recipient observations whose value is at most the horizontal-axis value. The middle and right panels distinguish improvement in score from effort measured by the recourse cost to achieve the improved score. Figure 6: Target distributions for the ACSIncome dataset with an affine scoring model and λ=3λ=3. The panels show the cumulative density function of the recommended targets (left), required score increases (middle), and recourse costs (right) among recipients for seed 4242. Vertical dashed lines in the left panel indicate the original threshold and common target. The left panel of Figure 6 shows that both personalized policies assign very similar targets, and the fraction of individuals receiving each target score is almost uniform. The middle panel shows that even a common target requires different score increases because recipients have different initial scores. Furthermore, personalized policies generally require larger score increases than the common targets. The right panel shows that personalization does not necessarily reduce effort. The median recipient cost is approximately 0.5890.589 for the common target, 0.7470.747 for personalized targets without selection, and 0.7310.731 for personalized targets with selection. Thus, many personalized recommendations require expenditure close to the maximum allowable budget of B=0.75B=0.75. Further analysis, comparing the personalized policy with common-target policy, indicates that the personalized policy with selection assigns higher targets than the common-target policy to approximately 94%94\% of their shared recipient, with a mean additional cost of 0.1470.147. Figure 7: Effect of modifying the recipient selection for the Synthetic Curved dataset with a quadratic scoring model. The panels report mean cost (left), post-shift validity (middle), and recourse objective (right) for λ∈1,3,10λ∈\1,3,10\. The Role of Selection. To isolate the effect of recipient selection, we take a learned personalized policy, retain its target function q, and replace its recommendation rule with ρ(x)=1ρ(x)=1 for every eligible rejected applicant. Previously selected applicants retain their recommended actions, while previously unselected eligible applicants now implement their minimum-cost responses to the learned targets. We recompute the competitive threshold and measure cost, validity, and the objective value. In this experiment, we use λ∈1,3,10λ∈\1,3,10\ and default values for all the other parameters. Figure 8: Group outcomes partitioned by gender for the Adult dataset with an affine scoring model and λ=3λ=3. The panels report recommendation rates among eligible rejected applicants (left), post-shift validity gains relative to no action (middle), and mean cost per initially rejected applicant (right). Points show means across the seeds with 95%95\% confidence intervals. Figure 7 illustrates this comparison for the Synthetic Curved dataset with a quadratic scoring function. The three panels plot outcomes against λ. The left panel reports mean recourse cost (including expenditure on unsuccessful recourse). The middle panel reports post-shift validity. The right panel reports the objective value as in Equation (12). At λ=3λ=3, disabling selection increases mean cost from approximately 0.1480.148 to 0.2230.223 (left panel), while validity increases only from 0.1390.139 to 0.1440.144 (middle panel). Consequently, the objective worsens from approximately −0.268-0.268 to −0.210-0.210 (right panel). Further analysis shows that expenditure on unsuccessful recourse increases from 0.0500.050 to 0.1210.121 per initially rejected applicant. Thus, selection can avoid substantial expenditure for a small reduction in aggregate validity. Figure 9: Partial adoption for the German Credit dataset with an affine scoring model and λ=30λ=30. The policy selected under full adoption is held fixed while the adoption probability varies, and the competitive allocation is recomputed after each realization. Group Outcomes. We also examine how recourse benefits and costs are distributed across subpopulations. In this experiment, we use λ∈1,3,10λ∈\1,3,10\ and default values for all the other parameters. To form the subpopulations, we used gender or race for real datasets. For synthetic datasets, we use diagnostic groups defined by the sign of the immutable first coordinate. Figure 8 shows outcomes by gender for the Adult dataset with an affine scoring model and λ=3λ=3. The left panel reports recommendation rates among eligible rejected applicants. The middle panel reports validity gains relative to no action. The right panel reports mean cost over initially rejected members of each group. For personalized targets with selection, the mean recommendation rate is approximately 83.9%83.9\% among eligible male applicants and 66.7%66.7\% among eligible female applicants. Validity gains are approximately 23.1%23.1\% and 11.4%11.4\%, respectively, while mean costs are 0.2760.276 and 0.1610.161. These results reveal differences in both access to recommendations and realized benefits. The lower mean cost for female applicants does not imply that their recommended actions are individually cheaper: cost per initially rejected applicant also reflects how many applicants receive recommendations. The comparisons show that optimizing aggregate cost and validity does not ensure equal group outcomes. This is not surprising as equity is not included in the optimization objective [59]. Partial Adoption. We examine how incomplete adoption affects policies designed under the assumption that every recommendation is implemented. We keep the policy selected under full adoption fixed and let each recommended applicant independently implement their response with probability p where p belongs to the set 0,0.25,0.5,0.75,1\0,0.25,0.5,0.75,1\. Non-adopters retain their original features, and we recompute the competitive allocation after each realization. We measure cost and validity over all initially rejected applicants. Figure 9 presents results for the German Credit dataset with an affine scoring model, λ=30λ=30, and the remaining parameters at their default values. At 50%50\% adoption, mean cost is approximately 0.2460.246 and validity is 20.9%20.9\%, compared with 0.4930.493 and 31.2%31.2\% under full adoption. Thus, half adoption retains approximately two-thirds of full-adoption validity at half the cost. Although expected expenditure scales proportionally with adoption when recommendations remain fixed, validity need not. This is because fewer implemented actions also change the competition faced by adopters. Further analysis across all 1212 datasets and scoring function combinations shows that, at λ=30λ=30, average validity increases as more applicants implement their recommendations. Full adoption achieves the lowest average objective value: although more applicants incur recourse costs, the increase in validity outweighs this additional expenditure at the chosen value of λ. Therefore, partial adoption can preserve some of the benefits of recourse, while reducing both expenditure and overall validity. 6 Discussion and Limitations In this work, we introduced a framework for algorithmic recourse under competition that explicitly anticipates the effects of population-wide feature modifications. We studied population-wide recourse computation policies and how these policies can affect the validity and cost of recourse. We discuss some of the limitations of our setting and flesh out new directions for future work. First, our analysis assumes that achieved scores and recourse costs depend smoothly on the policy parameters. Even in such settings, our approach does not guarantee optimality. Understanding under what conditions optimal strategies can be designed for the smooth setting is a natural next step. Handling nonsmooth response changes and analyzing the performance in such settings likely requires different optimization techniques and analysis. Second, our formulation models a single round of recourse in which (in almost all our experiments) individuals fully implement the recourse. Extending the framework to a repeated setting where individuals repeatedly go through the decision-making process, adoption of recourse is selective and asynchronous remains an important direction. Finally, improvements in aggregate cost and validity do not mean these benefits are distributed equitably across all individuals and subpopulations. Understanding what it means for a recourse policy to be equitable in a competitive setting and providing equitable recourse policies for such settings is left for future work (see the Ethical Consideration section). Ethical Consideration. Our framework assumes that the decision-maker’s goal is to help initially rejected individuals by balancing their aggregate recourse cost and post-shift validity. Although we model individual costs and competitive outcomes, we do not assess the broader consequences of these decisions for individuals and subpopulations. Selecting recipients may distribute acceptance opportunities unequally across subpopulations, unsuccessful recourse may impose unrewarded effort, and initially accepted individuals may lose access to the resource due to future competition. Since our objective does not incorporate equity into considerations, improvements in aggregate cost and validity should not be interpreted as guarantees of individual/subpopulation benefit or societal welfare. Future work should carefully analyze these aspects. Acknowledgments. We thank Kshitij Kayastha for discussions during the early stages of this work. Usage of LLMs. Gemini 3.1 Pro was used to write the initial version of the experiments from the problem formulation and algorithm. GPT-6 Astra was used to verify the correctness of implementation. We then checked the edited code by Astra. GPT-6 Astra was used to proofread the paper and provide edits, especially in the implementation details of the experiments. LLMs were not used for problem formulation, formation of research questions, algorithmic solutions, and the description of related work. References [1] Patrick Altmeyer, Giovan Angela, Aleksander Buszydlik, Karol Dobiczek, Arie van Deursen, and Cynthia Liem. Endogenous macrodynamics in algorithmic recourse. In 1st Conference on Secure and Trustworthy Machine Learning, pages 418–431, 2023. [2] Srikanth Avasarala, Varun Gupta, Shahin Jabbari, Saber Salehkaleybar, and Juba Ziani. The role of causality in algorithmic recourse. CoRR, abs/2607.28497, 2026. [3] Solon Barocas, Moritz Hardt, and Arvind Narayanan. Fairness and Machine Learning: Limitations and Opportunities. fairmlbook.org, 2019. [4] Andrew Bell, João Fonseca, Carlo Abrate, Francesco Bonchi, and Julia Stoyanovich. Fairness in algorithmic recourse through the lens of substantive equality of opportunity. CoRR, abs/2401.16088, 2024. [5] Richard Berk, Hoda Heidari, Shahin Jabbari, Michael Kearns, and Aaron Roth. Fairness in criminal justice risk assessments: The state of the art. Sociological Methods & Research, 50(1):3–44, 2021. [6] Tom Bewley, Salim Amoukou, Saumitra Mishra, Daniele Magazzeni, and Manuela Veloso. Counterfactual metarules for local and global recourse. In 41st International Conference on Machine Learning, 2024. [7] Kate Boxer and Daniel Neill. Realizing the promises of algorithmic recourse through reliability, accessibility, and fairness principles. In 5th ACM Conference on Equity and Access in Algorithms, Mechanisms, and Optimization, pages 218–240, 2025. [8] Andrei Buliga, Chiara Di Francescomarino, Chiara Ghidini, Marco Montali, and Massimiliano Ronzani. Generating counterfactual explanations under temporal constraints. In 39th Annual AAAI Conference on Artificial Intelligence, pages 15622–15631, 2025. [9] Marina Ceccon, Alessandro Fabris, Goran Radanovic, Asia J. Biega, and Gian Antonio Susto. Reinforcement learning for durable algorithmic recourse. CoRR, abs/2509.22102, 2025. [10] Yatong Chen, Andrew Estornell, Yevgeniy Vorobeychik, and Yang Liu. To give or not to give? the impacts of strategically withheld recourse. In 28th International Conference on Artificial Intelligence and Statistics, volume 258, pages 739–747, 2025. [11] Seung Hyun Cheon, Anneke Wernerfelt, Sorelle Friedler, and Berk Ustun. Feature responsiveness scores: Model-agnostic explanations for recourse. In 13th International Conference on Learning Representations, 2025. [12] Frances Ding, Moritz Hardt, John Miller, and Ludwig Schmidt. Retiring adult: New datasets for fair machine learning. In Advances in Neural Information Processing Systems 34, pages 6478–6490, 2021. [13] Sanghamitra Dutta, Jason Long, Saumitra Mishra, Cecilia Tilli, and Daniele Magazzeni. Robust counterfactual explanations for tree-based ensembles. In 39th International Conference on Machine Learning, volume 162, pages 5742–5756, 2022. [14] Ahmad-Reza Ehyaei, Ali Shirali, and Samira Samadi. Collective counterfactual explanations: Balancing individual goals and collective dynamics. In Advances in Neural Information Processing Systems 38, 2025. [15] Hidde Fokkema, Damien Garreau, and Tim van Erven. The risks of recourse in binary classification. In 27th International Conference on Artificial Intelligence and Statistics, pages 550–558, 2024. [16] João Fonseca, Andrew Bell, Carlo Abrate, Francesco Bonchi, and Julia Stoyanovich. Setting the right expectations: Algorithmic recourse over time. In 3rd ACM Conference on Equity and Access in Algorithms, Mechanisms, and Optimization, pages 29:1–29:11, 2023. [17] Ruijiang Gao and Himabindu Lakkaraju. On the impact of algorithmic recourse on social segregation. In 40th International Conference on Machine Learning, pages 10727–10743, 2023. [18] Prateek Garg, Lokesh Nagalapatti, and Sunita Sarawagi. From search to sampling: Generative models for robust algorithmic recourse. In 13th International Conference on Learning Representations, 2025. [19] Ozgur Guldogan, Yuchen Zeng, Jy-yong Sohn, Ramtin Pedarsani, and Kangwook Lee. Equal improvability: A new fairness notion considering the long-term impact. In 11th International Conference on Learning Representations, 2023. [20] Hangzhi Guo, Feiran Jia, Jinghui Chen, Anna Squicciarini, and Amulya Yadav. RoCourseNet: Robust training of a prediction aware recourse model. In 32nd ACM International Conference on Information and Knowledge Management, pages 619–628, 2023. [21] Vivek Gupta, Pegah Nokhiz, Chitradeep Roy, and Suresh Venkatasubramanian. Equalizing recourse across groups. CoRR, abs/1909.03166, 2019. [22] Moritz Hardt and Celestine Mendler-Dünner. Performative prediction: Past and future. CoRR, abs/2310.16608, 2023. [23] Moritz Hardt, Eric Price, and Nathan Srebro. Equality of opportunity in supervised learning. In 30th Annual Conference on Neural Information Processing Systems, pages 3315–3323, 2016. [24] Hoda Heidari, Vedant Nanda, and Krishna Gummadi. On the long-term impact of algorithmic decision policies: Effort unfairness and feature segregation through social learning. In 36th International Conference on Machine Learning, pages 2692–2701, 2019. [25] Zachary Izzo, Lexing Ying, and James Zou. How to learn when data reacts to your model: Performative gradient descent. In 38th International Conference on Machine Learning, pages 4641–4650, 2021. [26] Zachary Izzo, James Zou, and Lexing Ying. How to learn when data gradually reacts to your model. In 25th International Conference on Artificial Intelligence and Statistics, pages 3998–4035, 2022. [27] Junqi Jiang, Francesco Leofante, Antonio Rago, and Francesca Toni. Robust counterfactual explanations in machine learning: A survey. In 33rd International Joint Conference on Artificial Intelligence, pages 8086–8094, 2024. [28] Kentaro Kanamori, Takuya Takagi, Ken Kobayashi, and Yuichi Ike. Learning decision trees and forests with algorithmic recourse. In 41st International Conference on Machine Learning, 2024. [29] Amir-Hossein Karimi, Gilles Barthe, Borja Balle, and Isabel Valera. Model-agnostic counterfactual explanations for consequential decisions. In 23rd International Conference on Artificial Intelligence and Statistics, pages 895–905, 2020a. [30] Amir-Hossein Karimi, Bodo Julius von Kügelgen, Bernhard Schölkopf, and Isabel Valera. Algorithmic recourse under imperfect causal knowledge: a probabilistic approach. In Advances in Neural Information Processing Systems 33, 2020b. [31] Amir-Hossein Karimi, Gilles Barthe, Bernhard Schölkopf, and Isabel Valera. A survey of algorithmic recourse: Contrastive explanations and consequential recommendations. ACM Comput. Surv., 55(5):95:1–95:29, 2023. [32] Kshitij Kayastha, Vasilis Gkatzelis, and Shahin Jabbari. Learning-augmented robust algorithmic recourse. Transactions on Machine Learning Research, 2026. [33] Zahra Khotanlou, Kate Larson, and Amir-Hossein Karimi. Your recourse, my loss? algorithmic recourse under shared constraints. In 9th ACM Conference on Fairness, Accountability, and Transparency, pages 3717–3737, 2026. [34] Michael Kim and Juan Perdomo. Making decisions under outcome performativity. In 14th Innovations in Theoretical Computer Science Conference, pages 79:1–79:15, 2023. [35] Gunnar König, Timo Freiesleben, and Moritz Grosse-Wentrup. Improvement-focused causal recourse (ICR). In 37th AAAI Conference on Artificial Intelligence, pages 11847–11855, 2023. [36] Gunnar König, Hidde Fokkema, Timo Freiesleben, Celestine Mendler-Dünner, and Ulrike von Luxburg. Performative validity of recourse explanations. CoRR, abs/2506.15366, 2025. [37] Phone Kyaw, Kshitij Kayastha, and Shahin Jabbari. Optimal robust recourse with lp p-bounded model change. In 4th IEEE Conference on Secure and Trustworthy Machine Learning, pages 303–325, 2026. [38] Himabindu Lakkaraju, Stephen Bach, and Jure Leskovec. Interpretable decision sets: A joint framework for description and prediction. In 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 1675–1684, 2016. [39] Francesco Leofante and Nico Potyka. Promoting counterfactual robustness through diversity. In 38th AAAI Conference on Artificial Intelligence, pages 21322–21330, 2024. [40] Bo-Yi Liu, Zhi-Xuan Liu, Kuan Lun Chen, Shih-Yu Tsai, Jie Gao, and Hao-Tsung Yang. Understanding endogenous data drift in adaptive models with recourse-seeking users. In 8th AAAI/ACM Conference on AI, Ethics, and Society, 2025. [41] Arnaud Van Looveren and Janis Klaise. Interpretable counterfactual explanations guided by prototypes. In Machine Learning and Knowledge Discovery in Databases, pages 650–665, 2021. [42] Scott Lundberg and Su-In Lee. A unified approach to interpreting model predictions. In Advances in Neural Information Processing Systems 30, pages 4765–4774, 2017. [43] Celestine Mendler-Dünner, Frances Ding, and Yixin Wang. Anticipating performativity by predicting from predictions. In Advances in Neural Information Processing Systems 35, 2022. [44] Duy Nguyen, Ngoc Bui, and Viet Anh Nguyen. Distributionally robust recourse action. In 11th International Conference on Learning Representations, 2023. [45] Tuan-Duy Nguyen, Ngoc Bui, Duy Nguyen, Man-Chung Sue, and Viet Anh Nguyen. Robust bayesian recourse. In 38th Conference on Uncertainty in Artificial Intelligence, pages 1498–1508, 2022. [46] Martin Pawelczyk, Teresa Datta, Johannes van den Heuvel, Gjergji Kasneci, and Himabindu Lakkaraju. Probabilistically robust recourse: Navigating the trade-offs between costs and robustness in algorithmic recourse. In 11th International Conference on Learning Representations, 2023. [47] Juan Perdomo, Tijana Zrnic, Celestine Mendler-Dünner, and Moritz Hardt. Performative prediction. In 37th International Conference on Machine Learning, pages 7599–7609, 2020. [48] Juan Perdomo, Tolani Britton, Moritz Hardt, and Rediet Abebe. Difficult lessons on social prediction from wisconsin public schools. In 8th ACM Conference on Fairness, Accountability, and Transparency, 2025. [49] Nicholas Perello, Cyrus Cousins, Yair Zick, and Przemyslaw A. Grabowicz. Discrimination induced by algorithmic recourse objectives. In 8th ACM Conference on Fairness, Accountability, and Transparency, pages 1653–1663, 2025. [50] Kaivalya Rawal and Himabindu Lakkaraju. Beyond individualized recourse: Interpretable and interactive summaries of actionable recourses. In Advances in Neural Information Processing Systems 33, 2020. [51] Marco Túlio Ribeiro, Sameer Singh, and Carlos Guestrin. “Why should I trust you?": Explaining the predictions of any classifier. In 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 1135–1144, 2016. [52] Cynthia Rudin. Stop explaining black box machine learning models for high stakes decisions and use interpretable models instead. Nat. Mach. Intell., 1(5):206–215, 2019. [53] Meirav Segal, Anne-Marie George, Ingrid Chieh Yu, and Christos Dimitrakakis. Better luck next time: About robust recourse in binary allocation problems. In 2nd World Conference on Explainable Artificial Intelligence, pages 374–394, 2024. [54] Dylan Slack, Anna Hilgard, Himabindu Lakkaraju, and Sameer Singh. Counterfactual explanations can be manipulated. In Advances in Neural Information Processing Systems 34, pages 62–75, 2021. [55] Daniel Smilkov, Nikhil Thorat, Been Kim, Fernanda Viégas, and Martin Wattenberg. Smoothgrad: removing noise by adding noise. CoRR, abs/1706.03825, 2017. [56] Giovanni De Toni, Stefano Teso, Bruno Lepri, and Andrea Passerini. Time can invalidate algorithmic recourse. CoRR, abs/2410.08007, 2024. [57] Bohdan Turbal, Iryna Voitsitska, and Lesia Semenova. ElliCE: Efficient and provably robust algorithmic recourse via the Rashomon sets. In Advances in Neural Information Processing Systems 38, 2025. [58] Sohini Upadhyay, Shalmali Joshi, and Himabindu Lakkaraju. Towards robust and reliable algorithmic recourse. In Advances in Neural Information Processing Systems 34, pages 16926–16937, 2021. [59] Berk Ustun, Alexander Spangher, and Yang Liu. Actionable recourse in linear classification. In 3rd AMC Conference on Fairness, Accountability, and Transparency, pages 10–19, 2019. [60] Sahil Verma, John Dickerson, and Keegan Hines. Counterfactual explanations for machine learning: A review. CoRR, abs/2010.10596, 2020. [61] Sahil Verma, Keegan Hines, and John Dickerson. Amortized generation of sequential algorithmic recourses for black-box models. In 36th AAAI Conference on Artificial Intelligence, pages 8512–8519, 2022. [62] Sandra Wachter, Brent Mittelstadt, and Chris Russell. Counterfactual explanations without opening the black box: automated decisions and the GDPR. Harvard Journal of Law and Technology, 31(2):841–887, 2018. [63] Jayanth Yetukuri, Ian Hardy, Yevgeniy Vorobeychik, Berk Ustun, and Yang Liu. Providing fair recourse over plausible groups. In 38th AAAI Conference on Artificial Intelligence, pages 21753–21760, 2024. [64] Muhammad Zafar, Isabel Valera, Manuel Gomez-Rodriguez, and Krishna P. Gummadi. Fairness constraints: Mechanisms for fair classification. In 20th International Conference on Artificial Intelligence and Statistics, pages 962–970, 2017. Appendix A Additional Experimental Results A.1 Convergence (a) ASCIncome dataset, quadratic model, λ=3λ=3. (b) ASCIncome dataset, quadratic model, λ=30λ=30. Figure 10: Convergence results for the ASCIncome dataset with a quadratic scoring model. Each subfigure corresponds to a different λ value as stated in the caption. Each curve corresponds to a different learning rate as indicated in the legend. (a) ASCIncome dataset, quadratic model, λ=3λ=3. (b) ASCIncome dataset, quadratic model, λ=30λ=30. Figure 11: Convergence results for the Adult dataset with a quadratic scoring model. Each subfigure corresponds to a different λ value as stated in the caption. Each curve corresponds to a different learning rate as indicated in the legend. A.2 The Trade-Off Between Cost and Validity (a) Adult dataset, affine model. (b) Adult dataset, quadratic model. (c) German Credit dataset, affine model. (d) Synthetic non-linear dataset, affine model. Figure 12: The trade-off between validity of recourse and its cost. Each subfigure corresponds to a different dataset and scoring model as indicated by the caption. In each subfigure, each curve corresponds to the Pareto frontier of the trade-off between cost and validity for Algorithm 1 and the baselines.