On the complexity of deciding bimatrix games similarity

DOI10.1016/J.TCS.2008.07.021MaRDI QIDQ955038zbMATH OpenOpenAlexFDO

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

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)

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

Cites work

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

Cited in

(6)

• The complexity of computational problems about Nash equilibria in symmetric win-lose games
• 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

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)