# PAC-Learning for Strategic Classification

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

## Key facts

- Cited by 50 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 6 Dec 2020.

## Built on by (most cited first, 30 of 50)

- [Strategic Classification in the Dark](https://mlsanity.com/paper/2102.11592/) (2021)
- [Strategic Classification Made Practical](https://mlsanity.com/paper/2103.01826/) (2021)
- [Information Discrepancy in Strategic Learning](https://mlsanity.com/paper/2103.01028/) (2021)
- [Generalized Strategic Classification and the Case of Aligned Incentives](https://mlsanity.com/paper/2202.04357/) (2022)
- [How to Learn when Data Gradually Reacts to Your Model](https://mlsanity.com/paper/2112.07042/) (2021)
- [Causal Strategic Classification: A Tale of Two Shifts](https://mlsanity.com/paper/2302.06280/) (2023)
- [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)
- [Fundamental Bounds on Online Strategic Classification](https://mlsanity.com/paper/2302.12355/) (2023)
- [Learnability Gaps of Strategic Classification](https://mlsanity.com/paper/2402.19303/) (2024)
- [Adversarial Robustness for Tabular Data through Cost and Utility Awareness](https://mlsanity.com/paper/2208.13058/) (2022)
- [Strategic Classification with Graph Neural Networks](https://mlsanity.com/paper/2205.15765/) (2022)
- [One-Shot Strategic Classification Under Unknown Costs](https://mlsanity.com/paper/2311.02761/) (2023)
- [Non-linear Welfare-Aware Strategic Learning](https://mlsanity.com/paper/2405.01810/) (2024)
- [Strategic Littlestone Dimension: Improved Bounds on Online Strategic Classification](https://mlsanity.com/paper/2407.11619/) (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)
- [Classification Under Strategic Self-Selection](https://mlsanity.com/paper/2402.15274/) (2024)
- [Algorithmic Decision-Making under Agents with Persistent Improvement](https://mlsanity.com/paper/2405.01807/) (2024)
- [Combinatorial Bandits under Strategic Manipulations](https://mlsanity.com/paper/2102.12722/) (2021)
- [PAC Learning with Improvements](https://mlsanity.com/paper/2503.03184/) (2025)
- [Strategic Linear Contextual Bandits](https://mlsanity.com/paper/2406.00551/) (2024)
- [Who's Gaming the System? A Causally-Motivated Approach for Detecting Strategic Adaptation](https://mlsanity.com/paper/2412.02000/) (2024)
- [How Strategic Agents Respond: Comparing Analytical Models with LLM-Generated Responses in Strategic Classification](https://mlsanity.com/paper/2501.16355/) (2025)
- [Incentive-Aware Machine Learning; Robustness, Fairness, Improvement & Causality](https://mlsanity.com/paper/2505.05211/) (2025)
- [Strategic Representation](https://mlsanity.com/paper/2206.08542/) (2022)
- [Minimax Group Fairness in Strategic Classification](https://mlsanity.com/paper/2410.02513/) (2024)
- [Strategic Classification with Randomised Classifiers](https://mlsanity.com/paper/2502.01313/) (2025)
- [Strategic Classification with Non-Linear Classifiers](https://mlsanity.com/paper/2505.23443/) (2025)
- [Adversaries With Incentives: A Strategic Alternative to Adversarial Robustness](https://mlsanity.com/paper/2406.11458/) (2024)

## Abstract (arXiv)

The study of strategic or adversarial manipulation of testing data to fool a classifier has attracted much recent attention. Most previous works have focused on two extreme situations where any testing data point either is completely adversarial or always equally prefers the positive label. In this paper, we generalize both of these through a unified framework for strategic classification, and introduce the notion of strategic VC-dimension (SVC) to capture the PAC-learnability in our general strategic setup. SVC provably generalizes the recent concept of adversarial VC-dimension (AVC) introduced by Cullina et al. arXiv:1806.01471. We instantiate our framework for the fundamental strategic linear classification problem. We fully characterize: (1) the statistical learnability of linear classifiers by pinning down its SVC; (2) its computational tractability by pinning down the complexity of the empirical risk minimization problem. Interestingly, the SVC of linear classifiers is always upper bounded by its standard VC-dimension. This characterization also strictly generalizes the AVC bound for linear classifiers in arXiv:1806.01471.