On the computational complexity of Nash equilibria for \((0,1)\) bimatrix games

DOI10.1016/j.ipl.2005.01.010zbMath1192.68315OpenAlexW2043166017MaRDI QIDQ1041739

Bruno Codenotti, Daniel Štefanković

Publication date: 4 December 2009

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2005.01.010

zbMATH Keywords

computational complexityNash equilibriumNP-completenessbimatrix gamesimitation games

Mathematics Subject Classification ID

Games involving graphs (91A43) General equilibrium theory (91B50) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (11)

Simulating cardinal preferences in Boolean games: a proof technique ⋮ The Computational Complexity of Finding a Mixed Berge Equilibrium for a k-Person Noncooperative Game in Normal Form ⋮ The complexity of computational problems about Nash equilibria in symmetric win-lose games ⋮ Complexity of rational and irrational Nash equilibria ⋮ A Polynomial-Time Algorithm for 1/2-Well-Supported Nash Equilibria in Bimatrix Games ⋮ A Polynomial-Time Algorithm for 1/3-Approximate Nash Equilibria in Bimatrix Games ⋮ The complexity of uniform Nash equilibria and related regular subgraph problems ⋮ Single Parameter FPT-Algorithms for Non-trivial Games ⋮ On the complexity of deciding bimatrix games similarity ⋮ Simple complexity from imitation games ⋮ Imitation games and computation

Cites Work

• 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
• Algorithms, games, and the internet
• Equilibrium Points of Bimatrix Games

This page was built for publication: On the computational complexity of Nash equilibria for \((0,1)\) bimatrix games