Home
Algorithmic Game Theory (Spring 2017) – 0368-4483
Location and hours
Wednesday 14:10-17:00 — Dan David 203
Instructor: Michal Feldman
Assistant: Kineret Segal
Course Material
- Selected parts of the book Algorithmic Game Theory, Cambridge University Press 2007 (online version),
- Selected parts of the book (draft) Approximation in Economic Design (online version)
- Some of the classes are based on Tim Roughgarden's course, which can be found here.
Syllabus (tentative)
- Introduction: games, mechanism design, inefficiency of equilibrium and equilibrium computation
- Nash equilibrium and Nash’s theorem
- Zero-sum games: normal form and extensive form, minmax theorem, Yao’s principle
- Congestion games and potential games, pure NE existence and computation, best-response dynamics
- Inefficiency of equilibria: price of anarchy, price of stability, smoothness framework (extension to correlated equilibrium and regret minimization)
- Mechanism design basics: single-item auctions, Myerson’s lemma
- Algorithmic mechanism design: Multi-unit auctions: computation and communication
- VCG mechanisms
- Market models, equilibium, Welfare theorems, computational aspects
Course Requirements
- Scribe notes (latex template, latex tutorial)
- Problem sets: 3-4 problem sets will be given during the semeter. You should submit them in pairs.
- Final project (survey or research project) – up to 10 pages.