Course Schedule

** Computational Game Theory with Applications to AI and ML

*** { @unit = “2nd Apr”, @title = “Lecture 1: Introduction to game theory”, @reading, @lecture, @foldout}

Introduction and logistics. Basics of game theory, equilibria, zero-sum games, Minimax theorem.

Presentation: Lecture 1

Readings:

• Chapters 1-2 of AI, Games and Markets
• Lecture Notes

*** { @unit = “4th Apr”, @title = “Lecture 2: Online (no-regret) learning”, @reading, @lecture, @foldout}

Basics of online learning algorithms and theoretical foundations.

Presentation: Lecture 2

Readings:

• Lecture Notes
• Lecture Notes, First Half

Further Reading

• Online Learning and Online Convex Optimization, Chapters 1-2

*** {@unit = “5th Apr”, @title = “Python Tutorial”, @lecture, @foldout}

Presentation Python Tutorial

*** { @unit = “9th Apr”, @title = “Homework 1 (due 16th Apr)”, @assignment}

*** { @unit = “9th Apr”, @title = “Lecture 3: Solving zero-sum games with no-regret”, @reading, @lecture, @foldout}

Solving zero-sum games using no-regret dynamics.

Presentation: Lecture 3

Readings:

• Lecture Notes

*** { @unit = “11th Apr”, @title = “Lecture 4: Applications of zero-sum games to ML and AI”, @reading, @lecture, @foldout}

Applications of zero-sum games in machine learning and AI: boosting, adversarial robustness, distributional robustness, fairness, GANs, Imitation learning, Reinforcement learning from human feedback, NPIV (causal machine learning).

Presentation: Lecture 4

Readings:

• Game Theory, Online Prediction and Boosting
• Tutorial on GANs, Especially Sections 3.2, 5.1, 8.2
• Robust Optimization for Non-Convex Objectives
• Distributionally Robust Neural Networks
• Adversarial Training for Causal ML
• Zero-Sum Games for RLHF
• Zero-Sum Games for Imitation Learning
• Zero-Sum Games for Fair ML

*** { @unit = “16th Apr”, @title = “Homework 2 (due 23rd Apr)”, @assignment}

Due: April 23rd

*** { @unit = “16th Apr”, @title = “Lecture 5: Extensive-form games”, @reading, @lecture, @foldout}

Extensive form games of complete and incomplete information.

Presentation: Lecture 5

Readings:

• Chapter 8-9, AI, Games and Markets

Videos:

• Noam Brown, Superhuman AI for heads-up no-limit poker: Libratus beats top professionals

Further Reading:

• Stratego AI
• Poker AI
• Chess, Shogi and Go AI
• Optimistic FTRL for Extensive Games

*** { @unit = “18th Apr”, @title = “Lecture 6: No-regret learning for extensive form games”, @reading, @lecture, @foldout}

Presentation: Lecture 6

Readings:

• Chapter 8-9, AI, Games and Markets

Videos:

• Noam Brown, Superhuman AI for heads-up no-limit poker: Libratus beats top professionals

Further Reading

• Chapter 5, AI, Games and Markets
• Lectures 11-15, CMU Computational Game Solving Course

Further Videos:

• Noam Brown, Deep Learning and Search for Imperfect Information Games

*** { @unit = “23rd Apr”, @title = “Homework 3 (due 1st May)”, @assignment}

Due: April 30th

*** { @unit = “23rd Apr”, @title = “Lecture 7: General games”, @reading, @lecture, @foldout}

No-regret learning in general games and coarse correlated equilibria. No-swap regret and correlated equilibria.

Presentation: Lecture 7

Readings:

• Lecture Notes

Further Readings:

• Quality of Learning Outcomes Lecture Note

*** { @unit = “25th Apr”, @title = “Lecture 8: Learning in General Games”, @reading, @lecture, @foldout}

Learning algorithms for correlated equilibria. Reduction from no-regret to no-swap regret.

Presentation: Lecture 8

Readings:

• Lecture Notes

Further Readings:

• From Internal to External Regret, Blum and Mansour
• Example of Correlated equilibria in recent multi-agent RL research
• Noah Golowich, Lecture Notes on Stochastic Games, Part I
• Grandmaster Level AI Agent for Starcraft

*** { @unit = “1st May”, @title = “Homework 4 (due 8th May)”, @assignment}

Due: May 7th

** Data Science for Auctions and Mechanisms

*** { @unit = “30th Apr”, @title = “Lecture 9: Auctions and mechanisms”, @reading, @lecture, @foldout}

Basics (Bayes-Nash equilibrium, truthfulness, First-Price auction, Vickrey auction) and applications (GSP, GFP etc). Sponsored search.

Presentation: Lecture 9

Readings:

• Lecture Notes

*** { @unit = “2nd May”, @title = “Lecture 10: Basics continued (VCG). Learning in auctions”, @reading, @lecture, @foldout}

Presentation: Lecture 10

Readings:

• Lecture Notes

Further Readings:

• Shai-Shalev Schwarz, OCO, Chapters 4.2 and 2.7-2.8

*** { @unit = “8th May”, @title = “Homework 5 (due 15th May)”, @assignment}

*** { @unit = “7th May”, @title = “Lecture 11: Optimal mechanism design”, @reading, @lecture, @foldout}

Presentation: Lecture 11

Readings:

• Lecture Notes

*** { @unit = “9th May”, @title = “Lecture 12: Simple vs optimal mechanisms”, @reading, @lecture, @foldout}

Presentation: Lecture 12

Readings:

• Lecture Notes
• Lecture Notes
• Lecture Notes

*** { @unit = “15th May”, @title = “Homework 6 (due 22nd May)”, @assignment}

*** { @unit = “14th May”, @title = “Lecture 13: Statistical Learning Theory and Pricing from Samples”, @reading, @lecture, @foldout}

Presentation: Lecture 13

Readings:

• Lecture Notes
• Lecture Notes

*** { @unit = “16th May”, @title = “Lecture 14: Statistical Learning Theory and Learning Mechanisms from Data”, @reading, @lecture, @foldout}

Presentation: Lecture 14

Readings:

• Lecture Notes
• Lecture Notes

*** { @unit = “22nd May”, @title = “Homework 7 (due 29th May)”, @assignment}

** Further Topics

*** { @unit = “21st May”, @title = “Lecture 15: Econometrics in games and auctions”, @reading, @lecture, @foldout}

Presentation: Lecture 15

Readings:

• Lecture Notes on Estimation of CDFs
• Lecture Notes on Estimation from First Price Auctions

*** { @unit = “23rd May”, @title = “Lecture 16: A/B testing in markets”, @reading, @lecture, @foldout}

Presentation: Lecture 16

Readings:

• Lecture Notes on A/B Testing in Auctions
• A/B Testing of Auctions, Chawla, Hartline, Nekipelov
• A/B Testing in Auctions with Budgets from Meta
• A/B Testing in Two-Sided Markets

*** { @unit = “29th May”, @title = “Homework 8 (due 5th Jun)”, @assignment}

** Guest Lectures

*** { @unit = “28th May”, @title = “Mechanism Design for LLMs (Renato Paes Leme; Google)”, @reading, @lecture, @foldout}

*** { @unit = “30th May”, @title = “Autobidding and Sponsored Search (Kshipra Bhawalkar; Google)”, @reading, @lecture, @foldout}

*** { @unit = “4th Jun”, @title = “Lecture 17: A/B testing in markets + Recap + Q/A”, @reading, @lecture, @foldout}

Presentation: Lecture 17 A/B Testing in Two-Sided Markets: Colab Notebook

Readings:

• A/B Testing in Auctions with Budgets from Meta
• A/B Testing in Two-Sided Markets