Evolution Strategies for Approximate Solution of Bayesian Games
Keywords:Equilibrium, Auctions and Market-Based Systems, Game Theory, Evolutionary Computation
AbstractWe address the problem of solving complex Bayesian games, characterized by high-dimensional type and action spaces, many (> 2) players, and general-sum payoffs. Our approach applies to symmetric one-shot Bayesian games, with no given analytic structure. We represent agent strategies in parametric form as neural networks, and apply natural evolution strategies (NES) [wierstra2014natural] for deep model optimization. For pure equilibrium computation, we formulate the problem as bi-level optimization, and employ NES in an iterative algorithm to implement both inner-loop best response optimization and outer-loop regret minimization. In simple games including first- and second-price auctions, it is capable of recovering known analytic solutions. For mixed equilibrium computation, we adopt an incremental strategy generation framework, with NES as strategy generator producing a finite sequence of approximate best-response strategies. We then calculate equilibria over this finite strategy set via a model-based optimization process. Both our pure and mixed equilibrium computation methods employ NES to efficiently search for strategies over the functional space, given only black-box simulation access to noisy payoff samples. We experimentally demonstrate the efficacy of all methods on two simultaneous sealed-bid auction games with distinct type distributions, and observe that the solutions exhibit qualitatively different behavior in these two environments.
How to Cite
Li, Z., & Wellman, M. P. (2021). Evolution Strategies for Approximate Solution of Bayesian Games. Proceedings of the AAAI Conference on Artificial Intelligence, 35(6), 5531-5540. https://doi.org/10.1609/aaai.v35i6.16696
AAAI Technical Track on Game Theory and Economic Paradigms