Time: MWF 11:15-12:05
Place: Phillips 219.
Office Hours:
Mondays 10-11 and Thursdays 2:30-3:30, or by appointment.
Office hour Monday 17: 2-3pm.
TA: Mark Sandler
Office Hours:
Fridays 2-3, or by appointment.
Mark will have additional office hours during the regular class times.
Final Project due Wednesday, May 19th
Submit a brief proposal for your final project before spring break. The project proposal is a few paragraph long explanation on what you are hoping to accomplish. The goal of asking for the proposals is to get each group started on thinking about the projects, and also to allow early feedback on the plans. You can work on this project in groups of at most 3.
There are many different types of projects possible. You can consider a game, and propose to work on understanding the algorithmic issues associated with this game, such as how to find an equilibria, are there many equilibria, do natural plays find such equilibria, what are the quality of the worst or best equilibria, etc. I think the most interesting projects would model some phenomena in computer science as a game, and analyze a simplified version. Projects may be theoretical or experimental in nature. Alternatively, your project may be an extended survey of the literature in a sub-area. If you choose to do a survey, you should make sure that you understand the papers well, and can compare the results, and techniques of different papers, explain their advantages and disadvantages.
Algorithmic Game Theory combines algorithmic thinking with game-theoretic, or, more generally, economic concepts. The course will focus on problems arising from, and motivated by, the Internet and other decentralized computer networks. The most defining characteristic of the Internet is that it was not designed by a single central entity, but emerged from the complex interaction of many economic agents, such as network operators, service providers, designers, users, etc., in varying degrees of collaboration and competition. The course will focus on some of the many questions at the interface between algorithms and game theory that arise from this point of view.
Topics include some of the following (subject to change):
Notes for January 26- February 6 on Introduction to games, Nash equilibria, load balancing game, potential games, a routing game, non-atomic games, and convex optimization.
Week of January 26-30:
- E. Koutsoupias, C. H. Papadimitriou "Worst-case equilibria", STACS 99.
- Monderer and Shapley, Potential Games, Games and Economic Behavior, 14:124--143, 1996.
Week of February 2-6:
- Alex Fabrikant, Christos Papadimitriou, and Kunal Talwar On the complexity of pure equilibria, to appear in STOC 2004.
Week of February 9-13:
- Notes for February 9: worst case Opt/Nash ratio is on two links
- Notes for February 11: more on Nash/Opt, fair flows, and the Braess' paradox
- Notes for February 13: bounding Nash by Opt on twice the delay
- T. Roughgarden and É. Tardos. How Bad is Selfish Routing?. In JACM 2002.
- T. Roughgarden. The Price of Anarchy is Independent of the Network Topology. In JCSS 2003.
Week of February 16-20:
- Notes for February 16: proof of Brower's fixed point theorem.
- Notes for February 18: Proving the existence of Nash equlibrium.
- Notes for February 20: Correlated equilibria.
Week of February 23-27 (Price of anarchy on randomized load balancing games):
- Notes for February 23: worst case Opt/Nash for maximum expected load in randomized load balancing
- Notes for February 25: worst case Opt/Nash for expected maximum load in randomized load balancing
- Notes for February 27: On evolutionary games, and evolutionary stable strategies
- E. Koutsoupias, C. H. Papadimitriou: ``Worst-case equilibria,'' in STACS 1999.
- A. Czumaj and B. Vöcking: Tight Bounds for Worst-Case Equilibria, in SODA 2002.
Week of March 1-5 (Markets, and market equilibria)
- Notes for March 1st: On Vetta's facility location game
- Notes for March 3rd: On the existence of market equilibrium with strictly concave utilities.
- Notes for March 5th: On an algorithm for the case with linear utilities, and separated goods and buyers.
- Adrian Vetta, Nash equilibria in competitive societies with applications to facility location, traffic routing and auctions. FOCS, 2002.
- Deng Xiaotie, C. H. Papadimitriou, Muli Safra On the Complexity of Equilibria., STOC 02
- N. Devanur, C. Papadimitriou, A. Saberi, and V. Vazirani ``Market Equilibrium via a Primal-Dual-Type Algorithm'', FOCS 2002.
Week of March 8-12: guest lectures by
- Notes for March 8: Eric Friedman's lecture about some problems with the Nash equilibrium.
- Notes for March 10: Mark Sandler's lecture about: Graphical Models for Game Theory, by M. Kearns, M. Littman, and S. Singh. 2001. In Proceedings of UAI 2001.
- Notes for March 12: Tom Wexler talked about Near-optimal network design with selfish agents, by E. Anshelevich, A. Dasgupta, É. Tardos, T. Wexler, in STOC'03
Week of March 15-19 Bandwidth sharing: mechanisms and the price of anarchy.
European Transactions on Telecommunications, vol. 8, pp. 33–37, 1997.
Notes for March 15: On Kelly's Bandwidth sharing game.
Notes for March 17: For the Johari-Tsitsiklis game on a single link
Notes for March 19: On extending Kelly's and the Johari-Tsitsiklis game to a network. Improved version with the last proof expanded.
F. P. Kelly, “Charging and rate control for elastic traffic,”
Ramesh Johari, and John N. Tsitsiklis. (2004). Efficiency loss in a network resource allocation game.
see also: Frank Kelly, Aman Maulloo and David Tan: Rate control in communication networks: shadow prices, proportional fairness and stability. Journal of the Operational Research Society 49 (1998) 237-252.
S. H. Low, Larry Peterson and Limin Wang: Understanding Vegas: A Duality Model Journal of ACM, 49(2):207-235, March 2002.
Week of March 29-April 2: Fair bandwidth sharing
Notes for March 29: on the characterization of core allocations.
Notes for March 31: on Shapley value
Notes for April 2: on serial cost-sharing
Herve Moulin and Scott Shenker, "Serial Cost Sharing," Econometrica, vol. 60, no. 5, pp. 1009-1037, 1992.
- Scott Shenker Making Greed Work in Networks A Game Theoretic Analysis of Switch Switch Service Disciplines, SIGCOMM'95
Week of April 5-9: We continue discussing the fair bandwidth sharing game, and start talking about cross monotone cost-sharing.
Notes for April 5: Showing that all cost-sharing games can result in solutions that are not pareto optimal.
Notes for April 7: define cross monotone cost-sharing and show that for submodular cost-functions, Shapley value is cross-monotone
Notes for April 9: give a cross-monotone cost-sharing function for the spanning tree problem (or muticast).
H. Moulin and S. Shenker: Strategyproof Sharing of Submodular Costs: budget balance versus efficiency
K. Jain and V. Vazirani Applications of Approximation Algorithms to Cooperative Games, STOC 2001
Week of April 12-16: We define truthfulness, and discuss the VCG mechanism
Notes for April 12: on Vickrey auction and VCG mechanisms for cost-sharing.
Notes for April 14: on the VCG mechanism
Notes for April 16: on combinatorial auction
N. Nisan and A. Ronen. Algorithmic Mechanism Design, STOC 1999.
John Hershberger and Subhash Suri. Vickrey Prices and Shortest Paths: What is an edge worth?, FOCS 2001
J. Feigenbaum, C. H. Papadimitriou, R. Sami, S. Shenker A BGP-based Mechanism for Lowest-cost Routing, PODC, 2002.
Week of April 19-23: More on truthful mechanisms and impossibility results
- Notes for April 19: on using linear programming and rounding to design truthful auctions
- Notes for April 21: on auction for digital goods
- Notes for April 23: on Arrow's impossibility theorem
- Aaron Archer, Christos Papadimitriou, Kunal Talwar and Éva Tardos, "An approximate truthful mechanism for combinatorial auctions with single parameter agents"
- A. V. Goldberg, J. D. Hartline, A. R. Karlin, and A. Wright: Competitive Auctions
Week of April 26-31: More on impossibility and Bayesian games
- Notes for April 26: on the Gibbard-Setterthwaite impossibility theorem on truthfulness without side payments.
- April 28: Bayesian games, and first price auction, see notes with next lecture
- Notes for April 30: on first price auction, revenue equivalence and auctions with reserve prices.
Week of May 3-7: Three recent results
- Notes for May 3: On the severity of Braess' paradox
- Notes for May 5: On finding correlated equilibria in compactly represented games
- Notes for May 7: stable matching games
- T. Roughgarden. On the Severity of Braess's Paradox: Designing Networks for Selfish Users Is Hard.
- C. Papadimitriou, and T. Roughgarden. Computing equilibria in multiplayer games.
The course pre-requisites include background in algorithms and graphs at the level of CS 482. No prior knowledge of game theory or economics will be assumed.
You may discuss the homework problems with other members of the class, but you must write up the assignment separately and list the names of the people with whom you discussed the assignment.
There are many different types of projects possible both experimental, theoretical, or an extended survey of literature in a sub-area. You can work on the final project in groups of up to three people. The first step in the project will be a short `proposal'.There is no textbook for the course, as it covers recent research. The following book is a very nice introduction to game theory. (But it is not required for the course.)