Core course: Algorithmic game theory
This course will next be offered in the summer term 2021.
This course was offered in the summer term 2020.
Algorithmic game theory is a topic at the intersection of economics and computation. It deals with analyzing the behavior and interactions of strategic agents, who often try to maximize their incentives. The environment in which those agents interact is referred to as a game. We wish to understand if the agents can reach an "equilibrium", or steady state of the game, in which agents have no incentive to deviate from their chosen strategies. The algorithmic part is to design efficient methods to find equilibria in games, and to make recommendations to the agents so that they can quickly reach a state of personal satisfaction.
We will also study mechanism design. In mechanism design, we wish to design markets and auctions and give strategic options to agents, so that they have an incentive to act rationally. We also wish to design the markets and auctions so that they are efficient, in the sense that all goods are cleared and agents do not overpay for the goods which they acquire.
In this course you will learn
- basic equilibrium concepts (Nash equilibria, correlated equilibria, ...)
- strategic actions (best-response dynamics, no-regret dynamics, ...)
- auction design (revenue-maximizing auctions, Vickrey auctions)
- stable matching theory (preference aggregations, kidney exchanges, ...)
- price of anarchy and selfish routing (Braess' paradox, congestion games, ...)
Weekly lectures (online) and weekly exercise session.
- T. Roughgarden: Twenty Lectures on Algorithmic Game Theory, Cambridge University Press, 2016.
- N. Nisan, T. Roughgarden, E. Tardos, V. Vazirani. Algorithmic Game Theory. Cambridge University Press, 2007.