{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,9,13]],"date-time":"2022-09-13T17:52:27Z","timestamp":1663091547512},"reference-count":29,"publisher":"Association for Computing Machinery (ACM)","issue":"2","funder":[{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"publisher","award":["CCR-0133096CCF 0729137CCR-0133096"]},{"DOI":"10.13039\/501100001742","name":"United States-Israel Binational Science Foundation","doi-asserted-by":"publisher","award":["2006060"]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCR-0133096CCF 0729137CCR-0133096"]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM Trans. Comput. Theory"],"published-print":{"date-parts":[[2012,5]]},"abstract":"\n Games may be represented in many different ways, and different representations of games affect the complexity of problems associated with games, such as finding a Nash equilibrium. The traditional method of representing a game is to explicitly list all the payoffs, but this incurs an exponential blowup as the number of agents grows. We study two models of concisely represented games:\n circuit games<\/jats:italic>\n , where the payoffs are computed by a given boolean circuit, and\n graph games<\/jats:italic>\n , where each agent\u2019s payoff is a function of only the strategies played by its neighbors in a given graph. For these two models, we study the complexity of four questions: determining if a given strategy is a Nash equilibrium, finding a Nash equilibrium, determining if there exists a pure Nash equilibrium, and determining if there exists a Nash equilibrium in which the payoffs to a player meet some given guarantees. In many cases, we obtain tight results, showing that the problems are complete for various complexity classes.\n <\/jats:p>","DOI":"10.1145\/2189778.2189779","type":"journal-article","created":{"date-parts":[[2012,6,12]],"date-time":"2012-06-12T13:13:25Z","timestamp":1339506805000},"page":"1-50","source":"Crossref","is-referenced-by-count":8,"title":["The Computational Complexity of Nash Equilibria in Concisely Represented Games"],"prefix":"10.1145","volume":"4","author":[{"given":"Grant R.","family":"Schoenebeck","sequence":"first","affiliation":[{"name":"Princeton University"}]},{"given":"Salil","family":"Vadhan","sequence":"additional","affiliation":[{"name":"Harvard University"}]}],"member":"320","reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"crossref","unstructured":"\u00c0lvarez C. Gabarr\u00f3 J. and \n \n \n Serna M\n \n \n . \n 2005\n . Pure Nash equilibria in games with a large number of actions. In Mathematical Foundations of Computer Science 2005 J. Jedrzejowicz and A. Szepietowski Eds. Lecture Notes in Computer Science Series vol. \n 3618 Springer Berlin 95--106. 10.1007\/11549345_10 \u00c0lvarez C. Gabarr\u00f3 J. and Serna M. 2005. Pure Nash equilibria in games with a large number of actions. In Mathematical Foundations of Computer Science 2005 J. Jedrzejowicz and A. Szepietowski Eds. Lecture Notes in Computer Science Series vol. 3618 Springer Berlin 95--106. 10.1007\/11549345_10","DOI":"10.1007\/11549345_10"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/278298.278306"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/273865.273901"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(88)90028-1"},{"key":"e_1_2_1_5_1","unstructured":"Chen X. and Deng X. 2005. 3-Nash is PPAD-complete. Tech. rep. TR05-134 Electronic Colloquium on Computational Complexity. Chen X. and Deng X. 2005. 3-Nash is PPAD-complete. Tech. rep. TR05-134 Electronic Colloquium on Computational Complexity."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2006.69"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2006.20"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.geb.2008.02.015"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132516.1132527"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/070699652"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/11561071_9"},{"key":"e_1_2_1_12_1","unstructured":"Daskalakis C. and Papadimitriou C. 2005b. Three-player games are hard. Tech. rep. TR05-139 Electronic Colloquium on Computational Complexity. Daskalakis C. and Papadimitriou C. 2005b. Three-player games are hard. Tech. rep. TR05-139 Electronic Colloquium on Computational Complexity."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/226643.226652"},{"key":"e_1_2_1_14_1","volume-title":"Proceedings of the 10th Annual IEEE Conference on Computational Complexity (CCC). 227--237","author":"Feigenbaum J."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-008-0252-2"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/0899-8256(89)90006-7"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132516.1132526"},{"key":"e_1_2_1_18_1","unstructured":"Goldreich O. 2005. On promise problems (a survey in memory of Shimon Even {1935--2004}). Tech. rep. TR05-018 Electronic Colloquium on Computational Complexity. Goldreich O. 2005. On promise problems (a survey in memory of Shimon Even {1935--2004}). Tech. rep. TR05-018 Electronic Colloquium on Computational Complexity."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/116825.116852"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/0218012"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/846241.846269"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(02)00025-9"},{"key":"e_1_2_1_23_1","volume-title":"Proceedings of the Conference on Uncertainty in Artificial Intelligence (UAI). 253--260","author":"Kearns M."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/779928.779933"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(91)90200-L"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.2307\/1969529"},{"key":"e_1_2_1_27_1","first-page":"105","article-title":"A simple three-person poker game","volume":"1","author":"Nash J. F.","year":"1950","journal-title":"Contrib. Theor. Games"},{"key":"e_1_2_1_28_1","unstructured":"Schoenebeck G. 2004. The complexity of finding Nash equilibria in succinctly represented games. Undergraduate thesis Harvard University. Schoenebeck G. 2004. The complexity of finding Nash equilibria in succinctly represented games. Undergraduate thesis Harvard University."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/1134707.1134737"}],"container-title":["ACM Transactions on Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2189778.2189779","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,2,28]],"date-time":"2021-02-28T17:17:53Z","timestamp":1614532673000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2189778.2189779"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,5]]},"references-count":29,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2012,5]]}},"alternative-id":["10.1145\/2189778.2189779"],"URL":"http:\/\/dx.doi.org\/10.1145\/2189778.2189779","relation":{},"ISSN":["1942-3454","1942-3462"],"issn-type":[{"value":"1942-3454","type":"print"},{"value":"1942-3462","type":"electronic"}],"subject":["Computational Theory and Mathematics","Theoretical Computer Science"],"published":{"date-parts":[[2012,5]]}}}