Approximating the existential theory of the reals

DOI10.1007/978-3-030-04612-5_9zbMath1443.91012arXiv1810.01393OpenAlexW2894903419MaRDI QIDQ5918881

Paul G. Spirakis, John Fearnley, Argyrios Deligkas, Themistoklis Melissourgos

Publication date: 18 June 2020

Published in: Web and Internet Economics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1810.01393

zbMATH Keywords

quasi-polynomial time approximation schemeapproximate existential theory of reals

Mathematics Subject Classification ID

Noncooperative games (91A10) Stochastic games, stochastic differential games (91A15)

Related Items (4)

Lipschitz continuity and approximate equilibria ⋮ Approximating the existential theory of the reals ⋮ Approximating the existential theory of the reals ⋮ Computing Exact Solutions of Consensus Halving and the Borsuk-Ulam Theorem

Cites Work

• Unnamed Item
• Unnamed Item
• Fixed points, Nash equilibria, and the existential theory of the reals
• Computing constrained approximate equilibria in polymatrix games
• New complexity results about Nash equilibria
• The complexity of optimizing over a simplex, hypercube or sphere: a short survey
• Nash and correlated equilibria: Some complexity considerations
• On sparse approximations to randomized strategies and convex combinations
• Complexity of rational and irrational Nash equilibria
• Inapproximability results for constrained approximate Nash equilibria
• Solving standard quadratic optimization problems via linear, semidefinite and copositive pro\-gramming
• An alternative proof of a PTAS for fixed-degree polynomial optimization over the simplex
• A PTAS for the minimization of polynomials of fixed degree over the simplex
• Lipschitz Continuity and Approximate Equilibria
• Approximating Nash Equilibria and Dense Bipartite Subgraphs via an Approximate Version of Caratheodory's Theorem
• Empirical Distribution of Equilibrium Play and Its Testing Application
• How Hard Is It to Approximate the Best Nash Equilibrium?
• ETR-Completeness for Decision Versions of Multi-player (Symmetric) Nash Equilibria
• Approximating Nash Equilibria in Tree Polymatrix Games
• A Catalog of EXISTS-R-Complete Decision Problems About Nash Equilibria in Multi-Player Games.
• Existential-R-Complete Decision Problems about Symmetric Nash Equilibria in Symmetric Multi-Player Games
• The Complexity of Decision Problems about Nash Equilibria in Win-Lose Games
• Approximating the best Nash Equilibrium in n^{o(log n)}-time breaks the Exponential Time Hypothesis
• Most Tensor Problems Are NP-Hard
• Exact algorithms for solving stochastic games
• Approximating the existential theory of the reals

This page was built for publication: Approximating the existential theory of the reals