Random bimatrix games are asymptotically easy to solve (a simple proof)
From MaRDI portal
Publication:1678770
DOI10.1007/s00224-013-9446-3zbMath1380.91021OpenAlexW2103463385MaRDI QIDQ1678770
Panagiota N. Panagopoulou, Paul G. Spirakis
Publication date: 7 November 2017
Published in: Theory of Computing Systems (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00224-013-9446-3
Noncooperative games (91A10) Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming) (90C33) Stochastic games, stochastic differential games (91A15)
Related Items (4)
A Glimpse at Paul G. Spirakis ⋮ 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 ⋮ On Random Symmetric Bimatrix Games
Cites Work
- On sparse approximations to randomized strategies and convex combinations
- Non-cooperative games
- Reducibility among equilibrium problems
- The complexity of computing a Nash equilibrium
- Random Bimatrix Games Are Asymptotically Easy to Solve (A Simple Proof)
- Probability Inequalities for Sums of Bounded Random Variables
- Equilibrium Points of Bimatrix Games
- Bimatrix Equilibrium Points and Mathematical Programming
This page was built for publication: Random bimatrix games are asymptotically easy to solve (a simple proof)