{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,23]],"date-time":"2025-06-23T16:10:04Z","timestamp":1750695004093,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":38,"publisher":"ACM","funder":[{"name":"NSF (National Science Foundation)","award":["CCF-1901292, DMS-2022448, CCF-244306"],"award-info":[{"award-number":["CCF-1901292, DMS-2022448, CCF-244306"]}]},{"name":"Simons Foundation","award":["Investigator Award, Simons Collaboration on the Theory of Algorithmic Fairness"],"award-info":[{"award-number":["Investigator Award, Simons Collaboration on the Theory of Algorithmic Fairness"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2025,6,15]]},"DOI":"10.1145\/3717823.3718307","type":"proceedings-article","created":{"date-parts":[[2025,6,15]],"date-time":"2025-06-15T23:34:42Z","timestamp":1750030482000},"page":"542-553","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Efficient Learning and Computation of Linear Correlated Equilibrium in General Convex Games"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-5451-0490","authenticated-orcid":false,"given":"Constantinos","family":"Daskalakis","sequence":"first","affiliation":[{"name":"Massachusetts Institute of Technology, Cambridge, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3976-0061","authenticated-orcid":false,"given":"Gabriele","family":"Farina","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology, Cambridge, USA"}]},{"ORCID":"https:\/\/orcid.org\/0009-0008-8461-3459","authenticated-orcid":false,"given":"Maxwell","family":"Fishelson","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology, Cambridge, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4152-7565","authenticated-orcid":false,"given":"Charilaos","family":"Pipis","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology, Cambridge, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5392-3560","authenticated-orcid":false,"given":"Jon","family":"Schneider","sequence":"additional","affiliation":[{"name":"Google Research, New York, USA"}]}],"member":"320","published-online":{"date-parts":[[2025,6,15]]},"reference":[{"key":"e_1_3_2_1_1_1","volume-title":"Proceedings of the 24th Annual Conference on Learning Theory. 27\u201346","author":"Abernethy Jacob","year":"2011","unstructured":"Jacob Abernethy, Peter L Bartlett, and Elad Hazan. 2011. Blackwell approachability and no-regret learning are equivalent. In Proceedings of the 24th Annual Conference on Learning Theory. 27\u201346."},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2764468.2764497"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898718829"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.2140\/pjm.1956.6.1"},{"key":"e_1_3_2_1_5_1","volume-title":"The Thirty-eighth Annual Conference on Neural Information Processing Systems.","author":"Cai Yang","year":"2024","unstructured":"Yang Cai, Constantinos Costis Daskalakis, Haipeng Luo, Chen-Yu Wei, and Weiqiang Zheng. 2024. On Tractable \u03a6 -Equilibria in Non-Concave Games. In The Thirty-eighth Annual Conference on Neural Information Processing Systems."},{"key":"e_1_3_2_1_6_1","first-page":"7722","article-title":"No-regret learning dynamics for extensive-form correlated equilibrium","volume":"33","author":"Celli Andrea","year":"2020","unstructured":"Andrea Celli, Alberto Marchesi, Gabriele Farina, and Nicola Gatti. 2020. No-regret learning dynamics for extensive-form correlated equilibrium. Advances in Neural Information Processing Systems, 33 (2020), 7722\u20137732.","journal-title":"Advances in Neural Information Processing Systems"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1516512.1516516"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/3618260.3649681"},{"key":"e_1_3_2_1_9_1","volume-title":"International Conference on Algorithmic Learning Theory. 471\u2013509","author":"Dann Christoph","year":"2023","unstructured":"Christoph Dann, Yishay Mansour, Mehryar Mohri, Jon Schneider, and Balubramanian Sivan. 2023. Pseudonorm Approachability and Applications to Regret Minimization. In International Conference on Algorithmic Learning Theory. 471\u2013509."},{"key":"e_1_3_2_1_10_1","unstructured":"Christoph Dann Yishay Mansour Mehryar Mohri Jon Schneider and Balasubramanian Sivan. 2024. Rate-Preserving Reductions for Blackwell Approachability. arXiv preprint arXiv:2406.07585."},{"key":"e_1_3_2_1_11_1","unstructured":"Constantinos Daskalakis Gabriele Farina Maxwell Fishelson Charilaos Pipis and Jon Schneider. 2024. Efficient Learning and Computation of Linear Correlated Equilibrium in General Convex Games. arxiv:2412.20291. arxiv:2412.20291"},{"key":"e_1_3_2_1_12_1","unstructured":"Constantinos Daskalakis Gabriele Farina Noah Golowich Tuomas Sandholm and Brian Hu Zhang. 2024. A Lower Bound on Swap Regret in Extensive-Form Games. arXiv preprint arXiv:2406.13116."},{"key":"e_1_3_2_1_13_1","volume-title":"Papadimitriou","author":"Daskalakis Constantinos","year":"2009","unstructured":"Constantinos Daskalakis, Paul W. Goldberg, and Christos H. Papadimitriou. 2009. The complexity of computing a Nash equilibrium. Commun. ACM, 52, 2 (2009), feb, 89\u201397. issn:0001-0782"},{"key":"e_1_3_2_1_14_1","volume-title":"Strategizing against no-regret learners. Advances in neural information processing systems, 32","author":"Deng Yuan","year":"2019","unstructured":"Yuan Deng, Jon Schneider, and Balasubramanian Sivan. 2019. Strategizing against no-regret learners. Advances in neural information processing systems, 32 (2019)."},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/3563772"},{"key":"e_1_3_2_1_16_1","volume-title":"The Thirty-eighth Annual Conference on Neural Information Processing Systems.","author":"Farina Gabriele","year":"2024","unstructured":"Gabriele Farina and Charilaos Pipis. 2024. Polynomial-Time Computation of Exact \u03a6 -Equilibria in Polyhedral Games. In The Thirty-eighth Annual Conference on Neural Information Processing Systems."},{"key":"e_1_3_2_1_17_1","volume-title":"Polynomial-time linear-swap regret minimization in imperfect-information sequential games. Advances in Neural Information Processing Systems, 36","author":"Farina Gabriele","year":"2024","unstructured":"Gabriele Farina and Charilaos Pipis. 2024. Polynomial-time linear-swap regret minimization in imperfect-information sequential games. Advances in Neural Information Processing Systems, 36 (2024)."},{"key":"e_1_3_2_1_18_1","unstructured":"Kaito Fujii. 2023. Bayes correlated equilibria and no-regret dynamics. arXiv preprint arXiv:2304.05005."},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1390156.1390202"},{"volume-title":"Geometric Algorithms and Combinatorial Optimization","author":"Gr\u00f6tschel Martin","key":"e_1_3_2_1_20_1","unstructured":"Martin Gr\u00f6tschel, L\u00e1szl\u00f3 Lov\u00e1sz, and Alexander Schrijver. 1993. Geometric Algorithms and Combinatorial Optimization. Springer Berlin, Heidelberg."},{"key":"e_1_3_2_1_21_1","volume-title":"Computational equivalence of fixed points and no regret algorithms, and convergence to equilibria. Advances in Neural Information Processing Systems, 20","author":"Hazan Elad","year":"2007","unstructured":"Elad Hazan and Satyen Kale. 2007. Computational equivalence of fixed points and no regret algorithms, and convergence to equilibria. Advances in Neural Information Processing Systems, 20 (2007)."},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.18.5.312"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-92185-1_56"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.geb.2013.02.002"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.5555\/261619.261620"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.5555\/647235.760142"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1006\/game.1996.0051"},{"volume-title":"Simulated Annealing in Convex Bodies and an O*(n4)","author":"Lovasz Laszlo","key":"e_1_3_2_1_28_1","unstructured":"Laszlo Lovasz and Santosh Vempala. 2003. Simulated Annealing in Convex Bodies and an O*(n4) Volume Algorithm. 17."},{"key":"e_1_3_2_1_29_1","volume-title":"Conference on Learning Theory. 5221\u20135252","author":"Mansour Yishay","year":"2022","unstructured":"Yishay Mansour, Mehryar Mohri, Jon Schneider, and Balasubramanian Sivan. 2022. Strategizing against learners in bayesian games. In Conference on Learning Theory. 5221\u20135252."},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v35i6.16702"},{"key":"e_1_3_2_1_31_1","unstructured":"Francesco Orabona. 2022. A Modern Introduction to Online Learning. arxiv:1912.13213."},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/1379759.1379762"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/3618260.3649691"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01737559"},{"key":"e_1_3_2_1_35_1","volume-title":"Settling the Complexity of Computing Approximate Two-Player Nash Equilibria. In 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS). 258\u2013265","author":"Rubinstein Aviad","year":"2016","unstructured":"Aviad Rubinstein. 2016. Settling the Complexity of Computing Approximate Two-Player Nash Equilibria. In 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS). 258\u2013265."},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1080.0340"},{"key":"e_1_3_2_1_37_1","unstructured":"Brian Hu Zhang Ioannis Anagnostides Gabriele Farina and Tuomas Sandholm. 2024. Efficient \u03a6 -Regret Minimization with Low-Degree Swap Deviations in Extensive-Form Games. In Neural Information Processing Systems."},{"key":"e_1_3_2_1_38_1","volume-title":"Mediator Interpretation and Faster Learning Algorithms for Linear Correlated Equilibria in General Sequential Games. In The Twelfth International Conference on Learning Representations.","author":"Zhang Brian Hu","year":"2024","unstructured":"Brian Hu Zhang, Gabriele Farina, and Tuomas Sandholm. 2024. Mediator Interpretation and Faster Learning Algorithms for Linear Correlated Equilibria in General Sequential Games. In The Twelfth International Conference on Learning Representations."}],"event":{"name":"STOC '25: 57th Annual ACM Symposium on Theory of Computing","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"Prague Czechia","acronym":"STOC '25"},"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.3718307","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,23]],"date-time":"2025-06-23T15:50:13Z","timestamp":1750693813000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3717823.3718307"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,15]]},"references-count":38,"alternative-id":["10.1145\/3717823.3718307","10.1145\/3717823"],"URL":"https:\/\/doi.org\/10.1145\/3717823.3718307","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"}}]}}