Enchères : apprentissage et approximations

Objectif

Billions of auctions are run everyday, in the amazingly huge online advertisement market. They require a complete knowledge of the different mechanism, how to improve them using past data and how to learn « good/reasonable/optimal » strategies. Matchings are also nowadays already quite important (allocation of students to universities) but will certainly become more and more used on local markets.

During the 8 lectures, we will first introduce the general concept of mechanism design, and especially auctions (1st/2nd price, combinatorial, VCG) and (stable) matchings that are or can be used in practice. The main questions are their approximation, optimisation and learning based on past data in a dynamical setting. We will introduce and study the main classical tools with a specific focus on prophet inequalities and secretary problems, but also quick reminder on statistical theory, multi-armed bandits and online algorithms.

This course will be at the intersection of mathematics (statistics, optimization), computer science (complexity, approximation), and economics (strategies, equilibria and applications). Yet it should not have strong prerequisites. The evaluation will be a written exam.

At the end of this course, students will be able to :

1. Compute optimal strategies and design mechanisms (especially auctions and matchings)
2. Find the sample complexity of approximate mechanism
3. Design and analyse online algorithms
4. Prove and generalise prophet inequalities

Références

KRISHNA, Vijay. Auction theory. Academic press, 2009.

ROUGHGARDEN, Tim. Twenty lectures on algorithmic game theory. Cambridge University Press, 2016.

MEHTA, Aranyak. Online Matching and Ad Allocation. Theoretical Computer Science, 2012, vol. 8, no 4, p. 265-368.

NEDELEC, Thomas, CALAUZENES, Clément, EL KAROUI, Nourreddine, PERCHET, Vianney. Learning in repeated auctions, https://arxiv.org/abs/2011.09365, 2020

NISAN, Noam, ROUGHGARDEN, Tim, TARDOS, Eva, et al. Algorithmic Game Theory.