CS Paper Radar

Algorithmic Recourse Under Competition

Shahin Jabbari

cs.LG cs.AI ·submitted 2026-09-30 14:53 UTC · v1
theory

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.

Closest papers

Nearest neighbours by meaning across the whole index.

Personalized Recommendations Without Inducing Congestion: Mitigating Disparities in the NYC High School Match

cs.CY econ.GN ·2026-10-06 ·Erica Chiang, Kenny Peng, Rebecca Lichtenstein, Brielle McDaniel, Kristen O'Neil +5 more
similarity 0.63
Abstract · Preliminary version in ACM EC 2026

Algorithmic recommendations can help participants navigate large matching markets. For example, recommendations for school and college choices may reduce information frictions and disparities in access to high-performing programs. At scale, however, recommenders in capacity-constrained settings can be self-defeating: if they steer too many users toward the same items, then even users who were originally predicted to have a high chance of matching to an item may not, due to increased competition. In this paper, we formalize this phenomenon of recommendation-induced congestion; motivated by the NYC high school match, we show that naive recommendations can cause sharp decreases in program acceptance rates, most affecting applicants with the fewest nearby options. Next, we propose and theoretically analyze a congestion-aware, bilevel optimize-and-simulate approach to allocate recommendations and improve match outcomes safely, in equilibrium. Finally, we deploy this approach in the 2025-26 admissions cycle of the NYC high school match, aiming to reduce disparities by highlighting personalized lists of nearby, high-performing programs where an applicant has a high predicted offer likelihood. In a randomized controlled trial, we find that 16.4% of treatment applicants ranked a recommended program, versus 10.5% of control applicants who ranked a program they would have been recommended (57% relative increase; $p$=0.011); 5.6% of treatment applicants matched to such a program, versus 3.3% of control applicants (71% relative increase; $p$=0.071); further, no treatment applicant was rejected from a recommended program. Our findings suggest that recommenders should be analyzed and designed as market-shaping interventions.

0.32

Optimizing Recourse Under Predictive Multiplicity

cs.LG ·2026-11-04 ·Shahin Jabbari
similarity 0.62
Abstract

Algorithmic recourse identifies modifications that can change an unfavorable model prediction into a favorable one. Under predictive multiplicity, similarly performing models can disagree on individual predictions, so recourse valid for one model may fail for another. We formulate robust recourse under predictive multiplicity as a budget-constrained minimization of the worst-case validity loss across a competing set of models, which can include models with different architectures or from different hypothesis classes. We propose an oracle-efficient algorithm called ORPM and prove sufficient conditions for its convergence. We evaluate ORPM on one synthetic and five real datasets, and competing sets consist of linear, neural, mixed, and decision-tree models. Our experiments show decreasing optimization-gap bounds and high validity in many tested settings, with favorable performance against baselines designed for specific model classes or architectures. We also quantify how requiring a common action across competing models changes recourse success at a given budget and examine disparities in this success across demographic groups.

0.30

Aligning Performance with Contribution: Towards Contribution-Aware Fair Recommendation

cs.IR ·2026-10-06 ·Shuai Zhang, Hui Fang, Zun Sun
position similarity 0.60
Abstract

Existing research on user fairness in recommender systems has developed diverse objectives. However, it has paid limited attention to a distinct distributive perspective: whether users' contributions to model learning should be reflected in the recommendation benefits they receive. We argue that, in addition to existing fairness protections, a fair system may account for the alignment between users' estimated contributions and the recommendation performance they receive. Such alignment can incentivize sustained and informative engagement, thereby supporting a sustainable recommendation ecosystem. To this end, we propose Contribution-Performance Fairness, a novel fairness perspective which requires recommendation performance to be aligned with estimated contribution across user groups and to remain equitable among users with comparable contributions within a same group. To instantiate this perspective, we introduce the Contribution-Performance Fair Recommender (CPFR), a framework applicable to different backbone recommenders. CPFR constructs ordered user groups from a training-dependent contribution considering interaction volume, loss alignment, and optimization intensity, and jointly optimizes recommendation accuracy with the two fairness requirements. A game-theoretic analysis shows that such alignment can strengthen contribution incentives and improve system-level recommendation accuracy under voluntary contribution. Experiments on three datasets and three backbone models demonstrate that CPFR achieves a strong accuracy--fairness trade-off under the proposed operational metric.

0.30

Follow the Herd: A Data-Driven Approach for Actionable Recourse

cs.AI ·2026-10-27 ·Nishtha Madaan, Srikanta Bedathur
similarity 0.59
Abstract

As machine learning systems make increasingly greater decisions about people's lives, it is critical to provide users with actionable recourse about how they can achieve their desired outcomes. This problem is currently tackled by relying on expensive human supervision which involves hand-designing a cost function before searching for low-cost actions that achieve the desired outcome. In this paper, we propose \textit{``Data-Driven Action Recourse"} (DDAR), the first approach for providing action recourse without requiring costly supervision from humans about action costs. We build upon the notion that highly likely trajectories in the historical user data should be associated with lower costs. With this, DDAR first builds a dynamics model of historical user trajectories. Under this model, it then searches for trajectories that achieve the desired outcome. In experiments, we find that this simple approach recommends plausible action recourse without requiring human supervision, achieving lower action costs than the existing approaches.

0.16

Training with Missed Targets in Generative Recommendation: Separating Supervision from Probability Competition

cs.IR cs.LG ·2026-10-07 ·Xuesi Wang, Yangbin Shi, Xiaolin Zheng
similarity 0.58
Abstract · 12 pages, 4 figures, 8 tables

Generative recommenders return a limited candidate set and may omit observed targets before reranking. A training strategy appends these missed targets to reranker training lists, although inference still ranks only original candidates. This operation simultaneously changes retrieved-target weight, adds supervision over appended targets, and makes the two groups compete for probability. An append/no-append comparison therefore cannot explain changes in returned-item rankings. We construct three matched losses that hold retrieved-target weight fixed while introducing appended-target supervision and group competition separately. The intermediate loss trains within both groups but normalizes them separately, preventing training-only targets from competing with inference candidates. Experiments with a released OneRec model and locally trained Amazon generators show that this competition can harm returned-item ranking. In four prespecified Amazon Video Games comparisons, removing it improved full-target normalized discounted cumulative gain (FT-NDCG) by 7.8--22.2\%; 95\% intervals over users and three of four intervals over training runs excluded zero. A conservative development-set rule selected appended-target training for two of three generators in one held-out category and rejected it for all three in another, avoiding a 1.7\% loss. Candidate completion should therefore be evaluated for each generator rather than applied automatically.

0.17

Incremental Recommendation via Causal Models

cs.LG stat.MLstat.ME ·2026-08-27 ·Athanasios Vlontzos, David Gustafsson, Michael O'Riordan, Ciarán M. Gilligan-Lee
published similarity 0.58
Abstract · Accepted at the CONSEQUENCES Workshop @ RecSys'26

Recommendation impressions are a finite resource, hence delivering a recommendation to a user who would discover the content organically yields no incremental value and displaces other recommendations that could. We address this by extending an existing production recommendation model to a causal architecture using holdback data that is already collected as part of routine experimentation infrastructure, requiring no new data collection. A central challenge is that attribution windows differ between treated and holdback observations: treated users are attributed a stream within a short direct-response window, while holdback users are attributed organic streams over a multi-day window. This mismatch makes naive treatment-effect subtraction invalid. We resolve this with a dual-threshold targeting policy that delivers a recommendation only when the probability of a treated stream is high and the probability of organic stream is low. In a production-scale A/B test on millions of Spotify users, this policy reduces recommendation impressions by 7% with no statistically significant reduction in overall recommended content consumption. We further show that joint training with holdback data improves calibration of the treated head relative to the production baseline, and argue this can be taken as evidence that causal models learn more generalisable representations than models trained on observational data alone.

0.52

CERBO: Certified Recourse at a Requested Rate for Gradient-Boosted Trees

cs.LG cs.AIcs.CY ·2026-11-02 ·Farhan Shahriyar Hossain, Taufikur Rahman Fuad, Md. Zarif Bin Hasnat, Md Abrar Jahin, Md Rizwan Parvez
similarity 0.58
Abstract · 23 pages, 6 figures, 15 tables

Recourse-aware learning trains models so that people who receive an adverse decision can reverse it with an affordable change. For gradient-boosted decision trees (GBDTs), the existing method, RABIT, exposes a single recourse weight whose effect on the recourse rate is abrupt and data-dependent, and its training bound cannot certify recourse for any rejected individual. We present Certified Recourse Boosting (CERBO), which takes a requested recourse rate and returns a GBDT with certified actions: it tracks exact additive effort along tree paths, trains against committed boxes (a family of bounds that contains RABIT's and certifies a within-budget action for each training sample) and adjusts the weight after every tree until the certified rate meets the request. A calibration step guarantees the rate on new individuals, and the certifier runs on any tree ensemble, including XGBoost and LightGBM, in milliseconds per person without a solver. In RABIT's own experimental protocol, at equal accuracy, CERBO raises the recourse ratio from 0.90 to 0.99 on FICO and from 0.64 to 0.77 on Bail. Under additive costs on six data sets, it raises the area under the accuracy-recourse frontier in all 12 settings, and in simulated deployments it guarantees recourse to 70% of rejected individuals in 11 of 12 settings, against 2 for RABIT.

0.34

Revisiting scaling laws for reward optimization

cs.LG cs.AI ·2026-09-29 ·Ali Aouad, Aymane El Gadarri, Vivek F. Farias
theory similarity 0.57
Abstract

Scaling laws for optimization against reward models in AI alignment have pinned down how performance depends on optimization effort---measured by a KL-divergence budget relative to a reference policy. Beyond a certain budget, over-optimization (or reward hacking) can arise: because we optimize against a proxy reward model (distinct from true rewards), performance can plateau or degrade. Naturally, the proxy reward's accuracy depends on how much preference data (often in the form of pairwise comparisons) was used to train it. However, existing research does not cleanly identify how performance jointly scales with the amount of training data and the divergence budget. Our main contribution is to provide an empirically accurate and theoretically grounded scaling law in such context. Performance roughly scales as $Θ(\sqrt{\min\{\log(M),K\}})$, where $M$ is the number of comparisons in training data and $K$ is the policy's divergence budget. We develop an information-theoretic model to establish this upper bound and prove it is tightly achievable through a constructive procedure. Informed by this, we conduct extensive empirical evaluations using a real-world annotation setup, whereby a large 70B gold reward model generates feedback data and proxy reward models are trained from less capable models (0.6B to 4B). Our scaling law provides an excellent fit (R2 from 97\% to 99\%), outperforms alternative specifications, and remains robust across model sizes, noise, and optimization procedures (best-of-$N$ or policy tilting). Our evidence suggests that reward optimization is analogous to a surprisingly simple selection task: choosing from a sequence of IID Gaussian random variables using noisy preference feedback.

0.47