Class Schedule

Fall 2019
(Subject to change at any time)


Assignments:

Lectures

Part I: Here the section numbers refer to Nisan/Roughgarden/Tardos/Vazirani: Algorithmic Game Theory.

  1. (Aug 29) Introduction to Game Theory (Sec 1.1-1.3)
  2. (Aug 03) Network Formation Games (Sec 17.1-17.2, 19.3)
  3. (Aug 05) Congestion Games and Potential Games (Sec 17.1-17.2, 19.3)
  4. (Sep 09) Selfish Routing (Ch 18, Roughgarden 11,12.2)
  5. (Sep 12) Price of Anarchy in Smooth Games (Roughgarden Lecture 14)
  6. (Sep 16) Correlated and Coarse-Correlated Equilibrium (Roughgarden Lecture 13)
  7. (Sep 19) Strong Equilibrium (Roughgarden Lecture 15)
Part II: Auctions and Mechanism Design
  1. (Sep 23) Mechanism Design and Auctions (Roughgarden Lecture 2)
  2. (Sep 26) Characterization of DSE for Single-Dimensional Mechanisms (Roughgarden Lecture 3)
  3. (Sep 30) Applying Myerson's Lemma; Sponsored Search Auctions (Roughgarden Lecture 2-3)
  4. (Oct 03) Monotone Allocation Rules and Monotone Approximation Algorithms (Roughgarden Lecture 4)
  5. (Oct 07) Multi-dimensional Mechanisms and Cycle Monotonicity, Combinatorial Auctions (Sec 9.5, Roughgarden Lecture 7)
  6. (Oct 10) Social Welfare and VCG (Sec 9.3, Roughgarden Lecture 7)
  7. (Oct 17) Bayes-Nash Equilibrium (Sec 9.6)
  8. (Oct 21) Simple Auctions and the Price of Anarchy
  9. (Oct 24) Revenue Maximization and Bayesian Mechanism Design (Sec 13.1-13.2, Roughgarden Lecture 5)
  10. (Oct 28) Prophet Inequalities and Approximating Revenue and Welfare using Posted Prices
  11. (Oct 31) Prior-Independent Approximation (Roughgarden Lecture 6)
Part III: Markets and Pricing
  1. (Nov 04) Introduction to Markets and Pricing (Sec 11.1, 11.3)
  2. (Nov 07) Social Welfare and Walrasian Equilibrium, Gross-Substitutes (Sec 11.3, 11.7)
  3. (Nov 11) Linear Programming and Walrasian Equilibrium (Sec 11.5)
  4. (Nov 14) Single Minded Valuations (Sec 11.2), Maximizing Revenue
  5. (Nov 18) Combinatorial Walrasian Equilibrium
Part IV:
  1. (Nov 21) Cost Sharing and Core-Stable Solutions (Sec 15.1-15.5)
  2. (Nov 25) No-regret Learning and Dynamics (Roughgarden Lecture 17)
  3. (Dec 02) Class canceled due to snow
  4. (Dec 05) No-regret Learning and Relationship to Gradient Descent and Machine Learning
  5. (Dec 09) Computational Complexity of Nash Equilibrium: PPAD, Sperner's Lemma, and Brower's Fixed Point Theorem (Roughgarden Lecture 20)