{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T19:59:44Z","timestamp":1760299184715,"version":"3.41.0"},"reference-count":24,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2015,7,31]],"date-time":"2015-07-31T00:00:00Z","timestamp":1438300800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Linde\/SISL postdoctoral fellowship"},{"name":"NSF","award":["CNS-0846025 and CCF-1101470"],"award-info":[{"award-number":["CNS-0846025 and CCF-1101470"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Econ. Comput."],"published-print":{"date-parts":[[2015,7,31]]},"abstract":"<jats:p>\n            We study lower bounds on the query complexity of determining correlated equilibrium. In particular, we consider a query model in which an\n            <jats:italic>n<\/jats:italic>\n            -player game is specified via a black box that returns players' utilities at pure action profiles. In this model, we establish that in order to compute a correlated equilibrium, any\n            <jats:italic>deterministic<\/jats:italic>\n            algorithm must query the black box an exponential (in\n            <jats:italic>n<\/jats:italic>\n            ) number of times.\n          <\/jats:p>","DOI":"10.1145\/2785668","type":"journal-article","created":{"date-parts":[[2015,8,4]],"date-time":"2015-08-04T13:57:39Z","timestamp":1438696659000},"page":"1-9","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":10,"title":["Query Complexity of Correlated Equilibrium"],"prefix":"10.1145","volume":"3","author":[{"given":"Yakov","family":"Babichenko","sequence":"first","affiliation":[{"name":"California Institute of Technology"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Siddharth","family":"Barman","sequence":"additional","affiliation":[{"name":"California Institute of Technology"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2015,7,31]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-4068(74)90037-8"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.2307\/1911154"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591829"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1379759.1379761"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1516512.1516516"},{"key":"e_1_2_1_6_1","unstructured":"Fan R. K. Chung. 1997. Spectral Graph Theory. American Mathematical Society.  Fan R. K. Chung. 1997. Spectral Graph Theory. American Mathematical Society."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/070699652"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2492002.2482558"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/2600057.2602847"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1093\/biomet\/85.2.379"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00199-006-0127-1"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132516.1132526"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2600057.2602845"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1468-0262.2005.00625.x"},{"key":"e_1_2_1_15_1","unstructured":"Sergiu Hart. 2011. On a panel discussing future directions in algorithmic game theory. http:\/\/www.youtube.com\/watch?v=tq2EvhOl2k0. Hebrew University.  Sergiu Hart. 2011. On a panel discussing future directions in algorithmic game theory. http:\/\/www.youtube.com\/watch?v=tq2EvhOl2k0. Hebrew University."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1111\/1468-0262.00153"},{"volume-title":"Proceedings of the 6th International Symposium on Algorithmic Game Theory (SAGT).","year":"2013","author":"Hart Sergiu","key":"e_1_2_1_17_1"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/0885-064X(89)90017-4"},{"issue":"2015","key":"e_1_2_1_19_1","first-page":"347","article-title":"Polynomial-time computation of exact correlated equilibrium in compact games","volume":"91","author":"Jiang Albert Xin","year":"2013","journal-title":"Games Econ. Behav."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1994.1009"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.2307\/1969529"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1379759.1379762"},{"key":"e_1_2_1_23_1","unstructured":"Luca Trevisan. 2011. Lecture notes on graph partitioning and expanders. cs.stanford.edu\/people\/trevisan\/cs359g\/lecture06.pdf.  Luca Trevisan. 2011. Lecture notes on graph partitioning and expanders. cs.stanford.edu\/people\/trevisan\/cs359g\/lecture06.pdf."},{"key":"e_1_2_1_24_1","doi-asserted-by":"crossref","unstructured":"H. Peyton Young. 2004. Strategic Learning and Its Limits. Vol. 2002. Oxford University Press on Demand.  H. Peyton Young. 2004. Strategic Learning and Its Limits. Vol. 2002. Oxford University Press on Demand.","DOI":"10.1093\/acprof:oso\/9780199269181.001.0001"}],"container-title":["ACM Transactions on Economics and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2785668","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2785668","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T05:07:10Z","timestamp":1750223230000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2785668"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,7,31]]},"references-count":24,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2015,7,31]]}},"alternative-id":["10.1145\/2785668"],"URL":"https:\/\/doi.org\/10.1145\/2785668","relation":{},"ISSN":["2167-8375","2167-8383"],"issn-type":[{"type":"print","value":"2167-8375"},{"type":"electronic","value":"2167-8383"}],"subject":[],"published":{"date-parts":[[2015,7,31]]},"assertion":[{"value":"2014-05-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-10-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-07-31","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}