{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:10:32Z","timestamp":1750219832179,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":37,"publisher":"ACM","license":[{"start":{"date-parts":[[2023,7,7]],"date-time":"2023-07-07T00:00:00Z","timestamp":1688688000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"NSF (National Science Foundation)","doi-asserted-by":"publisher","award":["CCF-2212968","CCF-2145898"],"award-info":[{"award-number":["CCF-2212968","CCF-2145898"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000893","name":"Simons Foundation","doi-asserted-by":"publisher","award":["Simons Collaboration on the Theory of Algorithmic Fairness"],"award-info":[{"award-number":["Simons Collaboration on the Theory of Algorithmic Fairness"]}],"id":[{"id":"10.13039\/100000893","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000185","name":"Defense Advanced Research Projects Agency","doi-asserted-by":"publisher","award":["HR00112020003"],"award-info":[{"award-number":["HR00112020003"]}],"id":[{"id":"10.13039\/100000185","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100020457","name":"C3.ai Digital Transformation Institute","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100020457","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Berkeley AI Research Commons Award"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2023,7,9]]},"DOI":"10.1145\/3580507.3597818","type":"proceedings-article","created":{"date-parts":[[2023,7,7]],"date-time":"2023-07-07T14:19:22Z","timestamp":1688739562000},"page":"22-58","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Fundamental Bounds on Online Strategic Classification"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1046-9940","authenticated-orcid":false,"given":"Saba","family":"Ahmadi","sequence":"first","affiliation":[{"name":"Toyota Technological Institute at Chicago, Chicago, United States of America"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2450-5102","authenticated-orcid":false,"given":"Avrim","family":"Blum","sequence":"additional","affiliation":[{"name":"Toyota Technological Institute at Chicago, Chicago, USA"}]},{"ORCID":"https:\/\/orcid.org\/0009-0001-5634-4975","authenticated-orcid":false,"given":"Kunhe","family":"Yang","sequence":"additional","affiliation":[{"name":"University of California, Berkeley, Berkeley, United States of America"}]}],"member":"320","published-online":{"date-parts":[[2023,7,7]]},"reference":[{"doi-asserted-by":"publisher","key":"e_1_3_2_1_1_1","DOI":"10.1145\/3465456.3467629"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_2_1","DOI":"10.4230\/LIPIcs.FORC.2022.3"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_3_1","DOI":"10.1609\/aaai.v34i02.5543"},{"key":"e_1_3_2_1_4_1","series-title":"SIAM journal on computing 32, 1","volume-title":"The nonstochastic multiarmed bandit problem","author":"Auer Peter","year":"2002","unstructured":"Peter Auer , Nicolo Cesa-Bianchi , Yoav Freund , and Robert E Schapire . 2002. The nonstochastic multiarmed bandit problem . SIAM journal on computing 32, 1 ( 2002 ), 48--77. Peter Auer, Nicolo Cesa-Bianchi, Yoav Freund, and Robert E Schapire. 2002. The nonstochastic multiarmed bandit problem. SIAM journal on computing 32, 1 (2002), 48--77."},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_5_1","DOI":"10.1145\/1007352.1007367"},{"key":"e_1_3_2_1_6_1","volume-title":"International Conference on Artificial Intelligence and Statistics. PMLR, 1234--1242","author":"Bechavod Yahav","year":"2021","unstructured":"Yahav Bechavod , Katrina Ligett , Steven Wu , and Juba Ziani . 2021 . Gaming helps! learning from strategic interactions in natural dynamics . In International Conference on Artificial Intelligence and Statistics. PMLR, 1234--1242 . Yahav Bechavod, Katrina Ligett, Steven Wu, and Juba Ziani. 2021. Gaming helps! learning from strategic interactions in natural dynamics. In International Conference on Artificial Intelligence and Statistics. PMLR, 1234--1242."},{"key":"e_1_3_2_1_7_1","volume-title":"International Conference on Machine Learning. PMLR, 1691--1715","author":"Bechavod Yahav","year":"2022","unstructured":"Yahav Bechavod , Chara Podimata , Steven Wu , and Juba Ziani . 2022 . Information discrepancy in strategic learning . In International Conference on Machine Learning. PMLR, 1691--1715 . Yahav Bechavod, Chara Podimata, Steven Wu, and Juba Ziani. 2022. Information discrepancy in strategic learning. In International Conference on Machine Learning. PMLR, 1691--1715."},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_8_1","DOI":"10.1103\/RevModPhys.34.123"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_9_1","DOI":"10.1017\/CBO9780511800481.006"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_10_1","DOI":"10.4230\/LIPIcs.FORC.2020.9"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_11_1","DOI":"10.1145\/2020408.2020495"},{"key":"e_1_3_2_1_12_1","first-page":"15265","article-title":"Learning strategy-aware linear classifiers","volume":"33","author":"Chen Yiling","year":"2020","unstructured":"Yiling Chen , Yang Liu , and Chara Podimata . 2020 . Learning strategy-aware linear classifiers . Advances in Neural Information Processing Systems 33 (2020), 15265 -- 15276 . Yiling Chen, Yang Liu, and Chara Podimata. 2020. Learning strategy-aware linear classifiers. Advances in Neural Information Processing Systems 33 (2020), 15265--15276.","journal-title":"Advances in Neural Information Processing Systems"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_13_1","DOI":"10.1145\/1014052.1014066"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_14_1","DOI":"10.5555\/1347082.1347179"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_15_1","DOI":"10.1145\/3219166.3219193"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_16_1","DOI":"10.1093\/jeea\/jvab017"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_17_1","DOI":"10.1006\/jcss.1997.1504"},{"key":"e_1_3_2_1_18_1","volume-title":"International Conference on Machine Learning. PMLR, 3672--3681","author":"Ghalme Ganesh","year":"2021","unstructured":"Ganesh Ghalme , Vineet Nair , Itay Eilat , Inbal Talgam-Cohen , and Nir Rosenfeld . 2021 . Strategic classification in the dark . In International Conference on Machine Learning. PMLR, 3672--3681 . Ganesh Ghalme, Vineet Nair, Itay Eilat, Inbal Talgam-Cohen, and Nir Rosenfeld. 2021. Strategic classification in the dark. In International Conference on Machine Learning. PMLR, 3672--3681."},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_19_1","DOI":"10.24963\/ijcai.2020\/23"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_20_1","DOI":"10.1145\/3490486.3538308"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_21_1","DOI":"10.1145\/2840728.2840730"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_22_1","DOI":"10.1145\/3287560.3287597"},{"key":"e_1_3_2_1_23_1","volume-title":"Proceedings of the Conference on Fairness, Accountability, and Transparency. 249--258","author":"Immorlica Nicole","year":"2019","unstructured":"Nicole Immorlica , Katrina Ligett , and Juba Ziani . 2019 . Access to population-level signaling as a source of inequality . In Proceedings of the Conference on Fairness, Accountability, and Transparency. 249--258 . Nicole Immorlica, Katrina Ligett, and Juba Ziani. 2019. Access to population-level signaling as a source of inequality. In Proceedings of the Conference on Fairness, Accountability, and Transparency. 249--258."},{"key":"e_1_3_2_1_24_1","volume-title":"International Conference on Machine Learning. PMLR, 4687--4697","author":"Jagadeesan Meena","year":"2021","unstructured":"Meena Jagadeesan , Celestine Mendler-D\u00fcnner , and Moritz Hardt . 2021 . Alternative microfoundations for strategic classification . In International Conference on Machine Learning. PMLR, 4687--4697 . Meena Jagadeesan, Celestine Mendler-D\u00fcnner, and Moritz Hardt. 2021. Alternative microfoundations for strategic classification. In International Conference on Machine Learning. PMLR, 4687--4697."},{"key":"e_1_3_2_1_25_1","volume-title":"Proceedings of the Conference on Fairness, Accountability, and Transparency. 240--248","author":"Kannan Sampath","year":"2019","unstructured":"Sampath Kannan , Aaron Roth , and Juba Ziani . 2019 . Downstream effects of affirmative action . In Proceedings of the Conference on Fairness, Accountability, and Transparency. 240--248 . Sampath Kannan, Aaron Roth, and Juba Ziani. 2019. Downstream effects of affirmative action. In Proceedings of the Conference on Fairness, Accountability, and Transparency. 240--248."},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_26_1","DOI":"10.1145\/3417742"},{"key":"e_1_3_2_1_27_1","volume-title":"Proceedings of the AAAI Conference on Artificial Intelligence","volume":"36","author":"Lechner Tosca","year":"2022","unstructured":"Tosca Lechner and Ruth Urner . 2022 . Learning losses for strategic classification . In Proceedings of the AAAI Conference on Artificial Intelligence , Vol. 36 . 7337--7344. Tosca Lechner and Ruth Urner. 2022. Learning losses for strategic classification. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 36. 7337--7344."},{"key":"e_1_3_2_1_28_1","volume-title":"International Conference on Machine Learning. PMLR, 6243--6253","author":"Levanon Sagi","year":"2021","unstructured":"Sagi Levanon and Nir Rosenfeld . 2021 . Strategic classification made practical . In International Conference on Machine Learning. PMLR, 6243--6253 . Sagi Levanon and Nir Rosenfeld. 2021. Strategic classification made practical. In International Conference on Machine Learning. PMLR, 6243--6253."},{"key":"e_1_3_2_1_29_1","volume-title":"Learning quickly when irrelevant attributes abound: A new linear-threshold algorithm. Machine learning 2","author":"Littlestone Nick","year":"1988","unstructured":"Nick Littlestone . 1988. Learning quickly when irrelevant attributes abound: A new linear-threshold algorithm. Machine learning 2 ( 1988 ), 285--318. Nick Littlestone. 1988. Learning quickly when irrelevant attributes abound: A new linear-threshold algorithm. Machine learning 2 (1988), 285--318."},{"volume-title":"Mistake bounds and logarithmic linear-threshold learning algorithms","author":"Littlestone Nicholas","unstructured":"Nicholas Littlestone . 1989. Mistake bounds and logarithmic linear-threshold learning algorithms . University of California , Santa Cruz . Nicholas Littlestone. 1989. Mistake bounds and logarithmic linear-threshold learning algorithms. University of California, Santa Cruz.","key":"e_1_3_2_1_30_1"},{"key":"e_1_3_2_1_31_1","volume-title":"Learning Theory: 17th Annual Conference on Learning Theory, COLT 2004, Banff, Canada, July 1--4, 2004. Proceedings 17","author":"McMahan H Brendan","year":"2004","unstructured":"H Brendan McMahan and Avrim Blum . 2004 . Online geometric optimization in the bandit setting against an adaptive adversary . In Learning Theory: 17th Annual Conference on Learning Theory, COLT 2004, Banff, Canada, July 1--4, 2004. Proceedings 17 . Springer, 109--123. H Brendan McMahan and Avrim Blum. 2004. Online geometric optimization in the bandit setting against an adaptive adversary. In Learning Theory: 17th Annual Conference on Learning Theory, COLT 2004, Banff, Canada, July 1--4, 2004. Proceedings 17. Springer, 109--123."},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_32_1","DOI":"10.1145\/3287560.3287576"},{"key":"e_1_3_2_1_33_1","volume-title":"Performative Prediction. In Proceedings of the 37th International Conference on Machine Learning (Proceedings of Machine Learning Research","author":"Perdomo Juan","year":"2020","unstructured":"Juan Perdomo , Tijana Zrnic , Celestine Mendler-D\u00fcnner , and Moritz Hardt . 2020 . Performative Prediction. In Proceedings of the 37th International Conference on Machine Learning (Proceedings of Machine Learning Research , Vol. 119), Hal Daum\u00e9 III and Aarti Singh (Eds.). PMLR, 7599--7609. https:\/\/proceedings.mlr.press\/v119\/perdomo20a.html Juan Perdomo, Tijana Zrnic, Celestine Mendler-D\u00fcnner, and Moritz Hardt. 2020. Performative Prediction. In Proceedings of the 37th International Conference on Machine Learning (Proceedings of Machine Learning Research, Vol. 119), Hal Daum\u00e9 III and Aarti Singh (Eds.). PMLR, 7599--7609. https:\/\/proceedings.mlr.press\/v119\/perdomo20a.html"},{"key":"e_1_3_2_1_34_1","volume-title":"Proceedings of the 37th International Conference on Machine Learning (Proceedings of Machine Learning Research","author":"Shavit Yonadav","year":"2020","unstructured":"Yonadav Shavit , Benjamin Edelman , and Brian Axelrod . 2020 . Causal Strategic Linear Regression . In Proceedings of the 37th International Conference on Machine Learning (Proceedings of Machine Learning Research , Vol. 119), Hal Daum\u00e9 III and Aarti Singh (Eds.). PMLR, 8676--8686. https:\/\/proceedings.mlr.press\/v119\/shavit20a.html Yonadav Shavit, Benjamin Edelman, and Brian Axelrod. 2020. Causal Strategic Linear Regression. In Proceedings of the 37th International Conference on Machine Learning (Proceedings of Machine Learning Research, Vol. 119), Hal Daum\u00e9 III and Aarti Singh (Eds.). PMLR, 8676--8686. https:\/\/proceedings.mlr.press\/v119\/shavit20a.html"},{"key":"e_1_3_2_1_35_1","volume-title":"International Conference on Machine Learning. PMLR, 9978--9988","author":"Sundaram Ravi","year":"2021","unstructured":"Ravi Sundaram , Anil Vullikanti , Haifeng Xu , and Fan Yao . 2021 . Pac-learning for strategic classification . In International Conference on Machine Learning. PMLR, 9978--9988 . Ravi Sundaram, Anil Vullikanti, Haifeng Xu, and Fan Yao. 2021. Pac-learning for strategic classification. In International Conference on Machine Learning. PMLR, 9978--9988."},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_36_1","DOI":"10.1609\/aaai.v35i6.16726"},{"key":"e_1_3_2_1_37_1","first-page":"15257","article-title":"Who Leads and Who Follows in Strategic Classification","volume":"34","author":"Zrnic Tijana","year":"2021","unstructured":"Tijana Zrnic , Eric Mazumdar , Shankar Sastry , and Michael Jordan . 2021 . Who Leads and Who Follows in Strategic Classification ? Advances in Neural Information Processing Systems 34 (2021), 15257 -- 15269 . Tijana Zrnic, Eric Mazumdar, Shankar Sastry, and Michael Jordan. 2021. Who Leads and Who Follows in Strategic Classification? Advances in Neural Information Processing Systems 34 (2021), 15257--15269.","journal-title":"Advances in Neural Information Processing Systems"}],"event":{"sponsor":["SIGecom Special Interest Group on Economics and Computation"],"acronym":"EC '23","name":"EC '23: 24th ACM Conference on Economics and Computation","location":"London United Kingdom"},"container-title":["Proceedings of the 24th ACM Conference on Economics and Computation"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3580507.3597818","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3580507.3597818","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:46:35Z","timestamp":1750178795000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3580507.3597818"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,7,7]]},"references-count":37,"alternative-id":["10.1145\/3580507.3597818","10.1145\/3580507"],"URL":"https:\/\/doi.org\/10.1145\/3580507.3597818","relation":{},"subject":[],"published":{"date-parts":[[2023,7,7]]},"assertion":[{"value":"2023-07-07","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}