Topics in Multiagent Learning

Fall 2023
While machine learning techniques have had significant success in single-agent settings, an increasingly large body of literature has been studying settings involving several learning agents with different objectives. In these settings, standard training methods, such as gradient descent, are less successful and the simultaneous learning of the agents commonly leads to nonstationary and even chaotic system dynamics.

Motivated by these challenges, this course presents the foundations of multi-agent systems from a combined game-theoretic, optimization and learning-theoretic perspective, building from matrix games (such as rock-paper-scissors) to stochastic games, imperfect information games, and games with non-concave utilities. We will present manifestations of these models in machine learning applications, from solving Go to multi-agent reinforcement learning, adversarial learning and broader multi-agent deep learning applications. We will discuss aspects of equilibrium computation and learning as well as the computational complexity of equilibria. We will also discuss how the different models and methods have allowed several recent breakthroughs in AI, including human- and superhuman-level agents for established games such as Go, Poker, Diplomacy, and Stratego. A tentative course syllabus can be found below.

Course Info

  • Instructors: Gabriele Farina and Constantinos Daskalakis
  • Time: Tuesdays & Thursdays, 11:00am - 12:30pm
  • Location: 3-333
  • Office hours: TBD
  • Prerequisites: Discrete Mathematics and Algorithms at the advanced undergraduate level; mathematical maturity.
  • This course will use Canvas

Course Structure

The course will be lecture-based. At the end of the course there will be a few lectures of project presentations by students.

Readings will consist of a mixture of textbooks and course notes, which will be uploaded after lectures.

This course will include 2-3 homework sets and a project presentation. Projects may be done individually or in groups of 2-3 students and can be theoretical or experimental.

Grading will be as follows:

  • 50% final project
  • 40% homework sets
  • 10% completion of readings, attendance, and participation in class discussions

Schedule (subject to change)

Topic Reading
Lecture notes
1 9/7
Introduction to the course and logistics
Part I: Normal-form games
2 9/12
Setting and equilibria: Nash equilibrium
Definition of normal-form games. Solution concepts and Nash equilibrium. Nash equilibrium existence theorem. Brouwer's fixed point theorem.
3 9/14
Setting and equilibria: Correlated equilibrium
Definition of Correlated and coarse correlated equilibria. Their relationships with Nash equilibria in two-player zero-sum games. Linear programming formulations
4 9/19
Learning in games: Foundations
Regret and hindsight rationality. Phi-regret minimization and special cases. Connections with equilibrium computation and saddle-point optimization
GGM08 Notes
5 9/21
Learning in games: Algorithms
Regret matching, regret matching plus, FTRL and multiplicative weights update
Blackwell ap. Notes
6 9/26
Project Brainstorming
Part Ib: Complexity of equilibrium
7 9/28
Nash equilibrium and PPAD complexity
Sperner's lemma, Brouwer's fixed point, and the PPAD complexity class. Nash's proof
8 10/3
PPAD-completeness of Nash equilibria, and open problems.
Part II: Stochastic games
9 10/5
Stochastic games
Minimax theorem, and existence of equilibrium. Stationary Markov Nash equilibria.
10 10/12
Computation of equilibria in stochastic games
Finite horizon vs infinite horizon (discounted) setting, the role of nonstationarity, and backward induction.
11 10/17
Minimax stationary Markov learning
12 10/19
Complexity of correlated equilibria in general-sum stochastic games
Part III: Imperfect-information games
13 10/24
Foundations of imperfect-information extensive-form games
Complete versus imperfect information. Kuhn's theorem. Normal-form and sequence-form strategies. Similarities and differences with normal-form games.
14 10/26
Counterfactual regret minimization
Construction and proof of learning algorithms for extensive-form games.
15 10/31
Extensive-form correlated equilibria
Uncoupled computation of extensive-form correlated equilibria in multi-player general-sum games via learning
16 11/2
Optimal equilibria and team coordination
Correlation plans and von Stengel-Forges's theorem. Connections between correlation and teams.
17 11/7
Nash equilibrium refinements and sequential rationality
Trembling-hand equilibrium refinements: quasi-perfect equilibrium (QPE) and extensive-form perfect equilibrium (EFPE). Relationships among refinements. Computational complexity and techniques
18 11/9
Practice of solving large games
Project break
19 11/14
Project break
No class this week
20 11/16
Project break
No class this week
Part IV: Nonconvex-noncave games
21 11/21
Aspects of nonconvex-nonconcave games (TBD)
22 11/28
Aspects of nonconvex-nonconcave games (TBD)
Project presentations
23 11/30
24 12/5
25 12/7

Below is a list of related courses at other schools.

Professor Title Year School
Farina & Sandholm Computational Game Solving 2021 CMU
Christian Kroer Economics, AI, and Optimization 2020 Columbia
Tuomas Sandholm Foundations of Electronic Marketplaces 2015 CMU
John P. Dickerson Applied Mechanism Design for Social Good 2018 UMD
Fei Fang Artificial Intelligence Methods for Social Good 2018 CMU
Constantinos Daskalakis Games, Decision, and Computation 2015 MIT
Yiling Chen Topics at the Interface between Computer Science and Economics 2016 Harvard
Vincent Conitzer Computational Microeconomics: Game Theory, Social Choice, and Mechanism Design 2016 Duke
Sanmay Das Multi-Agent Systems 2016 Wash U
Ariel Procaccia Truth, Justice, and Algorithms 2016 CMU
Milind Tambe Security and Game Theory 2016 USC
Tim Roughgarden Algorithmic Game Theory 2013 Stanford