English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We study the query complexity of identifying Nash equilibria in two-playerzero-sum matrix games. Grigoriadis and Khachiyan (1995) showed that anydeterministic algorithm needs to query $\Omega(n^2)$ entries in worst case froman $n\times n$ input matrix in order to compute an $\varepsilon$-approximateNash equilibrium, where $\varepsilon<\frac{1}{2}$. Moreover, they designed arandomized algorithm that queries $\mathcal O(\frac{n\log n}{\varepsilon^2})$entries from the input matrix in expectation and returns an$\varepsilon$-approximate Nash equilibrium when the entries of the matrix arebounded between $-1$ and $1$. However, these two results do not completelycharacterize the query complexity of finding an exact Nash equilibrium intwo-player zero-sum matrix games. In this work, we characterize the querycomplexity of finding an exact Nash equilibrium for two-player zero-sum matrixgames that have a unique Nash equilibrium $(x_\star,y_\star)$. We first showthat any randomized algorithm needs to query $\Omega(nk)$ entries of the inputmatrix $A\in\mathbb{R}^{n\times n}$ in expectation in order to find the uniqueNash equilibrium where $k=|\text{supp}(x_\star)|$. We complement this lowerbound by presenting a simple randomized algorithm that, with probability$1-\delta$, returns the unique Nash equilibrium by querying at most $\mathcalO(nk^4\cdot \text{polylog}(\frac{n}{\delta}))$ entries of the input matrix$A\in\mathbb{R}^{n\times n}$. In the special case when the unique NashEquilibrium is a pure-strategy Nash equilibrium (PSNE), we design a simpledeterministic algorithm that finds the PSNE by querying at most $\mathcal O(n)$entries of the input matrix.

Query-Efficient Algorithms to Find the Unique Nash Equilibrium in a Two-Player Zero-Sum Matrix Game