On the complexity of deciding bimatrix games similarity

DOI10.1016/J.TCS.2008.07.021zbMATH Open1151.91012OpenAlexW2062992879MaRDI QIDQ955038FDOQ955038

Authors: Ye Du 

Publication date: 18 November 2008

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2008.07.021

Recommendations

• On the computational complexity of Nash equilibria for \((0,1)\) bimatrix games
• The complexity of computational problems about Nash equilibria in symmetric win-lose games
• The complexity of decision problems about Nash equilibria in win-lose games
• New complexity results about Nash equilibria
• On the complexity of deciding degeneracy in a bimatrix game with sparse payoff matrix

zbMATH Keywords

Nash equilibriumComplexityGame theorySimilarityBimatrix game

Mathematics Subject Classification ID

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

Cites Work

• Equilibrium points in n -person games
• New complexity results about Nash equilibria
• On the complexity of the parity argument and other inefficient proofs of existence
• Equilibrium Points of Bimatrix Games
• Settling the complexity of computing two-player Nash equilibria
• Equilibrium computation for two-player games in strategic and extensive form
• The complexity of computing a Nash equilibrium
• Nash and correlated equilibria: Some complexity considerations
• Hard-to-Solve Bimatrix Games
• On the Complexity of Game Isomorphism
• On the computational complexity of Nash equilibria for \((0,1)\) bimatrix games

Cited In (6)

• The computational complexity of weak saddles
• Random bimatrix games are asymptotically easy to solve (a simple proof)
• On the complexity of deciding degeneracy in a bimatrix game with sparse payoff matrix
• The computational complexity of weak saddles
• On the computational complexity of Nash equilibria for \((0,1)\) bimatrix games
• The complexity of computational problems about Nash equilibria in symmetric win-lose games

This page was built for publication: On the complexity of deciding bimatrix games similarity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q955038)