2023/10/24 by Arnab Maiti, Ross Boczar, Maiti, Arnab +5
Computer Science · Decision Sciences · Economics, Econometrics and Finance · #Complexity and Algorithms in Graphs #Computer Science and Game Theory (cs.GT) #FOS: Computer and information sciences #Game Theory and Applications #Game Theory and Voting Systems
paper · pdf · doi:10.48550/arxiv.2310.16236
openalex publication_date 2023/10/24 · openalex created_date 2023/10/27 · openalex updated_date 2026/07/28
We study the query complexity of finding the set of all Nash equilibria \mathcal X_⋆ × \mathcal Y_⋆ in two-player zero-sum matrix games. Fearnley and Savani (2016) showed that for any randomized algorithm, there exists an n × n input matrix where it needs to query Ω(n2) entries in expectation to compute a single Nash equilibrium. On the other hand, Bienstock et al. (1991) showed that there is a special class of matrices for which one can query O(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. In this work, we characterize the query complexity of finding the set of all Nash equilibria \mathcal X_⋆ × \mathcal Y_⋆ in terms of the number of rows n of the input matrix A ∈ ℝn × n, row support size k1 := |\bigcupx ∈ \mathcal X_⋆ supp(x)|, and column support size k2 := |\bigcupy ∈ \mathcal Y_⋆ supp(y)|. We design a simple yet non-trivial randomized algorithm that, with probability 1 - δ, returns the set of all Nash equilibria \mathcal X_⋆ × \mathcal Y_⋆ by querying at most O(nk5 ⋅ polylog(n / δ)) entries of the input matrix A ∈ ℝn × n, where k := max\k1, k2\. This upper bound is tight up to a factor of poly(k), as we show that for any randomized algorithm, there exists an n × n input matrix with min\k1, k2\ = 1, for which it needs to query Ω(nk) entries in expectation in order to find the set of all Nash equilibria \mathcal X_⋆ × \mathcal Y_⋆.