research-article

How Do Classifiers Induce Agents to Invest Effort Strategically?

Authors:

Manish RaghavanAuthors Info & Claims

EC '19: Proceedings of the 2019 ACM Conference on Economics and Computation

Pages 825 - 844

https://doi.org/10.1145/3328526.3329584

Published: 17 June 2019 Publication History

Abstract

Algorithms are often used to produce decision-making rules that classify or evaluate individuals. When these individuals have incentives to be classified a certain way, they may behave strategically to influence their outcomes. We develop a model for how strategic agents can invest effort in order to change the outcomes they receive, and we give a tight characterization of when such agents can be incentivized to invest specified forms of effort into improving their outcomes as opposed to "gaming" the classifier. We show that whenever any "reasonable" mechanism can do so, a simple linear mechanism suffices.

Supplementary Material

MP4 File (p825-kleinberg.mp4)

Download
1395.97 MB

References

[1]

Kenneth J Arrow. 1963. Uncertainty and the welfare economics of medical care. American Economic Review (1963).

[2]

Kenneth J Arrow. 1968. The economics of moral hazard: further comment. American Economic Review, Vol. 58 (1968).

[3]

Jane R Bambauer and Tal Zarsky. 2018. The Algorithm Game. (2018).

[4]

Jöran Beel, Bela Gipp, and Erik Wilde. 2009. Academic Search Engine Optimization (ASEO) Optimizing Scholarly Literature for Google Scholar & Co. Journal of scholarly publishing, Vol. 41, 2 (2009), 176--190.

[5]

Michael Brückner and Tobias Scheffer. 2011. Stackelberg games for adversarial prediction problems. In Proceedings of the 17th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, 547--555.

Digital Library

[6]

Yiling Chen, Chara Podimata, Ariel D Procaccia, and Nisarg Shah. 2018. Strategyproof Linear Regression in High Dimensions. In Proceedings of the 2018 ACM Conference on Economics and Computation. ACM, 9--26.

Digital Library

[7]

Steven NS Cheung. 1969. The theory of share tenancy .Arcadia Press Ltd.

[8]

Stephen Coate and Glenn C Loury. 1993. Will affirmative-action policies eliminate negative stereotypes? The American Economic Review (1993), 1220--1240.

[9]

Rachel Cummings, Stratis Ioannidis, and Katrina Ligett. 2015. Truthful linear regression. In Conf. Learning Theory .

[10]

Nilesh Dalvi, Pedro Domingos, Sumit Sanghai, Deepak Verma, et almbox. 2004. Adversarial classification. In Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining. ACM.

Digital Library

[11]

Harold Davis. 2006. Search engine optimization .“O'Reilly Media, Inc.”.

[12]

Ofer Dekel, Felix Fischer, and Ariel D Procaccia. 2010. Incentive compatible regression learning. J. Comput. System Sci., Vol. 76, 8 (2010), 759--777.

Digital Library

[13]

Jinshuo Dong, Aaron Roth, Zachary Schutzman, Bo Waggoner, and Zhiwei Steven Wu. 2018. Strategic Classification from Revealed Preferences. In Proceedings of the 2018 ACM Conference on Economics and Computation. ACM, 55--70.

Digital Library

[14]

Virginia Eubanks. 2018. Automating Bias . Scientific American, Vol. 319, 5 (2018), 68--71.

[15]

Dean Foust and Aaron Pressman. 2008. Credit scores: Not-so-magic numbers. Business Week, Vol. 7 (2008).

[16]

Roland G Fryer Jr and Glenn C Loury. 2013. Valuing diversity. Journal of Political Economy, Vol. 121, 4 (2013), 747--774.

[17]

Sanford J Grossman and Oliver D Hart. 1983. An analysis of the principal-agent problem. Econometrica (1983), 7--45.

[18]

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.

Digital Library

[19]

Benjamin E Hermalin and Michael L Katz. 1991. Moral hazard and verifiability: The effects of renegotiation in agency. Econometrica: Journal of the Econometric Society (1991), 1735--1753.

[20]

Bengt Holmstrom and Paul Milgrom. 1987. Aggregation and linearity in the provision of intertemporal incentives. Econometrica: Journal of the Econometric Society (1987), 303--328.

[21]

Bengt Holmstrom and Paul Milgrom. 1991. Multitask principal-agent analyses: Incentive contracts, asset ownership, and job design. JL Econ. & Org., Vol. 7 (1991), 24.

[22]

Lily Hu and Yiling Chen. 2017. A short-term intervention for long-term fairness in the labor market. In Proc. World Wide Web Conference .

Digital Library

[23]

Lily Hu, Nicole Immorlica, and Jennifer Wortman Vaughan. 2019. The Disparate Effects of Strategic Manipulation. In Proceedings of the Conference on Fairness, Accountability, and Transparency (FAT*) .

Digital Library

[24]

Michael C Jensen and William H Meckling. 1976. Theory of the firm: Managerial behavior, agency costs and ownership structure. Journal of financial economics, Vol. 3, 4 (1976), 305--360.

[25]

Steven Kerr. 1975. On the folly of rewarding A, while hoping for B . Academy of Management journal, Vol. 18 (1975).

[26]

Daniel Koretz, Robert Linn, Stephen Dunbar, and Lorrie Shepard. 1991. The Effects of High-Stakes Testing On Achievement: Preliminary Findings About Generalization Across Tests. In American Educational Research Association and the National Council on Measurement in Education .

[27]

Daniel M Koretz. 2008. Measuring up .Harvard University Press.

[28]

Jean-Jacques Laffont and David Martimort. 2009. The Theory of Incentives: The Principal-Agent Model .Princeton University Press.

[29]

Smitha Milli, John Miller, Anca D Dragan, and Moritz Hardt. 2019. The Social Cost of Strategic Classification. In Proceedings of the Conference on Fairness, Accountability, and Transparency (FAT*) .

Digital Library

[30]

Balas Kausik Natarajan. 1995. Sparse approximate solutions to linear systems. SIAM journal on computing (1995).

Digital Library

[31]

Mark V Pauly. 1968. The economics of moral hazard: comment. American Economic Review (1968).

[32]

Stephen A Ross. 1973. The economic theory of agency: The principal's problem. American Economic Review, Vol. 63 (1973).

[33]

Michael Spence. 1973. Job Market Signaling. Quarterly Journal of Economics, Vol. 87 (1973), 355--374.

[34]

Joseph E Stiglitz. 1974. Incentives and risk sharing in sharecropping. The Review of Economic Studies, Vol. 41 (1974).

[35]

Tal Z Zarsky. 2007. Law and online social networks: Mapping the challenges and promises of user-generated information flows. Fordham Intell. Prop. Media & Ent. LJ, Vol. 18 (2007), 741.

[36]

Malte Ziewitz. Forthcoming. Rethinking Gaming: The Ethical Work of Optimization in Web Search Engines. Social Studies of Science .

Cited By

Immorlica NJagadeesan MLucier BChua TNgo CKa-Wei Lee RKumar RLauw H(2024)Clickbait vs. Quality: How Engagement-Based Optimization Shapes the Content Landscape in Online PlatformsProceedings of the ACM Web Conference 202410.1145/3589334.3645353(36-45)Online publication date: 13-May-2024
https://dl.acm.org/doi/10.1145/3589334.3645353
Jagadeesan MGarg NSteinhardt JOh ANaumann TGloberson ASaenko KHardt MLevine S(2023)Supply-side equilibria in recommender systemsProceedings of the 37th International Conference on Neural Information Processing Systems10.5555/3666122.3666764(14597-14608)Online publication date: 10-Dec-2023
https://dl.acm.org/doi/10.5555/3666122.3666764
Saig ETalgam-Cohen IRosenfeld NOh ANaumann TGloberson ASaenko KHardt MLevine S(2023)Delegated classificationProceedings of the 37th International Conference on Neural Information Processing Systems10.5555/3666122.3666701(13200-13236)Online publication date: 10-Dec-2023
https://dl.acm.org/doi/10.5555/3666122.3666701
Show More Cited By

Index Terms

How Do Classifiers Induce Agents to Invest Effort Strategically?
1. Theory of computation
  1. Theory and algorithms for application domains
    1. Algorithmic game theory and mechanism design
      1. Algorithmic game theory
      2. Algorithmic mechanism design

Recommendations

How Do Classifiers Induce Agents to Invest Effort Strategically?
Special Issue on EC’19

Algorithms are often used to produce decision-making rules that classify or evaluate individuals. When these individuals have incentives to be classified a certain way, they may behave strategically to influence their outcomes. We develop a model for ...
The Social Cost of Strategic Classification
FAT* '19: Proceedings of the Conference on Fairness, Accountability, and Transparency

Consequential decision-making typically incentivizes individuals to behave strategically, tailoring their behavior to the specifics of the decision rule. A long line of work has therefore sought to counteract strategic behavior by designing more ...
The Disparate Effects of Strategic Manipulation
FAT* '19: Proceedings of the Conference on Fairness, Accountability, and Transparency

When consequential decisions are informed by algorithmic input, individuals may feel compelled to alter their behavior in order to gain a system's approval. Models of agent responsiveness, termed "strategic manipulation," analyze the interaction between ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

EC '19: Proceedings of the 2019 ACM Conference on Economics and Computation

June 2019

947 pages

ISBN:9781450367929

DOI:10.1145/3328526

General Chair:
Anna Karlin
University of Washington, USA
,
Program Chairs:
Nicole Immorlica
Microsoft Research, USA
,
Ramesh Johari
Stanford University, USA

Copyright © 2019 ACM.

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 ACM 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

SIGecom: Special Interest Group on Economics and Computation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 17 June 2019

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

EC '19

Sponsor:

SIGecom

EC '19: ACM Conference on Economics and Computation

June 24 - 28, 2019

AZ, Phoenix, USA

Acceptance Rates

EC '19 Paper Acceptance Rate 106 of 382 submissions, 28%;

Overall Acceptance Rate 664 of 2,389 submissions, 28%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

26
Total Citations
View Citations
244
Total Downloads

Downloads (Last 12 months)11
Downloads (Last 6 weeks)0

Reflects downloads up to 21 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Immorlica NJagadeesan MLucier BChua TNgo CKa-Wei Lee RKumar RLauw H(2024)Clickbait vs. Quality: How Engagement-Based Optimization Shapes the Content Landscape in Online PlatformsProceedings of the ACM Web Conference 202410.1145/3589334.3645353(36-45)Online publication date: 13-May-2024
https://dl.acm.org/doi/10.1145/3589334.3645353
Jagadeesan MGarg NSteinhardt JOh ANaumann TGloberson ASaenko KHardt MLevine S(2023)Supply-side equilibria in recommender systemsProceedings of the 37th International Conference on Neural Information Processing Systems10.5555/3666122.3666764(14597-14608)Online publication date: 10-Dec-2023
https://dl.acm.org/doi/10.5555/3666122.3666764
Saig ETalgam-Cohen IRosenfeld NOh ANaumann TGloberson ASaenko KHardt MLevine S(2023)Delegated classificationProceedings of the 37th International Conference on Neural Information Processing Systems10.5555/3666122.3666701(13200-13236)Online publication date: 10-Dec-2023
https://dl.acm.org/doi/10.5555/3666122.3666701
Carroll MChan AAshton HKrueger D(2023)Characterizing Manipulation from AI SystemsProceedings of the 3rd ACM Conference on Equity and Access in Algorithms, Mechanisms, and Optimization10.1145/3617694.3623226(1-13)Online publication date: 30-Oct-2023
https://dl.acm.org/doi/10.1145/3617694.3623226
Emelianov VGast NLoiseau PPennock DSegal ISeuken S(2022)Fairness in Selection Problems with Strategic CandidatesProceedings of the 23rd ACM Conference on Economics and Computation10.1145/3490486.3538287(375-403)Online publication date: 12-Jul-2022
https://dl.acm.org/doi/10.1145/3490486.3538287
Dutting PEzra TFeldman MKesselheim T(2022)Combinatorial Contracts2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS52979.2021.00084(815-826)Online publication date: Feb-2022
https://doi.org/10.1109/FOCS52979.2021.00084
Eliaz KSpiegler R(2022)On incentive-compatible estimatorsGames and Economic Behavior10.1016/j.geb.2022.01.002Online publication date: Jan-2022
https://doi.org/10.1016/j.geb.2022.01.002
Alon TDütting PTalgam-Cohen IBiró PChawla SEchenique F(2021)Contracts with Private Cost per Unit-of-EffortProceedings of the 22nd ACM Conference on Economics and Computation10.1145/3465456.3467651(52-69)Online publication date: 18-Jul-2021
https://dl.acm.org/doi/10.1145/3465456.3467651
Dai JFazelpour SLipton ZFourcade MKuipers BLazar SMulligan D(2021)Fair Machine Learning Under Partial ComplianceProceedings of the 2021 AAAI/ACM Conference on AI, Ethics, and Society10.1145/3461702.3462521(55-65)Online publication date: 21-Jul-2021
https://dl.acm.org/doi/10.1145/3461702.3462521
Finocchiaro JMaio RMonachou FPatro GRaghavan MStoica ATsirtsis S(2021)Bridging Machine Learning and Mechanism Design towards Algorithmic FairnessProceedings of the 2021 ACM Conference on Fairness, Accountability, and Transparency10.1145/3442188.3445912(489-503)Online publication date: 3-Mar-2021
https://dl.acm.org/doi/10.1145/3442188.3445912
Show More Cited By

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents