{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,15]],"date-time":"2026-01-15T13:51:11Z","timestamp":1768485071676,"version":"3.49.0"},"reference-count":21,"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"}],"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 study the deterministic and randomized query complexity of finding approximate equilibria in a\n            <jats:italic>k<\/jats:italic>\n            \u00d7\n            <jats:italic>k<\/jats:italic>\n            bimatrix game. We show that the deterministic query complexity of finding an \u03f5-Nash equilibrium when \u03f5 &lt; \u00bd is \u03a9(\n            <jats:italic>k<\/jats:italic>\n            <jats:sup>2<\/jats:sup>\n            ), even in zero-one constant-sum games. In combination with previous results [Fearnley et al. 2013], this provides a complete characterization of the deterministic query complexity of approximate Nash equilibria. We also study randomized querying algorithms. We give a randomized algorithm for finding a (3-\u221a5\/2 + \u03f5)-Nash equilibrium using\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>k<\/jats:italic>\n            .log\n            <jats:italic>k<\/jats:italic>\n            \/\u03f5\n            <jats:sup>2<\/jats:sup>\n            ) payoff queries, which shows that the \u00bd barrier for deterministic algorithms can be broken by randomization. For well-supported Nash equilibria (WSNE), we first give a randomized algorithm for finding an \u03f5-WSNE of a zero-sum bimatrix game using\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>k<\/jats:italic>\n            .log\n            <jats:italic>k<\/jats:italic>\n            \/\u03f5\n            <jats:sup>4<\/jats:sup>\n            ) payoff queries, and we then use this to obtain a randomized algorithm for finding a (\u2154 + \u03f5)-WSNE in a general bimatrix game using\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>k<\/jats:italic>\n            .log\n            <jats:italic>k<\/jats:italic>\n            \/\u03f5\n            <jats:sup>4<\/jats:sup>\n            ) payoff queries. Finally, we initiate the study of lower bounds against randomized algorithms in the context of bimatrix games, by showing that randomized algorithms require \u03a9(\n            <jats:italic>k<\/jats:italic>\n            <jats:sup>2<\/jats:sup>\n            ) payoff queries in order to find an \u03f5-Nash equilibrium with \u03f5 &lt; 1\/4\n            <jats:italic>k<\/jats:italic>\n            , even in zero-one constant-sum games. In particular, this rules out query-efficient randomized algorithms for finding exact Nash equilibria.\n          <\/jats:p>","DOI":"10.1145\/2956579","type":"journal-article","created":{"date-parts":[[2016,8,29]],"date-time":"2016-08-29T12:17:07Z","timestamp":1472473027000},"page":"1-19","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":14,"title":["Finding Approximate Nash Equilibria of Bimatrix Games via Payoff Queries"],"prefix":"10.1145","volume":"4","author":[{"given":"John","family":"Fearnley","sequence":"first","affiliation":[{"name":"University of Liverpool, Merseyside, United Kingdom"}]},{"given":"Rahul","family":"Savani","sequence":"additional","affiliation":[{"name":"University of Liverpool, Merseyside, United Kingdom"}]}],"member":"320","published-online":{"date-parts":[[2016,8,26]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-45046-4_2"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591829"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2785668"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2009.09.023"},{"key":"e_1_2_1_5_1","unstructured":"X. Chen Y. Cheng and B. Tang. 2015. Well-supported versus approximate Nash equilibria: Query complexity of large games. CoRR abs\/1511.00785 (2015).  X. Chen Y. Cheng and B. Tang. 2015. Well-supported versus approximate Nash equilibria: Query complexity of large games. CoRR abs\/1511.00785 (2015)."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1516512.1516516"},{"key":"e_1_2_1_7_1","unstructured":"A. Czumaj A. Deligkas M. Fasoulakis J. Fearnley M. Jurdzinski and R. Savani. 2015. Distributed methods for computing approximate equilibria. CoRR abs\/1512.03315 (2015).  A. Czumaj A. Deligkas M. Fasoulakis J. Fearnley M. Jurdzinski and R. Savani. 2015. Distributed methods for computing approximate equilibria. CoRR abs\/1512.03315 (2015)."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250910.1250962"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2008.12.031"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2492002.2482558"},{"key":"e_1_2_1_11_1","volume-title":"Symposium on Algorithmic Game Theory (SAGT'12)","author":"Fearnley J.","unstructured":"J. Fearnley , P. W. Goldberg , R. Savani , and T. B. S\u00f8rensen . 2012. Approximate well-supported Nash equilibria below two-thirds . In Symposium on Algorithmic Game Theory (SAGT'12) . 108--119. J. Fearnley, P. W. Goldberg, R. Savani, and T. B. S\u00f8rensen. 2012. Approximate well-supported Nash equilibria below two-thirds. In Symposium on Algorithmic Game Theory (SAGT'12). 108--119."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250910.1250961"},{"key":"e_1_2_1_13_1","unstructured":"P. Goldberg and A. Roth. 2013. Bounds for the query complexity of approximate equilibria. Electronic Colloquium on Computational Complexity (ECCC) TR13 136 (2013).  P. Goldberg and A. Roth. 2013. Bounds for the query complexity of approximate equilibria. Electronic Colloquium on Computational Complexity (ECCC) TR13 136 (2013)."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-48995-6_26"},{"key":"e_1_2_1_15_1","volume-title":"Proc. of Symposium on Algorithmic Game Theory (SAGT'13)","author":"Hart S.","unstructured":"S. Hart and N. Nisan . 2013. The query complexity of correlated equilibria . In Proc. of Symposium on Algorithmic Game Theory (SAGT'13) . S. Hart and N. Nisan. 2013. The query complexity of correlated equilibria. In Proc. of Symposium on Algorithmic Game Theory (SAGT'13)."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.5555\/1517859.1518201"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.5555\/3118226.3118462"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/779928.779933"},{"key":"e_1_2_1_19_1","volume-title":"Settling the complexity of computing approximate two-player Nash equilibria. CoRR abs\/1606.04550","author":"Rubinstein A.","year":"2016","unstructured":"A. Rubinstein . 2016. Settling the complexity of computing approximate two-player Nash equilibria. CoRR abs\/1606.04550 ( 2016 ). A. Rubinstein. 2016. Settling the complexity of computing approximate two-player Nash equilibria. CoRR abs\/1606.04550 (2016)."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1080\/15427951.2008.10129172"},{"key":"e_1_2_1_21_1","volume-title":"Proc. of AAAI Conference on Artificial Intelligence (AAAI'06)","author":"Wellman M. P.","year":"2006","unstructured":"M. P. Wellman . 2006 . Methods for empirical game-theoretic analysis . In Proc. of AAAI Conference on Artificial Intelligence (AAAI'06) . 1552--1555. M. P. Wellman. 2006. Methods for empirical game-theoretic analysis. In Proc. of AAAI Conference on Artificial Intelligence (AAAI'06). 1552--1555."}],"container-title":["ACM Transactions on Economics and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2956579","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2956579","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\/2956579"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,8,26]]},"references-count":21,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2016,8,26]]}},"alternative-id":["10.1145\/2956579"],"URL":"https:\/\/doi.org\/10.1145\/2956579","relation":{},"ISSN":["2167-8375","2167-8383"],"issn-type":[{"value":"2167-8375","type":"print"},{"value":"2167-8383","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,8,26]]},"assertion":[{"value":"2014-11-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-05-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"}}]}}