Abstraction Using Analysis of Subgames

Anjon BasakAAAI 2016 · DOI

Introduction

Solving massive games, such as Poker or complex strategic simulations, presents a significant computational challenge. In game theory, a Normal Form Game (NFG) maps strategies and payoffs for multiple players. Finding a Nash Equilibrium—the state where no player can improve their outcome by unilaterally changing their strategy—is often computationally infeasible for large-scale games.

To address this, researchers employ abstraction, grouping similar strategies into clusters to create a smaller, manageable version of the game. However, traditional abstraction often overlooks the "noise" or subtle differences within these clusters. This leads to an "abstraction error," where the solution derived for the simplified game performs poorly when applied back to the original, un-abstracted environment.

The ISASC Framework and MEB Solution Concept

This paper introduces two primary innovations to bridge the gap between abstract models and original games: ISASC and MEB.

ISASC (Iterative Subgame Abstraction and Solution Concept)

ISASC is designed for games with an AIOS (Approximately Identical Outside Subgames) structure. Unlike traditional methods that solve a subgame once, ISASC is an iterative process. It calculates an "error offset"—the difference between a strategy's actual payoff and the cluster average—and feeds this error back into subsequent solving rounds. This iterative refinement allows the system to "learn" and compensate for the details lost during the initial clustering phase.

MEB (Minimum Epsilon Bounded Equilibrium)

Standard abstraction techniques often rely on the Pure Strategy Nash Equilibrium (PSNE), which evaluates the average payoff of a cluster. The author argues this is fundamentally flawed because players in the real game execute specific actions, not averages. MEB instead considers the maximum possible payoff a player could achieve by deviating to any specific action in the original game. This provides a more robust and honest estimate of equilibrium stability.

Experimental Results

The effectiveness of these methods was evaluated using synthetic test games based on the AIOS model, varying the level of "noise" ($δ$), which represents the maximum payoff difference within a cluster.

Convergence and Stability

A key finding is the convergence behavior of the ISASC method. As shown in Figure 1, the approximation error ($ε$)—the distance from a true Nash Equilibrium—decreases significantly as iterations progress. This trend holds across various noise levels, demonstrating that iteration effectively acts as a "de-noiser" for imperfect abstractions.

Convergence of epsilon over iterations in ISASC for various noise levels (delta).

Comparative Performance

When compared against standard baselines like k-means clustering combined with PSNE or Quantal Response Equilibrium (QRE), the ISASC and MEB approaches consistently yielded higher-quality solutions.

Comparison of solution quality (epsilon) across different solution concepts and noise levels.

As illustrated in Figure 2, ISASC maintains a lower epsilon value across different delta values compared to traditional solution concepts. Notably, MEB generally outperforms PSNE and QRE regardless of the abstraction method used, confirming that accounting for maximum deviations rather than averages leads to more stable solutions in the original game space.

Conclusion and Future Work

The research demonstrates that perfect abstraction is not a prerequisite for high-quality game solutions. Through iterative refinement (ISASC) and robust solution concepts (MEB), it is possible to compensate for the information lost during simplification.

Future research will focus on extending these methods beyond the AIOS structure to more varied, less structured scenarios. Additionally, the author aims to adapt MEB for mixed strategies, where players randomize their moves, and to further analyze the computational trade-offs involved in iterative subgame solving.

Summary updated

BibTeX
@inproceedings{basak2016abstraction,
  author = {Anjon Basak},
  title = {{Abstraction Using Analysis of Subgames}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2016},
  doi = {10.1609/aaai.v30i1.9956},
}
Figure