Computing Optimal Equilibria and Mechanisms via Learning in Zero-Sum Extensive-Form Games

Speaker: Brian Zhang (CMU)

Abstract: We introduce a unified framework for understanding optimal equilibria in general games by explicitly augmenting the game with a mediator who can communicate with players. By varying restrictions governing the communication, the framework covers a wide family of solution concepts and problems including---but not limited to---communication equilibria, mechanism and information design, and extensive-form correlated equilibria. We will then demonstrate a reduction from computing optimal equilibria in this framework to solving zero-sum games. This reformulation allows us to apply the vast family of techniques for learning in zero-sum games, yielding the first learning algorithms for optimal equilibria in general games. Within this framework, we show that optimal extensive-form correlated equilibria---which are NP-hard to compute---correspond to the zero-sum game having imperfect recall, and that this imperfect recall is precisely the reason for the hardness of computation. We demonstrate the practical scalability and flexibility of our approach by attaining state-of-the-art performance in benchmark tabular games, and by computing an optimal mechanism for a sequential auction design problem using deep reinforcement learning.