Query-Efficient Algorithm to Find all Nash Equilibria in a Two-Player Zero-Sum Matrix Game

We study the query complexity of finding the set of all Nash equilibria \(\mathcal {X}_\star \unicode{x00D7} \mathcal {Y}_\star\) in two-player zero-sum matrix games. Fearnley and Savani [ 18 ] showed that for any randomized algorithm, there exists an n × n input matrix where it needs to query Ω ( n 2 ) entries in expectation to compute a single Nash equilibrium. On the other hand, Bienstock et al. [ 5 ] 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}_\star \unicode{x00D7} \mathcal {Y}_\star\) in terms of the number of rows n of the input matrix \(A \in \mathbb {R}^{n \unicode{x00D7} n}\) , row support size \(k_1 := |\bigcup \nolimits _{x \in \mathcal {X}_\star } \text{supp}(x)|\) , and column support size \(k_2 := |\bigcup \nolimits _{y \in \mathcal {Y}_\star } \text{supp}(y)|\) . We design a simple yet non-trivial randomized algorithm that returns the set of all Nash equilibria \(\mathcal {X}_\star \unicode{x00D7} \mathcal {Y}_\star\) by querying at most \(O(nk^5 \cdot \text{polylog}(n))\) entries of the input matrix \(A \in \mathbb {R}^{n \unicode{x00D7} n}\) in expectation, where \(k := \max \lbrace k_1, k_2\rbrace\) . 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 \lbrace k_1, k_2\rbrace = 1\) , for which it needs to query Ω ( nk ) entries in expectation in order to find the set of all Nash equilibria \(\mathcal {X}_\star \unicode{x00D7} \mathcal {Y}_\star\) .