# Exploiting Extensive-Form Structure in Empirical Game-Theoretic Analysis

arXiv: https://arxiv.org/abs/2302.01366 · HTML: https://mlsanity.com/paper/2302.01366/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 2 Feb 2023.

## Built on by (most cited first, 2 of 2)

- [Policy Space Response Oracles: A Survey](https://mlsanity.com/paper/2403.02227/) (2024)
- [Co-Learning Empirical Games and World Models](https://mlsanity.com/paper/2305.14223/) (2023)

## Abstract (arXiv)

Empirical game-theoretic analysis (EGTA) is a general framework for reasoning about complex games using agent-based simulation. Data from simulating select strategy profiles is employed to estimate a cogent and tractable game model approximating the underlying game. To date, EGTA methodology has focused on game models in normal form; though the simulations play out in sequential observations and decisions over time, the game model abstracts away this temporal structure. Richer models of textitextensive-form games (EFGs) provide a means to capture temporal patterns in action and information, using tree representations. We propose textittree-exploiting EGTA (TE-EGTA), an approach to incorporate EFG models into EGTA@. TE-EGTA constructs game models that express observations and temporal organization of activity, albeit at a coarser grain than the underlying agent-based simulation model. The idea is to exploit key structure while maintaining tractability. We establish theoretically and experimentally that exploiting even a little temporal structure can vastly reduce estimation error in strategy-profile payoffs compared to the normal-form model. Further, we explore the implications of EFG models for iterative approaches to EGTA, where strategy spaces are extended incrementally. Our experiments on several game instances demonstrate that TE-EGTA can also improve performance in the iterative setting, as measured by the quality of equilibrium approximation as the strategy spaces are expanded.