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

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.
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License