{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:19:35Z","timestamp":1759637975553,"version":"3.41.0"},"reference-count":27,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2016,8,26]],"date-time":"2016-08-26T00:00:00Z","timestamp":1472169600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100000266","name":"EPSRC","doi-asserted-by":"crossref","award":["EP\/K01000X\/1"],"award-info":[{"award-number":["EP\/K01000X\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"crossref"}]},{"name":"NSF CAREER award under NSF","award":["CCF-1101389 and CNS-1065060"],"award-info":[{"award-number":["CCF-1101389 and CNS-1065060"]}]},{"name":"Google Faculty Research award"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Econ. Comput."],"published-print":{"date-parts":[[2016,8,26]]},"abstract":"<jats:p>\n            We analyze the number of payoff queries needed to compute approximate equilibria of multi-player games. We find that query complexity is an effective tool for distinguishing the computational difficulty of alternative solution concepts, and we develop new techniques for upper- and lower bounding the query complexity. For binary-choice games, we show logarithmic upper and lower bounds on the query complexity of approximate correlated equilibrium. For\n            <jats:italic>well-supported<\/jats:italic>\n            approximate correlated equilibrium (a restriction where a player\u2019s behavior must always be approximately optimal, in the worst case over draws from the distribution) we show a linear lower bound, thus separating the query complexity of well supported approximate correlated equilibrium from the standard notion of approximate correlated equilibrium.\n          <\/jats:p>\n          <jats:p>\n            Finally, we give a query-efficient reduction from the problem of\n            <jats:italic>computing<\/jats:italic>\n            an approximate well-supported Nash equilibrium to the problem of verifying a well supported Nash equilibrium, where the additional query overhead is proportional to the description length of the game. This gives a polynomial-query algorithm for computing well supported approximate Nash equilibria (and hence correlated equilibria) in concisely represented games. We identify a class of games (which includes congestion games) in which the reduction can be made not only query efficient, but also computationally efficient.\n          <\/jats:p>","DOI":"10.1145\/2956582","type":"journal-article","created":{"date-parts":[[2016,8,29]],"date-time":"2016-08-29T12:17:07Z","timestamp":1472473027000},"page":"1-25","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":18,"title":["Bounds for the Query Complexity of Approximate Equilibria"],"prefix":"10.1145","volume":"4","author":[{"given":"Paul W.","family":"Goldberg","sequence":"first","affiliation":[{"name":"University of Oxford, Oxford, U.K."}]},{"given":"Aaron","family":"Roth","sequence":"additional","affiliation":[{"name":"University of Pennsylvania, Philadelphia, PA"}]}],"member":"320","published-online":{"date-parts":[[2016,8,26]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2012.v008a006"},{"key":"e_1_2_1_2_1","doi-asserted-by":"crossref","unstructured":"Y. Babichenko. 2013. Query complexity of approximate Nash equilibria. arXiv:1306.6686.  Y. Babichenko. 2013. Query complexity of approximate Nash equilibria. arXiv:1306.6686.","DOI":"10.1145\/2591796.2591829"},{"key":"e_1_2_1_3_1","unstructured":"Y. Babichenko and S. Barman. 2013. Query complexity of correlated equilibrium. arXiv:1306.2437.  Y. Babichenko and S. Barman. 2013. Query complexity of correlated equilibrium. arXiv:1306.2437."},{"key":"e_1_2_1_4_1","unstructured":"Y. Babichenko S. Barman and R. Peretz. 2013. Small-support approximate correlated equilibria. arXiv:1308.6025.  Y. Babichenko S. Barman and R. Peretz. 2013. Small-support approximate correlated equilibria. arXiv:1308.6025."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2600057.2602873"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.5555\/1005332.1005356"},{"key":"e_1_2_1_7_1","doi-asserted-by":"crossref","unstructured":"A. Blum and Y. Mansour. 2007. Learning regret minimization and equilibria. In Algorithmic Game Theory N. Nisan T. Roughgarden E. Tardos and Vijay V. Vazirani (Eds.). Cambridge University Press New York NY 79--102.  A. Blum and Y. Mansour. 2007. Learning regret minimization and equilibria. In Algorithmic Game Theory N. Nisan T. Roughgarden E. Tardos and Vijay V. Vazirani (Eds.). Cambridge University Press New York NY 79--102.","DOI":"10.1017\/CBO9780511800481.006"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1516512.1516516"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/501158.501191"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1613\/jair.2606"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/070699652"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2492002.2482558"},{"volume":"7615","volume-title":"Algorithmic Game Theory. Lecture Notes in Computer Science","author":"Fearnley J.","key":"e_1_2_1_13_1"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2600057.2602847"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1006\/game.1999.0738"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.geb.2014.01.009"},{"key":"e_1_2_1_17_1","doi-asserted-by":"crossref","unstructured":"P. W. Goldberg and S. Turchetta. 2014. Query complexity of approximate equilibria in anonymous games. arXiv:1412.6455.  P. W. Goldberg and S. Turchetta. 2014. Query complexity of approximate equilibria in anonymous games. arXiv:1412.6455.","DOI":"10.1145\/2600057.2602845"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-28914-9_19"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.85"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.geb.2007.12.002"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1111\/1468-0262.00153"},{"key":"e_1_2_1_22_1","unstructured":"S. Hart and N. Nisan. 2013. The query complexity of correlated equilibria. arXiv:1305.4874.  S. Hart and N. Nisan. 2013. The query complexity of correlated equilibria. arXiv:1305.4874."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/2554797.2554834"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.5555\/3118226.3118462"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1379759.1379762"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806794"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1080\/15427951.2008.10129172"}],"container-title":["ACM Transactions on Economics and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2956582","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2956582","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T03:39:43Z","timestamp":1750217983000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2956582"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,8,26]]},"references-count":27,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2016,8,26]]}},"alternative-id":["10.1145\/2956582"],"URL":"https:\/\/doi.org\/10.1145\/2956582","relation":{},"ISSN":["2167-8375","2167-8383"],"issn-type":[{"type":"print","value":"2167-8375"},{"type":"electronic","value":"2167-8383"}],"subject":[],"published":{"date-parts":[[2016,8,26]]},"assertion":[{"value":"2015-01-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-11-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-08-26","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}