February 09, 2018, Webb 1100

Multi-agent systems are naturally modeled using the framework of game theory. Desirable operating conditions of a multi-agent system can be modeled as an equilibrium of an associated game, and game-theoretic learning algorithms are growing increasingly popular as decentralized mechanisms for controlling multi-agent systems. A central idea in game theory is the notion of a best response--the Nash equilibrium is defined as a fixed point of the best-response map and many game-theoretic learning algorithms rely (often implicitly) on players adapting towards best-response strategies. In this talk we study the continuous best-response (BR) dynamics which underlie such learning algorithms. Despite their fundamental role in game theory, many properties of BR dynamics are not well understood due to the discontinuous set-valued nature of the best-response map. For example, we have only a limited understanding of the rate of convergence of BR dynamics in the important class of multi-agent games known as potential games--it has been speculated (and is generally believed to be true) that BR dynamics converge at an exponential rate in potential games, but a rigorous understanding of this issue has been lacking. In the talk, it is shown that the rate of convergence of continuous BR dynamics is in fact exponential. In order to show this result, two important properties regarding both BR dynamics and potential games are developed. First, it is shown that almost every potential game is regular. Regular games possess “well behaved” equilibria and play a key role in the foundations of classical equilibrium theory. Second, it is shown that, generically (from almost every initial condition and in almost every potential game), continuous BR dynamics converge to pure-strategy equilibria in potential games. Together these results elucidate many important properties of BR dynamics in potential games and allow for a simple characterization of the rate of convergence. Applications extend beyond game theory to include optimization and fast evasion of saddle points in non-convex problems.

Brian is a postdoc at Carnegie Mellon University in the department of electrical and computer engineering. He received his Ph.D. in electrical and computer engineering from Carnegie Mellon, an M.S. in mathematics from Carnegie Mellon, and a B.S. in electrical engineering from Brigham Young University.