# Fundamental Bounds on Online Strategic Classification

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

## Key facts

- Cited by 17 papers in the map (data through 14 Oct 2026).
- Builds on 21 of its 48 references that are in the map.
- First posted on arXiv 23 Feb 2023.

## Builds on (most cited first, 21 of 21)

- [Performative Prediction](https://mlsanity.com/paper/2002.06673/) (2020)
- [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)
- [How Do Classifiers Induce Agents To Invest Effort Strategically?](https://mlsanity.com/paper/1807.05307/) (2018)
- [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)
- [Strategic Classification Made Practical](https://mlsanity.com/paper/2103.01826/) (2021)
- [Who Leads and Who Follows in Strategic Classification?](https://mlsanity.com/paper/2106.12529/) (2021)
- [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 Role of Randomness and Noise in Strategic Classification](https://mlsanity.com/paper/2005.08377/) (2020)
- [Downstream Effects of Affirmative Action](https://mlsanity.com/paper/1808.09004/) (2018)
- [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)
- [Learning Losses for Strategic Classification](https://mlsanity.com/paper/2203.13421/) (2022)
- [Access to Population-Level Signaling as a Source of Inequality](https://mlsanity.com/paper/1809.04224/) (2018)

## Built on by (most cited first, 17 of 17)

- [Calibrated Stackelberg Games: Learning Optimal Commitments Against Calibrated Agents](https://mlsanity.com/paper/2306.02704/) (2023)
- [Strategic Classification under Unknown Personalized Manipulation](https://mlsanity.com/paper/2305.16501/) (2023)
- [Learnability Gaps of Strategic Classification](https://mlsanity.com/paper/2402.19303/) (2024)
- [Strategic Apple Tasting](https://mlsanity.com/paper/2306.06250/) (2023)
- [Strategic Littlestone Dimension: Improved Bounds on Online Strategic Classification](https://mlsanity.com/paper/2407.11619/) (2024)
- [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)
- [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)
- [Explanation Design in Strategic Learning: Sufficient Explanations that Induce Non-harmful Responses](https://mlsanity.com/paper/2502.04058/) (2025)
- [Learning Local Stackelberg Equilibria from Repeated Interactions with a Learning Agent](https://mlsanity.com/paper/2510.22471/) (2025)
- [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)
- [Linear Strategic Classification with Endogenous Improvements](https://mlsanity.com/paper/2606.01198/) (2026)
- [Ambiguous Strategic Classification](https://mlsanity.com/paper/2606.10137/) (2026)

## Abstract (arXiv)

We study the problem of online binary classification where strategic agents can manipulate their observable features in predefined ways, modeled by a manipulation graph, in order to receive a positive classification. We show this setting differs in fundamental ways from non-strategic online classification. For instance, whereas in the non-strategic case, a mistake bound of ln|H| is achievable via the halving algorithm when the target function belongs to a known class H, we show that no deterministic algorithm can achieve a mistake bound o(Delta) in the strategic setting, where Delta is the maximum degree of the manipulation graph (even when |H|=O(Delta)). We obtain an algorithm achieving mistake bound O(Deltaln|H|). We also extend this to the agnostic setting and obtain an algorithm with a Delta multiplicative regret, and we show no deterministic algorithm can achieve o(Delta) multiplicative regret. Next, we study two randomized models based on whether the random choices are made before or after agents respond, and show they exhibit fundamental differences. In the first model, at each round the learner deterministically chooses a probability distribution over classifiers inducing expected values on each vertex (probabilities of being classified as positive), which the strategic agents respond to. We show that any learner in this model has to suffer linear regret. On the other hand, in the second model, while the adversary who selects the next agent must respond to the learner's probability distribution over classifiers, the agent then responds to the actual hypothesis classifier drawn from this distribution. Surprisingly, we show this model is more advantageous to the learner, and we design randomized algorithms that achieve sublinear regret bounds against both oblivious and adaptive adversaries.