CS364A: Algorithmic Game Theory

Instructor: Tim Roughgarden (Gates 462)

Teaching Assistant: Sergei Vassilvitskii. Office hours: Tuesdays 10:30-noon in Gates 464.

Time/location: 1:15-2:30 PM on Tuesdays and Thursdays in Gates B08. (Room will be B12 starting on Thursday 10/7.)

Course description: Broad, graduate-level overview of topics on the interface of theoretical computer science and game theory. Possible topics include: auctions; congestion and potential games; cost sharing; existence and computation of equilibria; game theory in the Internet; mechanism design; network games; price of anarchy; pricing; selfish routing. Minimal overlap with 224M and 324. Prerequisites: 154N and 161, or equivalent.

Course requirements: Two problem sets and a 10-15 page report summarizing 2-3 research papers.

• Problem Set #1 (Due in class Tue 10/26.)
• Problem Set #2 (Due in class Tue 11/16.) (News flash: Due date extended to 11/18.)
  • Revised version posted 11/15.
• Suggested paper-reading topics
• Paper-reading proposal: due Mon 11/9 by email.
• Paper-reading report: due Thu 12/2 in class. Details.

Schedule and references:

• Tue 9/28: Introduction: Braess's Paradox, the Vickrey auction, and cost sharing.

• Thu 9/30: Selfish routing: examples and optimality conditions.
  • Most of these preliminaries date back to M. Beckmann, C. B. McGuire, and C. B. Winsten, Studies in the Economics of Transportation, Yale University Press, 1956.
  • Much of it can be found online in T. Roughgarden and E. Tardos, How Bad Is Selfish Routing?, Journal of the ACM, 49(2):236--259, 2002. (Conference version in FOCS 2000.)

• Tue 10/5: Selfish routing: Worst-case price of anarchy always occurs in Pigou-like networks.
  • This result was first proved in T. Roughgarden, The Price of Anarchy Is Independent of the Network Topology, Journal of Computer and System Sciences, 67(2):341--364, 2003. (Conference version in STOC 2002.)
  • The proof given in class is due to E. Tardos; see these lecture notes from Cornell CS684.
  • For another proof (that also works in a somewhat more general context), see J. R. Correa, N. E. Stier Moses, and A. S. Schulz, Selfish Routing in Capacitated Networks, Mathematics of Operations Research, 2004 (to appear). (Conference version in SODA 2003.)

• Thu 10/7: Selfish routing: Completion of last lecture and a bicriteria bound for general networks.
  • This result is from T. Roughgarden and E. Tardos, How Bad Is Selfish Routing?, Journal of the ACM, 49(2):236--259, 2002.

• Tue 10/12: Braess's Paradox: Worst-case severity; algorithmic complexity of detection.
  • Survey of results of three papers: (1) T. Roughgarden, On the Severity of Braess's Paradox: Designing Networks for Selfish Users Is Hard, Journal of Computer and System Sciences, to appear. (Conference version in FOCS 2001.)
  • (2) H. Lin, T. Roughgarden, and E. Tardos, A Stronger Bound on Braess's Paradox, SODA 2004.
  • (3) H. Lin, T. Roughgarden, E. Tardos, and A. Walkover, Braess's Paradox, Fibonacci Numbers, and Exponential Inapproximability. (Not online.)

• Thu 10/14: No class

• Tue 10/19: Price of anarchy in network design and congestion games.
  • This lecture is based on a very recent (FOCS 2004) paper: E. Anshelevich, A. Dasgupta, J. Kleinberg, E. Tardos, T. Wexler, and T. Roughgarden, The Price of Stability for Network Design with Fair Cost Allocation.
  • See also 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) for other recent papers along similar lines.

• Thu 10/21: Price of anarchy in bandwidth allocation.
  • This lecture is based on R. Johari and J. N. Tsitsiklis, Efficiency Loss in a Network Resource Allocation Game, Mathematics of Operations Research, 2004.

• Tue 10/26: Price of anarchy and convergence to Nash equilibrium in facility location games.
  • This lecture is based on A. Vetta, Nash equilibria in competitive societies with applications to facility location, traffic routing, and auctions, FOCS 2002 as well as
  • V. Mirrokni and A. Vetta, Convergence issues in competitive games, APPROX 2004.
  • The load-balancing balancing model (the "KP model") that we discussed briefly is from E. Koutsoupias and C. H. Papadimitriou, Worst-case equilibria, STACS 1999. See also Problem Set #2 for much more on this model.

• Thu 10/28: Vickrey auction, introduction to shortest-path auctions, combinatorial auctions, and Vickrey-Clarke-Groves (VCG) mechanisms. For surveys on algorithmic mechanism design geared toward computer scientists, see:
  • David Parkes's resources on the topic and
  • N. Nisan and A. Ronen, Algorithmic Mechanism Design, which first appeared in STOC 1999.

• Tue 11/2: Shortest-path auctions and frugal mechanisms. This lecture is based on:
  N. Nisan and A. Ronen, Algorithmic Mechanism Design, which first appeared in STOC 1999.
  • A. Archer and E. Tardos, Frugal Path Mechanisms, SODA 2002.
  • E. Elkind, A. Sahai, and K. Steiglitz, Frugality in Path Auctions , SODA 2004.

• Thu 11/4: No class

• Tue 11/9: Combinatorial auctions. The proof done in class is from
  • N. Nisan and I. Segal, The Communication Requirements of Efficient Allocations and Supporting Lindahl Prices (A Self-Contained CS-Friendly Executive Summary). The full paper (to appear in Journal of Economic Theory) is here.
  • See D. Lehmann, L. O'Callaghan, and Y. Shoham, Truth Revelation in Approximately Efficient Combinatorial Auctions, JACM 2002, for more on single-minded bidders.

• Thu 11/11: Auctions for digital goods.
  • This lecture is based on A. V. Goldberg, J. D. Hartline, A. R. Karlin, and A. Wright, Competitive Auctions.

• Tue 11/16: Cross-monotonic cost sharing yields group strategyproof mechanisms. The main result from this lecture is from
  • H. Moulin, Incremental Cost Sharing: Characterization by Group Strategyproofness, Social Choice and Welfare, 16:279--320, 1999. See also:
  • H. Moulin and S. Shenker, Strategyproof Sharing of Submodular Costs: Budget Balance versus Efficiency, Economic Theory, 18:511--533, 2001. The multicast application is from:
  • J. Feibenbaum, C. Papadimitriou, and S. Shenker, Sharing the Cost of Multicast Transmissions, Journal of Computer and System Sciences, 63:21--41, 2001. (Conference version in STOC 2000.)

• Thu 11/18: Multicast cost sharing.
  • See the home pages of Joan Feigenbaum and Rahul Sami for more details on most of the work discussed in this lecture on the fixed-tree case.
  • The result for when the tree is not fixed a priori is from K. Jain and V. Vazirani, Applications of Approximation Algorithms to Cooperative Games, STOC 2001.

• Tue 11/23: Finite noncooperative games, and the special case of two-player, zero-sum games.
  • This material 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).

• Thu 11/25: No class (Thanksgiving)

• Tue 11/30: Existence of Nash equilibria in non-zero-sum games: Nash's Theorem, Sperner's Lemma, and Brouwer's Theorem.
  • 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.
  • 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/2: Completion of proof of Nash's Theorem (see references for previous lecture).