Approximating the existential theory of the reals
From MaRDI portal
Publication:5918470
DOI10.1016/j.jcss.2021.11.002OpenAlexW3215281080MaRDI QIDQ5918470
Paul G. Spirakis, John Fearnley, Themistoklis Melissourgos, Argyrios Deligkas
Publication date: 31 January 2022
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1810.01393
Related Items (max. 100)
A Polynomial-Time Algorithm for 1/2-Well-Supported Nash Equilibria in Bimatrix Games ⋮ A Polynomial-Time Algorithm for 1/3-Approximate Nash Equilibria in Bimatrix Games
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
- Consensus-halving via theorems of Borsuk-Ulam and Tucker
- Solving standard quadratic optimization problems via linear, semidefinite and copositive pro\-gramming
- Computing exact solutions of consensus halving and the Borsuk-Ulam theorem
- 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?
- 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
- On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
- The Complexity of Decision Problems about Nash Equilibria in Win-Lose Games
- Reducibility among Combinatorial Problems
- Computing Exact Solutions of Consensus Halving and the Borsuk-Ulam Theorem
- On oblivious PTAS's for nash equilibrium
- Probability Inequalities for Sums of Bounded Random Variables
- Maxima for Graphs and a New Proof of a Theorem of Turán
- Approximating the best Nash Equilibrium in no(log n)-time breaks the Exponential Time Hypothesis
- Most Tensor Problems Are NP-Hard
- Exact algorithms for solving stochastic games
- Stochastic Games
- Approximating the existential theory of the reals
This page was built for publication: Approximating the existential theory of the reals
