• Classified by Topic • Classified by Publication Type • Sorted by Date • Sorted by First Author Last Name • Classified by Funding Source •

Michael L. Littman and Peter
Stone. **A Polynomial-time Nash Equilibrium Algorithm for Repeated Games**. *Decision Support Systems*, 39:55–66
, 2005.

An earlier version appeared in the proceedings of

Official version from Decision
Support Systems

[PDF]244.7kB [postscript]272.4kB

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.

@article(DSS04, author="Michael L.~Littman and Peter Stone", title="A Polynomial-time {N}ash Equilibrium Algorithm for Repeated Games", journal="Decision Support Systems", year="2005", volume="39", pages="55--66 ", 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. }, wwwnote={An earlier version appeared in the proceedings of <a href="http://cs.gmu.edu/~menasce/ec03/ecom03cfp.html">the fourth annual ACM Conference on Electronic Commerce</a><br>Official version from <a href="http://www.sciencedirect.com/science?_ob=ArticleURL&_udi=B6V8S-4DFT4HY-3&_user=10&_handle=B-WA-A-W-AA-MsSAYZW-UUA-AAUBZUDBDC-AAUAAYYADC-DZAUDBCVD-AA-U&_fmt=full&_coverDate=03%2F01%2F2005&_rdoc=6&_orig=browse&_srch=%23toc%235878%232005%23999609998%23529481!&_cdi=5878&view=c&_acct=C000050221&_version=1&_urlVersion=0&_userid=10&md5=64dc03ccf046c25d09f2d6f5c101164f">Decision Support Systems</a>}, )

Generated by bib2html.pl (written by Patrick Riley ) on Mon Jun 27, 2016 13:36:04