Topics in Multiagent Learning
Fall 2023
While machine learning techniques have had significant success in singleagent 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 multiagent systems from a combined gametheoretic, optimization and learningtheoretic perspective, building from matrix games (such as rockpaperscissors) to stochastic games, imperfect information games, and games with nonconcave utilities. We will present manifestations of these models in machine learning applications, from solving Go to multiagent reinforcement learning, adversarial learning and broader multiagent 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 superhumanlevel agents for established games such as Go, Poker, Diplomacy, and Stratego. A tentative course syllabus can be found below.
Motivated by these challenges, this course presents the foundations of multiagent systems from a combined gametheoretic, optimization and learningtheoretic perspective, building from matrix games (such as rockpaperscissors) to stochastic games, imperfect information games, and games with nonconcave utilities. We will present manifestations of these models in machine learning applications, from solving Go to multiagent reinforcement learning, adversarial learning and broader multiagent 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 superhumanlevel 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: 3333
 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 lecturebased. 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 23 homework sets and a project presentation. Projects may be done individually or in groups of 23 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)
# 
Date

Topic  Reading 
Lecture notes


1  9/7 
Introduction to the course and logistics

Slides  
Part I: Normalform games  
2  9/12 
Setting and equilibria: Nash equilibrium
Definition of normalform games. Solution concepts and Nash
equilibrium. Nash equilibrium existence theorem. Brouwer's fixed point theorem.

Slides  
3  9/14 
Setting and equilibria: Correlated equilibrium
Definition of Correlated and coarse correlated
equilibria. Their relationships with Nash equilibria in twoplayer
zerosum games. Linear programming formulations

Slides  
4  9/19 
Learning in games: Foundations
Regret and hindsight rationality. Phiregret
minimization and special cases. Connections with equilibrium computation
and saddlepoint 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 
PPADcompleteness 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 generalsum stochastic games


Part III: Imperfectinformation games  
13  10/24 
Foundations of imperfectinformation extensiveform games
Complete versus imperfect information. Kuhn's theorem.
Normalform and sequenceform strategies. Similarities and differences
with normalform games.


14  10/26 
Counterfactual regret minimization
Construction and proof of learning algorithms for
extensiveform games.


15  10/31 
Extensiveform correlated equilibria
Uncoupled computation of extensiveform correlated
equilibria in multiplayer generalsum games via learning


16  11/2 
Optimal equilibria and team coordination
Correlation plans and von StengelForges's theorem.
Connections between correlation and teams.


17  11/7 
Nash equilibrium refinements and sequential rationality
Tremblinghand equilibrium refinements: quasiperfect
equilibrium (QPE) and extensiveform 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: Nonconvexnoncave games  
21  11/21 
Aspects of nonconvexnonconcave games (TBD)


22  11/28 
Aspects of nonconvexnonconcave games (TBD)


Project presentations  
23  11/30 
Projects


24  12/5 
Projects


25  12/7 
Projects

Related Courses
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  MultiAgent 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 