Potential Games: Best-Response Dynamics and Equilibria

This lecture introduces potential games, a class of N-player non-zero-sum games where pure Nash equilibria are guaranteed to exist. The instructor begins by reviewing previous concepts, including static games and zero-sum games, before transitioning to potential games. The lecture covers the definition of potential functions, both ordinal and exact, and explains how these functions relate to the best-response dynamics of players. The instructor illustrates the convergence properties of best-response dynamics in potential games, emphasizing that these dynamics lead to pure Nash equilibria. Several examples are provided to demonstrate the application of potential functions in various games, including congestion games. The lecture also discusses the implications of the Braess paradox, where adding resources can lead to worse outcomes in terms of travel time. Finally, the instructor highlights the importance of understanding social welfare optimization and the price of anarchy in the context of potential games, setting the stage for further exploration of mechanism design in future lectures.