ETR-Completeness for Decision Versions of Multi-player (Symmetric) Nash Equilibria

DOI10.1007/978-3-662-47672-7_45zbMath1441.68072OpenAlexW2234020812MaRDI QIDQ3448815

Sadra Yazdanbod, Vijay V. Vazirani, Ruta Mehta, Jugal Garg

Publication date: 27 October 2015

Published in: Automata, Languages, and Programming (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-662-47672-7_45

Mathematics Subject Classification ID

Noncooperative games (91A10) (n)-person games, (n>2) (91A06) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (11)

ETR-Completeness for Decision Versions of Multi-player (Symmetric) Nash Equilibria ⋮ Smoothing the Gap Between NP and ER ⋮ Inapproximability Results for Approximate Nash Equilibria ⋮ Computing exact solutions of consensus halving and the Borsuk-Ulam theorem ⋮ The real computational complexity of minmax value and equilibrium refinements in multi-player games ⋮ Unnamed Item ⋮ Inapproximability results for constrained approximate Nash equilibria ⋮ Approximating the existential theory of the reals ⋮ Substitution with Satiation: A New Class of Utility Functions and a Complementary Pivot Algorithm ⋮ The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg ⋮ Computational complexity of multi-player evolutionarily stable strategies

Cites Work

• Unnamed Item
• Fixed points, Nash equilibria, and the existential theory of the reals
• New complexity results about Nash equilibria
• Nash and correlated equilibria: Some complexity considerations
• On the complexity of the parity argument and other inefficient proofs of existence
• Non-cooperative games
• On the Complexity of Nash Equilibria and Other Fixed Points
• ETR-Completeness for Decision Versions of Multi-player (Symmetric) Nash Equilibria
• Settling the complexity of computing two-player Nash equilibria
• The Complexity of Computing a Nash Equilibrium
• Dichotomies in equilibrium computation, and complementary pivot algorithms for a new class of non-separable utility functions
• Query complexity of approximate nash equilibria
• Equilibrium Points of Bimatrix Games
• Hard-to-Solve Bimatrix Games

This page was built for publication: ETR-Completeness for Decision Versions of Multi-player (Symmetric) Nash Equilibria