| Crédit : 4 ECTS |
| Langue du cours : anglais
|
|
|
|
Volume horaire
- CM :
24 h
- Volume horaire global (hors stage) :
24 h
Compétences à acquérir
- Basic of game theory: representation of strategic interactions, solution concepts, important classes of games.
- Long-run performance of learning procedures when several agents are playing against each other
- Familiarity with game dynamics
Description du contenu de l'enseignement
This course focuses on the behavior of learning algorithms when several agents interacts : specifically, what happens when an agent that follows an online learning algorithm interacts with one or several agents doing the same? The natural language to frame such questions is that of game theory. The course will begin with a short introduction to the topic : normal form games (in particular zero-sum, potential, and stable games), solution concepts (elimination of dominated strategies/rationalizability, Nash equilibrium, correlated and coarse correlated equilibrium, evolutionary stable strategies), and some extensions (Blackwell approachability). Subsequently, we will examine the long-term behavior of a variety of online learning algorithms (fictitious play, regret-matching, exponential weights, etc.). Time allowing, we will discuss links with evolutionary game dynamics, as well as applications to generative adversarial networks (GANs), traffic routing, prediction, or online auctions.
Mode de contrôle des connaissances
To be discussed with students
Pré-requis recommandés
A basic acquaintance with game theory is beneficial but the course is accessible to students who never studied game theory.
Bibliographie, lectures recommandées
- Nicolò Cesa-Bianchi and Gábor Lugosi, Prediction, learning, and games, Cambridge University Press, 2006.
- Drew Fudenberg and David K. Levine, The theory of learning in games, Economic learning and social evolution, vol. 2, MIT Press, Cambridge, MA, 1998.
- Sergiu Hart and Andreu Mas-Colell, Simple adaptive strategies: from regret matching to uncoupled dynamics, World Scientific Series in Economic Theory - Volume 4, World Scientific Publishing, 2013.
- Vianney Perchet, Approachability, regret and calibration: implications and equivalences, Journal of Dynamics and Games 1 (2014), no. 2, 181–254.
- Shai Shalev-Shwartz, Online learning and online convex optimization, Foundations and Trends in Machine Learning 4 (2011), no. 2, 107–194.
Enseignant responsable
YANNICK VIOSSAT