LIPIcs.FORC.2022.3.pdf
- Filesize: 0.97 MB
- 22 pages
Document
On Classification of Strategic Agents Who Can Both Game and Improve
Authors
-
Part of:
Volume:
3rd Symposium on Foundations of Responsible Computing (FORC 2022)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Symposium on Foundations of Responsible Computing (FORC) - License:
Creative Commons Attribution 4.0 International license
- Publication Date: 2022-07-15
Cite As Get BibTex
Saba Ahmadi, Hedyeh Beyhaghi, Avrim Blum, and Keziah Naggita. On Classification of Strategic Agents Who Can Both Game and Improve. In 3rd Symposium on Foundations of Responsible Computing (FORC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 218, pp. 3:1-3:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.FORC.2022.3
Abstract
In this work, we consider classification of agents who can both game and improve. For example, people wishing to get a loan may be able to take some actions that increase their perceived credit-worthiness and others that also increase their true credit-worthiness. A decision-maker would like to define a classification rule with few false-positives (does not give out many bad loans) while yielding many true positives (giving out many good loans), which includes encouraging agents to improve to become true positives if possible. We consider two models for this problem, a general discrete model and a linear model, and prove algorithmic, learning, and hardness results for each. For the general discrete model, we give an efficient algorithm for the problem of maximizing the number of true positives subject to no false positives, and show how to extend this to a partial-information learning setting. We also show hardness for the problem of maximizing the number of true positives subject to a nonzero bound on the number of false positives, and that this hardness holds even for a finite-point version of our linear model. We also show that maximizing the number of true positives subject to no false positive is NP-hard in our full linear model. We additionally provide an algorithm that determines whether there exists a linear classifier that classifies all agents accurately and causes all improvable agents to become qualified, and give additional results for low-dimensional data.
Subject Classification
ACM Subject Classification
- Theory of computation → Algorithmic mechanism design
- Theory of computation → Sample complexity and generalization bounds
Keywords
- Strategic Classification
- Social Welfare
- Learning
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- Saba Ahmadi, Hedyeh Beyhaghi, Avrim Blum, and Keziah Naggita. The strategic perceptron. In Proceedings of the 22nd ACM Conference on Economics and Computation, pages 6-25, New York, NY, USA, 2021. Association for Computing Machinery. URL: https://doi.org/10.1145/3465456.3467629.
- Saba Ahmadi, Hedyeh Beyhaghi, Avrim Blum, and Keziah Naggita. On classification of strategic agents who can both game and improve. arXiv preprint, 2022. URL: http://arxiv.org/abs/2203.00124.
- Tal Alon, Magdalen Dobson, Ariel Procaccia, Inbal Talgam-Cohen, and Jamie Tucker-Foltz. Multiagent evaluation mechanisms. In Proceedings of the AAAI Conference on Artificial Intelligence, 34(02):1774-1781, April 2020. URL: https://doi.org/10.1609/aaai.v34i02.5543.
- Yahav Bechavod, Katrina Ligett, Zhiwei Steven Wu, and Juba Ziani. Causal feature discovery through strategic modification. ArXiv, abs/2002.07024, 2020. URL: http://arxiv.org/abs/2002.07024.
- Mark Braverman and Sumegha Garg. The role of randomness and noise in strategic classification. In Proceedings of the 1st Symposium on Foundations of Responsible Computing, FORC 2020, June 1-3, 2020, Harvard University, Cambridge, MA, USA (virtual conference), volume 156 of LIPIcs, pages 9:1-9:20. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. URL: https://doi.org/10.4230/LIPIcs.FORC.2020.9.
- Michael Brückner and Tobias Scheffer. Stackelberg games for adversarial prediction problems. In Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD ’11, pages 547-555, New York, NY, USA, 2011. Association for Computing Machinery. URL: https://doi.org/10.1145/2020408.2020495.
- Jinshuo Dong, Aaron Roth, Zachary Schutzman, Bo Waggoner, and Zhiwei Steven Wu. Strategic classification from revealed preferences. In Proceedings of the 2018 ACM Conference on Economics and Computation, EC ’18, pages 55-70, New York, NY, USA, 2018. Association for Computing Machinery. URL: https://doi.org/10.1145/3219166.3219193.
- Uriel Feige. A threshold of ln n for approximating set cover. J. ACM, 45(4):634-652, 1998. URL: https://doi.org/10.1145/285055.285059.
- Alex M. Frankel and Navin Kartik. Improving information from manipulable data. arXiv: Theoretical Economics, June 2019. URL: https://doi.org/10.1093/jeea/jvab017.
- Nika Haghtalab, Nicole Immorlica, Brendan Lucier, and Jack Z. Wang. Maximizing welfare with incentive-aware evaluation mechanisms. In Christian Bessiere, editor, Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, IJCAI-20, pages 160-166. International Joint Conferences on Artificial Intelligence Organization, July 2020. Main track. URL: https://doi.org/10.24963/ijcai.2020/23.
- Moritz Hardt, Nimrod Megiddo, Christos Papadimitriou, and Mary Wootters. Strategic classification. In Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science, ITCS ’16, pages 111-122, New York, NY, USA, 2016. Association for Computing Machinery. URL: https://doi.org/10.1145/2840728.2840730.
- Keegan Harris, Hoda Heidari, and Zhiwei Steven Wu. Stateful strategic regression. CoRR, abs/2106.03827, 2021. URL: http://arxiv.org/abs/2106.03827.
- Lily Hu, Nicole Immorlica, and Jennifer Wortman Vaughan. The disparate effects of strategic manipulation. In Proceedings of the Conference on Fairness, Accountability, and Transparency, FAT* '19, pages 259-268, New York, NY, USA, 2019. ACM. URL: https://doi.org/10.1145/3287560.3287597.
- Jon Kleinberg and Manish Raghavan. How do classifiers induce agents to invest effort strategically? In Proceedings of the 2019 ACM Conference on Economics and Computation, EC '19, pages 825-844, New York, NY, USA, 2019. Association for Computing Machinery. URL: https://doi.org/10.1145/3328526.3329584.
- John Miller, Smitha Milli, and Moritz Hardt. Strategic classification is causal modeling in disguise. In Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event, volume 119 of Proceedings of Machine Learning Research, pages 6917-6926. PMLR, 2020. URL: http://proceedings.mlr.press/v119/miller20b.html.
- Smitha Milli, John Miller, Anca D. Dragan, and Moritz Hardt. The social cost of strategic classification. In Proceedings of the Conference on Fairness, Accountability, and Transparency, FAT* '19, pages 230-239, New York, NY, USA, 2019. Association for Computing Machinery. URL: https://doi.org/10.1145/3287560.3287576.
- Yonadav Shavit, Benjamin Edelman, and Brian Axelrod. Learning from strategic agents: Accuracy, improvement, and causality. In Hal Daumé III and Aarti Singh, editors, Proceedings of the 37th International Conference on Machine Learning, volume abs/2002.10066 of Proceedings of Machine Learning Research, pages 8676-8686. PMLR, 13-18 July 2020. URL: http://proceedings.mlr.press/v119/shavit20a.html, URL: http://arxiv.org/abs/2002.10066.
- Shenke Xiao, Zihe Wang, Mengjing Chen, Pingzhong Tang, and Xiwang Yang. Optimal common contract with heterogeneous agents. Proceedings of the AAAI Conference on Artificial Intelligence, 34(05):7309-7316, April 2020. URL: https://doi.org/10.1609/aaai.v34i05.6224.