Computational Game Theory 2008

Amos Fiat (fiat@tau.ac.il)
2nd Semester, 2007/2008 - Wednesday 1500-1800
School of Computer Science,
Tel-Aviv University

• Slides 1: Intro
• Slides 2: Nash
• Slides 3: Potential Games, Congestion Games, Routing Games
• Slides 4: Potential and Congestion, Loacal Search, PPAD, PLS, complexity of Nash Equilibria
• Slides 5: Machine and network congestion games
• No slides: Discussed Convergence to Approximate Nash Equilibria in Congestion Games by Steve Chien and Alistair Sinclair, Whiteboard talk in class.
  Also, read Fast Convergence to Nearly Optimal Solutions in Potential Games by Awerbuch et. al.
• Mechanism Design: inverse game theory. Arrows Theorem, Gibbert Satterthwaite, VCG mechanisms

Excellent classes on similar subjects(unfortunately given elsewhere or the lecturer is missing/abroad/etc.):

Paul W. Goldberg, Liverpool: Introduction to PPAD

Adam Tauman Kalai 2008: Game Theory and Computer Science (Class at Georgia Tech)

Yishay Mansour 2004: Computational Game Theory (Class at TAU)

Yishay Mansour 2006: Computational Game Theory (Class at TAU)

Tim Roughgarden and Jason Hartline 2005: Topics in Algorithmic Game Theory (Class at Stanford)

New: Survey of Algorithmic Game Theory, Tim Roughgarden, Stanford.

Vincent Conitzer 2006: Computational Game Theory and Mechanism Design (Class at Duke)

Michael Kearns, 2003 (Class at Penn)

Eva Tardos, 2004: Algorithmic Game Theory (Class at Cornell)

Joan Feigenbaum, 2006: Economics and Computation (Class at Yale)

David C. Parkes, 2007: Computational Mechanism Design (Class at Harvard)

Noam Nisan, 2007: Foundations of Electronic Commerce (Class at HU)

• The class will cover all or part of the above classes and chapters from
  "THE BOOK": Algorithmic Game Theory, Edited by Nisan, Rounghgarden, Tardos and Vazirani.
  
• Very Important: you must go to Noam Nisan's homepage and read everything linked from there.

• There will be an exam at the end.
• There will be three homework assignments.
• All participants will write scribe notes for this class.