2026-07-23T17:12:59Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8163 2024-03-06T10:39:23Z ddc:004 open_access

Well-Supported vs. Approximate Nash Equilibria: Query Complexity of Large Games Chen, Xi Cheng, Yu Tang, Bo Equilibrium Computation Query Complexity Large Games In this paper we present a generic reduction from the problem of finding an \epsilon-well-supported Nash equilibrium (WSNE) to that of finding an \Theta(\epsilon)-approximate Nash equilibrium (ANE), in large games with n players and a bounded number of strategies for each player. Our reduction complements the existing literature on relations between WSNE and ANE, and can be applied to extend hardness results on WSNE to similar results on ANE. This allows one to focus on WSNE first, which is in general easier to analyze and control in hardness constructions. As an application we prove a 2^{\Omega(n/\log n)} lower bound on the randomized query complexity of finding an \epsilon-ANE in binary-action n-player games, for some constant \epsilon>0. This answers an open problem posed by Hart and Nisan and Babichenko, and is very close to the trivial upper bound of 2^n. Previously for WSNE, Babichenko showed a 2^{\Omega(n)} lower bound on the randomized query complexity of finding an \epsilon-WSNE for some constant epsilon>0. Our result follows directly from combining Babichenko's result and our new reduction from WSNE to ANE. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Xi Chen and Yu Cheng and Bo Tang 2017 Is Part Of LIPIcs, Volume 67, 8th Innovations in Theoretical Computer Science Conference (ITCS 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2017.57 urn:nbn:de:0030-drops-81636 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2017.57 eng https://creativecommons.org/licenses/by/3.0/legalcode