Complexity of rational and irrational Nash equilibria

DOI10.1007/s00224-013-9523-7zbMath1380.91029OpenAlexW2104892205MaRDI QIDQ1678771

Marios Mavronicolas, Vittorio Bilò

Publication date: 7 November 2017

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

Full work available at URL: https://doi.org/10.1007/s00224-013-9523-7

zbMATH Keywords

decision problemsNash equilibriastrategic gamescomplexity theory

Mathematics Subject Classification ID

Noncooperative games (91A10) Abstract computational complexity for mathematical programming problems (90C60) Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming) (90C33) Decision theory for games (91A35)

Related Items (7)

The complexity of computational problems about Nash equilibria in symmetric win-lose games ⋮ Computing exact solutions of consensus halving and the Borsuk-Ulam theorem ⋮ The complexity of \((\mathsf{E}+\mathsf{Var})\)-equilibria, \(\mathsf{ESR}\)-equilibria, and \(\mathsf{SuperE}\)-equilibria for 2-players games with few cost values ⋮ 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 ⋮ Computing Exact Solutions of Consensus Halving and the Borsuk-Ulam Theorem

Cites Work

• Unnamed Item
• Unnamed Item
• New complexity results about Nash equilibria
• The myth of the folk theorem
• On the computational complexity of Nash equilibria for \((0,1)\) bimatrix games
• Nash and correlated equilibria: Some complexity considerations
• On the complexity of the parity argument and other inefficient proofs of existence
• Simple complexity from imitation games
• Non-cooperative games
• On the Complexity of Nash Equilibria and Other Fixed Points
• When the Players Are Not Expectation Maximizers
• Settling the complexity of computing two-player Nash equilibria
• The Complexity of Computing a Nash Equilibrium
• The complexity of theorem-proving procedures
• Equilibrium points in n -person games

This page was built for publication: Complexity of rational and irrational Nash equilibria