Selecting strategies using empirical game models: an experimental analysis of meta-strategies

ABSTRACT

In many complex multi-agent domains it is impractical to compute exact analytic solutions. An alternate means of analysis applies computational tools to derive and analyze empirical game models. These models are noisy approximations, which raises questions about how to account for uncertainty when analyzing the model. We develop a novel experimental framework and apply it to benchmark meta-strategies -- general algorithms for selecting strategies based on empirical game models.

We demonstrate that modeling noise is important; a naïve approach that disregards noise and plays according to Nash equilibrium yields poor choices. We introduce three parameterized algorithms that factor noise into the analysis by predicting distributions of opponent play. As observation noise increases, rational players generally make less specific outcome predictions. Our comparison of the algorithms identifies logit equilibrium as the best method for making these predictions. Logit equilibrium incorporates a form of noisy decision-making by players. Our evidence shows that this is a robust method for approximating the effects of uncertainty in many contexts. This result has practical relevance for guiding analysis of empirical game models. It also offers an intriguing rationale for behavioral findings that logit equilibrium is a better predictor of human behavior than Nash equilibrium.

REFERENCES

• 1: S. P. Anderson, J. K. Goeree, and C. A. Holt. Minimum-effort coordination games: stochastic potential and logit equilibrium. Games and Economic Behavior, 34:177--199, 2001.
• 2: O. Armantier, J.-P. Florens, and J.-F. Richard. Approximation of Bayesian Nash equilibrium. Journal of Applied Economics, 2006. Submitted.
• 3: J. Bednar and S. Page. Can game(s) theory explain culture? The emergence of cultural behavior within multiple games. Rationality and Society, 19(1):65--97, 2007.
• 4: Ronen I. Brafman , Moshe Tennenholtz, Efficient learning equilibrium, Artificial Intelligence, v.159 n.1-2, p.27-47, November 2004 [doi>10.1016/j.artint.2004.04.013]
• 5: C. M. Capra, J. K. Goeree, R. Gomez, and C. A. Holt. Anomalous behavior in a traveler's dilemma? American Economic Review, 89(3):678--690, 1999.
• 6: H. Carlsson and E. van Damme. Global games and equilibrium selection. Econometrica, 61(5):989--1018, 1993.
• 7: V. Conitzer and T. Sandholm. Complexity results about Nash equilibrium. In 18th International Joint Conference on Artificial Intelligence, pages 765--771, 2003.
• 8: J. K. Goeree, C. A. Holt, and T. R. Palfrey. Regular quantal response equilibrium. Experimental Economics, 8(4):347--367, 2005.
• 9: J. Harsanyi. Games with incomplete information played by Bayesian players, Parts I, II, and III. Management Science, 14:159--182, 320--334, 486--502, 1967--1968.
• 10: Patrick R. Jordan , Yevgeniy Vorobeychik , Michael P. Wellman, Searching for approximate equilibria in empirical games, Proceedings of the 7th international joint conference on Autonomous agents and multiagent systems, May 12-16, 2008, Estoril, Portugal
• 11: A. Lipson. An empirical evaluation of multiagent learning algorithms. Master's thesis, University of British Columbia, 2005.
• 12: R. D. McKelvey, A. M. McLennan, and T. L. Turocy. Gambit: Software tools for game theory, version 0.2006.01.20, 2006. http://econweb.tamu.edu/gambit.
• 13: R. D. McKelvey and T. R. Palfrey. Quantal response equilibria for normal form games. Games and Economic Behavior, 10:6--38, 1995.
• 14: S. Morris and H. S. Shin. Global Games: Theory and Applications, volume Advances in Economics and Econometrics (Proceedings of the Eighth World Congress of the Econometric Society). Cambridge University Press, 2003.
• 15: Eugene Nudelman , Jennifer Wortman , Yoav Shoham , Kevin Leyton-Brown, Run the GAMUT: A Comprehensive Approach to Evaluating Game-Theoretic Algorithms, Proceedings of the Third International Joint Conference on Autonomous Agents and Multiagent Systems, p.880-887, July 19-23, 2004, New York, New York [doi>10.1109/AAMAS.2004.238]
• 16: S. Phelps , M. Marcinkiewicz , S. Parsons, A novel method for automatic strategy acquisition in N-player non-zero-sum games, Proceedings of the fifth international joint conference on Autonomous agents and multiagent systems, May 08-12, 2006, Hakodate, Japan [doi>10.1145/1160633.1160760]
• 17: Daniel M. Reeves , Michael P. Wellman, Generating trading agent strategies: analytic and empirical methods for infinite and large games, University of Michigan, Ann Arbor, MI, 2005
• 18: P. Taylor and L. Jonker. Evolutionary stable strategies and game dynamics. Mathematical Biosciences, 16:76--83, 1978.
• 19: T. L. Turocy. A dynamic homotopy interpretation of the logistic quantal response equilibrium correspondence. Games and Economic Behavior, 51:243--263, 2005.
• 20: Yevgeniy Vorobeychik , Christopher Kiekintveld , Michael P. Wellman, Empirical mechanism design: methods, with application to a supply-chain scenario, Proceedings of the 7th ACM conference on Electronic commerce, p.306-315, June 11-15, 2006, Ann Arbor, Michigan, USA [doi>10.1145/1134707.1134741]
• 21: Yevgeniy Vorobeychik , Christopher Kiekintveld , Michael P. Wellman, Empirical mechanism design: methods, with application to a supply-chain scenario, Proceedings of the 7th ACM conference on Electronic commerce, p.306-315, June 11-15, 2006, Ann Arbor, Michigan, USA [doi>10.1145/1134707.1134741]
• 22: W. E. Walsh, R. Das, G. Tesauro, and J. O. Kephart. Analyzing complex strategic interactions in multi-agent systems. In AAAI-02 Workshop on Game-Theoretic and Decision-Theoretic Agents, 2002.
• 23: M. P. Wellman, J. Estelle, S. Singh, Y. Vorobeychik, C. Kiekintveld, and V. Soni. Strategic interactions in a supply chain game. Computational Intelligence, 21:1--26, 2005.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.11 Distributed Artificial Intelligence

General Terms:
Economics, Experimentation

Keywords:
computational game theory, empirical game modeling, experimentation, meta-strategy analysis, methodology, multi-agent systems, simulation, strategy selection, uncertainty