Robust Strategic Classification under Decision-Dependent Cost Uncertainty

Sura Alhanouti, Güzin Bayraksan, Parinaz Naghizadeh · 2026

Read Robust Strategic Classification under Decision-Dependent Cost Uncertainty by Sura Alhanouti, Güzin Bayraksan, Parinaz Naghizadeh (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2606-30136.txt.

Introduction

Sura Alhanouti, Güzin Bayraksan, and Parinaz Naghizadeh study classifiers that people actively try to game. Applicants tweak their data, at some cost, to win favorable decisions. Most robust designs assume that gaming cost is fixed and known. Real manipulation costs shift with the algorithm's own past choices. Today's policy shapes tomorrow's cost landscape for gamers.

The authors build a two-stage robust optimization framework for this. Its uncertainty set depends explicitly on the classifier's decisions. That decision-dependent set captures how costs evolve from inside the system. Awareness of policy-dependent costs brings two benefits at once. It shrinks what the designer must guard against. It also curtails gaming of the system more effectively over time. Lending, hiring, and admissions systems all face this dynamic. The approach offers them a principled way to anticipate adaptation.

Catalog record

CREATORSura Alhanouti, Güzin Bayraksan, Parinaz Naghizadeh
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE112 KB
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2606.30136

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Robust Strategic Classification under Decision-Dependent Cost Uncertainty Sura Alhanouti, Güzin Bayraksan, Parinaz Naghizadeh Abstract Humans facing algorithmic decision systems have been found to “game” them by altering their input data (at a cost to them) in order to favorably change the algorithmic outcomes they receive (at a cost to the algorithm). The growing literature on strategic classification seeks to develop robust machine learning algorithms that account for, and reduce, unwanted strategic behavior. A limitation of these existing works is that they assume the cost of strategic behavior to be fixed and independent of the classifier’s decision. In practice, however, manipulation costs evolve and depend on past algorithmic decisions: today’s decisions influence tomorrow’s costs. This paper proposes and analyzes a two-stage robust optimization framework with a decision-dependent uncertainty set to capture such dependencies. We highlight that awareness of policy-dependent costs not only reduces uncertainty, but also better curtails gaming of the algorithmic system over time. 1 Introduction Machine learning algorithms are increasingly deployed in decision making systems, including in financial lending, job hiring, recidivism prediction, and school admission decisions. A key issue arising in these systems is strategic behavior by humans, who modify their inputs to the algorithm (e.g., by misrepresenting their features), in a way that allows them to gain a favorable outcome but does not necessarily align with the system’s goal of making accurate predictions ( 46 ; 38 ; 26 ; 58 ; 54 ; 42 ) . This has motivated a growing line of works on strategic machine learning, which study the design of algorithms that are robust to such “gaming” of the system. The majority of this existing literature adopts a limiting assumption: both the decision maker and the agents have full information about the algorithmic system and the strategic recourse options, including which features can be manipulated and at what cost. Recent work has started introducing uncertainty into this problem by considering agents with incomplete or biased perceptions of the classifier ( 13 ; 19 ; 28 ) or classifiers uncertain about agents’ costs ( 48 ; 51 ; 1 ) . However, a type of uncertainty that arises in practice, but remains unaddressed by these works, is that classifier decisions that aim to curb agents’ gaming can endogenously shape cost uncertainty over time . Specifically, the criteria set by the present classifier influence the possible set of costs that the agents face when strategically responding to the algorithmic system in the future. For instance, test-optional policies started by colleges during the COVID-19 pandemic reduced demand and prices for test preparation in subsequent years, while simultaneously shifting spending toward alternative costly signals such as essay coaching and extracurricular activities ( 45 ; 17 ; 57 ; 20 ) . Thus, a school’s decisions this year shape future applicants’ strategic response costs; although, crucially, the exact impact is not fully known at the time of decision-making. Similar effects appear in other contexts such as lending and hiring ( 24 ; 8 ; 5 ) , wherein the criteria adopted for approval have been found to shape the options and costs of strategic gaming available to future applicants. These motivate the need to not only address strategic manipulation, but to do so with an eye towards its uncertain temporal effects. This paper is, to our knowledge, the first to formalize such time-evolving and decision-dependent uncertainty in strategic classification. We formulate the classifier selection as a two-stage robust optimization (TSRO) problem. In the first stage, the classifier anticipates that its choices will influence future response costs by the agents; we model this through a decision-dependent uncertainty set for the second-stage problem. Throughout, we provide support for different elements of our proposed model using university admissions as a motivating example, including by highlighting universities’ awareness of how their admissions’ criteria impose long-term costs and shape strategic behavior. Following the problem formulation, we note that solving the resulting TSRO remains challenging. Specifically, our second stage problem is nonlinear, and the uncertainty appears not only in the constraint set, but also in the objective through a dual-norm term, causing the dual feasible set to vary with each realization and preventing the reuse of dual extreme points or valid cut generation to solve the problem. We address this by proposing problem-specific approximations and reformulations. Specifically, we propose an approximation of the cost-induced norms that appear in the firm’s per-stage objective (which we show has an added benefit in the context of strategic classification, by enhancing robustness against harmful manipulations), linearize the objective function, and use McCormick envelopes to remove decision-dependence in the second-stage problem’s objective function. Following these, the relaxed problem becomes amenable to some existing solution methods for linear TSROs, including the commonly used Benders decomposition and Column-and-Constraint Generation (C&CG) algorithms ( 47 ; 66 ; 69 ; 11 ) , which we employ. We validate and bound the suboptimality gap of our approximations numerically by comparing the solution obtained from the relaxed problem to the original TSRO’s optimal solution obtained via brute-force search; see Section 6 . We then proceed to using numerical experiments (on both synthetic and semi-synthetic data) to assess the impacts of our method’s awareness of time-evolving and decision-dependence uncertainties. Our semi-synthetic experiments are built on real-world datasets on college admission statistics and costs ( 43 ; 15 ; 55 ; 44 ; 16 ; 14 ) . Our main findings here are two-fold. First, we illustrate that compared to a dependency-unaware baseline, our dependency-aware classifier strategically sacrifices some first-stage performance to gain second-stage robustness; this is a consequence of moving from myopic to temporally-aware decisions. Second, and less expected, we show that our method reduces overall loss not only due to its awareness of temporal effects and robustness to uncertainty, but by changing agents’ costs in a way that limits strategic manipulation. In other words, our experiments show that accounting for time-evolving, decision-dependent costs allows a decision maker to not only minimize its uncertainty, but also shape strategic responses , highlighting a different (and previously unexplored) lever for mitigating gaming of algorithmic systems over time. 2 Related Work Most of the works studying humans’ strategic responses to AI/ML systems assume full information for both classifiers and agents and explore the implications of agents manipulating inputs without changing their true qualifications ( 29 ; 41 ; 37 ; 59 ) , genuinely improving their qualifications ( 2 ; 63 ) , or choosing between manipulation and improvement ( 64 ; 34 ; 27 ; 31 ; 6 ; 4 ; 21 ; 65 ) . More recent works examine agents having incomplete information about the algorithm . 9 , 22 , and 59 propose randomized classifiers to obscure decision boundaries. 13 and 30 explore strategic communication. 23 and 7 study opacity and the fairness implications of limited information about the algorithm. A separate line of work, similar to ours, handles firms’ uncertainty about agent responses . These include learning under unknown manipulations ( 51 ; 36 ; 12 ) , unknown costs or preferences ( 1 ; 18 ) , or distributional shifts ( 33 ) . Some models address robustness to uncertain manipulation costs using worst-case optimization or distributionally robust methods ( 48 ; 60 )

Read the complete text