{"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":1773227913995,"version":"3.50.1"},"publisher-location":"New York, NY, USA","reference-count":19,"publisher":"ACM","license":[{"start":{"date-parts":[[2006,5,21]],"date-time":"2006-05-21T00:00:00Z","timestamp":1148169600000},"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":[],"published-print":{"date-parts":[[2006,5,21]]},"DOI":"10.1145\/1132516.1132526","type":"proceedings-article","created":{"date-parts":[[2006,7,24]],"date-time":"2006-07-24T16:53:01Z","timestamp":1153759981000},"page":"61-70","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":62,"title":["Reducibility among equilibrium problems"],"prefix":"10.1145","author":[{"given":"Paul W.","family":"Goldberg","sequence":"first","affiliation":[{"name":"University of Warwick, U.K."}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Christos H.","family":"Papadimitriou","sequence":"additional","affiliation":[{"name":"University of California, Berkeley"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2006,5,21]]},"reference":[{"key":"e_1_3_2_1_1_1","volume-title":"Electronic Colloquium in Computational Complexity TR-05-134","author":"Chen X.","year":"2005","unstructured":"X. Chen and X. Deng . \" 3-NASH is PPAD-Complete \", Electronic Colloquium in Computational Complexity TR-05-134 , 2005 . X. Chen and X. Deng. \"3-NASH is PPAD-Complete\", Electronic Colloquium in Computational Complexity TR-05-134, 2005."},{"key":"e_1_3_2_1_2_1","volume-title":"Electronic Colloquium in Computational Complexity TR-05-140","author":"Chen X.","year":"2005","unstructured":"X. Chen and X. Deng . \" Settling the Complexity of 2-Player Nash-Equilibrium \", Electronic Colloquium in Computational Complexity TR-05-140 , 2005 . X. Chen and X. Deng. \"Settling the Complexity of 2-Player Nash-Equilibrium\", Electronic Colloquium in Computational Complexity TR-05-140, 2005."},{"key":"e_1_3_2_1_3_1","volume-title":"Electronic Colloquium in Computational Complexity TR-05-055","author":"Codenotti B.","year":"2005","unstructured":"B. Codenotti , A. Saberi , K. Varadarajan , Y. Ye . \"Leontief Economies Encode Nonzero Sum Two-Player Games\" , Electronic Colloquium in Computational Complexity TR-05-055 , 2005 . B. Codenotti, A. Saberi, K. Varadarajan, Y. Ye. \"Leontief Economies Encode Nonzero Sum Two-Player Games\" , Electronic Colloquium in Computational Complexity TR-05-055, 2005."},{"key":"e_1_3_2_1_4_1","first-page":"765","volume-title":"Proceedings of 18th IJCAI","author":"Conitzer V.","year":"2003","unstructured":"V. Conitzer and T. Sandholm . \" Complexity Results about Nash Equilibria \", Proceedings of 18th IJCAI , pp. 765 -- 771 , Acapulco, Mexico , 2003 . V. Conitzer and T. Sandholm. \"Complexity Results about Nash Equilibria\", Proceedings of 18th IJCAI, pp. 765--771, Acapulco, Mexico, 2003."},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132516.1132527"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/11561071_9"},{"key":"e_1_3_2_1_7_1","volume-title":"Electronic Colloquium in Computational Complexity TR-05-139","author":"Daskalakis K.","year":"2005","unstructured":"K. Daskalakis and C.H. Papadimitriou . \" Three-Player Games are Hard \", Electronic Colloquium in Computational Complexity TR-05-139 , 2005 . K. Daskalakis and C.H. Papadimitriou. \"Three-Player Games are Hard\", Electronic Colloquium in Computational Complexity TR-05-139, 2005."},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1134707.1134719"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007352.1007445"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/846241.846269"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/0899-8256(89)90006-7"},{"key":"e_1_3_2_1_13_1","volume-title":"Proceedings of UAI","author":"Kearns M.","year":"2001","unstructured":"M. Kearns , M. Littman and S. Singh . \" Graphical Models for Game Theory \", Proceedings of UAI , 2001 . M. Kearns, M. Littman and S. Singh. \"Graphical Models for Game Theory\", Proceedings of UAI, 2001."},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-24698-5_45"},{"key":"e_1_3_2_1_15_1","first-page":"817","volume-title":"Proceedings of 14th NIPS (Advances in Neural Information Processing Systems)","author":"Littman M.","year":"2002","unstructured":"M. Littman , M. Kearns and S. Singh . \" An Efficient Exact Algorithm for Single Connected Graphical Games \", Proceedings of 14th NIPS (Advances in Neural Information Processing Systems) , pp. 817 -- 823 , 2002 . M. Littman, M. Kearns and S. Singh. \"An Efficient Exact Algorithm for Single Connected Graphical Games\", Proceedings of 14th NIPS (Advances in Neural Information Processing Systems), pp. 817--823, 2002."},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.2307\/1969529"},{"key":"e_1_3_2_1_17_1","volume-title":"Theory of Games and Economic Behavior","author":"von Neumann J.","year":"1944","unstructured":"J. von Neumann and O. Morgenstern . Theory of Games and Economic Behavior , Princeton University Press , 1944 . J. von Neumann and O. Morgenstern. Theory of Games and Economic Behavior, Princeton University Press, 1944."},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1060590.1060598"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(05)80063-7"},{"key":"e_1_3_2_1_20_1","volume-title":"Electronic Colloquiium on Computational Complexity TR-05-052","author":"Schoenebeck G.R.","year":"2005","unstructured":"G.R. Schoenebeck and S.P. Vadhan . \" The Computational Complexity of Nash Equilibria in Concisely Represented Games \", Electronic Colloquiium on Computational Complexity TR-05-052 , 2005 . G.R. Schoenebeck and S.P. Vadhan. \"The Computational Complexity of Nash Equilibria in Concisely Represented Games\", Electronic Colloquiium on Computational Complexity TR-05-052, 2005."}],"event":{"name":"STOC06: Symposium on Theory of Computing","location":"Seattle WA USA","acronym":"STOC06","sponsor":["ACM Association for Computing Machinery","SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the thirty-eighth annual ACM symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1132516.1132526","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1132516.1132526","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T16:18:50Z","timestamp":1750263530000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1132516.1132526"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,5,21]]},"references-count":19,"alternative-id":["10.1145\/1132516.1132526","10.1145\/1132516"],"URL":"https:\/\/doi.org\/10.1145\/1132516.1132526","relation":{},"subject":[],"published":{"date-parts":[[2006,5,21]]},"assertion":[{"value":"2006-05-21","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}