CSE logo University of Washington Computer Science & Engineering
 CSE 522 - Algorithmic Game Theory, Spring 2005
  CSE Home   About Us    Search    Contact Info 

Lecturer: Anna Karlin, CSE 403, WF 1:30-2:50pm

Description: We will study topics at the intersection of Game Theory, Economics and Computer Science.


March 30 Topics Introduction to Game Theory: Normal Form Games, Dominant Strategies, Nash Equilibria
 Notes Atri: pdf

From Game Theory course by Chris Wallace: Lecture 1: Strategic-Form Games


R. Mahajan, M. Rodrig, D. Wetherall and J. Zahorjan,  Experiences Applying Game Theory to System Design, SIGCOMM Workshop on Practice and   Theory of Incentives and Game Theory in Networked Systems (PINS), 2004.

April 6 Topics More Introduction: Mixed Nash Equilibria, Correlated Equilibria and Cooperative Games
 Notes Ashish:

From Game Theory course by Chris Wallace: Lecture 2: Mixed Strategies


R. J. Aumann, Subjectivity and Correlation in Randomized Strategies, Journal of Mathematical Economics, V.1(1), 67-96, 1974.

April 8 Topics Zero-Sum Games; Learning from Expert Advice
 Notes Chris: pdf

A. Blum, Online Learning tools for Online Algorithms, Dagstuhl workshop on Online Algorithms, 2002.


A. Blum, Online Learning and Prediction, a series of talks given at the Lipari summer school, 2000.


Y. Freund, R. E. Schapire, Game Theory, On-line Prediction and Boosting, COLT 1996.


Rohit Khandekar's Ph.D. Thesis, 2004.


Chapter 15 of Vasek Chvatal's book, Linear Programming, Freeman, 1983.

April 13 Topics More on Learning from Expert Advice
 Notes Ioannis:  pdf
References A. Blum and Y. Mansour, From External to Internal Regret, COLT 2005.
April 15 Topics Nash Equilibrium, Fixed-Point Theorem
 Notes Ning

J. F. Nash, Equilibrium Points in N-Person Games, Proceedings of the National Academy of Sciences, 36(1), 48-49, 1950. (Nash's Theorem)


J. F. Nash, Jr., Non-cooperative games, Annals of Mathematics, 54(2), 286-296, 1951.


J. Geanakoplos, Nash and Walras Equilibrium Via Brouwer, Economic Theory, 21(2-3):585--603, 2003.


Course notes from Berkeley and Cornell (part 1 and part 2).

April 20

Guest Lecturer: Kunal Talwar

Topics Complexity of Computing Equilibria
 Notes Ethan: pdf
References C. H. Papadimitriou Algorithms, Games, and the Internet, STOC 2001.

A. Fabrikant, K. Talwar and C. H. Papadimitriou, On the complexity of pure equilibria, STOC 2004.

April 22

Guest Lecturer:  Nati Linial

Topics Background for Linear Program: Simplex and Ellipsoid Methods
 Notes Neva: pdf
References M. Grotschel, L. Lovasz and A. Schrijver, Georetric Algorithms and Combinatorial Optimaization, Springer, 1991.
April 27 Topics Bandwidth Sharing Mechanisms
 Notes Chris: pdf
References F. P. Kelly, Charging and rate control for elastic traffic, European Transactions on Telecommunications, V.8, pp. 33ĘC37, 1997.

Frank Kelly, Aman Maulloo and David Tan, Rate control in communication networks: shadow prices, proportional fairness and stability, Journal of the Operational Research Society, V.49, pp237-252, 1998

Ramesh Johari and J. N. Tsitsiklis, Efficiency loss in a network resource allocation game, 2004.

S. H. Low, Larry Peterson and Limin Wang, Understanding Vegas: A Duality Model, JACM, 49(2), 207-235, 2002.

April 29 Topics Convex Optimization and Lagrangian Duality
 Notes Atri pdf
References M. Grotschel, L. Lovasz and A. Schrijver, Georetric Algorithms and Combinatorial Optimaization, Springer, 1991.

Stephen Boyd, Lieven Vandenberghe, Convex Optimization, Cambridge University Press, 2004.

May 4

Guest Lecturer: Kamal Jain

Topics Computation of Market Equilibrium
 Notes Ning: pdf
References X. Deng, C. H. Papadimitriou, and M. Safra, On the Complexity of Equilibria, STOC 2002.

N. Devanur, C. H. Papadimitriou, A. Saberi, and V. V. Vazirani, Market Equilibrium via a Primal-Dual-Type Algorithm, FOCS 2002.

K. Jain, A Polynomial Time Algorithm for Computing an Arrow-Debreu Market Equilibrium for Linear Utilities, FOCS 2004.

May 6 Topics Coaliational Game Theory
May 11

Guest Lecturer: M. Mahdian

Topics Selfish Routing
 Notes Ethan
References T. Roughgarden and É. Tardos, How Bad is Selfish Routing?, FOCS 2000.
May 13 Topics Introduction to Cost-Sharing
 Notes Ioannis: pdf
May 18

Guest Lecturer: N. Immorlica

Topics Cost-Sharing Schemes
 Notes Ashish: pdf
References J. Feigenbaum, C. H. Papadimitriou and S. Shenker, Sharing the cost of multicast transmission, STOC 2000.

N. Immorlica, M. Mahdian and V. Mirrokni, Limitations of cross-monotonic cost-sharing schemes, SODA 2005.

May 20 Topics Mechanism Design
 Notes Atri: pdf
References A. Mas-Collel, W. Whinston, J. Green, Microeconomic Theory (chap 23), Oxford University Press, 1995.

M. J. Osborne, A. Rubistein, A Course in Game Theory, MIT Press, 1994.

N. Nisan and A. Ronen, Algorithmic Mechanism Design, STOC 1999.

May 25 Topics More on Mechanism Design
 Notes Ioannis
May 27 Topics Mechanism Design with Revenue Consideration
 Notes Ning: pdf
June 1 Topics Class Presentations
TBA Topics Open Problems


Project: Interesting ideas can be found in the following links:


Game Theory Stuff:


Related Courses:


CSE 522 E-mail Group:

CSE logo Computer Science & Engineering
University of Washington
Box 352350
Seattle, WA  98195-2350
(206) 543-1695 voice, (206) 543-2969 FAX
[comments to ning]