Course Information

• Instructor: Yang Cai
  Office Hours: Thursday 3 pm - 4 pm.


• TA: Liana Yepremyan
  Office Hours: Thursday 4pm - 5pm and Friday 3pm - 4 pm


• Lecture: Mondays and Wednesdays 4:05 pm-5:25 pm, Rutherford Physics Building 118.


• Course Description: Broad survey of topics at the interface of theoretical computer science and economics, with an emphasis on algorithms and computational complexity. Our main focus will be on algorithmic tools in mechanism design, algorithms and complexity theory for learning and computing Nash and market equilibria, and the price of anarchy. Case studies in Web search auctions, wireless spectrum auctions, matching markets, and network routing, and social networks.


• Textbook: Algorithmic Game Theory, by Noam Nisan, Tim Roughgarden, Eva Tardos, Vijay V. Vazirani (eds.), Cambridge University Press, September 2007.


• Lecture Notes: Lecture notes and/or presentations will be provided.


• Prerequisites: A course in algorithms (COMP 360 or equivalent) and probability (MATH 323 or equivalent). No prior knowledge of Economics or Game Theory is required.
  
  
• Assessment: The grade comprises the following components:
  
  • 5% from games played in class; will play a few games with your classmates in class, and your score depends on your performance in these games.
  • 15% from scribing a lecture; in a team of two or three students.
  • 40% from homework problems; there will be 3-4 problem sets.
  • 40% from the final exam or the final project (you can choose either one).
    The project could either be a survey, or original research; students will be encouraged to relate the project to their own research interests.

Course Outline

There is a significant dynamic component to the course, as topics drop in and out, or get longer or shorter treatment, depending on audience interest/reaction/resistence. We consider this a feature. Given this, here is a rough outline of the course material.

Lectures (scribe sheet)

Please use the scribe template to produce your notes. The template contains commands for Theorem, Lemma, Corollary, Proposition, Claim, Definition, Construction, Remark etc. An example file where this template is used is here. As scribes become available, they will be published here. At the same time, the list below will contain notes/presentations produced by the instructor.

• Lecture 1 (Sept 3th): Introduction to Algorithmic Game Theory: Incentives in Large Systems; Games; Nash Equilibria and their computation; the Price of Anarchy; Mechanism Design. Slides | Slides in pdf without animation.
• Lecture 2 (Sept 8th): Mechanism Design Basics. Single Item Auctions. First Price Auction. Second Price Auction. Sponsored Search Auctions. Slides | Slides in pdf without animation | Notes
• Lecture 3 (Sept 10th): Myerson's Lemma. Single-dimensional Environment. Implementable allocation rules. Monotonicity. Revenue Equivalence. Slides | Slides in pdf without animation | Notes
• Lecture 4 (Sept 15th): Myerson's Lemma (cont'd). Truthful Payment Rule for Sponsored Search. Revelation Principle. Intro to Revenue Maximization. Bayesian Analysis. Slides | Slides in pdf without animation | Notes
• Lecture 5 (Sept 17th): Myerson's Optimal Auction. Expected Revenue = Expected Virtual Welfare. MHR and Regular Distributions. Slides | Slides in pdf without animation | Notes
• Lecture 6 (Sept 22nd): Simple Near-Optimal Auctions. Prophet Inequality. Vickrey with Reserve. Slides | Slides in pdf without animation | Notes
• Lecture 7 (Sept 24th): Prior-Independent Auctions. Bulow-Klemperer Theorem. Multi-Dimensional Settings. VCG mechanisms. Slides | Slides in pdf without animation | Notes
• Lecture 8 (Sept 29th): Combinatorial Auctions. Spectrum Auctions. Slides | Slides in pdf without animation | Notes
• Lecture 9 (Oct 1st): Revenue Maximization in Multi-Dimensional Settings. Examples for Bundling and Randomization. Pricing for a Unit-demand Bidder. Slides | Slides in pdf without animation | Notes
• Lecture 10 (Oct 6th): Pricing for a Unit-demand Bidder (cont'd). Multi-item Multi-bidder Auction with Additive Bidders. Basic LP Formulation. Slides | Slides in pdf without animation | Linear Programming
• Lecture 11 (Oct 8th): Basic LP formulation for Multi-bidders. Reduced Form of an Auction. Succinct LP with Reduced Form. Slides | Slides in pdf without animation
• Lecture 12 (Oct 15th): Implementation of Reduced Forms. Structure of the Optimal Multi-item Auction. Arrow's Impossibility Theorem. Gibbard-Satterthwaite Impossibility Theorem. Slides | Slides in pdf without animation | Moni Naor's Slides
• Lecture 13 (Oct 20th): Proof of Arrow's Impossibility Theorem. Moni Naor's Slides | Notes
• Lecture 14 (Oct 22nd): 2-Player (Normal-From) Games. Nash Equilibrium. Intro to LP Duality. Zero-sum Games. Costis Daskalakis's Notes
• Lecture 15 (Oct 27th): 2-Player Zero-sum Games. Minmax Theorem. Costis Daskalakis's Notes
• Lecture 16 (Oct 29th): Multiplayer Games. Separable Multi-player Zero-sum Games. Costis Daskalakis's Notes
• Lecture 17 (Nov 3rd): Fictitious Play. Costis Daskalakis's Notes
• Lecture 18 (Nov 5th): Fictitious Play (cont'd). Multiplicative Weight Updates. Costis Daskalakis's Notes
• Lecture 19 (Nov 10th): Application of Online Learning to 2-Player Zero-sum Games. Nash's Theorem. Costis Daskalakis's Notes
• Lecture 20 (Nov 12th): Brouwer's fixed point theorem. Sperner's Lemma. Total Search Problems. Slides | Slides in pdf without animation
• Lecture 21 (Nov 17th): PPAD, PPA, PPP, PLS. PPAD-completeness of 2-Player Games. Support Enumeration. Lipton-Markakis-Mehta. Slides | Slides in pdf without animation
• Lecture 22 (Nov 19th): Exchange Market Model. Walrasian Equilibria. The Arrow-Debreu Theorem. CES utilities. Slides | Slides in pdf without animation
• Lecture 23 (Nov 24th): Fisher's Market Model. Eisenberg-Gale Convex Program. Slides
• Lecture 24 (Nov 26th): Atomic Congestion Games. Price of Anarchy. Potential Function and the existence of pure Nash equilibria in Congestion Games. Eva Tardos's Notes
• Lecture 25 (Dec 1st): Non-atomic Congestion Games. Pigou's Example. PoA for Non-atomic Congestion Games. Christos Papadimitriou's Notes
• Lecture 26 (Dec 3rd): Smooth Games. PoA for Atomic Congestion Games. Price of Stability. Vasilis Syrgkanis's Notes

Online Resources

Previous incarnation of this class:

• Algorithmic Game Theory by Adrian Vetta

Similar Classes in other universities:

• Seminar on Algorithmic Game Theory by Christos Papadimitriou
• Topics in Algorithmic Game Theory by Costis Daskalakis
• Algorithmic Game Theory by Eva Tardos
• Algorithmic Game Theory by Tim Roughgarden
• Algorithmic Mechanism Design by Jason Hartline

Other reference books:

• Networks, Crowds and Markets by D. Easley and J. Kleinberg, Cambridge University Press, 2010.
• Multiagent Systems: Algorithmic, Game Theoretic and Logical Foundations by Y. Shoham and K. Leyton-Brown, Cambridge University Press, 2009.