# Strategic Classification under Unknown Personalized Manipulation

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

## Key facts

- Cited by 24 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 27 references that are in the map.
- First posted on arXiv 25 May 2023.

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

- [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)
- [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)
- [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)
- [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)
- [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)
- [Fundamental Bounds on Online Strategic Classification](https://mlsanity.com/paper/2302.12355/) (2023)

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

- [Learnability Gaps of Strategic Classification](https://mlsanity.com/paper/2402.19303/) (2024)
- [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)
- [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)
- [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)
- [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)
- [Contextual Dynamic Pricing with Strategic Buyers](https://mlsanity.com/paper/2307.04055/) (2023)
- [Practical Performative Policy Learning with Strategic Agents](https://mlsanity.com/paper/2412.01344/) (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)
- [Explanation Design in Strategic Learning: Sufficient Explanations that Induce Non-harmful Responses](https://mlsanity.com/paper/2502.04058/) (2025)
- [When Tabular Foundation Models Meet Strategic Tabular Data: A Prior Alignment Approach](https://mlsanity.com/paper/2605.19662/) (2026)
- [On Randomized Algorithms in Online Strategic Classification](https://mlsanity.com/paper/2602.06257/) (2026)
- [Strategic PAC Learnability via Geometric Definability](https://mlsanity.com/paper/2605.13426/) (2026)
- [Partial Fairness Awareness: Belief-Guided Strategic Mechanism for Strategic Agents](https://mlsanity.com/paper/2606.00826/) (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)

We study the fundamental mistake bound and sample complexity in the strategic classification, where agents can strategically manipulate their feature vector up to an extent in order to be predicted as positive. For example, given a classifier determining college admission, student candidates may try to take easier classes to improve their GPA, retake SAT and change schools in an effort to fool the classifier. Ball manipulations are a widely studied class of manipulations in the literature, where agents can modify their feature vector within a bounded radius ball. Unlike most prior work, our work considers manipulations to be personalized, meaning that agents can have different levels of manipulation abilities (e.g., varying radii for ball manipulations), and unknown to the learner. We formalize the learning problem in an interaction model where the learner first deploys a classifier and the agent manipulates the feature vector within their manipulation set to game the deployed classifier. We investigate various scenarios in terms of the information available to the learner during the interaction, such as observing the original feature vector before or after deployment, observing the manipulated feature vector, or not seeing either the original or the manipulated feature vector. We begin by providing online mistake bounds and PAC sample complexity in these scenarios for ball manipulations. We also explore non-ball manipulations and show that, even in the simplest scenario where both the original and the manipulated feature vectors are revealed, the mistake bounds and sample complexity are lower bounded by Omega(|H|) when the target function belongs to a known class H.