Small Nash Equilibrium Certificates in Very Large Games

Brian Hu Zhang, Tuomas Sandholm

Introduction

In the field of game theory, the Nash Equilibrium (NE) represents a stable state where no player can improve their outcome by unilaterally changing their strategy. A critical challenge in applying NE to real-world scenarios is the calculation of "exploitability"—a measure of how much a perfect opponent could gain if they knew a player's strategy. Traditionally, determining exploitability requires a complete traversal of the game tree. For massive games like No-Limit Texas Hold'em or complex simulations in finance and defense, the game tree is often too large to store or compute.

While Modern Deep Reinforcement Learning (DRL) has produced superhuman performance in such games, these models often lack formal safety guarantees. This paper addresses this gap by introducing "certificates"—truncated versions of a game tree that provide formal exploitability guarantees without requiring full exploration.

Methodology: Trunks and Certificates

The authors propose a framework that bridges the gap between black-box play and formal verification through three primary components:

  1. Pseudogames and Trunks: Instead of analyzing the entire game tree, the approach focuses on a "trunk"—a subset of the tree starting from the root. For unexplored branches, the framework assigns lower ($\alpha$) and upper ($\beta$) bounds on potential utility, creating a "pseudogame."
  2. $\epsilon$-Certificates: A certificate consists of a trunk and a corresponding strategy. It serves as a formal proof that the strategy is an $\epsilon$-Nash Equilibrium within the full game, meaning it is at most $\epsilon$ away from being unexploitable.
  3. Iterative Solving Algorithm: To construct these certificates, the authors developed an iterative process described in Algorithm 6.7.
Algorithm 6.7: Finding a certificate in a two-player zero-sum game.

The algorithm functions by solving the current trunk using a Linear Programming (LP) solver to find an "optimistic" strategy. It then identifies "pseudoterminal" nodes—the boundaries of the current trunk—that the optimistic strategy utilizes. These specific nodes are expanded by querying a game "oracle," and the process repeats until the gap between optimistic and pessimistic values is sufficiently small.

Handling Infinite Rewards

A significant contribution of this work is the ability to handle games with potentially infinite rewards or lengths. In games like certain poker variants where players can raise indefinitely, standard solvers fail. The authors introduce a correction mechanism, Algorithm 6.9, to adjust strategies in these edge cases.

Algorithm 6.9: Correcting a strategy in the case of infinite reward.

This allows the algorithm to find finite 0-certificates even in infinite-size variants, effectively proving that after a certain point, further actions (like additional raises) are suboptimal and can be safely "clipped."

Key Insights and Theoretical Results

The research yields several important insights into the nature of game certificates:

  • Efficiency of Verification: Verifying a certificate is computationally cheap, with time complexity linear to the size of the certificate rather than the full game.
  • The Role of Sparsity: The existence of small certificates is tied to "sparse equilibria," where optimal play only involves a small subset of all possible move sequences.
  • Lower Bounds on Certificate Size: The authors prove that not all games permit small certificates. In games characterized by significant information asymmetry, such as multi-round "matching pennies," a certificate may need to be nearly as large as the full game tree.

Experimental Results

The approach was evaluated on several zero-sum benchmark games, demonstrating that certificates are often orders of magnitude smaller than the full game:

  • Goofspiel (6-rank PI): In a game with over 2 million nodes, the algorithm identified an exact Nash Equilibrium certificate using only 21,948 nodes (~1.1%).
  • Search Games: Certificates were found using only 5.8% of the total game nodes.
  • Leduc Poker: In an infinite-length variant, the algorithm successfully generated finite 0-certificates. For the 13-rank version, the certificate occupied only 9.4% of the restricted trunk used for comparison.

Conclusion and Future Directions

This work provides a robust method for verifying strategies in massive games. However, limitations remain. Finding the absolute smallest certificate is NP-hard, and the current algorithm may not always find the most efficient proof. Additionally, the reliance on an "oracle" for exact bounds becomes more complex in games with stochastic elements (nature nodes). Future research will explore extending these techniques to multi-player and general-sum games, where finding equilibria is inherently more difficult.

Summary updated

BibTeX
@inproceedings{zhang2020small,
  author = {Brian Hu Zhang and Tuomas Sandholm},
  title = {{Small Nash Equilibrium Certificates in Very Large Games}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2020},
  url = {https://openreview.net/forum?id=pf7mCxPkOG},
}
Figure