An Approximate Subgame-Perfect Equilibrium Computation Technique for Repeated Games

Andriy Burkov, Brahim Chaib-draaAAAI 2010 · DOI

Abstract

Computing Subgame-Perfect Equilibrium (SPE) strategies in repeated games is a fundamental challenge in multiagent systems. This paper presents the ASPECT algorithm (Approximate Subgame-Perfect Equilibrium Computation Technique), which approximates the set of SPE payoff profiles in discounted repeated games. By iteratively partitioning the payoff space and employing Mixed Integer Programming (MIP), ASPECT identifies sustainable equilibria and automatically constructs them as finite automata for agent implementation.

Introduction

In multiagent environments, selfish agents must often interact over an infinite or indefinite horizon. Game theory provides the framework of repeated games to model these interactions. A Subgame-Perfect Equilibrium (SPE) represents a strategy profile where no player has an incentive to deviate at any point in the game, including all possible future subgames. However, computing these equilibria is computationally intensive due to the non-convex nature of the payoff space and the difficulty of representing strategies with finite memory.

The ASPECT Algorithm

The core contribution is the ASPECT algorithm, which follows a systematic "search and prune" methodology to find SPE payoffs.

1. Hypercube Partitioning

The algorithm begins with a large hypercube encompassing all feasible payoffs. This space is iteratively subdivided into smaller hypercubes, increasing the precision of the approximation as the algorithm progresses.

2. Mixed Integer Programming (MIP) Filter

For each hypercube, a MIP is solved to determine if the payoffs within it can be sustained as an equilibrium. This involves checking if there exists a combination of current actions and future "continuation payoffs" that satisfy the equilibrium conditions. To handle mixed strategies, the MIP uses binary indicator variables to enforce indifference between actions chosen with non-zero probability.

3. Automaton Construction

Unlike previous methods, ASPECT bridges the gap between theory and implementation by representing the equilibrium as a finite automaton. Valid payoff hypercubes serve as states, and transitions are defined by the players' actions and subsequent continuation payoffs, allowing artificial agents to implement complex strategies with finite memory.

Experimental Evaluation

The authors evaluated ASPECT on several classic strategic benchmarks, most notably the Prisoner's Dilemma, which serves as the iconic model for studying cooperation versus defection.

Payoff matrix for the Prisoner's Dilemma, a primary benchmark for the ASPECT algorithm.

The algorithm was also tested on Rock-Paper-Scissors, Battle of the Sexes, and Abreu’s Duopoly model of market competition.

Key Results and Insights

ASPECT demonstrates strong convergence properties. As the number of iterations increases and hypercubes become smaller, the approximation of the SPE payoff set becomes increasingly refined, evolving from a coarse cloud into a sharp representation of sustainable outcomes.

Visualization of the approximated set of SPE payoff profiles after 50 iterations, showing the refined 'cloud' of sustainable equilibria.

Key findings include:

  • Completeness: With the inclusion of public correlation (a shared random signal), the algorithm can approximate the entire set of feasible and individually rational payoffs.
  • Efficiency Trade-offs: There is a clear relationship between precision and computational time. For coordination games like Battle of the Sexes, low-precision runs take seconds, while high-precision runs can take nearly 30 minutes.
  • Theoretical Validation: The algorithm's results for the Duopoly model matched established theoretical thresholds for cooperation, correctly identifying that certain payoffs are only possible when the discount factor $\gamma > 4/7$.

Conclusion and Future Work

ASPECT provides a robust framework for automated equilibrium computation in two-player repeated games. While the current implementation faces the "curse of dimensionality" for three or more players due to non-linearities in the MIP, it marks a significant step toward practical agent strategies. Future research will explore non-convex mixed-integer quadratically constrained programs to scale the algorithm to larger multiagent systems and complex environmental states.

Summary updated

BibTeX
@inproceedings{burkov2010approximate,
  author = {Andriy Burkov and Brahim Chaib-draa},
  title = {{An Approximate Subgame-Perfect Equilibrium Computation Technique for Repeated Games}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2010},
  doi = {10.1609/aaai.v24i1.7623},
}
Figure