{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:49:10Z","timestamp":1781077750061,"version":"3.54.1"},"publisher-location":"New York, NY, USA","reference-count":117,"publisher":"ACM","funder":[{"name":"Vannevar Bush Faculty Fellowship ONR","award":["N00014-23-1-2876"],"award-info":[{"award-number":["N00014-23-1-2876"]}]},{"name":"National Science Foundation grants","award":["RI-2312342 and RI-1901403"],"award-info":[{"award-number":["RI-2312342 and RI-1901403"]}]},{"name":"ARO award","award":["W911NF2210266"],"award-info":[{"award-number":["W911NF2210266"]}]},{"name":"NIH award","award":["A240108S001"],"award-info":[{"award-number":["A240108S001"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2025,6,15]]},"DOI":"10.1145\/3717823.3718250","type":"proceedings-article","created":{"date-parts":[[2025,6,15]],"date-time":"2025-06-15T22:21:27Z","timestamp":1750026087000},"page":"530-541","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Computational Lower Bounds for No-Regret Learning in Normal-Form Games"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-8037-6360","authenticated-orcid":false,"given":"Ioannis","family":"Anagnostides","sequence":"first","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1479-5268","authenticated-orcid":false,"given":"Alkis","family":"Kalavasis","sequence":"additional","affiliation":[{"name":"Yale University, New Haven, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8861-9366","authenticated-orcid":false,"given":"Tuomas","family":"Sandholm","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2025,6,15]]},"reference":[{"key":"e_1_3_2_1_1_1","volume-title":"Conference on Learning Theory (COLT).","author":"Abernethy Jacob","year":"2018","unstructured":"Jacob Abernethy, Kevin A Lai, Kfir Y Levy, and Jun-Kun Wang. 2018. Faster rates for convex-concave games. In Conference on Learning Theory (COLT)."},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250790.1250863"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1098-2418(199810\/12)13:3\/4<457::AID-RSA14>3.0.CO;2-W"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/0024-3795(94)90357-3"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806715"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2775105"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/278298.278306"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1502793.1502794"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-4068(74)90037-8"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.4086\/TOC.2013.V009A003"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/2785668"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2600057.2602873"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","unstructured":"Anton Bakhtin Noam Brown Emily Dinan Gabriele Farina Colin Flaherty Daniel Fried Andrew Goff Jonathan Gray Hengyuan Hu Athul Paul Jacob Mojtaba Komeili Karthik Konath Minae Kwon Adam Lerer Mike Lewis Alexander H. Miller Sasha Mitts Adithya Renduchintala Stephen Roller Dirk Rowe Weiyan Shi Joe Spisak Alexander Wei David Wu Hugh Zhang and Markus Zijlstra. 2022. Human-level play in the game of Diplomacy by combining language models with strategic reasoning. Science 378 6624 (2022) 1067\u20131074. https:\/\/doi.org\/10.1126\/science.ade9097 10.1126\/science.ade9097","DOI":"10.1126\/science.ade9097"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1137\/110821317"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/2597890"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973105.55"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/17M1138236"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591886"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746605"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.95"},{"key":"e_1_3_2_1_21_1","volume-title":"Proceedings of International Congress of Mathematicians.","author":"Barak Boaz","year":"2014","unstructured":"Boaz Barak and David Steurer. 2014. Sum-of-squares proofs and the quest toward optimal algorithms. In Proceedings of International Congress of Mathematicians."},{"key":"e_1_3_2_1_22_1","unstructured":"Boaz Barak and David Steurer. 2016. Proofs beliefs and algorithms through the lens of sum-of-squares. https:\/\/www.sumofsquares.org"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/2764468.2764497"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539796302531"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/195058.195129"},{"key":"e_1_3_2_1_26_1","volume-title":"Complexity Theoretic Lower Bounds for Sparse Principal Component Detection. In Conference on Learning Theory (COLT).","author":"Berthet Quentin","year":"2013","unstructured":"Quentin Berthet and Philippe Rigollet. 2013. Complexity Theoretic Lower Bounds for Sparse Principal Component Detection. In Conference on Learning Theory (COLT)."},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.2140\/pjm.1956.6.1"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374430"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.5555\/1314498.1314543"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS46700.2020.00034"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1126\/science.1259433"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973730.66"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1609\/AAAI.V33I01.33011829"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1126\/science.aay2400"},{"key":"e_1_3_2_1_35_1","volume-title":"Near-Optimal Policy Optimization for Correlated Equilibrium in General-Sum Markov Games. In International Conference on Artificial Intelligence and Statistics (AISTATS).","author":"Cai Yang","year":"2024","unstructured":"Yang Cai, Haipeng Luo, Chen-Yu Wei, and Weiqiang Zheng. 2024. Near-Optimal Policy Optimization for Correlated Equilibrium in General-Sum Markov Games. In International Conference on Artificial Intelligence and Statistics (AISTATS)."},{"key":"e_1_3_2_1_36_1","volume-title":"Prediction, learning, and games","author":"Cesa-Bianchi Nicolo","unstructured":"Nicolo Cesa-Bianchi and Gabor Lugosi. 2006. Prediction, learning, and games. Cambridge University Press."},{"key":"e_1_3_2_1_37_1","volume-title":"Proceedings of the Annual Conference on Neural Information Processing Systems (NeurIPS).","author":"Cevher Volkan","year":"2023","unstructured":"Volkan Cevher, Ashok Cutkosky, Ali Kavis, Georgios Piliouras, Stratis Skoulakis, and Luca Viano. 2023. Alternation makes the adversary weaker in two-player games. In Proceedings of the Annual Conference on Neural Information Processing Systems (NeurIPS)."},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","unstructured":"Xi Chen Xiaotie Deng and Shang-Hua Teng. 2009. Settling the Complexity of Computing Two-Player Nash Equilibria. J. ACM https:\/\/doi.org\/10.1145\/1516512.1516516 10.1145\/1516512.1516516","DOI":"10.1145\/1516512.1516516"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/1015330.1015351"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1016\/J.GEB.2008.02.015"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/3618260.3649681"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1016\/J.GEB.2014.01.003"},{"key":"e_1_3_2_1_43_1","volume-title":"Proceedings of the Annual Conference on Neural Information Processing Systems (NeurIPS).","author":"Daskalakis Constantinos","year":"2021","unstructured":"Constantinos Daskalakis, Maxwell Fishelson, and Noah Golowich. 2021. Near-Optimal No-Regret Learning in General Games. In Proceedings of the Annual Conference on Neural Information Processing Systems (NeurIPS)."},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1137\/070699652"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/3519935.3519950"},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/1536414.1536427"},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS54457.2022.00022"},{"key":"e_1_3_2_1_48_1","volume-title":"International Conference on Machine Learning (ICML).","author":"Erez Liad","year":"2023","unstructured":"Liad Erez, Tal Lancewicki, Uri Sherman, Tomer Koren, and Yishay Mansour. 2023. Regret Minimization and Convergence to Equilibria in General-sum Markov Games. In International Conference on Machine Learning (ICML)."},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2007.48"},{"key":"e_1_3_2_1_50_1","volume-title":"Proceedings of the Annual Conference on Neural Information Processing Systems (NeurIPS).","author":"Farina Gabriele","year":"2024","unstructured":"Gabriele Farina and Charilaos Pipis. 2024. Polynomial-Time Computation of Exact \u03a6 -Equilibria in Polyhedral Games. In Proceedings of the Annual Conference on Neural Information Processing Systems (NeurIPS)."},{"key":"e_1_3_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/2956579"},{"key":"e_1_3_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250910.1250961"},{"key":"e_1_3_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1137\/070680977"},{"key":"e_1_3_2_1_54_1","doi-asserted-by":"publisher","unstructured":"Uriel Feige Michal Feldman and Inbal Talgam-Cohen. 2016. Oblivious Rounding and the Integrality Gap. In Approximation Randomization and Combinatorial Optimization. Algorithms and Techniques (APPROX\/RANDOM). https:\/\/doi.org\/10.4230\/LIPICS.APPROX-RANDOM.2016.8 10.4230\/LIPICS.APPROX-RANDOM.2016.8","DOI":"10.4230\/LIPICS.APPROX-RANDOM.2016.8"},{"key":"e_1_3_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/226643.226652"},{"key":"e_1_3_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.4086\/TOC.2010.V006A011"},{"key":"e_1_3_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1561\/0400000086"},{"key":"e_1_3_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1006\/game.1997.0595"},{"key":"e_1_3_2_1_59_1","volume-title":"Hardness of Independent Learning and Sparse Equilibrium Computation in Markov Games. In International Conference on Machine Learning (ICML).","author":"Foster Dylan J.","unstructured":"Dylan J. Foster, Noah Golowich, and Sham M. Kakade. 2023. Hardness of Independent Learning and Sparse Equilibrium Computation in Markov Games. In International Conference on Machine Learning (ICML)."},{"key":"e_1_3_2_1_60_1","doi-asserted-by":"publisher","unstructured":"Anat Ganor and Karthik C. S.. 2018. Communication Complexity of Correlated Equilibrium with Small Support. In Approximation Randomization and Combinatorial Optimization. Algorithms and Techniques (APPROX\/RANDOM). https:\/\/doi.org\/10.4230\/LIPICS.APPROX-RANDOM.2018.12 10.4230\/LIPICS.APPROX-RANDOM.2018.12","DOI":"10.4230\/LIPICS.APPROX-RANDOM.2018.12"},{"key":"e_1_3_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1016\/0899-8256(89)90006-7"},{"key":"e_1_3_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1145\/227683.227684"},{"key":"e_1_3_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1016\/J.TCS.2023.113931"},{"key":"e_1_3_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1145\/2956582"},{"key":"e_1_3_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1137\/19M1242069"},{"key":"e_1_3_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1145\/1390156.1390202"},{"key":"e_1_3_2_1_67_1","volume-title":"Correlated Q-learning. In International Conference on Machine Learning (ICML).","author":"Greenwald Amy","year":"2003","unstructured":"Amy Greenwald and Keith Hall. 2003. Correlated Q-learning. In International Conference on Machine Learning (ICML)."},{"key":"e_1_3_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579273"},{"key":"e_1_3_2_1_69_1","volume-title":"Proceedings of the Annual Conference on Neural Information Processing Systems (NeurIPS).","author":"Hadiji H\u00e9di","unstructured":"H\u00e9di Hadiji, Sarah Sachs, Tim van Erven, and Wouter M. Koolen. 2023. Towards Characterizing the First-order Query Complexity of Learning (Approximate) Nash Equilibria in Zero-sum Matrix Games. In Proceedings of the Annual Conference on Neural Information Processing Systems (NeurIPS)."},{"key":"e_1_3_2_1_70_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.CCC.2016.22"},{"key":"e_1_3_2_1_71_1","doi-asserted-by":"publisher","DOI":"10.1111\/1468-0262.00153"},{"key":"e_1_3_2_1_72_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02392825"},{"key":"e_1_3_2_1_73_1","doi-asserted-by":"publisher","DOI":"10.1137\/090766991"},{"key":"e_1_3_2_1_74_1","doi-asserted-by":"publisher","DOI":"10.1137\/0211045"},{"key":"e_1_3_2_1_75_1","doi-asserted-by":"publisher","DOI":"10.1002\/RSA.3240030402"},{"key":"e_1_3_2_1_76_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993574.1993593"},{"key":"e_1_3_2_1_77_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(88)90046-3"},{"key":"e_1_3_2_1_78_1","doi-asserted-by":"publisher","unstructured":"Richard Karp. 1972. Reducibility among Combinatorial Problems. In Complexity of Computer Computations. 85\u2013103. https:\/\/doi.org\/10.1007\/978-1-4684-2001-2_9 10.1007\/978-1-4684-2001-2_9","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"e_1_3_2_1_79_1","doi-asserted-by":"publisher","unstructured":"David Kempe Sixie Yu and Yevgeniy Vorobeychik. 2020. Inducing Equilibria in Networked Public Goods Games through Network Structure Modification. In Autonomous Agents and Multi-Agent Systems. https:\/\/doi.org\/10.5555\/3398761.3398835","DOI":"10.5555\/3398761.3398835"},{"key":"e_1_3_2_1_80_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2001.959936"},{"key":"e_1_3_2_1_81_1","doi-asserted-by":"publisher","DOI":"10.1145\/3485447.3512055"},{"key":"e_1_3_2_1_82_1","volume-title":"Polynomial-Time Sum-of-Squares Can Robustly Estimate Mean and Covariance of Gaussians Optimally. In International Conference on Algorithmic Learning Theory (ALT).","author":"Kothari Pravesh K.","year":"2022","unstructured":"Pravesh K. Kothari, Peter Manohar, and Brian Hu Zhang. 2022. Polynomial-Time Sum-of-Squares Can Robustly Estimate Mean and Covariance of Gaussians Optimally. In International Conference on Algorithmic Learning Theory (ALT)."},{"key":"e_1_3_2_1_83_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188892"},{"key":"e_1_3_2_1_84_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(94)00103-K"},{"key":"e_1_3_2_1_85_1","doi-asserted-by":"publisher","DOI":"10.1137\/S1052623400366802"},{"key":"e_1_3_2_1_86_1","volume-title":"Proceedings of the Annual Conference on Neural Information Processing Systems (NeurIPS).","author":"Li Jiayang","year":"2020","unstructured":"Jiayang Li, Jing Yu, Yu Marco Nie, and Zhaoran Wang. 2020. End-to-End Learning and Intervention in Games. In Proceedings of the Annual Conference on Neural Information Processing Systems (NeurIPS)."},{"key":"e_1_3_2_1_87_1","doi-asserted-by":"publisher","DOI":"10.1145\/779928.779933"},{"key":"e_1_3_2_1_88_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00116827"},{"key":"e_1_3_2_1_89_1","doi-asserted-by":"publisher","DOI":"10.1006\/INCO.1994.1009"},{"key":"e_1_3_2_1_90_1","volume-title":"Proceedings of the Annual Conference on Neural Information Processing Systems (NeurIPS).","author":"Liu Boyi","year":"2022","unstructured":"Boyi Liu, Jiayang Li, Zhuoran Yang, Hoi-To Wai, Mingyi Hong, Yu Nie, and Zhaoran Wang. 2022. Inducing Equilibria via Incentives: Simultaneous Design-and-Play Ensures Global Convergence. In Proceedings of the Annual Conference on Neural Information Processing Systems (NeurIPS)."},{"key":"e_1_3_2_1_91_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2016.54"},{"key":"e_1_3_2_1_92_1","volume-title":"Ratliff","author":"Maiti Arnab","year":"2023","unstructured":"Arnab Maiti, Ross Boczar, Kevin G. Jamieson, and Lillian J. Ratliff. 2023. Query-Efficient Algorithms to Find the Unique Nash Equilibrium in a Two-Player Zero-Sum Matrix Game."},{"key":"e_1_3_2_1_93_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-03685-9_50"},{"key":"e_1_3_2_1_94_1","doi-asserted-by":"publisher","DOI":"10.1145\/2764468.2764522"},{"key":"e_1_3_2_1_95_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4615-4381-7_13"},{"key":"e_1_3_2_1_96_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.CCC.2021.26"},{"key":"e_1_3_2_1_97_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(05)80063-7"},{"key":"e_1_3_2_1_98_1","doi-asserted-by":"publisher","DOI":"10.1145\/1379759.1379762"},{"key":"e_1_3_2_1_99_1","volume-title":"Structured semidefinite programs and semialgebraic geometry methods in robustness and optimization","author":"Parrilo Pablo A","unstructured":"Pablo A Parrilo. 2000. Structured semidefinite programs and semialgebraic geometry methods in robustness and optimization. California Institute of Technology."},{"key":"e_1_3_2_1_100_1","volume-title":"Conference on Learning Theory (COLT).","author":"Peng Binghui","year":"2024","unstructured":"Binghui Peng and Aviad Rubinstein. 2024. The complexity of approximate (coarse) correlated equilibrium for incomplete information games. In Conference on Learning Theory (COLT)."},{"key":"e_1_3_2_1_101_1","doi-asserted-by":"publisher","DOI":"10.1145\/3618260.3649691"},{"key":"e_1_3_2_1_102_1","doi-asserted-by":"publisher","unstructured":"Julien Perolat Bart De Vylder Daniel Hennes Eugene Tarassov Florian Strub Vincent de Boer Paul Muller Jerome T. Connor Neil Burch Thomas Anthony Stephen McAleer Romuald Elie Sarah H. Cen Zhe Wang Audrunas Gruslys Aleksandra Malysheva Mina Khan Sherjil Ozair Finbarr Timbers Toby Pohlen Tom Eccles Mark Rowland Marc Lanctot Jean-Baptiste Lespiau Bilal Piot Shayegan Omidshafiei Edward Lockhart Laurent Sifre Nathalie Beauguerlange Remi Munos David Silver Satinder Singh Demis Hassabis and Karl Tuyls. 2022. Mastering the game of Stratego with model-free multiagent reinforcement learning. Science 378 6623 (2022) 990\u2013996. https:\/\/doi.org\/10.1126\/science.add4679 10.1126\/science.add4679","DOI":"10.1126\/science.add4679"},{"key":"e_1_3_2_1_103_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579324"},{"key":"e_1_3_2_1_104_1","volume-title":"Proceedings of the Annual Conference on Neural Information Processing Systems (NeurIPS).","author":"Rakhlin Alexander","year":"2013","unstructured":"Alexander Rakhlin and Karthik Sridharan. 2013. Optimization, learning, and games with predictable sequences. In Proceedings of the Annual Conference on Neural Information Processing Systems (NeurIPS)."},{"key":"e_1_3_2_1_105_1","doi-asserted-by":"publisher","DOI":"10.2307\/1969530"},{"key":"e_1_3_2_1_106_1","doi-asserted-by":"publisher","DOI":"10.1145\/2806883"},{"key":"e_1_3_2_1_107_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2016.35"},{"key":"e_1_3_2_1_108_1","volume-title":"Population games and evolutionary dynamics","author":"Sandholm William H","unstructured":"William H Sandholm. 2010. Population games and evolutionary dynamics. MIT press."},{"key":"e_1_3_2_1_109_1","doi-asserted-by":"publisher","DOI":"10.1007\/S10994-005-0465-4"},{"key":"e_1_3_2_1_110_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.geb.2006.04.007"},{"key":"e_1_3_2_1_111_1","volume-title":"Proceedings of the Annual Conference on Neural Information Processing Systems (NeurIPS).","author":"Syrgkanis Vasilis","year":"2015","unstructured":"Vasilis Syrgkanis, Alekh Agarwal, Haipeng Luo, and Robert E Schapire. 2015. Fast convergence of regularized learning in games. In Proceedings of the Annual Conference on Neural Information Processing Systems (NeurIPS)."},{"key":"e_1_3_2_1_112_1","doi-asserted-by":"publisher","DOI":"10.5555\/2832249.2832339"},{"key":"e_1_3_2_1_113_1","doi-asserted-by":"publisher","DOI":"10.1145\/1536414.1536457"},{"key":"e_1_3_2_1_114_1","volume-title":"Proceedings of the Annual Conference on Neural Information Processing Systems (NeurIPS).","author":"Wibisono Andre","year":"2022","unstructured":"Andre Wibisono, Molei Tao, and Georgios Piliouras. 2022. Alternating Mirror Descent for Constrained Min-Max Games. In Proceedings of the Annual Conference on Neural Information Processing Systems (NeurIPS)."},{"key":"e_1_3_2_1_115_1","doi-asserted-by":"publisher","DOI":"10.1145\/3490486.3538330"},{"key":"e_1_3_2_1_116_1","doi-asserted-by":"publisher","DOI":"10.1609\/AAAI.V36I9.21181"},{"key":"e_1_3_2_1_117_1","doi-asserted-by":"publisher","DOI":"10.4086\/TOC.2007.V003A006"}],"event":{"name":"STOC '25: 57th Annual ACM Symposium on Theory of Computing","location":"Prague Czechia","acronym":"STOC '25","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 57th Annual ACM Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3717823.3718250","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,23]],"date-time":"2025-06-23T15:46:26Z","timestamp":1750693586000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3717823.3718250"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,15]]},"references-count":117,"alternative-id":["10.1145\/3717823.3718250","10.1145\/3717823"],"URL":"https:\/\/doi.org\/10.1145\/3717823.3718250","relation":{},"subject":[],"published":{"date-parts":[[2025,6,15]]},"assertion":[{"value":"2025-06-15","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}