Lecturer:
Yishay Mansour (mansour@cs.tau.ac.il)
TA:
Nir Andelman (andelmni@post.tau.ac.il)
Time
& Place :Tuesday
1013, Dan David 204
Lectures:
lecture

sources

scribe

Additional
sources

1.
Introduction

A
Course in Game Theory
Martin J. Osborne, Ariel Rubinstein
Parts
of Chapters 1 & 2 


2.
Coordination Ratio: Job scheduling

Worstcase
EquilibriaKoutsoupias and Papadimitriou
Tight Bounds for WorstCase 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
Owen 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



8. External and Internal Regret

From
External to Internal Regret Blum
and Mansour


9.
Dynamics in Load balancing & Routing

EvenDar,
Kesselman &Mansour Fast
Convergance to Selfish Routing EvenDar
& Mansour 


10.
Mechanism Design & Social Choice

M.
Jackson Three
Brief proofs of Arrows impossibility results J.
Geanakoplos A
GibbardSatterthwaite theorem: a simple proof J.
Benoit 


11
Combinatorial Auctions

Lehmann,
O’Callaghan & Shoham Incentive
compatible multi unit combinatorial auctions Bartal,
Gonen & Nisan 
HOMEWORKS:
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):
1.Introduction
2.Coordination
Ratio
a.Job
Scheduling
b.Routing
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
b.Routing
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
GRADE:
Scribe
notes: Each student will write
a scribe note for a lecture
(template
[tex ps] explanation
[texps])
Additional
Latex information: http://www.maths.tcd.ie/~dwilkins/LaTeXPrimer/