CS364A: Introduction to Algorithmic Game Theory

Instructor: Tim Roughgarden (Gates 462)

Teaching Assistants:
Mukund Sundararajan (Office hours: Tue 4-5 PM and by appt in Gates 470).
Sergei Vassilvitskii (Office hours: Wed 11-noon and by appt in Gates 492).

Time/location: 2:45-4 PM on Tuesdays and Thursdays in Gates B12.

Course description: Broad survey of topics at the interface of theoretical computer science and game theory such as: algorithmic mechanism design; combinatorial and competitive auctions; congestion and potential games; cost sharing; existence, computation, and learning of equilibria; game theory in the Internet; network games; price of anarchy and stability; pricing; and selfish routing. Minimal overlap with 224M and 324. Prerequisites: 154N and 161, or equivalents.

Course requirements: Three problem sets and a 10-15 page report summarizing 1-3 research papers. (Students taking the course pass/fail need only do the problems sets or the report, not both.)

• Problem Set #1 (Out Thu 10/5, due in class Thu 10/19.)
• Problem Set #2 (Out Tue 10/24, due in class Tue 11/7.)
• Problem Set #3 (Out Thu 11/9, due in class Thu 11/30.)

• Paper-reading topic: due Tue 10/31 by email.
• Report outline (1-3 pages): due Fri 11/17 by email.
• Final report: due Fri 12/15 Noon (submit soft or hard copy directly to instructor).
  • No extensions, no exceptions.
• Suggested topics.
• Instructions
• An Excellent Sample Report (by Nikola Milosavljev, from Fall 2004).

Schedule and references:

• Tue 9/26: Introduction to the course; introduction to auctions. References:
  • For more on the Vickrey auction, see Section 1 of Lecture Notes on Combinatorial Auctions, from last year's 364B course.
  • For more on Braess's Paradox, see Sections 1.1 and 3 of Selfish Routing and the Price of Anarchy, to appear in OPTIMA.
  • The recent result on the PPAD-completeness of finding Nash equilibria in bimatrix games is in Chen/Deng, Settling the Complexity of 2-Player Nash-Equilibrium, to appear in FOCS 2006.

• Thu 9/28: Introduction to algorithmic mechanism design. The Vickrey (second-price) auction. Introduction to competitive auctions for profit-maximization. Reading:
  • Section 1 of Lecture Notes on Combinatorial Auctions, from last year's 364B course.
  • Sections 3.1-3.4 of Lecture Notes on Optimal Mechanism Design, from last year's 364B course.

• Tue 10/3: Guest lecture by Jason Hartline (Microsoft) on competitive auctions. Reading:
  • Section 3 of Lecture Notes on Optimal Mechanism Design, from last year's 364B course.

• Thu 10/5: Guest lecture by Zoe Abrams (Yahoo) on sponsored search auctions. Reading:
  • Aggarwal/Goel/Motwani, Truthful auctions for pricing search keywords, EC '06.
  A few other recent papers on the topic include:
  • Edelman/Ostrovsky/Schwarz, Internet Advertising and the Generalized Second Price Auction: Selling Billions of Dollars Worth of Keywords, to appear in American Economic Review.
  • Mehta/Saberi/Vazirani/Vazirani, Adwords and Generalized On-line Matching, FOCS 2005.
  • Varian, Position Auctions, Working paper, 2006.

• Tue 10/10: Introduction to combinatorial auctions. The VCG mechanism. Reading:
  • Section 2 of Lecture Notes on Combinatorial Auctions, from last year's 364B course.
  For more surveys on algorithmic mechanism design, combinatorial auctions, and the VCG mechanism that are geared toward computer scientists, see:
  • Sections 1-4 of D. Lehmann, L. O'Callaghan, and Y. Shoham, Truth Revelation in Approximately Efficient Combinatorial Auctions, JACM 2002;
  • David Parkes's resources on the topic (especially Sections 2.1-2.4 of his thesis); and
  • N. Nisan and A. Ronen, Algorithmic Mechanism Design, which first appeared in STOC 1999.
  There's also an excellent recent book on the topic:
  • Cramton/Shoham/Steinberg (eds.), Combinatorial Auctions, MIT Press, 2006.

• Thu 10/12: Truthful approximate combinatorial auctions and the winner determination problem. For material on single-minded bidders, see
  • Section 3 of Lecture Notes on Combinatorial Auctions; and
  • D. Lehmann, L. O'Callaghan, and Y. Shoham, Truth Revelation in Approximately Efficient Combinatorial Auctions, JACM 2002;
  • Sandholm, Algorithm for Optimal Winner Determination in Combinatorial Auctions, AI '02.
  For a good discussion of the winner determination problem with complement-free bidders, and for the best approximation algorithm known for the subadditive case, see
  • Feige, On Maximizing Welfare when Utility Functions are Subadditive, STOC '06.

• Tue 10/17: Communication lower bounds in combinatorial auctions. Introduction to cost-sharing mechanisms. References for communication lower bounds:
  • N. Nisan, The Communication Complexity of Approximate Set Packing and Covering , ICALP 2002. (Better than \sqrt{m} approximation of surplus requires exponential communication.)
  • This line of research was pioneered by Nisan and Segal. See Nisan/Segal, The Communication Requirements of Efficient Allocations and Supporting Lindahl Prices (A Self-Contained CS-Friendly Executive Summary). The full paper (Journal of Economic Theory, 2006) is here.
  The fixed-tree multicast problem was introduced in
  • Feigenbaum/Papadimitriou/Shenker, Sharing the Costs of Multicast Transmission, STOC '00 and
  • Moulin/Shenker, Strategyproof Sharing of Submodular Costs: Budget Balance Versus Efficiency, Economic Theory 2001.

• Thu 10/19: Design and analysis of optimal Moulin cost-sharing mechanisms. Reference:
  • Roughgarden/Sundararajan, New Trade-offs in Cost-Sharing Mechanisms, STOC '06.

• Tue 10/24: Finish cost-sharing mechanisms. Introduction to nonatomic selfish routing games and the price of anarchy.

• Thu 10/26: Bounding the price of anarchy for nonatomic selfish routing. Reference:
  • Roughgarden, "Routing Games", draft of book chapter to appear in Algorithmic Game Theory, to appear in 2007. (Handed out in class.)
  • For much more on this topic, see the book on Selfish Routing and the Price of Anarchy, MIT Press, 2005.

• Tue 10/31: The price of anarchy in nonatomic and atomic selfish routing games. Reference:
  • "Routing Games" (see last lecture).
  The price of anarchy in atomic selfish routing games was first analyzed in:
  • Awerbuch/Azar/Epstein, The price of routing unsplittable flow, STOC 2005.
  • Christodoulou/Koutsoupias, The price of anarchy of finite congestion games, STOC 2005.

• Thu 11/2: Existence of equilibrium flows. The potential function method. Introduction to Shapley network design games and the price of stability. Main reference:
  • Roughgarden, Potential Functions and the Inefficiency of Equilibria, ICM 2006.
  Shapley network design games were defined in:
  • Anshelevich/Dasgupta/Kleinberg/Tardos/Wexler/Roughgarden, The Price of Stability for Network Design with Fair Cost Allocation.
  For more studies on the inefficiency of equilibria in network formation games, see, for example:
  • E. Anshelevich, A. Dasgupta, E. Tardos, and T. Wexler, Near-Optimal Network Design with Selfish Agents (STOC 2003) and
  • A. Fabrikant, A. Luthra, E. Maneva, C. H. Papadimitriou, and S. Shenker, On a Network Creation Game (PODC 2003).

• Tue 11/7: Finish Shapley network design games. Convergence of better-response dynamics in congestion and potential games.
  • Congestion games were first defined in Robert Rosenthal, "A Class of Games Possessing Pure-Strategy Nash Equilibria", International Journal of Game Theory 1973.
  • Potential games were first defined in Dov Monderer and Lloyd Shapley, "Potential Games", Games and Economic Behavior 1996.

• Thu 11/9: The interplay between convergence and price of anarchy bounds. Sink equilibria. References:
  • A. Vetta, Nash equilibria in competitive societies with applications to facility location, traffic routing, and auctions, FOCS 2002;
  • V. Mirrokni and A. Vetta, Convergence issues in competitive games, APPROX 2004.
  • M. X. Goemans, V. Mirrokni, and A. Vetta, Sink equilibria and convergence, FOCS 2005.

• Tue 11/14: Convergence of best-response dynamics to Nash equilibria in congestion games: fast convergence to approximate equilbria. Reference:
  • Chien/Sinclair, Convergence to approximate Nash equilibria in congestion games, SODA 2007.

• Thu 11/16: Convergence of best-response dynamics to Nash equilibria in congestion games: slow convergence to exact equilbria. PLS-completeness. Main reference:
  • Voecking, Congestion Games: Optimization in Competition (Survey Paper), ACiD '06.
  See also:
  • Fabrikant/Papadimitriou/Talwar, The Complexity of Pure Nash Equilibria, STOC '04.
  • Ackermann/Roeglin/Voecking, On the Impact of Combinatorial Structure on Congestion Games, FOCS '06.

• Tue 11/21: No class (Thanksgiving break).

• Thu 11/23: No class (Thanksgiving break).

• Tue 11/28: Computing equilibria using linear programming: 2-player zero-sum games. Proof sketch of Nash's Theorem.
  • The material on zero-sum games is classical and can be found in many different sources; a favorite of mine is Chapter 15 of Vasek Chvatal's book, "Linear Programming" (Freeman, 1983).
  • The von Neumann correspondence to Econometrica that I discussed is here.
  • The Dantzig quote was from the Preface to Volume 1 of his book on Linear Programming (with Thapa), 1997.
  For references on Nash's Theorem, see the following.
  • Nash's Theorem is originally from J. F. Nash, Jr., Equilibrium Points in N-Person Games, Proceedings of the National Academy of Sciences (USA), 36(1):48--49, 1950.
  • A year later Nash showed how to reduce his theorem to Brouwer's fixed-point theorem: J. F. Nash, Jr., Non-cooperative games, Annals of Mathematics, 54(2):286--296, 1951.
  • The reduction of Nash's theorem to Brouwer's theorem that we covered in class is from J. Geanakoplos, Nash and Walras Equilibrium Via Brouwer, Economic Theory 21(2-3):585--603, 2003.

• Thu 11/30: Approximate Nash equilibria via sampling and enumeration. Introduction to correlated equilibria.
  • The quasipolynomial-time algorithm for finding approximate Nash equilibria is from
    • R. Lipton, E. Markakis, and A. Mehta, Playing Large Games using Simple Strategies, EC '03.
  • For recent applications of enumeration algorithms to random games, see:
    • I. Barany, S. Vempala, and A. Vetta, Nash equilibria in random games, FOCS '05.
    This paper shows that for various distributions on bimatrix games, with high probability there is a Nash equilibrium with small (constant-size) support. Thus the enumeration algorithm runs in polynomial time with high probability. (It is still open whether or not the expected running time of the enumeration algorithm is polynomial for these distributions.)

• Tue 12/5: Computing correlated equilibria using linear programming. Warm-up to PPAD: Sperner's Lemma and Brouwer's FIxed-Point Theorem.
  • Our treatment of Sperner's Lemma and Brouwer's Theorem follows that outlined in course notes from UC Berkeley and Cornell (part 1 and part 2).

• Thu 12/7: PPAD-completeness. Reductions between computing Nash equilibria and computing Brouwer fixed-points. References:
  • N. Megiddo and C. Papadimitriou, A note on total functions, existence theorems and complexity, Theoretical Computer Science, 81:317--324, 1991.
  • C. Papadimitriou, The complexity of the parity argument and other inefficient proofs of existence, JCSS 1994.
  • K. Daskalakis, P. Goldberg, C. Papadimitriou, The Complexity of Computing a Nash Equilibrium, STOC 2006.
  • Chen/Deng, Settling the Complexity of 2-Player Nash-Equilibrium, FOCS 2006.