Computational Game Theory (2010)


Lecturer: Yishay Mansour (


Time & Place :  Monday 9-12, Kaplun Building Room 118


This is a tentative list of the subjects (not all will be covered):

1. Introduction                  pptx

2. Quality of Equilibrium  (Price of Anarchy)

a. Job Scheduling

b. Routing           pptx

c. Price of Stability & Strong Price of Anarchy  pptx

3. Equilibrium Existence

a. Two players zero-sum

b. General Nash Equilibrium

4. Regret Minimization

a. External (including dynamics)

b. Swap (and calibration and Multi-Arm-Bandit)         

5. Mechanism Design

a. Social Choice

b. Maximizing Social Welfare (VCG)

c. Sponsored Search

d. combinatorial auctions

e. Revenue maximization





Scribe notes: Each student will write a scribe note for a lecture (template [pdf,tex] explanation on Latex [pdf,tex])

List of students and scribes


Home work 1 (handed out March 8, 2010)

Home work 2

Homework 3




Student projects


·         Similar Courses around the world:

o    Michael Kearns, Computational Game Theory, University of Pennsylvania

o    Adrian Vetta, Algorithmic Game Theory, McGill University

o    Eva Tardos, Algorithmic Game Theory, Cornell University

o    Tim Roughgarden, Algorithmic Game Theory, Stanford University

o    Christos Papadimitriou, Algorithmic Aspects of Game Theory, Berkeley

o    Joan Feigenbaum, Economics and Computation, Yale University

o    Noam Nisan, CS, Game theory, and Economics, Hebrew University

o    Peter Bro Miletersen, Algorithmic game theory, Fall 2008, Aarhus

o    Vincent Conitzer , Computational Game Theory and Mechanism Design , Duke University.

o    Kousha Etessami, Algorithmic Game Theory and Applications , 2003- 2008, University of Edinburgh

o    Adam Tauman Kalai, Game Theory and Computer Science, Spring 2008, Georgia Tech

o    Amos Fiat, Computational Game Theory, Spring 2008, Tel Aviv University

o    David Parkes, Computational Mechanism Design, Spring 2007

·         Books Surveys:

o    Noam Nisan, Tim Roughgarden, Eva Tardos and Vijay V. Vazirani (Editors), Algorithmic Game Theory, Cambridge University Press, 2007. Available for online viewing here (with username=agt1user, password=camb2agt).

o    Paul W. Goldberg, Liverpool: Introduction to PPAD

o    Survey of Algorithmic Game Theory, Tim Roughgarden, Stanford.