Mini-course

Due to covid crisis, the French conference SMAI-MODE postponed to September 7-9, 2020, and the mini-course postponed to September 10-11, 2020, will hold fully online. 
Registration is free of charge but mandatory in order to receive the connexion details to the video-conference platform.
Registration will remain open until September 9th, 2020 (via PGMO website)

Mini-courses

As in previous editions of SMAI-MODE conferences, in partnership with the GdR MOA (Mathematics of Optimization and Applications), we propose a course on the 2 days preceding the conference, on March 23 and 24, to be held at ENSTA (Palaiseau).
This year the course will also be supported by the program PGMO and the Master “Optimization” of Paris-Saclay University.

The theme of the course is “Algorithmic game theory: from multi-agent optimization to online learning”.

The lectures (9 hours in total) will be given by Panayotis Mertikopoulos (CNRS-LIG & Inria) and Roberto Cominetti (Universidad Adolfo Ibáñez, Chile). More precisely, the lectures will take place at the following time slots:

• Thursday, September 10th, 11h00-12h30 (Download: Introduction, Lecture 1)
• Thursday, September 10th, 13h30-15h00 (Download: Lecture 2)
• Thursday, September 10th, 15h30-17h00 (Download: Lecture 3)
• Friday,  September 11th, 11h00-12h30  (Download: Lecture 4)
• Friday,  September 11th, 13h30-15h00  (Download: Lecture 5)
• Friday,  September 11th, 15h30-17h00 (Download: Lecture 6)

The lectures will take place online on zoom platform. Registration is required in order to get the connexion details to the video-conference platform.

Abstract

Game theory is a thriving interdisciplinary field that studies the interactions between optimizing agents with competing objectives, be they humans, bacteria, or artificial neural networks. This course is intended to provide a gentle introduction to algorithmic game theory with a particular focus on its connections to learning and optimization, as well as some of its core applications (traffic routing, machine learning, auctions, etc.).

The first part of the course deals with the static elements that define a game, the different equilibrium notions that arise in game theory (Nash, Bayesian, Poisson, Wardrop equilibria,…), and the connections between them. Special attention will be put to analyze the classes of congestion games and routing games – both atomic and non-atomic – alongside with the more general class of potential games. We will describe the asymptotic behavior of large games with an increasing number of players, and we will discuss the social efficiency of equilibria by reviewing some basic bounds for the so-called price of anarchy (PoA) as a measure of the gap between global optimality and equilibrium.

The second part of the course will focus on online learning procedures that aim to maximize the rewards accrued by an individual agent over time. We will cover some classical procedures (such as the best-response dynamics, fictitious play and their variants), and then focus on online optimization algorithms that aim to minimize an agent’s regret (exponential weights, follow-the-regularized-leader, online gradient/mirror descent, etc.). Subsequently, we will examine the ramifications of no-regret learning in games, and we will study under which conditions online learning can lead to Nash equilibrium. We will also discuss the impact of the information available to the players, as well as a range of concrete applications to traffic routing, signal processing, and machine learning.

Important information:

• Registration to the course is free of charge but mandatory and should be done preferably before September 4th.
• Thanks to the support of  PGMO program and GdR MOA, the course is open to all attendees to the SMAI-MODE conference (no additional cost), just check the box dedicated for this purpose on the registration form for SMAI-MODE days. For those not registered to the SMAI-MODE conference, registration to the course is open via PGMO website.

• Old: Some funding is available to cover partially the registration and accommodation expenses (from March 23 to March 27, 2020). This funding is aimed to mainly support PhD students (young researchers and Postdocs may also apply).  To apply for a financial support, a request should be sent to smai-mode2020@inria.fr, before February 1st.  The application should include a CV, contact information of a referent (to whom a recommendation may be requested), and specify the amount requested (the supporting documents must be produced for reimbursement). Acceptance decisions will be sent by February 10th.

For any question on the mini-course, contact us at the address: smai-mode2020@inria.fr