Exploiting Extensive-Form Structure in Empirical Game-Theoretic Analysis

Autor: Konicki, Christine, Chakraborty, Mithun, Wellman, Michael P.
Rok vydání: 2023
Předmět:
Zdroj: Web and Internet Economics: 18th International Conference (WINE 2022), Proceedings. 132--149
Druh dokumentu: Working Paper
Popis: 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 \textit{extensive-form games} (EFGs) provide a means to capture temporal patterns in action and information, using tree representations. We propose \textit{tree-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.
Comment: This paper has been slightly revised from the original version published at WINE 2022; to wit, the proof included in the appendices of our key theoretical result has been expanded
Databáze: arXiv
Externí odkaz: