Searching for approximate equilibria in empirical games

ABSTRACT

When exploring a game over a large strategy space, it may not be feasible or cost-effective to evaluate the payoff of every relevant strategy profile. For example, determining a profile payoff for a procedurally defined game may require Monte Carlo simulation or other costly computation. Analyzing such games poses a search problem, with the goal of identifying equilibrium profiles by evaluating payoffs of candidate solutions and potential deviations from those candidates. We propose two algorithms, applicable to distinct models of the search process. In the revealed-payoff model, each search step determines the exact payoff for a designated pure-strategy profile. In the noisy-payoff model, a step draws a stochastic sample corresponding to such a payoff. We compare our algorithms to previous proposals from the literature for these two models, and demonstrate performance advantages.

REFERENCES

• 1: R. Arunachalam and N. M. Sadeh. The supply chain trading agent competition. Electronic Commerce Research and Applications, 4:63--81, 2005.
• 2: Joakim Eriksson , Niclas Finne , Sverker Janson, Evolution of a supply chain management game for the trading agent competition, AI Communications, v.19 n.1, p.1-12, January 2006
• 3: Amy R. Greenwald , Jeffrey O. Kephart, Shopbots and Pricebots, Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence, p.506-511, July 31-August 06, 1999
• 4: Patrick R. Jordan , Christopher Kiekintveld , Michael P. Wellman, Empirical game-theoretic analysis of the TAC Supply Chain game, Proceedings of the 6th international joint conference on Autonomous agents and multiagent systems, May 14-18, 2007, Honolulu, Hawaii [doi>10.1145/1329125.1329359]
• 5: P. R. Jordan and M. P. Wellman. Best-first search for approximate equilibria in empirical games. AAAI-07 Workshop on Trading Agent Design and Analysis (TADA), July 2007.
• 6: S. Kullback and R. Leibler. On information and sufficiency. Annals of Mathematical Statistics, 22:79--86, 1951.
• 7: D. Monderer and L. S. Shapley. Potential games. Games and Economic Behavior, 14:124--143, 1996.
• 8: 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]
• 9: 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
• 10: Daniel M. Reeves , Michael P. Wellman , Jeffrey K. MacKie-Mason , Anna Osepayshvili, Exploring bidding strategies for market-based scheduling, Decision Support Systems, v.39 n.1, p.67-85, March 2005 [doi>10.1016/j.dss.2004.08.014]
• 11: R. Rosenthal. A class of games possessing pure-strategy Nash equilibria. International Journal of Game Theory, 2:65--67, 1973.
• 12: S. M. Ross. Simulation. Academic Press, 3rd edition, 2001.
• 13: Stuart Russell, Principles of metareasoning, Artificial Intelligence, v.49 n.1-3, p.361-395, May 1991 [doi>10.1016/0004-3702(91)90015-C]
• 14: Ashish Sureka , Peter R. Wurman, Using tabu best-response search to find pure strategy nash equilibria in normal form games, Proceedings of the fourth international joint conference on Autonomous agents and multiagent systems, July 25-29, 2005, The Netherlands [doi>10.1145/1082473.1082628]
• 15: 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]
• 16: Y. Vorobeychik and M. P. Wellman. Mechanism design based on beliefs about responsive play (position paper). In ACM EC-06 Workshop on Alternative Solution Concepts for Mechanism Design, Ann Arbor, 2006.
• 17: W. Walsh, D. Parkes, and R. Das. Choosing samples to compute heuristic-strategy Nash equilibrium. In Fifth Workshop on Agent-Mediated Electronic Commerce, 2003.
• 18: M. P. Wellman. Methods for empirical game-theoretic analysis (extended ). In Twenty-First National Conference on Artificial Intelligence, pages 1152--1155, Boston, 2006.
• 19: M. P. Wellman, D. M. Reeves, K. M. Lochner, S.-F. Cheng, and R. Suri. Approximate strategic reasoning through hierarchical reduction of large symmetric games. In Twentieth National Conference on Artificial Intelligence, pages 502--508, Pittsburgh, 2005.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search

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

General Terms:
Economics, Experimentation

Keywords:
approximate equilibria, empirical game, heuristic search