Lecture

Beyond equilibrium: A dynamical systems approach to learning in games

Graph Chat

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

Description

This lecture explores the behavior of learning dynamics in zero-sum and congestion games, drawing parallels with conservative systems. It delves into no-regret algorithms, such as Follow the Regularized Leader, and their convergence to Nash equilibria. The instructor discusses the implications of Poincaré recurrence in game dynamics and the concept of limit cycles. Chaos and butterfly effects in Follow-the-Regularized Leader dynamics are also examined, highlighting the interplay between chaos and local stability. The session concludes with insights on the emergence of chaos in online learning dynamics, showcasing the intricate relationship between time-average convergence and chaos.

Official source

Related concepts (32)

Nash equilibrium

In game theory, the Nash equilibrium, named after the mathematician John Nash, is the most common way to define the solution of a non-cooperative game involving two or more players. In a Nash equilibrium, each player is assumed to know the equilibrium strategies of the other players, and no one has anything to gain by changing only one's own strategy. The principle of Nash equilibrium dates back to the time of Cournot, who in 1838 applied it to competing firms choosing outputs.

Zero-sum game

Zero-sum game is a mathematical representation in game theory and economic theory of a situation that involves two sides, where the result is an advantage for one side and an equivalent loss for the other. In other words, player one's gain is equivalent to player two's loss, with the result that the net improvement in benefit of the game is zero. If the total gains of the participants are added up, and the total losses are subtracted, they will sum to zero.

Game theory

Game theory is the study of mathematical models of strategic interactions among rational agents. It has applications in all fields of social science, as well as in logic, systems science and computer science. The concepts of game theory are used extensively in economics as well. The traditional methods of game theory addressed two-person zero-sum games, in which each participant's gains or losses are exactly balanced by the losses and gains of other participants.

Poincaré recurrence theorem

In mathematics and physics, the Poincaré recurrence theorem states that certain dynamical systems will, after a sufficiently long but finite time, return to a state arbitrarily close to (for continuous state systems), or exactly the same as (for discrete state systems), their initial state. The Poincaré recurrence time is the length of time elapsed until the recurrence. This time may vary greatly depending on the exact initial state and required degree of closeness. The result applies to isolated mechanical systems subject to some constraints, e.

Strategy (game theory)

In game theory, a player's strategy is any of the options which they choose in a setting where the outcome depends not only on their own actions but on the actions of others. The discipline mainly concerns the action of a player in a game affecting the behavior or actions of other players. Some examples of "games" include chess, bridge, poker, monopoly, diplomacy or battleship. A player's strategy will determine the action which the player will take at any stage of the game.

Related lectures (33)

Chaos Theory: Logistic Map and Periodic Orbits

Explores Chaos Theory, focusing on the logistic map, periodic orbits, and stability conditions.

Introduction to Game Theory

Covers game theory fundamentals, Nash equilibrium, and strategic interactions in multi-agent systems.

Game Theory: Stackelberg and Backward Induction

Discusses Stackelberg games and backward induction, illustrating game theory concepts through examples and applications in real-world scenarios.

Markov Games: Concepts and Applications in Reinforcement Learning

Covers Markov games, their dynamics, equilibria, and applications in reinforcement learning.

Multistage Games: Extensive Form and Feedback Strategies