Methods for Empirical Game-Theoretic Analysis

Michael P. WellmanAAAI 2006 · OpenReview

Abstract

An emerging empirical methodology bridges the gap between game theory and simulation for practical strategic reasoning. By using simulators to generate payoff data for a restricted set of strategies, researchers can find approximate Nash equilibria in environments that are far too complex for traditional analytical methods.

Introduction

Traditional game theory requires an explicit mathematical model—usually a payoff matrix or a function—to find a Nash equilibrium, a state where no player can benefit by changing their strategy. However, many real-world scenarios, such as supply chain management or high-frequency auctions, function as "black boxes." These games suffer from vast strategy spaces, incomplete information, and stochasticity, making them analytically intractable. Empirical Game-Theoretic Analysis (EGTA) addresses this by observing how specific strategies interact within a simulator to build an empirical model of the game.

Methodology

The EGTA framework transforms a complex simulator into a solvable empirical game through a three-step process:

  1. Parametrize Strategy Space: Since testing every possible strategy is impossible, researchers select a representative subset. These may include baseline strategies like truthful bidding or variations of game-tree search parameters.
  2. Estimate the Empirical Game: Strategy profiles (combinations of player strategies) are simulated to estimate expected payoffs. Techniques include Monte Carlo sampling with variance reduction, hierarchical game reduction (grouping players to reduce combinations), and regression models to predict payoffs for unsimulated profiles.
  3. Analyze the Empirical Game: Standard game-theoretic tools are applied to the resulting payoff table. The methodology emphasizes the $\epsilon$-Nash equilibrium, which measures "regret"—the maximum gain an agent could achieve by deviating from a strategy. This provides a gradient of stability rather than a binary equilibrium state.

Case Study: Trading Agent Competition (TAC/SCM)

The primary application for this methodology is the Trading Agent Competition Supply Chain Management (TAC/SCM) game, a six-player symmetric game of imperfect information. In this environment, a single simulation data point can take an hour to compute. By applying hierarchical reduction, researchers can approximate the 6-player game with significant computational savings.

Empirical game analysis of strategy profiles in the TAC/SCM competition, showing significant and insignificant deviations between strategy combinations across different regret levels.

Analysis of the 2005 TAC/SCM tournament revealed that while no pure Nash equilibrium existed, certain profiles were significantly more stable than others. For instance, the "Mertacor" (Mr) strategy was a dominant force; in 30 out of 35 profiles where Mertacor was absent, the "best deviation" for a player was to switch to it. The EGTA methodology also successfully verified that "Deep Maize" (Dm) served as an effective counter-measure to aggressive early procurement tactics seen in earlier competitions.

Key Insights and Future Directions

The core shift in EGTA is treating the simulator as the "ground truth" rather than a mathematical formula. Even as a stylized abstraction, the empirical game provides actionable insights into intractable systems. By focusing on stability (via $\epsilon$ measures) rather than perfect optimality, researchers can identify robust strategies in noisy environments.

Despite its successes, EGTA faces challenges in computational cost and the manual effort required to select candidate strategies. Future work aims to incorporate "active learning" to decide which strategy profiles are most valuable to simulate and to automate the discovery of parametric strategy variations, reducing the reliance on domain expertise.

Summary updated

Abstract

An emerging empirical methodology bridges the gap between game theory and simulation for practical strategic reasoning.
BibTeX
@inproceedings{wellman2006methods,
  author = {Michael P. Wellman},
  title = {{Methods for Empirical Game-Theoretic Analysis}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2006},
  url = {https://openreview.net/forum?id=HJWh0Ae_ZS},
}
Figure