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

DOI10.1007/s00224-015-9662-0zbMath1362.68088OpenAlexW2301555989MaRDI QIDQ519892

Marcus Schaefer, Daniel Š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 equilibriumBrouwerfixed point problemsexistential theory of the real numbers

Mathematics Subject Classification ID

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

Related Items

ETR-Completeness for Decision Versions of Multi-player (Symmetric) Nash Equilibria, The Complexity of Drawing a Graph in a Polygonal Region, Smoothing the Gap Between NP and ER, The complexity of computational problems about Nash equilibria in symmetric win-lose games, The complexity of reachability in parametric Markov decision processes, On the Expressive Power of Query Languages for Matrices, The Complexity of Drawing Graphs on Few Lines and Few Planes, The Complexity of Angular Resolution, The complexity of the Hausdorff distance, Completeness for the complexity class \(\forall \exists \mathbb{R}\) and area-universality, RAC-Drawability is ∃ℝ-complete and Related Results, Unnamed Item, The complexity of drawing a graph in a polygonal region, On the Complexity of Reachability in Parametric Markov Decision Processes, Termination of polynomial loops, Tractability conditions for numeric CSPs, The real computational complexity of minmax value and equilibrium refinements in multi-player games, Unnamed Item, Unnamed Item, Optimality program in segment and string graphs, Arrangements of pseudocircles: on circularizability, Tractability frontiers in probabilistic team semantics and existential second-order logic over the reals, Tractability frontiers in probabilistic team semantics and existential second-order logic over the reals, Approximating the existential theory of the reals, Approximating the existential theory of the reals, On the computational complexity of decision problems about multi-player Nash equilibria, Subexponential algorithms for variants of the homomorphism problem in string graphs, Substitution with Satiation: A New Class of Utility Functions and a Complementary Pivot Algorithm, Computing Exact Solutions of Consensus Halving and the Borsuk-Ulam Theorem, The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg, On the Complexity of Some Geometric Problems With Fixed Parameters, Computational complexity of multi-player evolutionarily stable strategies

Cites Work

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