This course studies multiagent systems through game theory, optimization, and learning theory. We cover foundational topics such as Nash equilibria, regret minimization, learning dynamics, and extensive-form games.
We also explore modern topics: multiagent deep reinforcement learning; information and mechanism design; team games and hidden-role games; alignment; high-dimensional and kernelized learning; nonconvex games; calibration; and the complexity of finding equilibria. Applications and open research questions connect the theory to multiagent AI.
Schedule & lecture notes
| # | Date | Topic | Notes |
|---|---|---|---|
| 00 | Course OverviewWe will discuss the syllabus, projects, administrative details, and an overview of the topics covered. |
Part I: Foundations
| # | Date | Topic | Notes |
|---|---|---|---|
| 01 | Setting and equilibria: the Nash equilibriumNash's existence theorem and its connection to fixed-point theorems. |
||
| 02 | Brouwer and SpernerSperner's lemma, Brouwer's theorem, and combinatorial proofs of equilibrium existence. |
||
| 03 | Properties of Nash equilibriumTopological and computational properties. Zero-sum games and linear programming. Correlated and coarse correlated equilibria. |
||
| 04 | Learning in games: FoundationsRegret and hindsight rationality. Regret minimization and its relationships with equilibrium concepts. |
||
| 05 | Learning in games: AlgorithmsGeneral principles for learning algorithms. Follow-the-leader, regret matching, multiplicative weights, and online mirror descent. |
||
| 06 | Learning with bandit feedbackPartial feedback and exploration. From multiplicative weights to Exp3; regret guarantees. |
||
| 07 | Modeling extensive-form gamesPerfect and imperfect information. Kuhn's theorem. Normal-form and sequence-form strategies. |
||
| 08 | Learning in extensive-form gamesNo-regret learning, counterfactual utilities, and counterfactual regret minimization (CFR). |
||
| No class | No classMIT follows a Monday schedule. | ||
| 09 | Multiagent deep RLReinforcement learning in games. Self-play and deep learning methods for perfect-information games. |
Not yet posted |
|
| # | Date | Topic | Notes |
|---|---|---|---|
| 10 | project | Taking stockWe will discuss big open questions in the field and possible project ideas. |
Not yet posted |
Part II: Information, Communication, Alignment
| # | Date | Topic | Notes |
|---|---|---|---|
| 11 | Information and mechanism designDesigning information and incentives in strategic interactions. |
Not yet posted |
|
| 12 | Team games and hidden-role gamesCoordination in teams and games with hidden roles. |
Not yet posted |
|
| 13 | Alignment (part I)Reinforcement learning from human feedback (RLHF) and alignment. |
Not yet posted |
|
| 14 | Alignment (part II)Regularized RLHF and direct preference optimization (DPO). |
Not yet posted |
Part III: Advanced learning
| # | Date | Topic | Notes |
|---|---|---|---|
| 15 | Forecasting and calibrationCalibrated prediction and its connections to learning in games. |
Not yet posted |
|
| 16 | High-dimensional gamesLearning with large strategy spaces. Kernelized methods and multiplicative weights. |
Not yet posted |
|
| 17 | Nonconvex gamesNonconvexity, learning dynamics, and local equilibrium concepts. |
Not yet posted |
Part IV: Computational complexity
| # | Date | Topic | Notes |
|---|---|---|---|
| 18 | Total search and TFNPTotal search problems, the TFNP framework, and the PPAD complexity class. |
Not yet posted |
|
| 19 | PPAD-hardness of Nash equilibriumReductions and the computational hardness of finding Nash equilibria. |
Project work and presentations
| # | Date | Topic | Notes |
|---|---|---|---|
| break | No classProject break | ||
| No class | No classThanksgiving holiday. | ||
| 20 | project | Project presentationsShow us your cool work! |
|
| 21 | project | Project presentationsShow us your cool work! |
|
| 22 | project | Project presentationsShow us your cool work! |
|
| 23 | project | Project presentationsShow us your cool work! |
|
Supplementary reading
Improving Material
We would like to make the lecture notes available to as many people as possible. You can now read them in a browser, follow links between sections and references, and move between the notes and their source. We would like everyone's help to make this a useful resource for learners around the world.
We will divide the class into groups, each focusing on a different part of the material. Using the class GitHub repository, each group can open issues to identify improvements and submit pull requests to implement them. We will improve the material together, reviewing and building on one another's contributions.
Contributions can include clarifying explanations and proofs, fixing errors, adding examples and homework-style exercises for future readers, and polishing figures, organization, and presentation. If anyone is brave enough, we would also love interactive components that let readers experiment with the ideas.
On the bright side, there is no homework! :-) Improving the shared material accounts for 30% of the course grade.
Project
Projects may be completed individually or in groups of 2-5 students and will include a presentation. We will offer three project directions:
Fog of War Chess Challenge. Build and evaluate an agent that plays with partial information. Explore how it uses observations, reasons about uncertainty, and chooses strategic actions. Each bot sandbox is allocated two CPU cores and 4 GiB of memory. A dedicated document will describe the challenge, including the rules, starter code, and how to access the arena.
Modeling questions. Formulate a multiagent problem by specifying the players, objectives, information, and available actions. Study how modeling choices affect the resulting strategic behavior. We will provide a separate document with possible modeling questions and leads to explore.
Theory questions. Investigate a mathematical question about equilibria, learning dynamics, or computational complexity. Develop rigorous proofs, bounds, or counterexamples that clarify the behavior of multiagent systems. We will provide a separate document with possible theory questions and leads to explore.
The project is the central component of the course and accounts for 50% of the final grade. We will therefore be "robust" in our grading: we will look carefully at the depth of your understanding, the quality and substance of your work, and how clearly you explain your results.