Course Information

• Instructor: Yang Cai
  Office Hours: Tuesday 4:30 pm - 5:30 pm, MC 324.


• TA: Mingfei Zhao
  Office Hours: Monday 10:00 am - 11:00 am and Wed 3:00 pm - 4:00 pm, MC 337.


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


• Syllabus: See the pdf.


• 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.
  • 5% from class participation.
  • 45% from homework problems; there will be 3 problem sets.
  • 45% from the final exam.

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/resistance. We consider this a feature. Given this, here is a rough outline of the course material.

Lectures

The list below will contain notes/presentations produced by the instructor.

• Lecture 1 (Sept 6th): 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): Games, Solution concepts and Nash's Theorem. Costis Daskalakis's Notes
• Lecture 3 (Sept 13th): Nash's Theorem (cont'd) and Two-player Zero-sum Games. Costis Daskalakis's Note
• Lecture 4 (Sept 15th): Two-player Zero-sum Games (cont'd). Minimax Theorem.Costis Daskalakis's Notes
• Lecture 5 (Sept 20th): Support Enumeration Algorithms. Symmetric Games. Slides | Costis Daskalakis's Notes
• Lecture 6 (Sept 22nd): The Lemke-Howson Algorithm. Slides | Costis Daskalakis's Notes
• Lecture 7 (Sept 27th): Arrow's Impossibility Theorem. Gibbard-Satterthwaite Theorem. Moni Naor's Slides | Scribed Notes
• Lecture 8 (Sept 29th): Intro to Mechanism Design. Single-item Auctions. Slides
• Lecture 9 (Oct 4th): Vickrey Auction. Sponsored Search. Slides
• Lecture 10 (Oct 6th): Myerson's Lemma. Slides
• Lecture 11 (Oct 11th): Intro to Revenue Maximization. The Revelation Principle. Slides
• Lecture 12 (Oct 13th): The Revelation Principle (cont'd). Myerson's Optimal Auction. Slides
• Lecture 13 (Oct 18th): Myerson's Optimal Auction (cont'd). Slides
• Lecture 14 (Oct 20th): The Prophet Inequality. Prior-independent Auctions. Slides | Supplement
• Lecture 15 (Oct 25th): The Prophet Inequality. Prior-independent Auctions (cont'd). Slides
• Lecture 16 (Oct 27th): The VCG Mechanism. Slides
• Lecture 17 (Nov 1st): The Combinatorial Auctions and Spectrum Auctions. Slides
• Lecture 18 (Nov 3rd): The Spectrum Auctions (cont'd). Revenue Maximization in Multi-item Settings. Slides
• Lecture 19 (Nov 8th): Revenue Maximization in Multi-item Settings: Upper Bound of the Revenue via the Partial Lagrangian Dual. Slides
• Lecture 20 (Nov 10th): Revenue Maximization in Multi-item Settings: Selling Separately and Grand Bundling. Slides
• Lecture 21 (Nov 15th): Atomic Congestion Games. Existence of Pure Nash Equilibrium via Potential Function. Definition of PoA and PoS. Slides
• Lecture 22 (Nov 17th): Non-atomic Congestion Games. Existence of Pure Nash Equilibrium. PoA for Non-atomic Congestion Games.
• Lecture 23 (Nov 22nd): PoA for Non-atomic Congestion Games and Atomic Congestion Games.
• Lecture 24 (Nov 24th): PoA for atomic Congestion Games. Sperner's Lemma Slides
• Lecture 25 (Nov 29th): Brouwer's Fixed Point Theorem. PPAD Class. Slides

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.
  
• Game Theory, Alive by Anna R. Karlin and Yuval Peres.