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