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: Hans Freudenthalgebouw, Room 611AB, Budapestlaan, Utrecht (De Uithof).
Lecturer: Prof.dr. G. Schäfer (CWI and VU University Amsterdam)

Course description:
Algorithmic game theory is a rather new and rapidly growing research area that lies at the intersection of mathematics, theoretical computer science and economics. It uses game-theoretical models and solution concepts to study situations of strategic decision making, with a particular focus on computational and algorithmic issues. It combines methodologies and techniques from areas like discrete optimization, algorithms, computational complexity, game theory, mechanism design, etc.
The overall goal of the course is to both learn about fundamental results of the field and to get acquainted with recent state-of-the-art techniques.
Potential topics that will be covered in the course are:
- computation of equilibria (potential function, PPAD-completeness)
- inefficiency of equilibria (price of stability, price of anarchy)
- selfish routing games (non-atomic, atomic, price of anarchy)
- congestion games (potential games, PLS-completeness)
- smoothness of games (robust price of anarchy, learning)
- reducing the inefficiency (network tolls, Stackelberg routing)
- combinatorial auctions (first-price, second-price, VCG mechanism)
- approximation and mechanism design (single-minded bidders)
- ad auctions and the generalized second-price auction
- revenue maximization and the Bayesian setting

Literature:
- Lecture notes will be provided in class.
- Most topics that will be covered in the course can be found in the following book:
N. Nisan, T. Roughgarden, E. Tardos, and V. V. Vazirani (Editors), Algorithmic Game Theory, Cambridge University Press, 2007.
Note: The full-text of the book is available online here (username=agt1user, password=camb2agt).

Prerequisites:
- Basic knowledge of algorithms, optimization and computational complexity.
- Some knowledge of game theory is advantageous.

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