skip to main content
10.1145/3219166.3219193acmconferencesArticle/Chapter ViewAbstractPublication PagesecConference Proceedingsconference-collections
research-article
Public Access

Strategic Classification from Revealed Preferences

Published: 11 June 2018 Publication History

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.

Supplementary Material

MP4 File (p55.mp4)

References

[1]
Kareem Amin, Rachel Cummings, Lili Dworkin, Michael Kearns, and Aaron Roth. 2015. Online Learning and Profit Maximization from Revealed Preferences. AAAI. 770--776.
[2]
Maria-Florina Balcan, Avrim Blum, Nika Haghtalab, and Ariel D. Procaccia. 2015. Commitment Without Regrets: Online Learning in Stackelberg Security Games Proceedings of the Sixteenth ACM Conference on Economics and Computation, EC '15, Portland, OR, USA, June 15--19, 2015. 61--78.
[3]
Maria-Florina Balcan, Amit Daniely, Ruta Mehta, Ruth Urner, and Vijay V Vazirani. 2014. Learning economic parameters from revealed preferences International Conference on Web and Internet Economics. Springer, 338--353.
[4]
Eyal Beigman and Rakesh Vohra. 2006. Learning from revealed preference. In Proceedings of the 7th ACM Conference on Electronic Commerce. ACM, 36--42.
[5]
Aharon Ben-Tal and Arkadi Nemirovski. 2001. Lectures on modern convex optimization: analysis, algorithms, and engineering applications. SIAM.
[6]
Michael Brückner, Christian Kanzow, and Tobias Scheffer. 2012. Static prediction games for adversarial learning problems. Journal of Machine Learning Research Vol. 13, Sep (2012), 2617--2654.
[7]
Michael Brückner and Tobias Scheffer. 2009. Nash equilibria of static prediction games. In Advances in neural information processing systems. 171--179.
[8]
Michael Brückner and Tobias Scheffer. 2011. Stackelberg games for adversarial prediction problems Proceedings of the 17th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, 547--555.
[9]
Sébastien Bubeck. 2015. Convex Optimization: Algorithms and Complexity. Foundations and Trends in Machine Learning Vol. 8, 3--4 (2015), 231--357.
[10]
Sébastien Bubeck, Yin Tat Lee, and Ronen Eldan. 2017. Kernel-based methods for bandit convex optimization. (2017), 72--85.
[11]
Nilesh Dalvi, Pedro Domingos, Sumit Sanghai, and Deepak Verma. 2004. Adversarial classification. In Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, 99--108.
[12]
Abraham D Flaxman, Adam Tauman Kalai, and H Brendan McMahan. 2005. Online convex optimization in the bandit setting: gradient descent without a gradient Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms. Society for Industrial and Applied Mathematics, 385--394.
[13]
Michael Großhans, Christoph Sawade, Michael Brückner, and Tobias Scheffer. 2013. Bayesian games for adversarial regression problems International Conference on Machine Learning. 55--63.
[14]
Moritz Hardt, Nimrod Megiddo, Christos Papadimitriou, and Mary Wootters. 2016. Strategic classification. In Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science. ACM, 111--122.
[15]
Shahin Jabbari, Ryan M Rogers, Aaron Roth, and Steven Z Wu. 2016. Learning from rational behavior: Predicting solutions to unknown linear programs Advances in Neural Information Processing Systems. 1570--1578.
[16]
Dmytro Korzhyk, Vincent Conitzer, and Ronald Parr. 2010. Complexity of Computing Optimal Stackelberg Strategies in Security Resource Allocation Games. In AAAI.
[17]
Brian Kulis and others. 2013. Metric learning: A survey. Foundations and Trends® in Machine Learning, Vol. 5, 4 (2013), 287--364.
[18]
Wei Liu and Sanjay Chawla. 2009. A game theoretical model for adversarial learning. Data Mining Workshops, 2009. ICDMW'09. IEEE International Conference on. IEEE, 25--30.
[19]
Ralph Tyrell Rockafellar. 1970. Convex analysis. Princeton University Press.
[20]
Aaron Roth, Aleksandrs Slivkins, Jonathan Ullman, and Zhiwei Steven Wu. 2017. Multidimensional Dynamic Pricing for Welfare Maximization Proceedings of the 2017 ACM Conference on Economics and Computation. ACM, 519--536.
[21]
Aaron Roth, Jonathan Ullman, and Zhiwei Steven Wu. 2016. Watch and learn: Optimizing from revealed preferences feedback Proceedings of the forty-eighth annual ACM symposium on Theory of Computing. ACM, 949--962.
[22]
Milind Tambe. 2011. Security and game theory: algorithms, deployed systems, lessons learned. Cambridge University Press.
[23]
Morteza Zadimoghaddam and Aaron Roth. 2012. Efficiently Learning from Revealed Preference. In WINE. Springer, 114--127.
[24]
Martin Zinkevich. 2003. Online convex programming and generalized infinitesimal gradient ascent Proceedings of the 20th International Conference on Machine Learning (ICML-03). 928--936.

Cited By

View all
  • (2025)Understanding users’ AI manipulation intentionInformation and Management10.1016/j.im.2024.10406162:1Online publication date: 1-Jan-2025
  • (2024)One-shot strategic classification under unknown costsProceedings of the 41st International Conference on Machine Learning10.5555/3692070.3693809(42719-42741)Online publication date: 21-Jul-2024
  • (2024)Two-timescale derivative free optimization for performative prediction with Markovian dataProceedings of the 41st International Conference on Machine Learning10.5555/3692070.3693339(31425-31450)Online publication date: 21-Jul-2024
  • Show More Cited By

Index Terms

  1. Strategic Classification from Revealed Preferences

      Recommendations

      Comments

      Information & Contributors

      Information

      Published In

      cover image ACM Conferences
      EC '18: Proceedings of the 2018 ACM Conference on Economics and Computation
      June 2018
      713 pages
      ISBN:9781450358293
      DOI:10.1145/3219166
      Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

      Sponsors

      Publisher

      Association for Computing Machinery

      New York, NY, United States

      Publication History

      Published: 11 June 2018

      Permissions

      Request permissions for this article.

      Check for updates

      Author Tags

      1. online learning
      2. revealed preferences
      3. stackelberg regret
      4. strategic agents
      5. strategic classification

      Qualifiers

      • Research-article

      Funding Sources

      Conference

      EC '18
      Sponsor:

      Acceptance Rates

      EC '18 Paper Acceptance Rate 70 of 269 submissions, 26%;
      Overall Acceptance Rate 664 of 2,389 submissions, 28%

      Upcoming Conference

      EC '25
      The 25th ACM Conference on Economics and Computation
      July 7 - 11, 2025
      Stanford , CA , USA

      Contributors

      Other Metrics

      Bibliometrics & Citations

      Bibliometrics

      Article Metrics

      • Downloads (Last 12 months)287
      • Downloads (Last 6 weeks)38
      Reflects downloads up to 20 Feb 2025

      Other Metrics

      Citations

      Cited By

      View all
      • (2025)Understanding users’ AI manipulation intentionInformation and Management10.1016/j.im.2024.10406162:1Online publication date: 1-Jan-2025
      • (2024)One-shot strategic classification under unknown costsProceedings of the 41st International Conference on Machine Learning10.5555/3692070.3693809(42719-42741)Online publication date: 21-Jul-2024
      • (2024)Two-timescale derivative free optimization for performative prediction with Markovian dataProceedings of the 41st International Conference on Machine Learning10.5555/3692070.3693339(31425-31450)Online publication date: 21-Jul-2024
      • (2024)Plug-in performative optimizationProceedings of the 41st International Conference on Machine Learning10.5555/3692070.3693300(30546-30565)Online publication date: 21-Jul-2024
      • (2024)Impact of decentralized learning on player utilities in stackelberg gamesProceedings of the 41st International Conference on Machine Learning10.5555/3692070.3692518(11253-11310)Online publication date: 21-Jul-2024
      • (2024)Performative prediction with bandit feedbackProceedings of the 41st International Conference on Machine Learning10.5555/3692070.3692354(7298-7324)Online publication date: 21-Jul-2024
      • (2024)Efficient Prior-Free Mechanisms for No-Regret AgentsProceedings of the 25th ACM Conference on Economics and Computation10.1145/3670865.3673460(511-541)Online publication date: 8-Jul-2024
      • (2024)Strategic ML: How to Learn With Data That 'Behaves'Proceedings of the 17th ACM International Conference on Web Search and Data Mining10.1145/3616855.3636453(1128-1131)Online publication date: 4-Mar-2024
      • (2024)Recourse for Reclamation: Chatting with Generative Language ModelsExtended Abstracts of the CHI Conference on Human Factors in Computing Systems10.1145/3613905.3650999(1-14)Online publication date: 11-May-2024
      • (2024)Contextual Dynamic Pricing with Strategic BuyersJournal of the American Statistical Association10.1080/01621459.2024.2370613(1-25)Online publication date: 26-Jun-2024
      • Show More Cited By

      View Options

      View options

      PDF

      View or Download as a PDF file.

      PDF

      eReader

      View online with eReader.

      eReader

      Login options

      Figures

      Tables

      Media

      Share

      Share

      Share this Publication link

      Share on social media