Strategic classification from revealed preferences

Jinshuo Dong, Aaron Roth, Zachary Schutzman, Bo Waggoner, Zhiwei Steven Wu

Research output: Chapter in Book/Report/Conference proceedingConference contribution

16 Scopus citations

Abstract

We study an online linear classification problem in which the data is generated by strategic agents who manipulate their features in an effort to change the classification outcome. In rounds, the learner deploys a classifier, then an adversarially chosen agent arrives and possibly manipulates her features to optimally respond to the learner's choice of classifier. The learner has no knowledge of the agents' utility functions or “real” features, which may vary widely across agents. Instead, the learner is only able to observe their “revealed preferences”, i.e., the manipulated feature vectors they provide. For a broad family of agent cost functions, we give a computationally efficient learning algorithm that is able to obtain diminishing “Stackelberg regret” - a form of policy regret that guarantees that the learner is realizing loss nearly as small as that of the best classifier in hindsight, even allowing for the fact that agents would have best-responded differently to the optimal classifier.

Original languageEnglish (US)
Title of host publicationACM EC 2018 - Proceedings of the 2018 ACM Conference on Economics and Computation
PublisherAssociation for Computing Machinery, Inc
Pages55-70
Number of pages16
ISBN (Electronic)9781450358293
DOIs
StatePublished - Jun 11 2018
Event19th ACM Conference on Economics and Computation, EC 2018 - Ithaca, United States
Duration: Jun 18 2018Jun 22 2018

Publication series

NameACM EC 2018 - Proceedings of the 2018 ACM Conference on Economics and Computation

Other

Other19th ACM Conference on Economics and Computation, EC 2018
CountryUnited States
CityIthaca
Period6/18/186/22/18

Keywords

  • Online learning
  • Revealed preferences
  • Stackelberg regret
  • Strategic agents
  • Strategic classification

Fingerprint Dive into the research topics of 'Strategic classification from revealed preferences'. Together they form a unique fingerprint.

Cite this