The role of randomness and noise in strategic classification

Mark Braverman, Sumegha Garg

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

12 Scopus citations


We investigate the problem of designing optimal classifiers in the “strategic classification” setting, where the classification is part of a game in which players can modify their features to attain a favorable classification outcome (while incurring some cost). Previously, the problem has been considered from a learning-theoretic perspective and from the algorithmic fairness perspective. Our main contributions include Showing that if the objective is to maximize the efficiency of the classification process (defined as the accuracy of the outcome minus the sunk cost of the qualified players manipulating their features to gain a better outcome), then using randomized classifiers (that is, ones where the probability of a given feature vector to be accepted by the classifier is strictly between 0 and 1) is necessary. Showing that in many natural cases, the imposed optimal solution (in terms of efficiency) has the structure where players never change their feature vectors (and the randomized classifier is structured in a way, such that the gain in the probability of being classified as a “1” does not justify the expense of changing one’s features). Observing that the randomized classification is not a stable best-response from the classifier’s viewpoint, and that the classifier doesn’t benefit from randomized classifiers without creating instability in the system. Showing that in some cases, a noisier signal leads to better equilibria outcomes – improving both accuracy and fairness when more than one subpopulation with different feature adjustment costs are involved. This is particularly interesting from a policy perspective, since it is hard to force institutions to stick to a particular randomized classification strategy (especially in a context of a market with multiple classifiers), but it is possible to alter the information environment to make the feature signals inherently noisier.

Original languageEnglish (US)
Title of host publication1st Symposium on Foundations of Responsible Computing, FORC 2020
EditorsAaron Roth
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959771429
StatePublished - May 1 2020
Event1st Symposium on Foundations of Responsible Computing, FORC 2020 - Virtual, Cambridge, United States
Duration: Jun 1 2020 → …

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
ISSN (Print)1868-8969


Conference1st Symposium on Foundations of Responsible Computing, FORC 2020
Country/TerritoryUnited States
CityVirtual, Cambridge
Period6/1/20 → …

All Science Journal Classification (ASJC) codes

  • Software


  • Fairness
  • Noisy features
  • Randomized classification
  • Strategic classification


Dive into the research topics of 'The role of randomness and noise in strategic classification'. Together they form a unique fingerprint.

Cite this