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/

Zendy Pro

Presents the zaia usage as premium feature

ZAIA

Presents AI Discovery search usage as a premium feature

AI Discovery

Presents AI Discovery explain and summary usage as a premium feature

Content Analysis

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Presents the pdf analysis as premium feature

PDF Analysis

1500 Top-up

3000 Top-up

Zendy Basic

2500 Top-up

Zendy Unlimited

Presents the access of premium content as premium feature

Premium Content

We show that for several solution concepts for finite n-player games, where n ≥ 3, the task of simply verifying its conditions is computationally equivalent to the decision problem of the existential theory of the reals. This holds for trembling hand perfect equilibrium, proper equilibrium, and CURB sets in strategic form games and for (the strategy part of) sequential equilibrium, trembling hand perfect equilibrium, and quasi-perfect equilibrium in extensive form games of perfect recall. For obtaining these results we first show that the decision problem for the minmax value in n-player games, where n ≥ 3, is also equivalent to the decision problem for the existential theory of the reals. Our results thus improve previous results of NP-hardness as well as Sqrt-Sum-hardness of the decision problems to completeness for ∃ℝ${\exists {\mathbb {R}}}$, the complexity class corresponding to the decision problem of the existential theory of the reals. As a byproduct we also obtain a simpler proof of a result by Schaefer and Štefankovič giving ∃ℝ${\exists {\mathbb {R}}}$-completeness for the problem of deciding existence of a probability constrained Nash equilibrium.

The Real Computational Complexity of Minmax Value and Equilibrium Refinements in Multi-player Games