Lecturer: Yishay Mansour (mansour@cs.tau.ac.il)
TA: Nir Andelman (andelmni@post.tau.ac.il)
Time & Place :Tuesday
10-13, 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 |
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
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 |
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 |
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/