Polynomial algorithms for approximating Nash equilibria of bimatrix games

DOI10.1016/j.tcs.2008.12.033zbMath1159.91307OpenAlexW2158702668MaRDI QIDQ1014631

Panagiota N. Panagopoulou, Spyros C. Kontogiannis, Paul G. Spirakis

Publication date: 29 April 2009

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

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

zbMATH Keywords

bimatrix gameapproximate Nash equilibrium

Mathematics Subject Classification ID

Noncooperative games (91A10) Computational methods for problems pertaining to game theory, economics, and finance (91-08)

Related Items (15)

Computing approximate Nash equilibria in general network revenue management games ⋮ Games of fixed rank: a hierarchy of bimatrix games ⋮ A Glimpse at Paul G. Spirakis ⋮ Approximating Nash Equilibria and Dense Subgraphs via an Approximate Version of Carathéodory's Theorem ⋮ On tightness of the Tsaknakis-Spirakis algorithm for approximate Nash equilibrium ⋮ Finite uniform approximation of two-person games defined on a product of staircase-function infinite spaces ⋮ 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 ⋮ Recent development in computational complexity characterization of Nash equilibrium ⋮ Well supported approximate equilibria in bimatrix games ⋮ A note on approximate Nash equilibria ⋮ New algorithms for approximate Nash equilibria in bimatrix games ⋮ Convergence method, properties and computational complexity for Lyapunov games ⋮ Near-Optimal Communication Lower Bounds for Approximate Nash Equilibria ⋮ Near-Optimal Communication Lower Bounds for Approximate Nash Equilibria

Cites Work

• A note on approximate Nash equilibria
• New algorithms for approximate Nash equilibria in bimatrix games
• On sparse approximations to randomized strategies and convex combinations
• On the complexity of the parity argument and other inefficient proofs of existence
• Non-cooperative games
• The complexity of computing a Nash equilibrium
• Equilibrium Points of Bimatrix Games
• Efficient Algorithms for Constant Well Supported Approximate Equilibria in Bimatrix Games
• Bimatrix Equilibrium Points and Mathematical Programming

This page was built for publication: Polynomial algorithms for approximating Nash equilibria of bimatrix games