A polynomial-time Nash equilibrium algorithm for repeated games

A polynomial-time Nash equilibrium algorithm for repeated games

0.00 Avg rating0 Votes
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: ,
Keywords: Nash equilibrium
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.