Computational Game Theory


Lecturer: Yishay Mansour (


Time & Place :  Tuesday 10-13, Shreiber Building Room 7


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


1.     Introduction


2.     Quality of an Equilibrium

a.      Job Scheduling      (Price of Anarchy)

b.     Routing                 (Price of Anarchy)

c.     Network Creation (Price of Anarchy)

d.      Congestion and Potential games

Network Design     (Price of Stability)

Bandwidth allocation


3.     Equilibrium Existence

a.      Two players zero sum game

b.     Correlated equilibrium

c.     Congestion and potential games.(moved to lecture 4)

d.     Nash Equilibrium (existence)

e.      Graphical games and hardness


4.     Repeated Games

a.      General folklore theorems

b.     Internal and External Regret

c.     GUEST LECTURE: Combinatorial Agency (Michal Feldman) [ppt]

d.     Internal/Swap regret and Dynamics of reaching equilibrium

e.      Vector payoff games (Approachability Theorem )

f.       Option pricing



5.     Mechanism Design

a.       Social choice

b.      Maximizing social welfare (VCG mechanism)

c.     Auctions  (combinatorial, maximizing social welfare )

d.     Auctions (digital goods)




Scribe notes: Each student will write a scribe note for a lecture LIST


            Homework 1

            Homework 2

            Homework 3


HOMEWORK (1,2 and 3) CAN BE TAKEN FROM THE GRADER URI NADAV (e-mail  uri.nadav at