A polynomial-time nash equilibrium algorithm for repeated games

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A polynomial-time nash equilibrium algorithm for repeated games

Full text

Pdf (172 KB)

Source

Electronic Commerce archive
Proceedings of the 4th ACM conference on Electronic commerce table of contents

San Diego, CA, USA

Pages: 48 - 54

Year of Publication: 2003

ISBN:1-58113-679-X

Authors

Michael L. Littman	Rutgers University, Piscataway, NJ
Peter Stone	The University of Texas at Austin, Austin, TX

Sponsors

ACM: Association for Computing Machinery
SIGEcom: ACM Special Interest Group on Electronic Commerce

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 4, Downloads (12 Months): 25, Citation Count: 13

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/779928.779935 What is a DOI?

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 closely related problem, that of finding a Nash equilibrium for an average-payoff phrepeated bimatrix game, and presents a polynomial-time algorithm. Our approach draws on the "folk theorem" from game theory and shows how finite-state equilibrium strategies can be found efficiently and expressed succinctly.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Robert Axelrod. The Evolution of Cooperation. Basic Books, 1984.
	2	Vincent Conitzer and Tuomas Sandholm. Complexity results about Nash equilibria. Technical Report CMU-CS-02-135, CMU School for Computer Science, 2002.
	3	János Csirik , Michael L. Littman , Satinder P. Singh , Peter Stone, FAucS: An FCC Spectrum Auction Simulator for Autonomous Bidding Agents, Proceedings of the Second International Workshop on Electronic Commerce, p.139-151, November 16-17, 2001
	4	Michael J. Kearns , Michael L. Littman , Satinder P. Singh, Graphical Models for Game Theory, Proceedings of the 17th Conference in Uncertainty in Artificial Intelligence, p.253-260, August 02-05, 2001
	5	Michael L. Littman, Friend-or-Foe Q-learning in General-Sum Games, Proceedings of the Eighteenth International Conference on Machine Learning, p.322-328, June 28-July 01, 2001
	6	Michael L. Littman , Peter Stone, Implicit Negotiation in Repeated Games, Revised Papers from the 8th International Workshop on Intelligent Agents VIII, p.393-404, August 01-03, 2001
	7	J. F. Nash. Non-cooperative games. Annals of Mathematics, 54:penalty0 286--295, 1951.
	8	John F. Nash. The bargaining problem. Econometrica, 28:penalty0 155--162, 1950.
	9	Martin J. Osborne and Ariel Rubinstein. A Course in Game Theory. The MIT Press, 1994.
	10	Christos Papadimitriou, Algorithms, games, and the internet, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.749-753, July 2001, Hersonissos, Greece [doi>10.1145/380752.380883]
	11	Paul S. A. Reitsma , Peter Stone , János Csirik , Michael L. Littman, Self-Enforcing Strategic Demand Reduction, Revised Papers from the Workshop on Agent Mediated Electronic Commerce on Agent-Mediated Electronic Commerce IV, Designing Mechanisms and Systems, p.289-306, July 16, 2002
	12	Alexandeer Schrijver, Theory of linear and integer programming, John Wiley & Sons, Inc., New York, NY, 1986
	13	J. von Neumann and O. Morgenstern. Theory of Games and Economic Behavior. Princeton University Press, Princeton, NJ, 1947.
	14	Robert J. Weber. Making more from less: Strategic demand reduction in the FCC spectrum auctions. Journal of Economics and Management Strategy, 6penalty0 (3):penalty0 529--548, 1997.

CITED BY 13

	Vincent Conitzer , Tuomas Sandholm, Communication complexity as a lower bound for learning in games, Proceedings of the twenty-first international conference on Machine learning, p.24, July 04-08, 2004, Banff, Alberta, Canada
	Jacob W. Crandall , Michael A. Goodrich, Learning to compete, compromise, and cooperate in repeated general-sum games, Proceedings of the 22nd international conference on Machine learning, p.161-168, August 07-11, 2005, Bonn, Germany
	Michael L. Littman , Peter Stone, A polynomial-time Nash equilibrium algorithm for repeated games, Decision Support Systems, v.39 n.1, p.55-66, March 2005
	Vincent Conitzer , Tuomas Sandholm, Complexity of (iterated) dominance, Proceedings of the 6th ACM conference on Electronic commerce, p.88-97, June 05-08, 2005, Vancouver, BC, Canada
	Christos H. Papadimitriou , Tim Roughgarden, Computing equilibria in multi-player games, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
	Vincent Conitzer , Tuomas Sandholm, Computing the optimal strategy to commit to, Proceedings of the 7th ACM conference on Electronic commerce, p.82-90, June 11-15, 2006, Ann Arbor, Michigan, USA
	Vincent Conitzer , Tuomas Sandholm, AWESOME: A general multiagent learning algorithm that converges in self-play and learns a best response against stationary opponents, Machine Learning, v.67 n.1-2, p.23-43, May 2007
	P. J. 't Hoen , S. M. Bohte , J. A. La Poutré, Learning from induced changes in opponent (re)actions in multi-agent games, Proceedings of the fifth international joint conference on Autonomous agents and multiagent systems, May 08-12, 2006, Hakodate, Japan
	Alex Fabrikant , Christos H. Papadimitriou, The complexity of game dynamics: BGP oscillations, sink equilibria, and beyond, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.844-853, January 20-22, 2008, San Francisco, California
	Andrew Gilpin , Tuomas Sandholm, Solving two-person zero-sum repeated games of incomplete information, Proceedings of the 7th international joint conference on Autonomous agents and multiagent systems, May 12-16, 2008, Estoril, Portugal
	Vincent Conitzer , Tuomas Sandholm, A generalized strategy eliminability criterion and computational methods for applying it, Proceedings of the 20th national conference on Artificial intelligence, p.483-488, July 09-13, 2005, Pittsburgh, Pennsylvania
	P. J. 't Hoen , S. M. Bohte , J. A. La Poutré, Strategic Foresighted Learning in Competitive Multi-Agent Games, Proceeding of the 2006 conference on ECAI 2006: 17th European Conference on Artificial Intelligence August 29 -- September 1, 2006, Riva del Garda, Italy, p.536-540, May 22, 2006
	Vincent Conitzer , Tüomas Sandholm, Complexity results about Nash equilibria, Proceedings of the 18th international joint conference on Artificial intelligence, p.765-771, August 09-15, 2003, Acapulco, Mexico