Lecture: Equilibria, Fixed Points, and Computational Complexity: from von Neumann to Generative Adversarial Networks
The concept of equilibrium, in its various forms, has played a central role in the development of Game Theory and Economics. The mathematical properties and computational complexity of equilibria are also intimately related to mathematical programming, online learning, and fixed point theory. More recently, equilibrium computation has been proposed as a means to learn generative models of high-dimensional distributions. In this talk, we review fundamental results on minimax equilibrium and its relationship to mathematical programming and online learning. We then turn to Nash equilibrium, reviewing some of our work on its computational intractability. We conclude with modern applications of equilibrium computation, presenting recent progress and open problems in the training of Generative Adversarial Networks.