Article ID: | iaor20051884 |
Country: | Netherlands |
Volume: | 39 |
Issue: | 1 |
Start Page Number: | 55 |
End Page Number: | 66 |
Publication Date: | Mar 2005 |
Journal: | Decision Support Systems |
Authors: | Littman Michael L., Stone Peter |
Keywords: | Nash equilibrium |
With the increasing reliance on game theory as a foundation for auctions and electronic commerce, efficient algorithms for computing equilibria in multiplayer general-sum games are of great theoretical and practical interest. The computational complexity of finding a Nash equilibrium for a one-shot bimatrix game is a well-known open problem. This paper treats a related but distinct problem – that of finding a Nash equilibrium for an average-payoff repeated bimatrix game, and presents a polynomial-time algorithm. Our approach draws on the well-known “folk theorem” from game theory and shows how finite-state equilibrium strategies can be found efficiently and expressed succinctly.