PGMO Course 2021
- February 3rd and 10th, 2021 "DYNAMICS IN GAMES: ALGORITHMS AND LEARNING"
Sylvain Sorin
Game theory studies interactions between agents with specific aims, be they rational actors, genes, or computers. This course is intended to provide the main mathematical concepts and tools used in game theory with a particular focus on their connections to learning and convex optimization. The first part of the course deals with the basic notions: value, (Nash and Wardrop) equilibria, correlated equilibria. We will give several dynamic proofs of the minmax theorem and describe the link with Blackwell’s approachability. We will also study the connection with variational inequalities.
The second part will introduce no-regret properties in on-line learning and exhibit a family of unilateral procedures satisfying this property. When applied in a game framework we will study the consequences in terms of convergence (value, correlated equilibria). We will also compare discrete and continuous time approaches and their analog in convex optimization (projected gradient, mirror descent, dual averaging). Finally we will present the main tools of stochastic approximation that allows to deal with random trajectories generated by the players.