Strategic classification

DOI10.1145/2840728.2840730MaRDI QIDQ2800558zbMATH OpenOpenAlexFDO

Authors Moritz Hardt, Nimrod Megiddo, Mary Wootters, Christos Papadimitriou

Publication date 15 April 2016

Published in Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1506.06980

zbMATH Keywords

classificationgame theorylearning theory

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05) Other game-theoretic models (91A40) Applications of game theory (91A80)

Abstract: 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.

Recommendations

• Network Games with Strategic Machine Learning
• Algorithms for strategyproof classification
• Induction over constrained strategic agents
• Scalable Optimal Classifiers for Adversarial Settings Under Uncertainty
• Adversarial classification using signaling games with an application to phishing detection

Cited in

(18)

• Algorithms for strategyproof classification
• On incentive-compatible estimators
• Human decisions and machine predictions
• GOODHART'S LAW AND MACHINE LEARNING: A STRUCTURAL PERSPECTIVE
• On classification of strategic agents who can both game and improve
• Scalable Optimal Classifiers for Adversarial Settings Under Uncertainty
• Network Games with Strategic Machine Learning
• Eliciting truthful reports with partial signals in repeated games
• Truthful and privacy-preserving generalized linear models
• Performative prediction: past and future
• The search for stability: learning dynamics of strategic publishers with initial documents
• Contextual Dynamic Pricing with Strategic Buyers
• Should Humans Lie to Machines? The Incentive Compatibility of Lasso and GLM Structured Sparsity Estimators
• Asymptotic degradation of linear regression estimates with strategic data sources
• Understanding simultaneous train and test robustness
• Algorithmic contract theory: a survey
• Numerical methods for stochastic optimization problems with decision-dependent distributions under large delays
• Optimal scoring rule design under partial knowledge

This page was built for publication: Strategic classification

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2800558)