Settling Some Open Problems on 2-Player Symmetric Nash Equilibria

DOI10.1007/978-3-662-48433-3_21zbMath1358.91004arXiv1412.0969OpenAlexW2153135867MaRDI QIDQ3449600

Ruta Mehta, Vijay V. Vazirani, Sadra Yazdanbod

Publication date: 4 November 2015

Published in: Algorithmic Game Theory (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1412.0969

Mathematics Subject Classification ID

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

Related Items (3)

Constant Rank Two-Player Games are PPAD-hard ⋮ The complexity of computational problems about Nash equilibria in symmetric win-lose games ⋮ On the computational complexity of decision problems about multi-player Nash equilibria

Cites Work

• Unnamed Item
• Nash equilibria: complexity, symmetries, and approximation
• Games of fixed rank: a hierarchy of bimatrix games
• 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
• Approximate Nash equilibria in anonymous games
• Simple complexity from imitation games
• Non-cooperative games
• Settling the complexity of computing two-player Nash equilibria
• The Complexity of Computing a Nash Equilibrium
• Constant rank bimatrix games are PPAD-hard
• Rank-1 bimatrix games

This page was built for publication: Settling Some Open Problems on 2-Player Symmetric Nash Equilibria