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.

Lectures
March 30	Topics	Introduction to Game Theory: Normal Form Games, Dominant Strategies, Nash Equilibria
	Notes	Atri: pdf
	References	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:
	References	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
	References	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
	References	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
	Notes
	References
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
	References
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
	References
May 27	Topics	Mechanism Design with Revenue Consideration
	Notes	Ning: pdf
	References
June 1	Topics	Class Presentations
	Notes
	References
TBA	Topics	Open Problems
	Notes
	References

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

• Yoav Shoham, Thoughts on basic research directions in AI.
• Joan Feigenbaum and Scott Shenker, Distributed Algorithmic Mechanism Design: Recent Results and Future Directions, in Proceedings of the 6th International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications, pp1-13, 2002.
• Jeffrey Shneidman and David C. Parkes, Rationality and Self-Interest in Peer to Peer Networks, in Proceedings of the Second International Workshop on Peer-to-Peer Systems (IPTPS '03), 2003.
• Rajdeep K. Dash, Nicholas R. Jennings, and David C. Parkes, Computational- Mechanism Design: A Call to Arms, IEEE Intelligent Systems 18(6), pp40-47.
• 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.

Game Theory Stuff:

• Chris Wallace's Game Theory Lectures: http://malroy.econ.ox.ac.uk/ccw/Games.shtml

Related Courses:

• Joan Feigenbaum: (2002) http://zoo.cs.yale.edu/classes/cs455/index2002.html and (2003) http://zoo.cs.yale.edu/classes/cs455/
• Mike kearns: (2003) http://www.cis.upenn.edu/~mkearns/teaching/cgt/
• Noam Nisan: (2001-3) http://www.cs.huji.ac.il/~noam/econcs/index.html and (2004-5) http://www.cs.huji.ac.il/~foec/index.html
• Christos Papadimitriou: (2001) http://www.cs.berkeley.edu/~christos/games/cs294.html
• David Parkes: http://www.eecs.harvard.edu/~parkes/cs286r/
• Tim Roughgarden: (2004) http://theory.stanford.edu/~tim/364a.html
• Tuomas Sandholm: http://www-2.cs.cmu.edu/~sandholm/cs15-892/cs15-892.htm
• Eva Tardos: (2004) http://www.cs.cornell.edu/courses/cs684/2004sp/

CSE 522 E-mail Group:

• To subscribe to the CSE 522 E-mail Group, visit http://mailman.cs.washington.edu/mailman/listinfo/cse522.

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