Exploiting Tree Structure in Empirical Game-Theoretic Analysis for Extensive-Form Games

Abstract

Many real-world multiplayer scenarios are too large or complex to be described and analyzed with game theory. Empirical Game-Theoretic Analysis (EGTA) reasons about complex game scenarios by organizing data accumulated from gameplay simulation into an empirical game model and then computing a solution from the model using game-theoretic algorithms. In most uses to date, EGTA has represented the game model in normal form, which excludes the conditional information and nuanced sequential decision-making that define player strategies within the underlying game. Intuitively, a game model in extensive form presents an opportunity to exploit the benefits of this tree structure in service of EGTA.

I develop new methods to improve EGTA by incorporating extensive-form models based on the sequential structure of the underlying game. I introduce a general framework called Tree-Exploiting EGTA (TE-EGTA), which constructs an empirical game model that expresses observations and organizes gameplay actions sequentially in time. I demonstrate that incorporating even a little tree structure vastly reduces estimation error in strategy-profile payoffs compared to the normal-form model. Then, I address the problem of expanding the strategy space of an extensive-form model with new best responses. I demonstrate how to exploit tree structure for iterative model refinement. This allows strategy exploration to occur on a finer-grained level across old and new paths through the empirical game tree as the model grows. Then, I introduce a more general approach that uses an empirical game tree whose edges correspond to implicit policies learned through deep reinforcement learning. The approach also selectively incorporates best responses at certain information sets so the tree can grow scalably over time.

I also leverage the extensive-form model to employ refined Nash equilibria (NE) in EGTA, specifically subgame perfect equilibrium (SPE) and perfect Bayesian equilibrium (PBE). I give an algorithm for computing each solution from a game and prove its correctness and runtime theoretically and empirically. Then, I compared them as targets for learning best responses during strategy exploration and found that refined NE steered the empirical model toward a solution yielding smaller regret than when NE was used as the target. Additionally, my results showed that SPE was best suited to games with minimal imperfect information at the start while PBE was best suited to games with large swaths of imperfect information distributed throughout.