{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,16]],"date-time":"2025-09-16T17:37:53Z","timestamp":1758044273852,"version":"3.44.0"},"reference-count":22,"publisher":"Association for Computing Machinery (ACM)","issue":"3","funder":[{"name":"NSF TRIPODS CCF Award","award":["2023166"],"award-info":[{"award-number":["2023166"]}]},{"name":"Northrop Grumman University Research Award","award":["ONR YIP award N00014-20-1-2571, and NSF award #1844729"],"award-info":[{"award-number":["ONR YIP award N00014-20-1-2571, and NSF award #1844729"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Econ. Comput."],"published-print":{"date-parts":[[2025,9,30]]},"abstract":"\n We study the query complexity of finding the set of all Nash equilibria\n \n \\(\\mathcal {X}_\\star \\unicode{x00D7} \\mathcal {Y}_\\star\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n in two-player zero-sum matrix games. Fearnley and Savani [\n 18<\/jats:xref>\n ] showed that for any randomized algorithm, there exists an\n n \u00d7 n<\/jats:italic>\n input matrix where it needs to query \u03a9 (\n n<\/jats:italic>\n 2<\/jats:sup>\n ) entries in expectation to compute a\n single<\/jats:italic>\n Nash equilibrium. On the other hand, Bienstock et\u00a0al. [\n 5<\/jats:xref>\n ] showed that there is a special class of matrices for which one can query\n O(n)<\/jats:italic>\n entries and compute its set of all Nash equilibria. However, these results do not fully characterize the query complexity of finding the set of all Nash equilibria in two-player zero-sum matrix games.\n <\/jats:p>\n \n In this work, we characterize the query complexity of finding the set of all Nash equilibria\n \n \\(\\mathcal {X}_\\star \\unicode{x00D7} \\mathcal {Y}_\\star\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n in terms of the number of rows\n n<\/jats:italic>\n of the input matrix\n \n \\(A \\in \\mathbb {R}^{n \\unicode{x00D7} n}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n , row support size\n \n \\(k_1 := |\\bigcup \\nolimits _{x \\in \\mathcal {X}_\\star } \\text{supp}(x)|\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n , and column support size\n \n \\(k_2 := |\\bigcup \\nolimits _{y \\in \\mathcal {Y}_\\star } \\text{supp}(y)|\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n . We design a simple yet non-trivial randomized algorithm that returns the set of all Nash equilibria\n \n \\(\\mathcal {X}_\\star \\unicode{x00D7} \\mathcal {Y}_\\star\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n by querying at most\n \n \\(O(nk^5 \\cdot \\text{polylog}(n))\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n entries of the input matrix\n \n \\(A \\in \\mathbb {R}^{n \\unicode{x00D7} n}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n in expectation, where\n \n \\(k := \\max \\lbrace k_1, k_2\\rbrace\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n . This upper bound is tight up to a factor of poly(\n k<\/jats:italic>\n ), as we show that for any randomized algorithm, there exists an\n n \u00d7 n<\/jats:italic>\n input matrix with\n \n \\(\\min \\lbrace k_1, k_2\\rbrace = 1\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n , for which it needs to query \u03a9 (\n nk<\/jats:italic>\n ) entries in expectation in order to find the set of all Nash equilibria\n \n \\(\\mathcal {X}_\\star \\unicode{x00D7} \\mathcal {Y}_\\star\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n .\n <\/jats:p>","DOI":"10.1145\/3732787","type":"journal-article","created":{"date-parts":[[2025,4,25]],"date-time":"2025-04-25T07:16:50Z","timestamp":1745565410000},"page":"1-18","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Query-Efficient Algorithm to Find all Nash Equilibria in a Two-Player Zero-Sum Matrix Game"],"prefix":"10.1145","volume":"13","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-9142-6255","authenticated-orcid":false,"given":"Arnab","family":"Maiti","sequence":"first","affiliation":[{"name":"Computer Science & Engineering, University of Washington","place":["Seattle, United States"]}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7604-3133","authenticated-orcid":false,"given":"Ross","family":"Boczar","sequence":"additional","affiliation":[{"name":"University of Washington","place":["Seattle, United States"]}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2054-2985","authenticated-orcid":false,"given":"Kevin","family":"Jamieson","sequence":"additional","affiliation":[{"name":"University of Washington","place":["Seattle, United States"]}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8936-0229","authenticated-orcid":false,"given":"Lillian","family":"Ratliff","sequence":"additional","affiliation":[{"name":"University of Washington","place":["Seattle, United States"]}]}],"member":"320","published-online":{"date-parts":[[2025,9,12]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00182-012-0328-8"},{"key":"e_1_3_2_3_2","volume-title":"Proceedings of the Asian Conference on Machine Learning","author":"Auger David","year":"2014","unstructured":"David Auger, Jialin Liu, Sylvie Ruette, David Lupien St-Pierre, and Olivier Teytaud. 2014. Sparse binary zero-sum games. In Proceedings of the Asian Conference on Machine Learning."},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.1145\/2908734"},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.1145\/3381329.3381333"},{"issue":"5","key":"e_1_3_2_6_2","doi-asserted-by":"crossref","first-page":"418","DOI":"10.1080\/00029890.1991.12000780","article-title":"A note on finding a strict saddlepoint","volume":"98","author":"Bienstock Daniel","year":"1991","unstructured":"Daniel Bienstock, Fan Chung, Michael L Fredman, Alejandro A Sch\u00e4ffer, Peter W Shor, and Subhash Suri. 1991. A note on finding a strict saddlepoint. The American Mathematical Monthly 98, 5 (1991), 418\u2013419.","journal-title":"The American Mathematical Monthly"},{"key":"e_1_3_2_7_2","doi-asserted-by":"crossref","unstructured":"HF Bohnenblust MA Girshick RN Snow Melvin Dresher Olaf Helmer-Hirschberg JCC McKinsey Lloyd S. Shapley and Theodore Edward Harris. 1948. Mathematical theory of zero-sum two-person games with a finite number or a continuum of strategies. (1948).","DOI":"10.7249\/R115"},{"key":"e_1_3_2_8_2","first-page":"51","article-title":"Solutions of discrete, two-person games","volume":"1","author":"Bohnenblust HF","year":"1950","unstructured":"HF Bohnenblust, S. Karlin, and LS Shapley. 1950. Solutions of discrete, two-person games. Contributions to the Theory of Games 1 (1950), 51\u201372.","journal-title":"Contributions to the Theory of Games"},{"key":"e_1_3_2_9_2","article-title":"A canonical game\u2013nearly 75 years in the making\u2013showing the equivalence of matrix games and linear programming","author":"Brooks Benjamin","year":"2021","unstructured":"Benjamin Brooks and Philip J. Reny. 2021. A canonical game\u2013nearly 75 years in the making\u2013showing the equivalence of matrix games and linear programming. Available at SSRN 3851583 (2021).","journal-title":"Available at SSRN 3851583"},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.1145\/1516512.1516516"},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ESA.2024.44"},{"key":"e_1_3_2_12_2","doi-asserted-by":"crossref","first-page":"168","DOI":"10.1137\/1.9781611977936.17","volume-title":"Proceedings of the 2024 Symposium on Simplicity in Algorithms.","author":"Dallant Justin","year":"2024","unstructured":"Justin Dallant, Frederik Haagensen, Riko Jacob, L\u00e1szl\u00f3 Kozma, and Sebastian Wild. 2024. Finding the saddlepoint faster than sorting. In Proceedings of the 2024 Symposium on Simplicity in Algorithms.SIAM, 168\u2013178."},{"key":"e_1_3_2_13_2","article-title":"A proof of the equivalence of the programming problem and the game problem","volume":"13","author":"Dantzig George B.","year":"1951","unstructured":"George B. Dantzig. 1951. A proof of the equivalence of the programming problem and the game problem. Activity Analysis of Production and Allocation 13 (1951).","journal-title":"Activity Analysis of Production and Allocation"},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1145\/1250910.1250962"},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2008.12.031"},{"key":"e_1_3_2_16_2","doi-asserted-by":"crossref","first-page":"3777","DOI":"10.1137\/1.9781611977554.ch146","volume-title":"Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms","author":"Deligkas Argyrios","year":"2023","unstructured":"Argyrios Deligkas, Michail Fasoulakis, and Evangelos Markakis. 2023. A polynomial-time algorithm for 1\/2-well-supported nash equilibria in bimatrix games. In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM, 3777\u20133787."},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.1145\/3606697"},{"key":"e_1_3_2_18_2","first-page":"397","volume-title":"Proceedings of the 14th ACM Conference on Electronic Commerce","author":"Fearnley John","year":"2013","unstructured":"John Fearnley, Martin Gairing, Paul Goldberg, and Rahul Savani. 2013. Learning equilibria of games via payoff queries. In Proceedings of the 14th ACM Conference on Electronic Commerce. 397\u2013414."},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.1145\/2956579"},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.1145\/2956582"},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.1090\/mbk\/101"},{"key":"e_1_3_2_22_2","first-page":"2602","volume-title":"Proceedings of the International Conference on Artificial Intelligence and Statistics","author":"Maiti Arnab","year":"2024","unstructured":"Arnab Maiti, Ross Boczar, Kevin Jamieson, and Lillian Ratliff. 2024. Near-optimal pure exploration in matrix games: A generalization of stochastic bandits and dueling bandits. In Proceedings of the International Conference on Artificial Intelligence and Statistics. PMLR, 2602\u20132610."},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01448847"}],"container-title":["ACM Transactions on Economics and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3732787","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,12]],"date-time":"2025-09-12T11:42:44Z","timestamp":1757677364000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3732787"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,9,12]]},"references-count":22,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2025,9,30]]}},"alternative-id":["10.1145\/3732787"],"URL":"https:\/\/doi.org\/10.1145\/3732787","relation":{},"ISSN":["2167-8375","2167-8383"],"issn-type":[{"type":"print","value":"2167-8375"},{"type":"electronic","value":"2167-8383"}],"subject":[],"published":{"date-parts":[[2025,9,12]]},"assertion":[{"value":"2024-11-06","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-04-21","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-09-12","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}