Best-First Search for Approximate Equilibria in Empirical Games

Patrick Jordan, Michael P. Wellman

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, evaluating each payoff of an empirically defined game may require Monte Carlo simulation or other costly computation. Analyzing such games poses a search problem, with the goal of identifying and confirming pure-strategy equilibrium profiles by evaluating payoffs of candidates and potential deviations from those can didates. Sureka and Wurman studied this problem and proposed a search method based on best-response dynamics. We introduce a family of best-first algorithms, which prioritize unconfirmed profiles by their known bound away from equilibrium and select the profile with the current minimum. We compare algorithms by measuring the fraction of profile space explored to confirm equilibria, as well as the search effort required to confirm approximate equilibria, on several game classes. Our best-first approach compares similarly to the existing best-response algorithms when searching for exact equilibria, and favorably when searching for approximate equilibria.

Subjects: 7.1 Multi-Agent Systems; 15.7 Search

Submitted: May 15, 2007

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.