Home
Algorithmic Game Theory – 0368-4483
Location and hours
Fall 2013 — Monday 2-5 — Shenkar 222
Instructor: Michal Feldman
Assistant: Shai Vardi
Course Text
The course will be based on selected parts of the book Algorithmic Game Theory, Cambridge University Press 2007 (online version), and selected parts of the book (draft) Approximation in Economic Design (online version)..
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: you may work with others (groups up to 3 students), but you need to write and hand in your own solution by yourself and explicitly mention whom you worked with.
- Final project (survey or research project) – up to 10 pages.