Courses > PHD Courses
Top image

 
Home
News
Courses
Management Team
Conferences
Dutch OR Groups
People
Links
Contact
 

Landelijk Netwerk Mathematische Besliskunde

Course AGT: Algorithmic Game Theory

 
Time: Monday 11.00 – 12.45 (March 14 - April 11, April 25 - May 23).
Location: All LNMB courses will be taught on-line until further notice. Upon registration for a course, students receive a link for the video connection.
Lecturer: Prof.dr. G. Schäfer (CWI and University of Amsterdam)

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
- selfish load balancing and scheduling
- complexity of equilibrium computation
- quantifying the inefficiency of equilibria
- equilibrium hierarchy and no-regret learning
- smoothness and extension theorems
- markets and fair division

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