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

DOI10.1007/S00224-015-9662-0zbMATH Open1362.68088OpenAlexW2301555989MaRDI QIDQ519892FDOQ519892

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)

Cites Work

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

Cited In (43)

• Title not available (Why is that?)
• The complexity of drawing a graph in a polygonal region
• Tractability conditions for numeric CSPs
• The complexity of recognizing geometric hypergraphs
• Framework for \(\exists\mathbb{R}\)-completeness of two-dimensional packing problems
• On classifying continuous constraint satisfaction problems
• The complexity of reachability in parametric Markov decision processes
• The complexity of the Hausdorff distance
• Arrangements of pseudocircles: on circularizability
• On the Complexity of Reachability in Parametric Markov Decision Processes
• The Complexity of Drawing a Graph in a Polygonal Region
• 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
• On the Complexity of Some Geometric Problems With Fixed Parameters
• The Complexity of Drawing Graphs on Few Lines and Few Planes
• Representing matroids over the reals is \(\exists \mathbb{R}\)-complete
• Subexponential algorithms for variants of the homomorphism problem in string graphs
• The Hadamard decomposition problem
• Title not available (Why is that?)
• RAC-Drawability is ∃ℝ-complete and Related Results
• Termination of polynomial loops
• Complexity of reachability problems in neural networks
• Completeness for the complexity class \(\forall \exists \mathbb{R}\) and area-universality
• On the computational complexity of decision problems about multi-player Nash equilibria
• Approximating the existential theory of the reals
• The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg
• Computing Exact Solutions of Consensus Halving and the Borsuk-Ulam Theorem
• Tractability frontiers in probabilistic team semantics and existential second-order logic over the reals
• Beyond the Existential Theory of the Reals
• On the Expressive Power of Query Languages for Matrices
• The Complexity of Angular Resolution
• Title not available (Why is that?)
• Tractability frontiers in probabilistic team semantics and existential second-order logic over the reals
• Substitution with Satiation: A New Class of Utility Functions and a Complementary Pivot Algorithm
• The real computational complexity of minmax value and equilibrium refinements in multi-player games
• ETR-Completeness for Decision Versions of Multi-player (Symmetric) Nash Equilibria
• Smoothing the Gap Between NP and ER
• 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
• Computational complexity of multi-player evolutionarily stable strategies
• The complexity of computational problems about Nash equilibria in symmetric win-lose games

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)