# Strategic Classification

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

## Key facts

- Cited by 257 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Jun 2015.

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

- [Outside the Echo Chamber: Optimizing the Performative Risk](https://mlsanity.com/paper/2102.08570/) (2021)
- [Feedback Loops With Language Models Drive In-Context Reward Hacking](https://mlsanity.com/paper/2402.06627/) (2024)
- [How to Learn when Data Reacts to Your Model: Performative Gradient Descent](https://mlsanity.com/paper/2102.07698/) (2021)
- [Strategic Classification in the Dark](https://mlsanity.com/paper/2102.11592/) (2021)
- [Data Feedback Loops: Model-driven Amplification of Dataset Biases](https://mlsanity.com/paper/2209.03942/) (2022)
- [Strategic Classification Made Practical](https://mlsanity.com/paper/2103.01826/) (2021)
- [Describing Differences between Text Distributions with Natural Language](https://mlsanity.com/paper/2201.12323/) (2022)
- [Conformal Prediction Under Feedback Covariate Shift for Biomolecular Design](https://mlsanity.com/paper/2202.03613/) (2022)
- [Who Leads and Who Follows in Strategic Classification?](https://mlsanity.com/paper/2106.12529/) (2021)
- [Performative Prediction: Past and Future](https://mlsanity.com/paper/2310.16608/) (2023)
- [Information Discrepancy in Strategic Learning](https://mlsanity.com/paper/2103.01028/) (2021)
- [Alternative Microfoundations for Strategic Classification](https://mlsanity.com/paper/2106.12705/) (2021)
- [Multiplayer Performative Prediction: Learning in Decision-Dependent Games](https://mlsanity.com/paper/2201.03398/) (2022)
- [Performative Power](https://mlsanity.com/paper/2203.17232/) (2022)
- [Regret Minimization with Performative Feedback](https://mlsanity.com/paper/2202.00628/) (2022)
- [Anticipating Performativity by Predicting from Predictions](https://mlsanity.com/paper/2208.07331/) (2022)
- [Modeling Content Creator Incentives on Algorithm-Curated Platforms](https://mlsanity.com/paper/2206.13102/) (2022)
- [The Sample Complexity of Online Contract Design](https://mlsanity.com/paper/2211.05732/) (2022)
- [Generalized Strategic Classification and the Case of Aligned Incentives](https://mlsanity.com/paper/2202.04357/) (2022)
- [Multi-agent Performative Prediction: From Global Stability and Optimality to Chaos](https://mlsanity.com/paper/2201.10483/) (2022)
- [Supply-Side Equilibria in Recommender Systems](https://mlsanity.com/paper/2206.13489/) (2022)
- [Making Decisions under Outcome Performativity](https://mlsanity.com/paper/2210.01745/) (2022)
- [Stateful Strategic Regression](https://mlsanity.com/paper/2106.03827/) (2021)
- [Strategic Instrumental Variable Regression: Recovering Causal Relationships From Strategic Responses](https://mlsanity.com/paper/2107.05762/) (2021)
- [Algorithmic Collective Action in Machine Learning](https://mlsanity.com/paper/2302.04262/) (2023)
- [How to Learn when Data Gradually Reacts to Your Model](https://mlsanity.com/paper/2112.07042/) (2021)
- [A Validity Perspective on Evaluating the Justified Use of Data-driven Decision-making Algorithms](https://mlsanity.com/paper/2206.14983/) (2022)
- [Causal Strategic Classification: A Tale of Two Shifts](https://mlsanity.com/paper/2302.06280/) (2023)
- [Learning in Stackelberg Games with Non-myopic Agents](https://mlsanity.com/paper/2208.09407/) (2022)
- [Fairness Transferability Subject to Bounded Distribution Shift](https://mlsanity.com/paper/2206.00129/) (2022)

## Abstract (arXiv)

Machine learning relies on the assumption that unseen test instances of a classification problem follow the same distribution as observed training data. However, this principle can break down when machine learning is used to make important decisions about the welfare (employment, education, health) of strategic individuals. Knowing information about the classifier, such individuals may manipulate their attributes in order to obtain a better classification outcome. As a result of this behavior---often referred to as gaming---the performance of the classifier may deteriorate sharply. Indeed, gaming is a well-known obstacle for using machine learning methods in practice; in financial policy-making, the problem is widely known as Goodhart's law. In this paper, we formalize the problem, and pursue algorithms for learning classifiers that are robust to gaming. We model classification as a sequential game between a player named "Jury" and a player named "Contestant." Jury designs a classifier, and Contestant receives an input to the classifier, which he may change at some cost. Jury's goal is to achieve high classification accuracy with respect to Contestant's original input and some underlying target classification function. Contestant's goal is to achieve a favorable classification outcome while taking into account the cost of achieving it. For a natural class of cost functions, we obtain computationally efficient learning algorithms which are near-optimal. Surprisingly, our algorithms are efficient even on concept classes that are computationally hard to learn. For general cost functions, designing an approximately optimal strategy-proof classifier, for inverse-polynomial approximation, is NP-hard.