A polynomial-time nash equilibrium algorithm for repeated games

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

• 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.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.m Miscellaneous

General Terms:
Algorithms, Theory

Keywords:
complexity analysis, computational game theory, nash equilibrium, repeated games