Strategic classification

DOI10.1145/2840728.2840730zbMATH Open1334.68184arXiv1506.06980OpenAlexW2913525780MaRDI QIDQ2800558FDOQ2800558

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)

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.

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

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

zbMATH Keywords

classificationlearning theorygame theory

Mathematics Subject Classification ID

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

Cited In (9)

• On classification of strategic agents who can both game and improve
• Network Games with Strategic Machine Learning
• Human decisions and machine predictions
• Algorithms for strategyproof classification
• GOODHART'S LAW AND MACHINE LEARNING: A STRUCTURAL PERSPECTIVE
• Truthful and privacy-preserving generalized linear models
• Eliciting truthful reports with partial signals in repeated games
• Scalable Optimal Classifiers for Adversarial Settings Under Uncertainty
• On incentive-compatible estimators

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)