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 Tools annual

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 Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

We study the randomized query complexity of approximate Nash equilibria (ANE) in large games. We prove that, for some constant $\epsilon>0$, any randomized oracle algorithm that computes an $\epsilon$-ANE in a binary-action, $n$-player game must make $2^{\Omega(n/\log n)}$ payoff queries. For the stronger solution concept of well-supported Nash equilibria (WSNE), Babichenko previously gave an exponential $2^{\Omega(n)}$ lower bound for the randomized query complexity of $\epsilon$-WSNE, for some constant $\epsilon>0$; the same lower bound was shown to hold for $\epsilon$-ANE, but only when $\epsilon=O(1/n)$. Our result answers an open problem posed by Hart and Nisan and Babichenko and is very close to the trivial upper bound of $2^n$. Our proof relies on a generic reduction from the problem of finding an $\epsilon$-WSNE to the problem of finding an $\epsilon/(4\alpha)$-ANE, in large games with $\alpha$ actions, which might be of independent interest.

Well-Supported vs. Approximate Nash Equilibria: Query Complexity of Large Games