Strategic Classification
By Moritz Hardt, N. Megiddo, Christos H. Papadimitriou, Mary Wootters. 2015
468 citations recorded by the source corpus.
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 drawn from a distribution. Before being classified, Contestant may change his input based on Jury's classifier. However, Contestant incurs a cost for these changes according to a cost function. Jury's goal is to achieve high classification accuracy with respect to Contestant's original input and some underlying target classification function, assuming Contestant plays best response. Contestant's goal is to achieve a favorable classification outcome while taking into account the cost of achieving it. For a natural class of "separable" cost functions, and certain generalizations, we obtain computationally efficient learning algorithms which are near optimal, achieving a classification error that is arbitrarily close to the theoretical minimum. 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.
Subfields: Artificial Intelligence, Computational Theory and Mathematics, Statistical Learning Theory, Game & Decision Theory
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Artificial Intelligence
- Percy Liang
- Bo Li
- Yoshua Bengio
- Bernhard Schölkopf
- Sergey Levine
- Quoc V. Le
- Mohit Bansal
- Jianfeng Gao
In Computational Theory and Mathematics
- Bernhard Schölkopf
- Manuel Gomez-Rodriguez
- Anca Dragan
- Moritz Hardt
- Bo Li
- Yevgeniy Vorobeychik
- Liang Tong
- Chen Hajaj
In Statistical Learning Theory
- Moritz Hardt
- Bo Li
- Yevgeniy Vorobeychik
- Liang Tong
- Chen Hajaj
- Manuel Gomez-Rodriguez
- Ludwig Schmidt
- Bernhard Schölkopf
In Game & Decision Theory
- Nicole Immorlica
- Lily Hu
- Jennifer Wortman Vaughan
- Bo Li
- Yevgeniy Vorobeychik
- Liang Tong
- Chen Hajaj
- Joshua A. Kroll
Citations in the corpus
- Price of Transparency in Strategic Machine Learning (2016, background): “Number of books: This example originates from the main motivating example of [4], but also involves a subtle but important modification: Social studies have shown that a student’s success can be very well predicted from the number of books in the parents’ household [5].”
- Actionable Recourse in Linear Classification (2018, background): “Other concepts related to recourse in machine learning include: anchors, which are subsets of features that fix the predicted outcome [25]; adversarial perturbations, which studies the robustness of predictions with respect to small changes in input [14]; and strategic classification, which consider”
- Performative Prediction (2020, background): “…. βγ η − ε(1.5ηβ2 + β)β+γ The conclusion of Theorem 3.8 is a strict generalization of a classical optimization result which considers a static objec- 1 − η βγ tive, in which case the rate of contraction is β+γ (see for example Theorem 2.1.15 in Nesterov (2013) or Lemma 3.7 in Hardt et al. (2016b)).”
- Feature Conservation in Adversarial Classifier Evasion: A Case Study (2017, methodology): “A series of methods follow their framework, but consider more general classes of classifiers, introducing a constraint on the evasion cost, and explicitly trading off the degree to which an instance appears as benign and evasion cost [2], [3], [14], [38], [16], [18], [19], [26], [34].”
- This Thing Called Fairness (2019, background): “This leads into the idea of strategically manipulating one’s attributes in order to get the most desirable output from a model and the related question of how to build a model to resist such gaming [59].”
- Hardening Classifiers against Evasion: the Good, the Bad, and the Ugly (2017, methodology): “A series of methods follow their framework, but consider more general classes of classifiers, introducing a constraint on the evasion cost, and explicitly trading off the degree to which an instance appears as benign and evasion cost [2], [3], [13], [38], [16], [18], [19], [25], [35].”
- Fair, Transparent, and Accountable Algorithmic Decision-making Processes (2017, unknown): “[28] have proposed adversarial methods for de-”
- The philosophical basis of algorithmic recourse (2020, background): “The second aspect draws a contrast with other literature that considers the problem of strategic manipulation of features to achieve a desired goal[14, 16, 24].”
- Data Feedback Loops: Model-driven Amplification of Dataset Biases (2022, background): “The general problem of modelinduced feedback in machine learning has been previously studied as performative prediction and strategic classification (Perdomo et al., 2020; Hardt et al., 2016), where future data distributions can change arbitrarily in response to the deployed model.”
- Fairness Violations and Mitigation under Covariate Shift (2019, background): “high predicted risk [36]), or might incentivize individuals to strategically adapt their features for favourable outcomes [22, 35], thus, causing distribution shift.”
- Algorithmic Decision-Making Based on Machine Learning from Big Data: Can Transparency Restore Accountability? (2017, background): “First results (concerning spam filtering) indicate that such dynamic classifiers perform somewhat better against gaming adversaries than static ones (Brückner et al. 2012; Hardt et al. 2016).”
- How Do Classifiers Induce Agents to Invest Effort Strategically? (2018, background): “in the case of spam detection, and more recently in terms of Stackelberg competitions, in which the evaluator publishes a rule and the agent may respond by manipulating their features strategically [5, 13, 18, 23, 29].”
- Explicit Defense Actions Against Test-Set Attacks (2017, background): “A separate line of research has posed the problem of learning in the presence of adversaries in game theoretic contexts (Liu and Chawla 2009; Brückner, Kanzow, and Scheffer 2012; Dalvi et al. 2004; Brückner and Scheffer 2009; 2011; Hardt et al. 2016; Brückner and Scheffer 2011).”
- Model Reconstruction from Model Explanations (2018, background): “Revealed models may also be easier to game, resulting in diminished predictive power [6, 8].”
- The Disparate Effects of Strategic Manipulation (2018, methodology): “As such, in this paper we ask, “What are the effects of strategic classification and manipulation in a world of social stratification?” As in previous work in strategic classification, we cast the problem as a Stackelberg game in which the learner moves first and publishes her classifier before cand”
- The Social Cost of Strategic Classification (2018, methodology): “[13] give algorithms to compute the Stackelberg equilibrium, which corresponds to the extreme τ ∗ solution in our trade-off curves.”
- Optimal Decision Making Under Strategic Behavior (2019, background): “Similarly as in most previous work in strategic classification [2, 5, 6, 8, 11], we consider a Stackelberg game in which the decision maker moves first and shares her decision policy before individuals best-respond3.”