Computational Game Theory (2010)

Lecturer: Yishay Mansour (mansour@tau.ac.il)

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

s

GRADE:

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

HOMEWORK

Home work 1 (handed out March 8, 2010)

Home work 2

Homework 3

PROJECT INSTRUCTIONS

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.