Computational Game Theory

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	pdf
2. Coordination Ratio: Job scheduling	Worst-case EquilibriaKoutsoupias and Papadimitriou Tight Bounds for Worst-Case Equilibria A. Czumaj and B. Vocking	pdf	Marios Mavronicolas
3. Coordination Ratio: Selfish Routing	How Bad is Selfish Routing? Roughgarden and Tardos	pdf	Tim Roughgarden
4. Zero Sum games	Game Theory Owen Adaptive game playing using multiplicative weights Freund and Schapire	pdf
5. General sum games: Nash	BrouwerLemma Playing large games using simple strategies Lipton, Markakis and Mehta Complexity results about Nash Equilibrium Conitzer and Sandholm	pdf
6. Congestion and Potential Games	Potential Games Monderer and Shapley On the complexity of pure equilibria Fabrikant, Papadimitriou and Talwar	pdf	Christos H. Papadimitriou
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	pdf
8. External and Internal Regret	From External to Internal Regret Blum and Mansour	pdf	Nicolò Cesa-Bianchi Sergiu Hart
9. Dynamics in Load balancing & Routing	Convergence Time to Nash Equilibria  Even-Dar, Kesselman &Mansour Fast Convergance to Selfish Routing Even-Dar & Mansour	pdf ppt
10. Mechanism Design & Social Choice	Mechanism Theory M. Jackson Three Brief proofs of Arrows impossibility results J. Geanakoplos A Gibbard-Satterthwaite theorem: a simple proof J. Benoit	pdf
11 Combinatorial Auctions	Truth revelation in approximately efficient combinatorial auctions Lehmann, O’Callaghan & Shoham Incentive compatible multi unit combinatorial auctions Bartal, Gonen & Nisan	pdf	Noam Nisan Tuomas Sandholm

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/

HOMEWORK

EXAM/PROJECT