Exploiting extensive-form structure in empirical game-theoretic analysis
From MaRDI portal
Abstract: 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 extit{extensive-form games} (EFGs) provide a means to capture temporal patterns in action and information, using tree representations. We propose extit{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.
Recommendations
- Automated construction of bounded-loss imperfect-recall abstractions in extensive-form games
- Empirical game theoretic models: Computational issues
- Solving for Best Responses and Equilibria in Extensive-Form Games with Reinforcement Learning Methods
- Action-graph games
- Learning to play games in extensive form by valuation
Cites work
This page was built for publication: Exploiting extensive-form structure in empirical game-theoretic analysis
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6167242)
