A polynomial-time Nash equilibrium algorithm for repeated games

摘要

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.