{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,11]],"date-time":"2026-03-11T11:18:33Z","timestamp":1773227913958,"version":"3.50.1"},"reference-count":43,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2008,7,1]],"date-time":"2008-07-01T00:00:00Z","timestamp":1214870400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCR-0121555"],"award-info":[{"award-number":["CCR-0121555"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2008,7]]},"abstract":"<jats:p>We develop polynomial-time algorithms for finding correlated equilibria\u2014a well-studied notion of rationality that generalizes the Nash equilibrium\u2014in a broad class of succinctly representable multiplayer games, encompassing graphical games, anonymous games, polymatrix games, congestion games, scheduling games, local effect games, as well as several generalizations. Our algorithm is based on a variant of the existence proof due to Hart and Schmeidler, and employs linear programming duality, the ellipsoid algorithm, Markov chain steady state computations, as well as application-specific methods for computing multivariate expectations over product distributions.<\/jats:p>\n          <jats:p>For anonymous games and graphical games of bounded tree-width, we provide a different polynomial-time algorithm for optimizing an arbitrary linear function over the set of correlated equilibria of the game. In contrast to our sweeping positive results for computing an arbitrary correlated equilibrium, we prove that optimizing over correlated equilibria is NP-hard in all of the other classes of games that we consider.<\/jats:p>","DOI":"10.1145\/1379759.1379762","type":"journal-article","created":{"date-parts":[[2008,8,5]],"date-time":"2008-08-05T13:35:10Z","timestamp":1217943310000},"page":"1-29","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":161,"title":["Computing correlated equilibria in multi-player games"],"prefix":"10.1145","volume":"55","author":[{"given":"Christos H.","family":"Papadimitriou","sequence":"first","affiliation":[{"name":"UC Berkeley, Berkeley, California"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tim","family":"Roughgarden","sequence":"additional","affiliation":[{"name":"Stanford University, Stanford, California"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2008,8,6]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2004.68"},{"key":"e_1_2_1_2_1","unstructured":"Arora S. Hazan E. and Kale S. 2005. The multiplicative weights update method: A meta algorithm and applications. Working paper.  Arora S. Hazan E. and Kale S. 2005. The multiplicative weights update method: A meta algorithm and applications. Working paper."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-4068(74)90037-8"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.2140\/pjm.1956.6.1"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-4068(99)00008-7"},{"key":"e_1_2_1_6_1","volume-title":"Proceedings of the 24th Annual Symposium on Theoretical Aspects of Computer Science (STACS). Lecture Notes in Computer Science","volume":"4393","author":"Brandt F."},{"key":"e_1_2_1_7_1","volume-title":"Contributions to the Theory Games","author":"Brown J. W."},{"key":"e_1_2_1_8_1","doi-asserted-by":"crossref","unstructured":"Cesa-Bianchi N. and Lugosi G. 2006. Prediction Learning and Games. Cambridge University Press Cambridge MA.   Cesa-Bianchi N. and Lugosi G. 2006. Prediction Learning and Games. Cambridge University Press Cambridge MA.","DOI":"10.1017\/CBO9780511546921"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2006.69"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1011767.1011771"},{"key":"e_1_2_1_11_1","unstructured":"Chv\u00e1tal V. 1983. Linear Programming. Freeman.  Chv\u00e1tal V. 1983. Linear Programming. Freeman."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132516.1132527"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/11561071_9"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1137\/0124043"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007352.1007445"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2005.18"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1006\/game.1997.0595"},{"key":"e_1_2_1_18_1","volume-title":"Proceedings of the 29th Annual International Colloquium on Automata, Languages, and Programming (ICALP). Lecture Notes in Computer Science","volume":"2380","author":"Fotakis D."},{"key":"e_1_2_1_19_1","unstructured":"Gale D. Kuhn H. W. and Tucker A. W. 1950. On symmetric games. In Contributions to the Theory Games H. W. Kuhn and A. W. Tucker Eds. Vol. 1. Princeton University Press Princeton NJ 81--87.  Gale D. Kuhn H. W. and Tucker A. W. 1950. On symmetric games. In Contributions to the Theory Games H. W. Kuhn and A. W. Tucker Eds. Vol. 1. Princeton University Press Princeton NJ 81--87."},{"key":"e_1_2_1_20_1","volume-title":"New York (Second Edition","author":"Gr\u00f6tschel M.","year":"1993"},{"key":"e_1_2_1_21_1","doi-asserted-by":"crossref","unstructured":"Hart S. and Mansour Y. 2008. The communication complexity of uncoupled Nash equilibrium procedures. Games Econ. Behav. To appear.  Hart S. and Mansour Y. 2008. The communication complexity of uncoupled Nash equilibrium procedures. Games Econ. Behav. To appear.","DOI":"10.1145\/1250790.1250843"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1111\/1468-0262.00153"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.14.1.18"},{"key":"e_1_2_1_24_1","first-page":"312","article-title":"Equilibria of polymatrix games. Manage","volume":"18","author":"Howson J. T.","year":"1972","journal-title":"Sci."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/779928.779934"},{"key":"e_1_2_1_26_1","volume-title":"Proceedings of the Conference on Uncertainty in Artificial Intelligence. 253--260","author":"Kearns M."},{"key":"e_1_2_1_27_1","first-page":"191","article-title":"A polynomial algorithm in linear programming","volume":"20","author":"Khachiyan L. G.","year":"1979","journal-title":"Soviet Math. Doklady"},{"key":"e_1_2_1_28_1","unstructured":"Khandekar R. 2004. Lagrangian relaxation based algorithms for convex programming problems. Ph.D. dissertation IIT Delhi.  Khandekar R. 2004. Lagrangian relaxation based algorithms for convex programming problems. Ph.D. dissertation IIT Delhi."},{"key":"e_1_2_1_29_1","unstructured":"Kleinberg J. and Tardos \u00c9. 2005. Algorithm Design. Addison-Wesley Reading MA.   Kleinberg J. and Tardos \u00c9. 2005. Algorithm Design. Addison-Wesley Reading MA."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01585745"},{"key":"e_1_2_1_31_1","volume-title":"Proceedings of the 18th International Joint Conference on Artificial Intelligence (IJCAI). 772--780","author":"Leyton-Brown K."},{"key":"e_1_2_1_32_1","volume-title":"Proceedings of the 6th Conference on Latin American Theoretical Informatics (LATIN). 413--422","author":"Lipton R. J."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1006\/game.1996.0027"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1006\/game.1997.0573"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.2307\/1969529"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0531(90)90011-8"},{"key":"e_1_2_1_37_1","first-page":"29","article-title":"The complexity of finding Nash equilibria. In Algorithmic Game Theory, N. Nisan, T. Roughgarden, \u00c9. Tardos, and V. V. Vazirani, Eds. Cambridge","volume":"2","author":"Papadimitriou C. H.","year":"2007","journal-title":"Chapter"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.5555\/31027"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0747-7171(10)80005-7"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01737559"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.geb.2003.06.004"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/1134707.1134737"},{"key":"e_1_2_1_44_1","first-page":"381","article-title":"Equilibrium situations in multi-matrix games","volume":"8","author":"Yanovskaya E. B.","year":"1968","journal-title":"Litovskii Matematicheskii Sbornik"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1379759.1379762","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1379759.1379762","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T13:57:45Z","timestamp":1750255065000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1379759.1379762"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,7]]},"references-count":43,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2008,7]]}},"alternative-id":["10.1145\/1379759.1379762"],"URL":"https:\/\/doi.org\/10.1145\/1379759.1379762","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,7]]},"assertion":[{"value":"2007-06-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2008-03-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2008-08-06","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}