Course Summary

This is a graduate-level course full-lecture course. It covers several foundational topics in algorithmic game theory and explores how these ideas inspire and connect with modern research in machine learning and AI. Topics include Nash equilibrium, social choice theory, no-regret online learning in game theory, multi-agent reinforcement learning. 

This course is primarily based on materials from two outstanding courses by Prof. Ariel Procaccia (link) and Prof. Aaron Roth (link), used with their kind permission.

Administrative Information

Lectures: Tu., Thu., 14:00-15:15

Location: SN011

Instructor: Zhun Deng

Teaching Assistants: Xiaowei Yin  Office hours: 3-4pm ET every Tuesday  Location: Common area at SN Hall 

Requirements: This is a graduate-level course that requires some mathematical background.
Required background: probability, discrete math, calculus, analysis, linear algebra, algorithms and data structures

Grading and Collaboration

Grading: Attendancy (15%), Assignments (40%), and a final course project (45%). 

Collaboration: Collaboration on course projects are allowed.

Textbook and Readings

1. Algorithmic Game Theory by Nisan, Roughgarden, Tardos, Vazirani, available here

2. (Draft) Learning in Games (and Games in Learning) by Aaron Roth, available here

Schedule

• Lecture 1: Nash Equilibrium

• Lecture 2: Equilibrium Computation

• Lecture 3: Extensive-Form Games

• Lecture 4: The Price of Anarchy

• Lecture 5: Voting Rules I

• Lecture 6: Voting Rules II

• Course Project Kick-off Presentation

• Course Project Kick-off Presentation

• Lecture 7: Online Learning Basics I

• Guest Lecture

• Guest Lecture

• Lecture 8: Online Learning Basics II

• Lecture 9: Online Learning Basics III

• Course Project Mid-Term Presentation

• Course Project Mid-Term Presentation

• Course Project Mid-Term Presentation

• Lecture 10: Zero Sum Games 

• Lecture 11: From Sequential Decision Making to The Minimax Theorem I

• Lecture 12: From Sequential Decision Making to The Minimax Theorem II

• Lecture 13: Minimax Theorem to Sequential Decision Making I

• Lecture 14: Minimax Theorem to Sequential Decision Making II

• Lecture 15: Convergence to Correlated Equilibria

• Lecture 16: Multi-Objective Sequential Learning I

• Lecture 17: Multi-Objective Sequential Learning II

• Lecture 18: Multi-Objective Sequential Learning III

• Guest Lecture

• Guest Lecture