Fixed points, Nash equilibria, and the existential theory of the reals

DOI10.1007/S00224-015-9662-0MaRDI QIDQ519892zbMATH OpenOpenAlexFDO

Authors Marcus Schaefer, D. Štefankovič

Publication date 31 March 2017

Published in Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00224-015-9662-0

zbMATH Keywords

computational complexityNash equilibriumfixed point problemsBrouwerexistential theory of the real numbers

Mathematics Subject Classification ID

Noncooperative games (91A10) Fixed-point and coincidence theorems (topological aspects) (54H25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Games involving topology, set theory, or logic (91A44) Decidability of theories and sets of sentences (03B25) Basic properties of first-order languages and structures (03C07) Semialgebraic sets and related spaces (14P10)

Recommendations

• On the Complexity of Nash Equilibria and Other Fixed Points
• Equilibria, fixed points, and complexity classes
• Equilibria, fixed points, and complexity classes
• A Catalog of EXISTS-R-Complete Decision Problems About Nash Equilibria in Multi-Player Games.
• \(\exists\mathbb{R}\)-complete decision problems about symmetric Nash equilibria in symmetric multi-player games

Cites work

• scientific article; zbMATH DE number 3870491 (Why is no real title available?)
• scientific article; zbMATH DE number 4092241 (Why is no real title available?)
• scientific article; zbMATH DE number 17663 (Why is no real title available?)
• scientific article; zbMATH DE number 1182922 (Why is no real title available?)
• scientific article; zbMATH DE number 6302984 (Why is no real title available?)
• A note on a theorem of Blum, Shub, and Smale
• Algorithms in real algebraic geometry
• Bounding the radii of balls meeting every connected component of semi-algebraic sets
• COMPLEXITY AND REAL COMPUTATION: A MANIFESTO
• Complexity of some geometric and topological problems
• Constraint networks of topological relations and convexity
• Counting complexity classes for numeric computations. II: Algebraic and semialgebraic sets
• Decision procedures. An algorithmic point of view. With foreword by Randal E. Bryant
• Intersection graphs of segments
• On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
• On the Complexity of Nash Equilibria and Other Fixed Points
• On the Complexity of Numerical Analysis
• On the Minimum of a Polynomial Function on a Basic Closed Semialgebraic Set and Applications
• On the complexity of the parity argument and other inefficient proofs of existence
• On the minimum of a positive polynomial over the standard simplex
• Realizability of graphs and linkages
• Realization spaces of 4-polytopes are universal
• Realization spaces of polytopes
• Simple realizability of complete abstract topological graphs in P
• Solving systems of polynomial inequalities in subexponential time
• Some provably hard crossing number problems
• Sphere and dot product representations of graphs
• The complexity of simultaneous geometric graph embedding
• The computational complexity of some problems of linear algebra
• Universality of Nash Equilibria

Cited in

(44)

• The complexity of computational problems about Nash equilibria in symmetric win-lose games
• On the complexity of an expanded Tarski's fixed point problem under the componentwise ordering
• Tractability conditions for numeric CSPs
• The complexity of drawing a graph in a polygonal region
• scientific article; zbMATH DE number 7559240 (Why is no real title available?)
• The complexity of recognizing geometric hypergraphs
• The complexity of reachability in parametric Markov decision processes
• Framework for \(\exists\mathbb{R}\)-completeness of two-dimensional packing problems
• On classifying continuous constraint satisfaction problems
• The complexity of the Hausdorff distance
• Computing exact solutions of consensus halving and the Borsuk-Ulam theorem
• On the complexity of recognizing nerves of convex sets
• Arrangements of pseudocircles: on circularizability
• Substitution with satiation: a new class of utility functions and a complementary pivot algorithm
• On the Complexity of Reachability in Parametric Markov Decision Processes
• Optimality program in segment and string graphs
• Further \(\exists{\mathbb{R}} \)-complete problems with PSD matrix factorizations
• A practical algorithm with performance guarantees for the art gallery problem
• Subexponential algorithms for variants of the homomorphism problem in string graphs
• The Complexity of Drawing Graphs on Few Lines and Few Planes
• Representing matroids over the reals is \(\exists \mathbb{R}\)-complete
• On the expressive power of query languages for matrices
• The Hadamard decomposition problem
• Termination of polynomial loops
• scientific article; zbMATH DE number 7559416 (Why is no real title available?)
• RAC-Drawability is ∃ℝ-complete and Related Results
• ETR-completeness for decision versions of multi-player (symmetric) Nash equilibria
• Complexity of reachability problems in neural networks
• Completeness for the complexity class \(\forall \exists \mathbb{R}\) and area-universality
• The complexity of drawing a graph in a polygonal region
• On the computational complexity of decision problems about multi-player Nash equilibria
• On the complexity of some geometric problems with fixed parameters
• Approximating the existential theory of the reals
• The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg
• Tractability frontiers in probabilistic team semantics and existential second-order logic over the reals
• Beyond the Existential Theory of the Reals
• The Complexity of Angular Resolution
• Tractability frontiers in probabilistic team semantics and existential second-order logic over the reals
• The real computational complexity of minmax value and equilibrium refinements in multi-player games
• Smoothing the Gap Between NP and ER
• Computational complexity of multi-player evolutionarily stable strategies
• Logics with probabilistic team semantics and the Boolean negation
• Computational complexity of decision problems about Nash equilibria in win-lose multi-player games
• Approximating the existential theory of the reals

This page was built for publication: Fixed points, Nash equilibria, and the existential theory of the reals

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q519892)