# Learnability Gaps of Strategic Classification arXiv: https://arxiv.org/abs/2402.19303 ยท HTML: https://mlsanity.com/paper/2402.19303/ ## Key facts - Cited by 16 papers in the map (data through 14 Oct 2026). - Builds on 24 of its 38 references that are in the map. - First posted on arXiv 29 Feb 2024. ## Builds on (most cited first, 24 of 24) - [Strategic Classification](https://mlsanity.com/paper/1506.06980/) (2015) - [Strategic Classification from Revealed Preferences](https://mlsanity.com/paper/1710.07887/) (2017) - [The Social Cost of Strategic Classification](https://mlsanity.com/paper/1808.08460/) (2018) - [Strategic Classification is Causal Modeling in Disguise](https://mlsanity.com/paper/1910.10362/) (2019) - [VC Classes are Adversarially Robustly Learnable, but Only Improperly](https://mlsanity.com/paper/1902.04217/) (2019) - [The Disparate Effects of Strategic Manipulation](https://mlsanity.com/paper/1808.08646/) (2018) - [Strategic Classification in the Dark](https://mlsanity.com/paper/2102.11592/) (2021) - [Causal Strategic Linear Regression](https://mlsanity.com/paper/2002.10066/) (2020) - [PAC-Learning for Strategic Classification](https://mlsanity.com/paper/2012.03310/) (2020) - [The Strategic Perceptron](https://mlsanity.com/paper/2008.01710/) (2020) - [Information Discrepancy in Strategic Learning](https://mlsanity.com/paper/2103.01028/) (2021) - [Alternative Microfoundations for Strategic Classification](https://mlsanity.com/paper/2106.12705/) (2021) - [Maximizing Welfare with Incentive-Aware Evaluation Mechanisms](https://mlsanity.com/paper/2011.01956/) (2020) - [The Disparate Equilibria of Algorithmic Decision Making when Individuals Invest Rationally](https://mlsanity.com/paper/1910.04123/) (2019) - [The Role of Randomness and Noise in Strategic Classification](https://mlsanity.com/paper/2005.08377/) (2020) - [Stateful Strategic Regression](https://mlsanity.com/paper/2106.03827/) (2021) - [Learning in Stackelberg Games with Non-myopic Agents](https://mlsanity.com/paper/2208.09407/) (2022) - [On classification of strategic agents who can both game and improve](https://mlsanity.com/paper/2203.00124/) (2022) - [Strategic Classification under Unknown Personalized Manipulation](https://mlsanity.com/paper/2305.16501/) (2023) - [Learning Losses for Strategic Classification](https://mlsanity.com/paper/2203.13421/) (2022) - [Optimal Decision Making Under Strategic Behavior](https://mlsanity.com/paper/1905.09239/) (2019) - [Optimal Prediction Using Expert Advice and Randomized Littlestone Dimension](https://mlsanity.com/paper/2302.13849/) (2023) - [Fundamental Bounds on Online Strategic Classification](https://mlsanity.com/paper/2302.12355/) (2023) - [Sequential Strategic Screening](https://mlsanity.com/paper/2301.13397/) (2023) ## Built on by (most cited first, 16 of 16) - [Strategic Littlestone Dimension: Improved Bounds on Online Strategic Classification](https://mlsanity.com/paper/2407.11619/) (2024) - [PAC Learning with Improvements](https://mlsanity.com/paper/2503.03184/) (2025) - [Incentive-Aware Machine Learning; Robustness, Fairness, Improvement & Causality](https://mlsanity.com/paper/2505.05211/) (2025) - [Should Decision-Makers Reveal Classifiers in Online Strategic Classification?](https://mlsanity.com/paper/2506.01936/) (2025) - [Minimax Group Fairness in Strategic Classification](https://mlsanity.com/paper/2410.02513/) (2024) - [Strategic Classification with Non-Linear Classifiers](https://mlsanity.com/paper/2505.23443/) (2025) - [Learning Classifiers That Induce Markets](https://mlsanity.com/paper/2502.20012/) (2025) - [Anticipating Gaming to Incentivize Improvement: Guiding Agents in (Fair) Strategic Classification](https://mlsanity.com/paper/2505.05594/) (2025) - [Conservative classifiers do consistently well with improving agents: characterizing statistical and online learning](https://mlsanity.com/paper/2506.05252/) (2025) - [Revealing Positive and Negative Role Models to Help People Make Good Decisions](https://mlsanity.com/paper/2603.02495/) (2026) - [On Randomized Algorithms in Online Strategic Classification](https://mlsanity.com/paper/2602.06257/) (2026) - [Online Learning with Improving Agents: Multiclass, Budgeted Agents and Bandit Learners](https://mlsanity.com/paper/2602.17103/) (2026) - [Strategic PAC Learnability via Geometric Definability](https://mlsanity.com/paper/2605.13426/) (2026) - [Linear Strategic Classification with Endogenous Improvements](https://mlsanity.com/paper/2606.01198/) (2026) - [Ambiguous Strategic Classification](https://mlsanity.com/paper/2606.10137/) (2026) - [Robust Strategic Classification under Decision-Dependent Cost Uncertainty](https://mlsanity.com/paper/2606.30136/) (2026) ## Abstract (arXiv) In contrast with standard classification tasks, strategic classification involves agents strategically modifying their features in an effort to receive favorable predictions. For instance, given a classifier determining loan approval based on credit scores, applicants may open or close their credit cards to fool the classifier. The learning goal is to find a classifier robust against strategic manipulations. Various settings, based on what and when information is known, have been explored in strategic classification. In this work, we focus on addressing a fundamental question: the learnability gaps between strategic classification and standard learning. We essentially show that any learnable class is also strategically learnable: we first consider a fully informative setting, where the manipulation structure (which is modeled by a manipulation graph G^star) is known and during training time the learner has access to both the pre-manipulation data and post-manipulation data. We provide nearly tight sample complexity and regret bounds, offering significant improvements over prior results. Then, we relax the fully informative setting by introducing two natural types of uncertainty. First, following Ahmadi et al. (2023), we consider the setting in which the learner only has access to the post-manipulation data. We improve the results of Ahmadi et al. (2023) and close the gap between mistake upper bound and lower bound raised by them. Our second relaxation of the fully informative setting introduces uncertainty to the manipulation structure. That is, we assume that the manipulation graph is unknown but belongs to a known class of graphs. We provide nearly tight bounds on the learning complexity in various unknown manipulation graph settings. Notably, our algorithm in this setting is of independent interest and can be applied to other problems such as multi-label learning.