**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.

- 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.

- 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.

- 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.

- 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.

- 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.

- Roughgarden, "Routing Games", draft of book chapter to
appear in
- Tue 10/31: The price of anarchy in nonatomic and atomic selfish
routing games. Reference:
- "Routing Games" (see last lecture).

- 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.

- Anshelevich/Dasgupta/Kleinberg/Tardos/Wexler/Roughgarden, The Price of Stability for Network Design with Fair Cost Allocation.

- 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.

- 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.

- 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.

- The quasipolynomial-time algorithm for finding approximate Nash
equilibria is from
- 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.