Query-Efficient Algorithm to Find all Nash Equilibria in a Two-Player Zero-Sum Matrix Game
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2023
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866916381327360000 |
|---|---|
| author | Maiti, Arnab Boczar, Ross Jamieson, Kevin Ratliff, Lillian J. |
| author_facet | Maiti, Arnab Boczar, Ross Jamieson, Kevin Ratliff, Lillian J. |
| contents | We study the query complexity of finding the set of all Nash equilibria $\mathcal X_\star \times \mathcal Y_\star$ in two-player zero-sum matrix games. Fearnley and Savani (2016) showed that for any randomized algorithm, there exists an $n \times 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. (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_\star \times \mathcal Y_\star$ in terms of the number of rows $n$ of the input matrix $A \in \mathbb{R}^{n \times n}$, row support size $k_1 := |\bigcup_{x \in \mathcal X_\star} \text{supp}(x)|$, and column support size $k_2 := |\bigcup_{y \in \mathcal Y_\star} \text{supp}(y)|$. We design a simple yet non-trivial randomized algorithm that, with probability $1 - δ$, returns the set of all Nash equilibria $\mathcal X_\star \times \mathcal Y_\star$ by querying at most $O(nk^5 \cdot \text{polylog}(n / δ))$ entries of the input matrix $A \in \mathbb{R}^{n \times n}$, where $k := \max\{k_1, k_2\}$. This upper bound is tight up to a factor of $\text{poly}(k)$, as we show that for any randomized algorithm, there exists an $n \times n$ input matrix with $\min\{k_1, k_2\} = 1$, for which it needs to query $Ω(nk)$ entries in expectation in order to find the set of all Nash equilibria $\mathcal X_\star \times \mathcal Y_\star$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2310_16236 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Query-Efficient Algorithm to Find all Nash Equilibria in a Two-Player Zero-Sum Matrix Game Maiti, Arnab Boczar, Ross Jamieson, Kevin Ratliff, Lillian J. Computer Science and Game Theory We study the query complexity of finding the set of all Nash equilibria $\mathcal X_\star \times \mathcal Y_\star$ in two-player zero-sum matrix games. Fearnley and Savani (2016) showed that for any randomized algorithm, there exists an $n \times 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. (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_\star \times \mathcal Y_\star$ in terms of the number of rows $n$ of the input matrix $A \in \mathbb{R}^{n \times n}$, row support size $k_1 := |\bigcup_{x \in \mathcal X_\star} \text{supp}(x)|$, and column support size $k_2 := |\bigcup_{y \in \mathcal Y_\star} \text{supp}(y)|$. We design a simple yet non-trivial randomized algorithm that, with probability $1 - δ$, returns the set of all Nash equilibria $\mathcal X_\star \times \mathcal Y_\star$ by querying at most $O(nk^5 \cdot \text{polylog}(n / δ))$ entries of the input matrix $A \in \mathbb{R}^{n \times n}$, where $k := \max\{k_1, k_2\}$. This upper bound is tight up to a factor of $\text{poly}(k)$, as we show that for any randomized algorithm, there exists an $n \times n$ input matrix with $\min\{k_1, k_2\} = 1$, for which it needs to query $Ω(nk)$ entries in expectation in order to find the set of all Nash equilibria $\mathcal X_\star \times \mathcal Y_\star$. |
| title | Query-Efficient Algorithm to Find all Nash Equilibria in a Two-Player Zero-Sum Matrix Game |
| topic | Computer Science and Game Theory |
| url | https://arxiv.org/abs/2310.16236 |