Computational Game Theory

Lecturer: Yishay Mansour (

TA: Nir Andelman (

Time & Place :Tuesday 10-13, Dan David 204


Additional sources
1. Introduction
A Course in Game Theory Martin J. Osborne, Ariel Rubinstein

Parts of Chapters 1 & 2

2. Coordination Ratio: Job scheduling
Worst-case EquilibriaKoutsoupias and Papadimitriou

Tight Bounds for Worst-Case Equilibria

A. Czumaj and B. Vocking

Marios Mavronicolas
3. Coordination Ratio: Selfish Routing
How Bad is Selfish Routing?

Roughgarden and Tardos

4. Zero Sum games
Game Theory


Adaptive game playing using multiplicative weights

Freund and Schapire

5. General sum games: Nash

Playing large games using simple strategies

Lipton, Markakis and Mehta

Complexity results about Nash Equilibrium

Conitzer and Sandholm

6. Congestion and Potential Games

Monderer and Shapley

On the complexity of pure equilibria

Fabrikant, Papadimitriou and Talwar

7. Extensive form and Repeated Games
A Course in Game Theory Martin J. Osborne, Ariel Rubinstein

Parts of Chapters 6 & 8

On Bounded Rationality And Computational Complexity
Papadimitriou and Yannakakis

8. External and Internal Regret

Sergiu Hart

9. Dynamics in Load balancing & Routing

Even-Dar, Kesselman &Mansour

Fast Convergance to Selfish Routing

Even-Dar & Mansour


10. Mechanism Design & Social Choice

M. Jackson

Three Brief proofs of Arrows impossibility results

J. Geanakoplos

A Gibbard-Satterthwaite theorem: a simple proof

J. Benoit

11 Combinatorial Auctions

Lehmann, O’Callaghan & Shoham

Incentive compatible multi unit combinatorial auctions Bartal, Gonen & Nisan

Tuomas Sandholm


Homework 1 (given March 16, due March 30) doc htm

Homework 2 (given March 30, due April 18) doc htm

Homework 3 (given May 11, due June 1) doc htm

A tentative list of the subjects (not all will be covered):


2.Coordination Ratio

a.Job Scheduling


3.Computation of Nash Eq.

a.Zero sum game & Correlated eq.

b.General Sum: existence proof

c.Two payers general sum: algo.

4.Internal and External Regret

5.Vector payoff games

a.Approachability Theorem 

6.Congestion and potential games.

7.Dynamics in games

a.Job scheduling


8.Repeated games and Bounded rationality 

9.Graphical models

10.Mechanism design

11.Stochastic games

12.Cooperative games

13.Extensive form games

14.Fictitious play

15.Evolutionary game theory (dynamics)

16.Implementation theory


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

(template [tex ps] explanation [texps])

Additional Latex information: