Course AGT: Algorithmic Game Theory

Course description:
Algorithmic Game Theory (AGT) is an interdisciplinary research area that lies in the intersection of Theoretical Computer Science, Discrete Mathematics and Economic Theory. The area builds upon game-theoretic foundations to study situations of strategic decision making, with a particular focus on computational and algorithmic aspects. It combines methodologies and techniques from several disciplines such as complexity theory, algorithm design, discrete and continuous optimization, online decision making and learning, auction and mechanism design, etc.
The overall goal of the course is to build up a mathematical toolbox of state-of-the-art models, methodologies and techniques to study the impact of strategic decision making and to develop efficient algorithms for such environments.
The main topics that will be covered in this course are:
- selfish routing games and the price of anarchy
- Braess paradox, Stackelberg routing, network tolls
- best-response dynamics and potential games
- complexity of equilibrium computation
- quantifying the inefficiency of equilibria
- equilibrium hierarchy and no-regret learning
- smoothness and extension theorems
- improving price of anarchy with predictions
- prophet inequalities
- fair division of indivisible goods

Literature:
- Lecture notes covering most of the topics will be provided throughout the course.

Additionally, the following books are excellent sources for additional background reading:
- N. Nisan, T. Roughgarden, E. Tardos, and V. V. Vazirani (Editors), Algorithmic Game Theory, Cambridge University Press, 2007.
- T. Roughgarden, Twenty Lectures on Algorithmic Game Theory, Cambridge University Press, 2016.
- Y. Shoham and K. Leyton-Brown, Multiagent Systems, Cambridge University Press, 2009. Note: The full-text of the book (pdf) is available here.
- A. R. Karlin and Y. Peres, Game Theory, Alive, American Mathematical Society, 2016. Note: The full-text of the book (pdf) is available here.
- We will also make use of some additional online resources (references will be provided throughout the course).

Prerequisites:
- Solid knowledge of complexity theory, mathematical programming, algorithms and optimization.
- Basic knowledge of game theory is advantageous but not required.

Examination:
Take home problems.

Website for the course:
Website AGT

Address of the lecturer:
Dr. P. Kleer
Department of Econometrics and Operations Research, Tilburg School of Economics and Management
Tilburg University, P.O. Box 90153, 5000 LE Tilburg
E-mail: p (dot) s (dot) kleer (at) tilburguniversity (dot) edu

Prof.dr. G. Schäfer
CWI, P.O. Box 94079, 1090 GB Amsterdam
Phone: 020 - 592 4165 E-mail: G.Schaefer@cwi.nl