Course schedule

Week 1. Introduction and background on game theory. 

In subsequent weeks we will discuss papers from the literature. 

Week 2
1. Noam Nisan.  Algorithms for selfish agents.  STACS 99.
2. Noam Nisan and Amir Ronen.  Algorithmic mechanism design.  Extended version of STOC 99 paper.

Week 3
3. Andrew Goldberg, Jason Hartline, Anna Karlin, Andrew Wright, Michael Saks.  Competitive auctions. Extended version of SODA 01 paper.
4.  Amos Fiat, Andrew Goldberg, Jason Hartline, Anna Karlin.  Competitive generalized auctions.  STOC 02, 72-81.

Week 4
3.  Andrew Goldberg, Jason Hartline.  Competitiveness via consensus.  SODA 03.
4.  Andrew Goldberg, Jason Hartline.  Envy free auctions for digital goods.  EC 03.

Week 5
5.  Liad Blumrosen, Noam Nisan.  Auctions with severely bounded communication.  FOCS 02.
6. Baruch Awerbuch, Yossi Azar, Adam Meyerson.  Reducing truth-telling online mechanisms to online optimization.  STOC 03, 503-510.

Week 6
7. Tim Roughgarden, Eva Tardos. How bad is selfish routing?  JACM 2002.

Week 7
8. Tim Roughgarden. Designing Networks for Selfish Users is Hard.  To appear,  JCSS.
9. Tim Roughgarden. Stackelberg Scheduling Strategies. To appear,  SIAM J. Computing.

Week 8
10. Richard Cole, Yevgeniy Dodis, Tim Roughgarden.  Pricing Network Edges for Heterogeneous Selfish Users.  STOC 03.
11. Richard Cole, Yevgeniy Dodis, Tim Roughgarden.  How Much Can Taxes Help Selfish Routing?  EC 03.

Week 9.
12. Vetta. Nash equilibria in competitive societies.   To appear,  SIAM J. Computing.

Week 10.
13. Joan Feigenbaum, Christos Papadimitriou, Rahul Sami, Scott Shenker. A BGP-based mechanism for lowest-cost routing. PODC 2002.
14. Edith Elkind, Amit Sahai, Ken Steiglitz. Frugality in path auctions. SODA 04.

Week 11.
15. Aditya Akella,  Srinivasan Seshan, Richard Karp, Scott Shenker, Christos Papadimitriou. Selfish behavior and stability of the Internet: a game-theoretic analysis of TCP. SIGCOMM 02.
16. Lee Breslau and Scott Shenker.  Best effort versus reservations: a simple comparative analysis.  SIGCOMM 98.

Week 12.  
17.  Daniel Lehmann and Liadan Ita  O'Callaghan and Yoav Shoham.  Truth revelation in approximately efficient combinatorial auctions.  JACM 02.
18. Ahuva Mu'alem and Noam Nisan.  Truthful Approximation mechanisms for restricted combinatorial auctions.  AAAI 02.

Week 13.
19.  Nikhil Devanur, Christos Papadimitriou, Amin Saberi, Vijay Vazirani.  Market equilibrium via a primal-dual- type algorithm.  FOCS 02.
20. Kamal Jain and Vijay Vazirani.  Equitable cost allocations via primal-dual-type algorithms.  STOC 02.

Week 14.
21. J. Kleinberg. Authoritative sources in a hyperlinked environment.  SODA 98.
22. Jon Kleinberg.  The small world phenomenon: an algorithmic perspective.