Equilibrium Approximation in Simulation-Based Extensive-Form Games

The class of simulation-based games, in which the payoffs are generated as an output of a simulation process, recently received a lot of attention in literature. In this paper, we extend such class to games in extensive form with continuous actions and perfect information. We design two convergent algorithms to find an approximate subgame perfect equilibrium (SPE) and an approximate Nash equilibrium (NE) respectively. Our algorithms can exploit different optimization techniques. In particular, we use: simulated annealing, cross entropy method, and Lipschitz optimization. We produce an extensive experimental evaluation of the performance of our algorithms in terms of approximation degree of the optimal solution and number of evaluated samples. Finding approximate NE and SPE requires exponential time in the game tree depth: an SPE can be computed in game trees with a small depth, while the computation of an NE is easier.

Authors

• Nicola Gatti Politecnico di Milano
• Marcello Restelli Politecnico di Milano

Keywords

• Game Theory (cooperative and non-cooperative)