PR Jordan, Y Vorobeychik, and MP Wellman

Seventh International Joint Conference on Autonomous Agents and Multiagent Systems, pages 1063-1070, May 2008.
Copyright (c) 2008, IFAAMAS.


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.

Includes material previously presented in:

Best-first search for approximate equilibria in empirical games (P. R. Jordan and M. P. Wellman). AAAI-07 Workshop on Trading Agent Design and Analysis, July 2007.