# Robust Strategic Classification under Decision-Dependent Cost Uncertainty

arXiv: https://arxiv.org/abs/2606.30136 · HTML: https://mlsanity.com/paper/2606.30136/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 36 of its 69 references that are in the map.
- First posted on arXiv 29 Jun 2026.

## Builds on (most cited first, 30 of 36)

- [Strategic Classification](https://mlsanity.com/paper/1506.06980/) (2015)
- [Strategic Classification from Revealed Preferences](https://mlsanity.com/paper/1710.07887/) (2017)
- [Combining Deep Reinforcement Learning and Search for Imperfect-Information Games](https://mlsanity.com/paper/2007.13544/) (2020)
- [The Social Cost of Strategic Classification](https://mlsanity.com/paper/1808.08460/) (2018)
- [Learning with Feature-Dependent Label Noise: A Progressive Approach](https://mlsanity.com/paper/2103.07756/) (2021)
- [Strategic Classification in the Dark](https://mlsanity.com/paper/2102.11592/) (2021)
- [PAC-Learning for Strategic Classification](https://mlsanity.com/paper/2012.03310/) (2020)
- [The Strategic Perceptron](https://mlsanity.com/paper/2008.01710/) (2020)
- [Maximizing Welfare with Incentive-Aware Evaluation Mechanisms](https://mlsanity.com/paper/2011.01956/) (2020)
- [The Role of Randomness and Noise in Strategic Classification](https://mlsanity.com/paper/2005.08377/) (2020)
- [Generalized Strategic Classification and the Case of Aligned Incentives](https://mlsanity.com/paper/2202.04357/) (2022)
- [Stateful Strategic Regression](https://mlsanity.com/paper/2106.03827/) (2021)
- [Causal Strategic Classification: A Tale of Two Shifts](https://mlsanity.com/paper/2302.06280/) (2023)
- [Calibrated Stackelberg Games: Learning Optimal Commitments Against Calibrated Agents](https://mlsanity.com/paper/2306.02704/) (2023)
- [SCORES: Shape Composition with Recursive Substructure Priors](https://mlsanity.com/paper/1809.05398/) (2018)
- [Strategic Classification under Unknown Personalized Manipulation](https://mlsanity.com/paper/2305.16501/) (2023)
- [Optimal Decision Making Under Strategic Behavior](https://mlsanity.com/paper/1905.09239/) (2019)
- [Manipulation-Proof Machine Learning](https://mlsanity.com/paper/2004.03865/) (2020)
- [Learnability Gaps of Strategic Classification](https://mlsanity.com/paper/2402.19303/) (2024)
- [Multi-agent Reinforcement Learning in Bayesian Stackelberg Markov Games for Adaptive Moving Target Defense](https://mlsanity.com/paper/2007.10457/) (2020)
- [Bayesian Persuasion for Algorithmic Recourse](https://mlsanity.com/paper/2112.06283/) (2021)
- [One-Shot Strategic Classification Under Unknown Costs](https://mlsanity.com/paper/2311.02761/) (2023)
- [Bayesian Strategic Classification](https://mlsanity.com/paper/2402.08758/) (2024)
- [The Double-Edged Sword of Behavioral Responses in Strategic Classification: Theory and User Studies](https://mlsanity.com/paper/2410.18066/) (2024)
- [Algorithmic Transparency with Strategic Users](https://mlsanity.com/paper/2008.09283/) (2020)
- [Learning under Imitative Strategic Behavior with Unforeseeable Outcomes](https://mlsanity.com/paper/2405.01797/) (2024)
- [Incentivizing Desirable Effort Profiles in Strategic Classification: The Role of Causality and Uncertainty](https://mlsanity.com/paper/2502.06749/) (2025)
- [Setting Fair Incentives to Maximize Improvement](https://mlsanity.com/paper/2203.00134/) (2022)
- [Bootstrapping the Relationship Between Images and Their Clean and Noisy Labels](https://mlsanity.com/paper/2210.08826/) (2022)
- [Breaking the Curse of Multiagency in Robust Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2409.20067/) (2024)

## Abstract (arXiv)

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.