{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,26]],"date-time":"2025-11-26T16:23:36Z","timestamp":1764174216399,"version":"3.41.0"},"reference-count":6,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2015,11,12]],"date-time":"2015-11-12T00:00:00Z","timestamp":1447286400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["SIGecom Exch."],"published-print":{"date-parts":[[2015,11,12]]},"abstract":"<jats:p>\n            One of the most appealing aspects of correlated equilibria and coarse correlated equilibria is that natural dynamics quickly arrive at approximations of such equilibria, even in games with many players. In addition, there exist polynomial-time algorithms that compute exact correlated and coarse correlated equilibria. However, in general these dynamics and algorithms do not provide a guarantee on the\n            <jats:italic>quality<\/jats:italic>\n            (say, in terms of social welfare) of the resulting equilibrium. In light of these results, a natural question is how\n            <jats:italic>good<\/jats:italic>\n            are the correlated and coarse correlated equilibria---in terms natural objectives such as social welfare or Pareto optimality---that can arise from any efficient algorithm or dynamics.\n          <\/jats:p>\n          <jats:p>\n            We address this question, and establish strong negative results. In particular, we show that in multiplayer games that have a succinct representation, it is NP-hard to compute any coarse correlated equilibrium (or approximate coarse correlated equilibrium) with welfare strictly better than the\n            <jats:italic>worst<\/jats:italic>\n            possible. The focus on succinct games ensures that the underlying complexity question is interesting; many multiplayer games of interest are in fact succinct. We show that analogous hardness results hold for correlated equilibria, and persist under the egalitarian objective or Pareto optimality.\n          <\/jats:p>\n          <jats:p>To complement the hardness results, we develop an algorithmic framework that identifies settings in which we can efficiently compute an approximate correlated equilibrium with near-optimal welfare. We use this framework to develop an efficient algorithm for computing an approximate correlated equilibrium with near-optimal welfare in aggregative games.<\/jats:p>","DOI":"10.1145\/2845926.2845929","type":"journal-article","created":{"date-parts":[[2015,11,13]],"date-time":"2015-11-13T14:19:41Z","timestamp":1447424381000},"page":"76-79","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Finding any nontrivial coarse correlated equilibrium is hard"],"prefix":"10.1145","volume":"14","author":[{"given":"Siddharth","family":"Barman","sequence":"first","affiliation":[{"name":"California Institute of Technology"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Katrina","family":"Ligett","sequence":"additional","affiliation":[{"name":"California Institute of Technology"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2015,11,12]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/2764468.2764497"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1516512.1516516"},{"key":"e_1_2_1_3_1","unstructured":"Jiang A. X. and Leyton-Brown K. 2013. Polynomial-time computation of exact correlated equilibrium in compact games. Games and Economic Behavior.  Jiang A. X. and Leyton-Brown K. 2013. Polynomial-time computation of exact correlated equilibrium in compact games. Games and Economic Behavior."},{"key":"e_1_2_1_4_1","doi-asserted-by":"crossref","unstructured":"Nisan N. Roughgarden T. Tardos E. and Vazirani V. V. 2007. Algorithmic game theory. Cambridge University Press.   Nisan N. Roughgarden T. Tardos E. and Vazirani V. V. 2007. Algorithmic game theory. Cambridge University Press.","DOI":"10.1017\/CBO9780511800481"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1379759.1379762"},{"key":"e_1_2_1_6_1","doi-asserted-by":"crossref","unstructured":"Young H. P. 2004. Strategic learning and its limits. Oxford University Press.  Young H. P. 2004. Strategic learning and its limits. Oxford University Press.","DOI":"10.1093\/acprof:oso\/9780199269181.001.0001"}],"container-title":["ACM SIGecom Exchanges"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2845926.2845929","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2845926.2845929","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T05:48:51Z","timestamp":1750225731000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2845926.2845929"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,11,12]]},"references-count":6,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2015,11,12]]}},"alternative-id":["10.1145\/2845926.2845929"],"URL":"https:\/\/doi.org\/10.1145\/2845926.2845929","relation":{},"ISSN":["1551-9031"],"issn-type":[{"type":"electronic","value":"1551-9031"}],"subject":[],"published":{"date-parts":[[2015,11,12]]},"assertion":[{"value":"2015-11-12","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}