Evolution Strategies for Approximate Solution of Bayesian Games

Authors

  • Zun Li University of Michigan, Ann Arbor
  • Michael P. Wellman University of Michigan, Ann Arbor

Keywords:

Equilibrium, Auctions and Market-Based Systems, Game Theory, Evolutionary Computation

Abstract

We 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.

Downloads

Published

2021-05-18

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. Retrieved from https://ojs.aaai.org/index.php/AAAI/article/view/16696

Issue

Section

AAAI Technical Track on Game Theory and Economic Paradigms