UTCS Artificial Intelligence
courses
talks/events
demos
people
projects
publications
software/data
labs
areas
admin
A Polynomial-time Nash Equilibrium Algorithm for Repeated Games (2005)
Michael L. Littman and
Peter Stone
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.
View:
PDF
,
PS
,
HTML
Citation:
Decision Support Systems
, Vol. 39 (2005), pp. 55-66.
Bibtex:
@article{DSS04, title={A Polynomial-time Nash Equilibrium Algorithm for Repeated Games}, author={Michael L. Littman and Peter Stone}, volume={39}, journal={Decision Support Systems}, pages={55-66}, url="http://www.cs.utexas.edu/users/ai-lab?DSS04", year={2005} }
People
Peter Stone
Faculty
pstone [at] cs utexas edu
Areas of Interest
Game Theory
Multiagent Systems
Other Areas
Planning
Labs
Learning Agents